继承优秀染色体片段的PSO算法求解TSP问题  

Excellent Chromosome Fragments Genetic PSO for Solving Traveling Salesman Problem

作　　者：程乐[1] 张洪斌[1] 

机构地区：[1]淮安信息职业技术学院计算机科学与工程系,江苏淮安223003

出　　处：《微电子学与计算机》2010年第7期202-205,209,共5页Microelectronics & Computer

基　　金：国家自然科学基金项目(60673102);江苏省自然科学基金项目(BK2006218)

摘　　要：粒子群优化算法(PSO)提出至今一直未能有效解决离散及组合优化问题,TSP问题是组合优化问题中一个典型的NP问题.文中参考了离散粒子群算法(DPSO)和遗传算法(GA)解决TSP问题的成功经验,提出了一种继承优秀染色体片段的PSO算法(ECFG-PSO).为避免早熟,在算法中加入了局部查找和二次初始化策略.实验证明ECFG-PSO算法解决TSP问题的效率和规模优于DPSO算法.Particle swarm optimization （PSO） has been applied to many practical continuous optimization problems. However, it could not be extended to solve discrete and combinatorial optimization problems effectively. Traveling salesman problem （TSP） is a typical NP-hard problem. In view of the success of and GA in discrete and continuous optimization problems,this paper proposes a new Excellent Chromosome Fragments Genetic PSO （ECFG-PSO） for TSP. To prevent premature convergence of ECFG-PSO, local searching and the secondery initialization were added to the algorithm. The experiments show that the ECFG-PSO is superior to the DPSO existed in time efficiency and problem size.

关 键 词：粒子群优化算法 TSP DPSO 遗传算法 ECFG-PSO 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]