一种分片混沌贪婪振荡退火TSP优化算法  

Divided chaotic oscillatory annealing TSP optimization algorithm based on greedy strategy

作　　者：林之博 刘媛华[1] Lin Zhibo;Liu Yuanhua(Business School,University of Shanghai for Science&Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《计算机应用研究》2021年第8期2359-2364,共6页Application Research of Computers

基　　金：国家自然科学基金资助项目(11505114)。

摘　　要：引入自适应升温策略或使用蒙特卡罗策略的模拟退火算法在复杂TSP求解时分别表现出收敛缓慢和全局最优逼近能力有限的问题;而现有的混沌优化算法由于logistic映射的缺陷,削弱了其跳出局部最优的能力。故设计一种融合型算法框架,在框架中嵌入分片Lorenz混沌映射系统,加强混沌算法对邻域解的搜索均匀度;引入了贪婪策略构造逼近全局最优解的初始解,使算法具有跃迁到全局最优解邻域的能力;此外设计了振荡退火互补机制,改善了子迭代解筛选过程,增强算法全局搜索性能。实现算法后,使用国际公开TSPLIB算例,经过多轮对比测试,验证了新算法对TSP的求解性能指标优于对比组模拟退火算法和logistic混沌优化算法,具有更短的收敛时间和更强的全局最优逼近能力。The simulated annealing algorithm with adaptive temperature rising strategy or Monte Carlo strategy has the problems of slow convergence and limited global optimal approximation ability in solving complex TSP respectively.On the other hand,the existing chaotic optimization algorithm has the defect of logistic mapping,which weakens its ability to jump out of local optima.Therefore,this paper designed a fusion algorithm framework,in which embedded the divided Lorenz chaotic mapping system to enhance the search efficiency of the chaotic algorithm for the neighborhood solution.It introduced the greedy strategy to construct the initial solution approaching the global optimal solution,which made the algorithm had the ability of transition to the neighborhood of the global optimal solution.In addition,it designed the complementary mechanism of oscillatory annealing to improve the sub iterative solution screening process,and enhanced the global search performance of the algorithm.After the implementation of the algorithm,using the international public TSPLIB point set,through multiple rounds of comparative testing,it verifies that the performance of the new algorithm is better than the comparison group simulated annealing algorithm and logistic chaos optimization algorithm,and has shorter convergence time and stronger global optimal approximation ability.

关 键 词：旅行商 贪婪策略 退火策略 混沌优化算法 邻域振荡 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]