Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (31): 30-33.DOI: 10.3778/j.issn.1002-8331.2009.31.010

• 研究、探讨 • Previous Articles     Next Articles

Improved self-organizing particle swarm optimization for Traveling Salesman Problem

SUN Jing-jing,LEI Xiu-juan   

  1. School of Computer Science,Shaanxi Normal University,Xi’an 710062,China
  • Received:2009-05-18 Revised:2009-06-25 Online:2009-11-01 Published:2009-11-01
  • Contact: SUN Jing-jing

求解TSP的改进自组织PSO算法

孙晶晶,雷秀娟   

  1. 陕西师范大学 计算机科学学院,西安 710062
  • 通讯作者: 孙晶晶

Abstract: To alleviate the premature convergence of basic particle swarm optimization(PSO),an improved self-organized particle swarm optimization(SOPSO) algorithm is proposed,whose parameter setting are improved based on the characteristics of self-organizing criticality in the interest of the diversity of population.That is,the self-organizing inertia weight and acceleration coefficients are applied and the mutation operator is introduced.In view of the concept of “Swap operator” and“Swap sequence”,the improved SOPSO algorithm which can search in the discrete domain directly is designed to solve the traveling salesman problem(TSP).Then compare the results of the improved algorithm with those of the basic PSO and other improved PSO algorithm.The results show that the improved SOPSO algorithm is effective.

Key words: Particle Swarm Optimization(PSO), self-organizing, population diversity, Traveling Salesman Problem(TSP)

摘要: 针对粒子群算法(PSO)的早熟收敛现象,从种群多样性出发,基于自组织临界性特点改进PSO 算法的参数设置,采用自组织的惯性权重和加速系数,并增加了变异算子。借鉴交换子和交换序概念,设计出了能直接在离散域进行搜索的改进的自组织PSO算法。用于旅行商问题(TSP)的求解,并与基本及其他典型改进PSO算法进行性能比较。实验结果证实改进的自组织PSO算法是有效的。

关键词: 粒子群算法, 自组织, 种群多样性, 旅行商问题(TSP)

CLC Number: