摘要
根据TSP适应度地貌特征,通过将传统的反转变异算子(Simple Inversion Operator,SIM)与插入变异算子(Insertion Operator,IM)进行组合,设计出了一种可变邻域搜索的复合变异算子(Greed Invert-Insertion Operator,GIIM)。在此基础上,结合常规的部分匹配交叉(PartiallyMatched Crossover,PMX)与带有精英策略的退火选择,构造出了一种求解TSP的高效遗传算法(SEGA)。仿真测试表明,提出的算法不但具有很强的全局搜索能力,且收敛速度快;其测试结果与最新文献和国际标准测试库TSPLIB中的最优路径相比,或相同或更优。
Based on the analysis of fitness landscape of TSP, a variable neighborhood search hybrid mutation operator, called GIIM, is designed by combining simple inversion mutation operator with insertion mutation operator,on the basis of which, an efficient genetic algorithm for TSP, called SEGA, is presented by combining partially matched crossover （PMX） and annealing selection with elitist strategy. The simulation for TSP shows that SEGA has not only very strong global search ability but also very fast convergence speed,whose testing results are the same or even more superior ones in comparison with the optimal path in the newest literatures and TSPLIB.
出处
《西安理工大学学报》
CAS
2006年第1期37-41,共5页
Journal of Xi'an University of Technology
基金
陕西省教育厅专项科研基金资助项目(05JK273)
关键词
遗传算法
简单反转算子
插入算子
可变邻域搜索的复合变异算子
旅行商问题
genetic algorithm
simple inversion operator
insertion operator
variabld neighbor search hybrid mutation
traveling salesman problem
