[关键词]
[摘要]
针对遗传算法求解TSP问题时存在初始化种群敏感的问题,提出一种初始化种群的邻域法,在该方法中,从某个城市出发其下一站不是其最近城市,而在比最近城市稍远的邻域范围进行随机选取。邻域法既能提取局部优化路径特征信息,又具有多样性。用4个通用的TSPLIB标准实例进行实验验证。邻域法初始化种群相比随机法,4个实例的最优解平均改进值达到了46.3%,最优解的质量有较大改善。仿真实验结果验证了邻域法初始化种群的有效性。
[Key word]
[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 asyetunvisited 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.
[中图分类号]
[基金项目]
国家111引智工程(B08036);国家高技术发展计划(863计划)资助项目(2006AA02Z4B7);重庆市自然科学基金资助项目(CSTC 2008BB6163)