Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (29): 43-46.DOI: 10.3778/j.issn.1002-8331.2010.29.012

• 研究、探讨 • Previous Articles     Next Articles

Two-stage evolutionary algorithm for traveling salesman problem

WANG Yu-ting,SUN Jian,LI Jun-qing,PAN Quan-ke   

  1. School of Computer Science,Liaocheng University,Liaocheng,Shandong 252059,China
  • Received:2009-03-25 Revised:2009-06-01 Online:2010-10-11 Published:2010-10-11
  • Contact: WANG Yu-ting

求解旅行商问题的二阶段演化算法

王玉亭,孙 剑,李俊青,潘全科   

  1. 聊城大学 计算机学院,山东 聊城 252059
  • 通讯作者: 王玉亭

Abstract: Based on the analysis of Inver-over operator,two improved Inver-over operators—1st-Inver-over operator and 2nd-Inver-over operator are proposed.Two-stage Evolutionary Algorithm based on improved Inver-over operator(Two-stage Inver-over EA) for TSP is implemented.In the prior period of the Two-stage Inver-over EA,in order to guarantee the convergence rate of the population,the algorithm only uses 1st-Inver-over operator.In the later period of the Two-stage Inver-over EA,in order to coordinate the convergence rate and the diversity of the population,the algorithm self-adaptively uses 1st-Inver-over operator and 2nd-Inver-over operator on the basis of the diversity of the population.The experiments results on TSPLIB(Traveling Salesman Problem Library) show that the Two-stage Inver-over EA is improved a lot on the convergence rate and efficiency compared with the classic GT algorithm.

摘要: 对Inver-over算子进行了改进,提出了1st-Inver-over算子和2nd-Inver-over算子,实现了求解TSP问题的基于改进Inver-over算子的二阶段演化算法(Two-stage Inver-over EA)。在算法前期,只采用1st-Inver-over算子来保证算法的收敛速度;在算法后期,根据种群的多样性自适应地选取1st-Inver-over算子和2nd-Inver-over算子来协调算法的收敛速度和种群的多样性。在TSPLIB(Traveling Salesman Problem Library)中的典型实例上的实验结果表明,Two-stage Inver-over EA比经典的GT算法具有更好的收敛性和搜索效率。

CLC Number: