计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (4): 52-53.DOI: 10.3778/j.issn.1002-8331.2010.04.016

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

改进粒子群优化算法求解TSP问题

苏晋荣,王建珍   

  1. 山西大学 商务学院 信息工程系,太原 030031
  • 收稿日期:2009-09-07 修回日期:2009-11-18 出版日期:2010-02-01 发布日期:2010-02-01
  • 通讯作者: 苏晋荣

Improved particle swarm optimization for traveling salesman problem

SU Jin-rong,WANG Jian-zhen   

  1. Department of Information Engineering,College of Business,Shanxi University,Taiyuan 030031,China
  • Received:2009-09-07 Revised:2009-11-18 Online:2010-02-01 Published:2010-02-01
  • Contact: SU Jin-rong

摘要: 针对粒子群优化算法易陷入局部极值的缺点,提出一种改进粒子群算法,该算法借鉴贪婪算法的思想初始化种群,利用两个种群同时寻优,并将遗传算法中交叉和变异操作引入其中,实现种群间的信息共享。用14点TSP标准数据对算法性能进行了测试,结果表明该算法能够较早跳出局部最优,具有较高的收敛速度和收敛率。

Abstract: In allusion to particle swarm optimization being prone to get into local minimum,an improved particle swarm optimization algorithm is proposed.The algorithm draws on the thinking of the greedy algorithm to initialize the particle swarm. Two swarms are used to optimize synchronously,and crossover and mutation operators in genetic algorithm are introduced into the new algorithm to realize the sharing of information among swarms.This paper tests the algorithm with a Traveling Salesman Problem with 14 nodes.The result shows that the algorithm can break away from local minimum earlier and it has high convergence speed and convergence ratio.

中图分类号: