一种求解TSP初始化种群问题的邻域法  

Neighbour field method for population initialization of TSP

作　　者：罗辞勇[1] 卢斌[1] 刘飞[2] 

机构地区：[1]重庆大学输配电装备及系统安全与新技术国家重点实验室,重庆400030 [2]重庆大学机械工程学院,重庆400030

出　　处：《重庆大学学报（自然科学版）》2009年第11期1311-1315,共5页Journal of Chongqing University

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

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

关 键 词：遗传算法 旅行商问题 初始种群 最近邻法 邻域法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]