摘要
基于求解TSP问题,提出一种离散型萤火虫群优化(DGSO)算法,该算法结合TSP问题特点,给出一种有效编码和解码方法,并定义适合编码的个体间距离计算公式和编码更新公式.同时,为增强算法求解TSP问题的局部搜索能力,加快算法的收敛速度,算法使用了操作简单的2-Opt优化算子.最后,通过对10个TSP问题进行仿真实验,实验结果表明本文提出的算法是在种群规模较小,迭代次数较少的情况下就可以收敛到已知最优解.在大规模TSP算例中算法获得的最优值与理论最优值的误差也在1%以下.
A discrete glowworm swarm optimization (DGSO) algorithm is designed to tackle the travelling salesman prob lem. A new encoding schema and decoding schema are given with the characteristics of the TSP problem, and a new distance formu la 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 2opt 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 algo rithm 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%.
出处
《电子学报》
EI
CAS
CSCD
北大核心
2012年第6期1164-1170,共7页
Acta Electronica Sinica
基金
国家自然科学基金(No.61165015)
广西自然科学基金重点项目(No.2012GXNSFDA053028)
智能感知与图像理解教育部重点实验室开放基金(No.IPIU012011001)