几种局部优化算子在求解TSP中的性能比较  

Several local optimization operators in TSP performance comparison

作　　者：向佐勇[1,2] 刘正才[2] 

机构地区：[1]中南林业科技大学理学院,湖南长沙410111 [2]湘潭大学信息工程学院,湖南湘潭411105

出　　处：《计算机工程与设计》2009年第8期1950-1953,共4页Computer Engineering and Design

基　　金：国家自然科学基金项目(10705055);湖南省自然科学基金项目(05JJ30189);中南林业科技大学青年科学研究基金项目(07014B)

摘　　要：将局部优化算子引入遗传算法求解TSP问题,以求提高算法的性能。具体措施是在标准遗传算法的最后阶段增加一步,即对每代的最优个体进行一定次数的局部搜索,以求改善该最优个体。首先提出将反序-杂交法引入局部优化过程中。同几种常用的局部优化方法相比,反序-杂交法的性能最为突出。实验结果表明,该优化方法能有效求解300个城市以内的TSP问题。Local optimization operator to introduce genetic algorithm for TSP in order to improve the algorithm＇s performance. In the final step of SGA, every generation of the best individual for a certain number of local search, in order to improve the best individual. First inver-cross method introduced into local optimization process is proposed. Several common with the local optimization method, the inver-crossay method act ofthe most outstanding performance. Experiments show that the new method can effectively solve 300 cities within the TSP.

关 键 词：旅行商问题 简单遗传算法 局部搜索 反序法 反序-杂交法 

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