求解TSP问题的自适应邻域搜索法及其扩展

TSP问题是测试组合优化领域算法性能的经典平台。提出了一种求解TSP问题的自适应邻域搜索算法,该算法通过为每个城市设定邻域来降低TSP问题的复杂度,并结合满意度和活跃度来构建一种自适应邻域搜索算子,使得其在局部优化的速度和收敛性方面取得了良好的效果。最后在该算法中融入遗传算法思想,将局部优化的高效性和遗传算法的鲁棒性有机结合起来构建成一种综合性能更好的混合优化算法。对eil75、CHN144和TSPLIB中的部分实例的仿真结果表明该算法在寻优度、收敛速度和稳定性等方面都优于目前一些比较常用的算法。

Design and expending of Adaptive Neighborhood Searching Algorithm for TSP

TSP is a classical platform for testing performance of algorithms in combinatorial optimization fields.This paper brings forward an Adaptive Neighborhood Searching Algorithm(ANSA).The new algorithm simplifies the complication of TSP problem by setting neighborhood area for each city,and an adaptive neighborhood searching operator based on satisfaction and activity is designed,aiming at gaining super performance in the speed of local optimization and convergence effect.In order to combine the efficiency of local optimization and robustness of GA,a combinatorial optimization algorithm is introduced.The simulation results of eil75,CHN144 and some problems from TSP library indicate that the over-all properties of the proposed scheme are superior to that of some current algorithms.