基于K-Means聚类的混合粒子群算法求解旅行商问题

Solving the Traveling Salesman Problem Using a Hybrid Particle Swarm Optimization Algorithm Based on K-Means Clustering

摘要: 本文针对基本粒子群算法在求解TSP问题时容易陷入局部最优的问题，提出了一种改进的混合粒子群算法。在利用粒子群算法的快速搜索能力引导全局优化的基础上，引入遗传算法的交叉、变异等操作增强种群多样性与局部寻优能力。同时使用K-Means算法对混合粒子群算法进行改进，提高算法迭代速度。通过TSPLIB中实例的求解与分析，实验结果表明改进后的混合粒子群算法能更加有效解决TSP问题。

Abstract: This paper addresses the issue of the basic Particle Swarm Optimization (PSO) algorithm easily falling into local optima when solving the Traveling Salesman Problem (TSP). It proposes an improved hybrid PSO algorithm. Building on the rapid search capability of PSO to guide global optimization, the algorithm introduces crossover and mutation operations from the Genetic Algorithm (GA) to enhance population diversity and local search ability. Additionally, the K-Means algorithm is utilized to refine the hybrid PSO algorithm, thereby increasing the iteration speed of the algorithm. Through the solution and analysis of instances from TSPLIB, experimental results demonstrate that the improved hybrid PSO algorithm can more effectively solve the TSP problem.