Computer Science ›› 2016, Vol. 43 ›› Issue (Z6): 90-92.doi: 10.11896/j.issn.1002-137X.2016.6A.021

Previous Articles     Next Articles

Improved Genetic Algorithm for Traveling Salesman Problem

WEN Yi and PAN Da-zhi   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Traveling salesman problem(TSP) is a typical combination optimization problem,which is also a NP hard problem.It’s hard to find a precision result,and it is very important to search for the near result.Based on basic genetic algorithm in solving TSP problems of slow convergence speed and easy to premature,an improved crossover ope-rator and the updating strategy based on similarity of a population was put forward in this paper.The improved crossover operator exchanges the two cities’ number by comparing the distance between the two cities,thus accelerates the convergence speed.And the updating strategy based on population can effectively prevent the population from premature in the later stages of the algorithm.Espcially,for the CHN144,the best path it finds is better than the basic one.

Key words: TSP,Genetic algorithm,Improved crossover operator,Similarity

[1] 周明,孙树栋.遗传算法原理及应用[M].北京:国防出版社,1999:60-80
[2] 袁满,刘耀林.基于多智体遗传算法的土地利用优化配置[J].农业工程学报,2014,30(1):191-199
[3] 门慧勇.基于遗传算法的图像分割优化研究[D].长春:东北师范大学,2012
[4] 陈侠.基于改进的遗传算法的网络编码优化方法研究[D].武汉:华中科技大学,2012
[5] 周康,强小利,同小军,等.求解TSP算法[J].计算机工程与应用,2007,43(29):43-47
[6] 赵颂华.城市公共资源监管设计新思维[J].科技资讯,2015,5:52-55
[7] Cheang B,Gao Xiang,Lim A,et al.Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints[J].European Journal of Operational Research,2012,223(1):60-75
[8] Nagata Y,Soler D.A new genetic algorithm for the asymmetric traveling salesman problem[J].Expert Systems with Applications,2012,39(10):8947-8953
[9] 周永权,黄正新,刘洪霞.求解TSP问题的离散型萤火虫群优化算法[J].电子学报,2012,40(6):1164-1170
[10] 刘全,王晓燕,傅启明,等.双精英协同进化遗传算法[J].软件学报,2012,23(4):765-775
[11] 姚明海,王娜,赵连朋.改进的模拟退火算法和遗传算法解决TSP问题[J].计算机工程与应用,2013,49(14):60-65
[12] 谢燕丽,许春林,姜文超.一种基于交叉和变异算子改进的遗传算法研究[J].计算机应用与发展,2014,24(14):80-83
[13] 汪金刚,罗辞勇.求解TSP问题的自适应领域遗传算法[J].2010,46(27):20-24

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!