AVOA-ACO混合算法结合2-opt局部搜索求解旅行商问题

于 兴博
辽宁科技大学　计算机与软件工程学院

摘要


旅行商问题（TSP）是组合优化领域经典的NP-hard问题，在物流配送、路径规划、生产调度等领域应用
广泛。蚁群算法（ACO）凭借良好的全局搜索能力被用于求解该问题，但传统ACO存在收敛慢、易陷入局部最优、
参数敏感性强的缺陷。针对此，本文提出基于非洲秃鹫优化算法（AVOA）的改进蚁群算法（AVOA-ACO），通过
AVOA自动优化ACO关键参数，引入候选邻域搜索、精英信息素更新及2-opt局部搜索策略提升算法搜索效率与解
质量，同时设计停滞重启机制避免算法早熟收敛、增强全局搜索能力。实验结果表明，该算法相较传统ACO在路径
长度和收敛速度上均有显著改善，验证了其求解TSP问题的有效性。

关键词


旅行商问题；蚁群算法；非洲秃鹫优化算法；路径规划；2-opt

全文:

PDF


参考


[1]ABDOLLAHZADEH B, MIRJALILI S, KHAN

M G, et al. African Vulture Optimization Algorithm: A

New Nature-Inspired Metaheuristic Algorithm for Global

Optimization[J]. Computers & Industrial Engineering, 2021,

158: 107408.

[2]DORIGO M, MANIEZZO V, COLORNI A.

The Ant System: Optimization by a Colony of Cooperating

Agents[J]. IEEE Transactions on Systems, Man, and

Cybernetics-Part B, 1996, 26(1): 29-41.

[3]DORIGO M, GAMBARDELLA L M. Ant Colonies

for the Traveling Salesman Problem[J]. Bio-Systems, 1997,

43(2): 73-81.

[4]CROES G A. A Method for Solving TravelingSalesman Problems[J]. Operations Research, 1958, 6(6): 791-

812.

[5]段海滨.蚁群算法原理及其应用[M].北京：科学

出版社，2005.

[6]卢宇凡，张莉.自适应蚁群算法在求解TSP问题

中的应用[J].微型机与应用，2012，31（17）：48-50.

[7]张于贤，丁修坤，薛殿春，等.求解旅行商问题

的改进蚁群算法研究[J].计算机工程与科学，2017，39

（8）：1576-1580.

[8]李朝迁，裴建朝.新型模拟退火遗传算法在路径

优化的应用[J].组合机床与自动化加工技术，2022，（3）：

52-55.

[9]王忠英，白艳萍，岳利霞.经过改进的求解TSP

问题的蚁群算法[J].数学的实践与认识，2012，42（4）：

133-140.


Refbacks

  • 当前没有refback。