基于K-means聚类的GWO-ACO混合算法对大规模TSP的优化求解

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

摘要


旅行商问题（TSP）是经典的组合优化NP-hard问题，在物流配送、路径规划等领域具有广泛应用价值。
针对大规模TSP 求解精度低、收敛速度慢、易陷入局部最优的缺陷，本文提出K-means-GWO-ACO混合求解框架。
该算法先通过K-means++聚类划分城市节点，降低求解维度；再采用灰狼优化算法生成高质量初始解，为蚁群算法
提供优质信息素初始分布；最后通过改进型蚁群算法全局寻优，并融合2-opt 局部搜索策略精修解。在不同个城市的
TSP 测试场景下验证，结果表明，该混合算法相较于单一智能算法，在求解精度、收敛稳定性和计算效率上均具显
著优势，可有效解决大规模TSP 的优化难题。

关键词


旅行商问题；K-means聚类；灰狼优化算法；蚁群算法；混合智能算法；2-opt局部搜索

全文:

PDF


参考


[1]MIRJALILI S, MIRJALILI S M, LEWIS A. Grey

Wolf Optimizer [J]. Advances in Engineering Software,

2014,69:46-61.

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

system: optimization by a colony of cooperating agents [J].

IEEE Transactions on Systems, Man, and Cybernetics-Part B:

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

[3]KERNIGHAN B W, LIN S. An efficient heuristic

procedure for partitioning graphs [J]. Bell System Technical

Journal,1970,49 (2):291-307.

[4]张军，李军，王艳秋.基于K-means聚类与改进

蚁群算法的大规模TSP求解[J].控制与决策，2020，35

（8）：1913-1920.

[5]刘建伟，张丽娜，方勇.灰狼优化与蚁群融合算

法的旅行商问题求解[J].计算机应用研究2021，38（5）：

1365-1369+1374.

[6]杨 明， 黄 涛， 吴 昊.K-means++聚 类 改 进 及 在

TSP中的应用[J].计算机工程与应用，2019，55（20）：

123-129.

[7]陈曦.基于混合群智能算法的大规模TSP求解研

究[D].哈尔滨：哈尔滨工业大学，2023.

[8]王鹏，赵旭，李丽.混合智能算法在大规模路径

规划中的应用[J].系统工程理论与实践，2022，42（7）：

1867-1878.


Refbacks

  • 当前没有refback。