混合退火算法求解旅行商问题  

Hybrid annealing algorithm for solving travellling salesman problem

作　　者：李阳[1] 李文芳[1] 马骊[1] 樊锁海[1] 

机构地区：[1]暨南大学信息科学技术学院,广州510632

出　　处：《计算机应用》2014年第A01期110-113,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(10671076);广东省自然科学基金资助项目(10151063201000005)

摘　　要：为优化旅行商问题(TSP),结合禁忌搜索算法(TS)和模拟退火算法(SA)的思想设计了混合退火算法(TSA)。针对模拟退火算法搜索效果不稳定等问题,在初始阶段TSA多次禁忌搜索并筛选初始解,确保算法稳定地收敛到全局最优值,在求解部分设计了快速退火算法,使其快速退火并收敛。与其他算法相比,TSA求解精度高,求解效果稳定鲁棒性强,并且求解时间短。TSA对China31问题的优化效果尤为精良,优化结果包括15375,15363,15352和15335等,均优于已知最好解15383。The hybrid annealing algorithm （TSA）, combining with the ideal of the Tabu Search （TS） algorithm and the Simulated Annealing （SA） algorithm, is proposed to optimize the well-known Traveling Salesman Problem （TSP）. In view of the defect that the search performance of SA is not stable, the TSA algorithm use TS to search initial solutions for several times, to ensure the stable convergence of the algorithm to the global optimal value. Compared with other algorithms, the TSA algorithm has a high precision, strong robustness and rapid convergence. The TSA algorithm has an excellent effect on China31 problem, its optimization results include 15 375, 15 363, 15 352, and 15 335, which all are better than the known best value 15 378.

关 键 词：旅行商问题 禁忌搜索 模拟退火 混合退火 快速退火 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP18[自动化与计算机技术—计算机科学与技术]