求解TSP问题的改进模拟退火算法
|
摘要
模拟退火算法是一种结构简单,鲁棒性强的群智能方法,在旅行商问题(Traveling Salesman Problem TSP)中得到了较好的应用。但是该算法在获取高性能解的过程中需要放慢降温过程,因此收敛速度较慢。为了解决该问题,本文对求解TSP问题的模拟退火算法进行了降温方式的改进,针对温度设置能量值,并根据能量值的高低状态判断是否进行跳跃式降温,从而在保证精度的同时,加快了算法的收敛速度。用TSPLIB标准库数据测试的结果表明,与改进前的模拟退火算法相比,改进的算法具有更加高效的寻优能力。
Simulated annealing is a simple and robust swarm optimization method, which has been well applied in solving Traveling Salesman Problem(TSP). However, the algorithm needs to slow down the cooling process in the process of obtaining highperformance solutions, so the convergence speed is slow. In order to solve this problem, this paper improves the simulated annealing algorithm for solving TSP, sets the energy value for the temperature, and judges whether the jumping cooling is carried out according to the state of the energy value, thus speeds up the convergence speed of the algorithm while ensuring the accuracy.The performance of the algorithm is verified by the test on standard TSPLIB data, the results show that the improved algorithm has a more efficient optimization.
Simulated annealing is a simple and robust swarm optimization method, which has been well applied in solving Traveling Salesman Problem(TSP). However, the algorithm needs to slow down the cooling process in the process of obtaining highperformance solutions, so the convergence speed is slow. In order to solve this problem, this paper improves the simulated annealing algorithm for solving TSP, sets the energy value for the temperature, and judges whether the jumping cooling is carried out according to the state of the energy value, thus speeds up the convergence speed of the algorithm while ensuring the accuracy.The performance of the algorithm is verified by the test on standard TSPLIB data, the results show that the improved algorithm has a more efficient optimization.
引文
[1]徐德明.改进的遗传混合蚁群算法在TSP问题中的应用[J].计算机时代,2012(11):31-32+36.
[2]张梦,陈仕军,李嘉宾,刘朝阳.基于模拟退火算法的一维下料研究[J].计算机时代,2017.12:1-4
[3]杜鹏桢,唐振民,孙研.一种面向对象的多角色蚁群算法及其TSP问题求解[J].控制与决策,2014.29(10):1729-1736
[4]易正俊,李勇霞,易校石.自适应蚁群算法求解最短路径和TSP问题[J].计算机技术与发展,2016.26(12):1-5
[5]姚明海,王娜,赵连朋.改进的模拟退火和遗传算法求解TSP问题[J].计算机工程与应用,2013.49(14):60-65
[6]郭中华,金灵,郑彩英.人工神经网络求解TSP问题的改进算法研究[J].计算机仿真,2014.31(4):355-358
[7]张家善,王志宏.基于信息素的改进蚁群算法及其在TSP中的应用[J].数学的实践与认识,2013.43(22):157-161
[8]于宏涛,高立群,田卫华.求解TSP的离散人工蜂群算法[J].东北大学学报:自然科学版,2015.36(8):1074-1079
[9]程博,杨育,刘爱军等.基于遗传模拟退火算法的大件公路运输路径选择优化[J].计算机集成制造系统,2013.19(4):879-887
[2]张梦,陈仕军,李嘉宾,刘朝阳.基于模拟退火算法的一维下料研究[J].计算机时代,2017.12:1-4
[3]杜鹏桢,唐振民,孙研.一种面向对象的多角色蚁群算法及其TSP问题求解[J].控制与决策,2014.29(10):1729-1736
[4]易正俊,李勇霞,易校石.自适应蚁群算法求解最短路径和TSP问题[J].计算机技术与发展,2016.26(12):1-5
[5]姚明海,王娜,赵连朋.改进的模拟退火和遗传算法求解TSP问题[J].计算机工程与应用,2013.49(14):60-65
[6]郭中华,金灵,郑彩英.人工神经网络求解TSP问题的改进算法研究[J].计算机仿真,2014.31(4):355-358
[7]张家善,王志宏.基于信息素的改进蚁群算法及其在TSP中的应用[J].数学的实践与认识,2013.43(22):157-161
[8]于宏涛,高立群,田卫华.求解TSP的离散人工蜂群算法[J].东北大学学报:自然科学版,2015.36(8):1074-1079
[9]程博,杨育,刘爱军等.基于遗传模拟退火算法的大件公路运输路径选择优化[J].计算机集成制造系统,2013.19(4):879-887