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

Excellent Chromosome Fragments Genetic PSO for Solving Traveling Salesman Problem

粒子群优化算法(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.