求解动态旅行商问题的蚁群优化算法新策略

Novel Strategy of Ant Colony Optimization for Dynamic Traveling Salesman Problem

动态旅行商问题是标准旅行商问题的一个扩展,由于其现实应用广泛,吸引了大量研究者的兴趣。蚁群优化算法可以转化历史环境信息,天然具有适应动态改变的能力,可以解决动态旅行商问题。使用蚁群优化算法解决优化问题时,算法探索能力和利用能力的权衡是一个关键问题。传统的思路是在搜索前期侧重探索能力,使蚁群充分获取搜索空间的信息,随着搜索过程的进行逐渐增强利用能力,使蚁群逐渐收敛。然而,以上思路不利于在动态场景中快速获得质量较高的解。针对动态旅行商问题,提出了一种新的探索-利用权衡策略,在环境变化后,首先使用模拟退火算法增强利用能力以快速获得质量较高的解,在解质量难以提高时再使用自适应性轮盘赌选择方法帮助算法跳出局部极值。在权重变化的动态旅行商问题上的实验证明,所提新策略优于其它蚁群优化算法及变体。

The dynamic traveling salesman problem is an extension of the standard traveling salesman problem and has attracted a great deal of interest due to its wide range of real-world applications.Ant colony optimization algorithms can transform historical environmental information and have the ability to adapt to dynamic changes to solve dynamic traveling salesman problems.The trade-off between algorithmic exploration and exploitation capability is a key issue when using ant colony optimization algorithms to solve optimization problems.The traditional idea is to focus on the exploration capability in the early stage of search,so that the ant colony can fully acquire the information of the search space,and gradually enhance the exploitation capability as the search process proceeds,so that the ant colony gradually converges.However,this way of thinking is not conducive to obtaining high-quality solutions quickly in dynamic scenarios.To address this problem,a new exploration-exploitation trade-off strategy is proposed,which first uses a simulated annealing algorithm to enhance the exploitation ability to quickly obtain higher-quality solutions after the environment changes,and then uses an adaptive roulette selection method to help the algorithm jump out of local extremes when the solution quality is difficult to improve.Experiments on dynamic traveling salesman problems with changing weights demonstrate that such strategies outperform other ant colony optimization algorithms and variants.