Abstract: For resolving the two problems, premature convergence and slow-footed convergence, when utilizing particle swarm optimization to solve combinatorial optimization problem, it is necessary tointegrate particle swarm optimization and local search optimization algorithms. This can enhance to restrain premature of particle swarm optimization, and accelerate the convergence rate of the algorithms. The solution quality and solution efficiency of local search algorithms can be improved through establishing reference optimization edge set used by local search algorithms. New hybrid particle swarm optimization utilizing the above-mentioned methods converges high efficaciously to global optimal solutions of middling and small scale TSP. The results of numerous experiments indicate that the new algorithm is efficacious.

Key words: traveling salesman problem, particle swarm optimization, middling and small scale problem, chained Lin-Kernighan algorithm

摘要： 为解决粒子群算法在求解组合优化问题中存在的早熟性收敛和收敛速度慢等问题，将粒子群算法与局部搜索优化算法结合，可抑制粒子群算法早熟收敛问题，提高粒子群算法的收敛速度。通过建立有效的局部搜索优化算法所需借助的参照优化边集，提高了局部搜索优化算法的求解质量和求解效率。新的混合粒子群算法高效收敛于中小规模旅行商问题的全局最优解，实验表明改进的混合粒子群算法是有效的。

关键词: 旅行商问题, 粒子群优化, 中小规模问题, 链式Lin-Kernighan算法

CLC Number: 

• TP18