计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (25): 38-40.DOI: 10.3778/j.issn.1002-8331.2009.25.012

• 研究、探讨 • 上一篇    下一篇

旅行商问题研究及混合粒子群算法求解

孙 聪,赵新超   

  1. 北京邮电大学 理学院 数学系,北京 100876
  • 收稿日期:2008-10-23 修回日期:2009-01-12 出版日期:2009-09-01 发布日期:2009-09-01
  • 通讯作者: 孙 聪

Research on traveling salesman problem and its solving with hybrid particle swarm optimization algorithm

SUN Cong,ZHAO Xin-chao   

  1. Department of Mathematics,School of Science,Beijing University of Posts and Telecommunications,Beijing 100876,China
  • Received:2008-10-23 Revised:2009-01-12 Online:2009-09-01 Published:2009-09-01
  • Contact: SUN Cong

摘要: 定性地分析了基本粒子群算法,结合遗传算法思想,构造了3种杂交和4种变异运算法则,从而得到了12种混合粒子群算法,并采用14城市算例对其检验和分析。为进一步验证混合算法的性能,根据分析结果挑选了几种较优的混合算法用以解决中国34城市(CTSP)问题和kroC100问题,其中CTSP问题很快达到最优解,对kroC100问题该文提供的算法获得了一个比现有已知结果更好的结果。

关键词: 旅行商问题, 粒子群算法, 2-opt, 3-opt, 遗传算法

Abstract: This paper qualitatively analyzes the basic Particle Swarm Optimization(PSO) algorithm.Integrating the ideas of genetic algorithm,3 kinds of crossover and 4 mutation operators are constructed and 12 hybrid PSO algorithms are obtained.A 14-city problem is firstly used to examine and analyze the proposed algorithms.To further verify the proposed algorithms’ performance,several good hybrid algorithms are selected based on the analytic results to solve the Chinese 34-city problem(CTSP) and the kroC100 problem.The optimal solution is quickly obtained for CTSP instance and an even better solution compared with the recent algorithms is obtained for kroC100 instance.

Key words: traveling salesman problem, Particle Swarm Optimization(PSO), 2-opt, 3-opt, genetic algorithm

中图分类号: