一种求解TSP的高效遗传算法

作     者：王超学 崔杜武 王竹荣 费蓉 WANG Chao-xue;CUI Du-wu;WANG Zhu-rong;FEI Rong

作者机构：西安理工大学计算机科学与工程学院陕西西安710048 

基　　金：陕西省教育厅专项科研基金资助项目(05JK273) 

出 版 物：《西安理工大学学报》 (Journal of Xi'an University of Technology)

年 卷 期：2006年第22卷第1期

页      码：37-41页

摘      要：根据TSP适应度地貌特征,通过将传统的反转变异算子(Simple Inversion Operator,SIM)与插入变异算子(Insertion Operator,IM)进行组合,设计出了一种可变邻域搜索的复合变异算子(Greed Invert-Insertion Operator,GIIM)。在此基础上,结合常规的部分匹配交叉(PartiallyMatched Crossover,PMX)与带有精英策略的退火选择,构造出了一种求解TSP的高效遗传算法(SEGA)。仿真测试表明,提出的算法不但具有很强的全局搜索能力,且收敛速度快;其测试结果与最新文献和国际标准测试库TSPLIB中的最优路径相比,或相同或更优。

主 题 词：遗传算法 简单反转算子 插入算子 可变邻域搜索的复合变异算子 旅行商问题 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.3969/j.issn.1006-4710.2006.01.009

馆 藏 号：203119332...