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

引入自适应升温策略或使用蒙特卡罗策略的模拟退火算法在复杂TSP求解时分别表现出收敛缓慢和全局最优逼近能力有限的问题;而现有的混沌优化算法由于logistic映射的缺陷,削弱了其跳出局部最优的能力.故设计一种融合型算法框架,在框架中嵌入分片Lorenz混沌映射系统,加强混沌算法对邻域解的搜索均匀度;引入了贪婪策略构造逼近全局最优解的初始解,使算法具有跃迁到全局最优解邻域的能力;此外设计了振荡退火互补机制,改善了子迭代解筛选过程,增强算法全局搜索性能.实现算法后,使用国际公开TSPLIB算例,经过多轮对比测试,验证了新算法对TSP的求解性能指标优于对比组模拟退火算法和logistic混沌优化算法,具有更短的收敛时间和更强的全局最优逼近能力.

Divided chaotic oscillatory annealing TSP optimization algorithm based on greedy strategy

The simulated annealing algorithm with adaptive temperature rising strategy or Monte Carlo strategy shows 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 have 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 enhance 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.