Abstract: This paper proposes a hybrid particle swarm optimization algorithm called SKHPSO to solve traveling salesman problem(TSP)by overcoming the premature convergence and low search efficiency of the standard particle swarm optimization algorithm(PSO). SKHPSO uses a similar Kruskal-based algorithm by which a specific means of implementation for Greedy Heuristic is given to get an initial feasible solution,as a member of the population in the PSO, then SKHPSO carries out the heuristic search with hybrid PSO algorithm combining the local search based on Lin-Kernighan local neighbor search operation and the global search, such as cross and replacement operations in single individual, which is used in genetic algorithm. The instances in the standard library, TSPLIB, are tested to verify our proposed algorithm. The results have shown that SKHPSO is effective to enhance the quality and efficiency of the solution.

Key words: operations research, hybrid particle swarm optimization, Kruskal, greedy heuristic, Lin-Kernighan, traveling salesman problem

摘要： 本文针对求解旅行商问题的标准粒子群算法所存在的早熟和低效的问题,提出一种基于Greedy Heuristic的初始解与粒子群相结合的混合粒子群算法(SKHPSO)。该算法通过本文给出的类Kruskal算法作为Greedy Heuristic的具体实现手段,产生一个较优的初始可行解,作为粒子群中的一员,然后再用改进的混合粒子群算法进行启发式搜索。SKHPSO的局部搜索借鉴了Lin-Kernighan邻域搜索,而全局搜索结合了遗传算法中的交叉及置换操作。应用该算法对TSPLIB中的典型算例进行了算法测试分析,结果表明:SKHPSO可明显提高求解的质量和效率。

关键词: 运筹学, 混合粒子群算法, Kruskal, Greedy Heuristic, Lin-Kernighan, 旅行商问题