求解TSP问题的离散型萤火虫群优化算法

摘要

A discrete glowworm swarm optimization (DGSO) algorithm is designed to tackle the travelling salesman problem. A new encoding schema and decoding schema are given with the characteristics of the TSP problem, and a new distance formula and encoding update formula for the new algorithm are given. In order to enhance the capability of the algorithm local searching, and to speed up the algorithm convergence speed, the 2-opt local search scheme is integrated into the new algorithm for solving TSP problem.The proposed algorithm was evaluated on 10 TSP test problems.The numerical experiments show that the proposed algorithm can find the global optimal solution with less computation and evolving time. In case of large scale TSP algorithm can achieve optimal solution of the theory and the error of the optimal solution is also less than 1 % .%基于求解TSP问题,提出一种离散型萤火虫群优化(DGSO)算法,该算法结合TSP问题特点,给出一种有效编码和解码方法,并定义适合编码的个体间距离计算公式和编码更新公式.同时,为增强算法求解TSP问题的局部搜索能力,加快算法的收敛速度,算法使用了操作简单的2-Opt优化算子.最后,通过对10个TSP问题进行仿真实验,实验结果表明本文提出的算法是在种群规模较小,迭代次散较少的情况下就可以收敛到已知最优解.在大规模TSP算例中算法获得的最优值与理论最优值的误差也在1％以下.