CAJ | 학술논문

本文针对求解旅行商问题的标准粒子群算法所存在的早熟和低效的问题，提出一种基于 Greedy Heuristic的初始解与粒子群相结合的混合粒子群算法（ SKHPSO ）。该算法通过本文给出的类Kruskal算法作为Greedy Heuristic的具体实现手段，产生一个较优的初始可行解，作为粒子群中的一员，然后再用改进的混合粒子群算法进行启发式搜索。 SKHPSO的局部搜索借鉴了Lin-Kernighan邻域搜索，而全局搜索结合了遗传算法中的交叉及置换操作。应用该算法对TSPLIB中的典型算例进行了算法测试分析，结果表明：SKHPSO可明显提高求解的质量和效率。
본문침대구해여행상문제적표준입자군산법소존재적조숙화저효적문제，제출일충기우 Greedy Heuristic적초시해여입자군상결합적혼합입자군산법（ SKHPSO ）。해산법통과본문급출적류Kruskal산법작위Greedy Heuristic적구체실현수단，산생일개교우적초시가행해，작위입자군중적일원，연후재용개진적혼합입자군산법진행계발식수색。 SKHPSO적국부수색차감료Lin-Kernighan린역수색，이전국수색결합료유전산법중적교차급치환조작。응용해산법대TSPLIB중적전형산례진행료산법측시분석，결과표명：SKHPSO가명현제고구해적질량화효솔。
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 parti -cle 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 popu-lation 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 replace-ment 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 .