一种求解TSP初始化种群问题的邻域法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家111引智工程(B08036);国家高技术发展计划(863计划)资助项目(2006AA02Z4B7);重庆市自然科学基金资助项目(CSTC 2008BB6163)


Neighbour field method for population initialization of TSP
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    针对遗传算法求解TSP问题时存在初始化种群敏感的问题,提出一种初始化种群的邻域法,在该方法中,从某个城市出发其下一站不是其最近城市,而在比最近城市稍远的邻域范围进行随机选取。邻域法既能提取局部优化路径特征信息,又具有多样性。用4个通用的TSPLIB标准实例进行实验验证。邻域法初始化种群相比随机法,4个实例的最优解平均改进值达到了46.3%,最优解的质量有较大改善。仿真实验结果验证了邻域法初始化种群的有效性。

    Abstract:

    It is sensitive to the initial population while the genetic algorithm (GA) is used to solve the traveling salesman problem (TSP). To overcome this problem, the neighbour field method is presented to create initial population. In this method the next city is not the nearest asyetunvisited location but randomly selected from the unvisited cities in neighbour field. Neighbour filed method can extract the local optimal information of adjacent cities, and the constructed population has the diversity character. Comparing to the random initial method, the mean value obtained by the neighbour field method in four standard test instances of TSPLIB improved by 46.3%. The simulation results show the effectiveness of the neighbour field method for creating the initial population.

    参考文献
    相似文献
    引证文献
引用本文

罗辞勇,卢斌,刘飞.一种求解TSP初始化种群问题的邻域法[J].重庆大学学报,2009,32(11):1311-1315.

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2009-06-28
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期:
  • 出版日期: