基于k-中心点法的改进粒子群算法在旅行商问题中的应用

Improved particle swarm optimization based on k-center and its application in traveling salesman problem

为将面向连续优化的粒子群优化算法应用于旅行商问题的求解,提出了旅行商问题的权重编码方案。该方案将属于组合优化的旅行商问题转化为连续优化问题,同时保留了粒子群算法的易操作性和高效性。针对粒子群算法易陷入局部最优的问题,提出了适合旅行商问题的基于k-中心点法的改进措施。该措施利用简单匹配系数构建粒子群的相异度矩阵,在此基础上采用k-中心点法对粒子群进行聚类分析,实现了粒子之间的信息交换,扩大了粒子的搜索空间,避免算法陷入局部最优。最后,用旅行商问题标准库的4个算例验证了权重编码方案和改进粒子群算法的有效性。

To apply Particle Swarm Optimization （PSO） algorithm oriented to continuous optimization problems in solving Traveling Salesman Problem （TSP）, a new coding method based on the priority was put forward to transform the TSP from combinatorial optimization to continuous optimization. And the easy operation and high efficiency of the PSO were reserved. Then an innovative approach based on k-center algorithm was proposed with purpose of preventing PSO algorithm from local optimum. In this approach, the dissimilarity matrix was constructed by simple matching coefficient. Based on this, the k-center algorithm was used to execute cluster analysis on the particle swarm, which made particles exchange information with each other and search the best solution in a larger solution space than ever, so as to prevent the algorithm from local optimum. Finally, some TSPLIB examples were used to verify the effectiveness of the improved PSO in the TSP.