基于蚁群数量动态调整的改进蚁群优化算法

doi:10.11772/j.issn.1001-9081.2022081155

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (S1): 163-168.DOI: 10.11772/j.issn.1001-9081.2022081155

• 先进计算 • 上一篇

基于蚁群数量动态调整的改进蚁群优化算法

白玮¹(), 王成², 王彩玲¹, 詹熙¹, 张磊¹

^1.中国人民解放军陆军工程大学指挥控制工程学院，南京 210014
^2.中国人民解放军 92403部队，福州 350007

收稿日期:2022-08-07 修回日期:2022-10-22 接受日期:2022-11-03 发布日期:2023-07-04 出版日期:2023-06-30
通讯作者: 白玮
作者简介:白玮（1983—），男，河北张家口人，讲师，博士，主要研究方向：人工智能、网络智能管理.baiwei_lgdx@126.com
王成（1983—），男，福建莆田人，硕士，主要研究方向：信息系统安全与管理
王彩玲（1981—），女，山东临沂人，硕士，主要研究方向：人工智能算法优化
詹熙（1999—），男，江西上饶人，硕士研究生，主要研究方向：数据工程、时间序列分析
张磊（1989—），男，江西宜春人，博士研究生，主要研究方向：强化学习、数据工程。
基金资助:
陆军工程大学基础前沿科技创新项目(KYZYJQZL2008)

Improved ant colony optimization algorithm based on ant number dynamic adjustment

Wei BAI¹(), Cheng WANG², Cailing WANG¹, Xi ZHAN¹, Lei ZHANG¹

^1.College of Command and Control Engineering，Army Engineering University of PLA，Nanjing Jiangsu 210014，China
^2.Unit 92403，PLA，Fuzhou Fujian 350007，China

Received:2022-08-07 Revised:2022-10-22 Accepted:2022-11-03 Online:2023-07-04 Published:2023-06-30
Contact: Wei BAI

摘要/Abstract

摘要：

蚁群优化（ACO）算法是一种常用的元启发式算法，它通过模拟蚁群寻找食物的过程，为求解多维背包问题（MKP）等NP难（Non-deterministic Polynomial hard）问题提供可行途径。原始ACO算法及其改进算法，通常分为多个轮次，每个轮次均会生成一个蚂蚁种群寻找可行解。在不同轮次中，每轮蚁群中蚂蚁的数量是固定的，因此，如果将其指定一个较大的值，会导致算法出现不必要的时间消耗；反之，如果指定的值较小，则会降低算法全局最优解搜索能力。为此，提出了一种基于蚁群数量动态调整的改进蚁群优化算法ACO-ANDA（ACO algorithm based on Ant Number Dynamic Adjustment），所提算法在可行解搜索过程中，引入了一种新的蚁群数量动态调整机制。在每轮可行解搜索结束后，均根据近几轮可行解和历史最优解之间的关系，调整下一轮蚁群数量，实现对算法时间耗费和最优解搜索能力的平衡。再基于MKP基准测试集SAC-94的多组实验结果表明，相较于原始ACO算法，所提算法能够在最优解利润平均降低0.02%的情况下，平均降低77.85%的时间耗费。

关键词: 元启发式算法, 蚁群优化算法, 多维背包问题, 蚁群数量, 动态调整

Abstract:

The Ant Colony Optimization （ACO） algorithm is a common meta-heuristic algorithm， which provides feasible approaches to solve NP-hard （Non-deterministic Polynomial hard） problems such as Multi-dimensional Knapsack Problem （MKP） by simulating the process of ant colony searching for food. The original ACO algorithm and its improved algorithms are often divided into several rounds. In each round， a fixed number of ants are generated to find a feasible solution， which will lead to the difficulty of determining the number of ants， as a larger number will lead to unnecessary time consumption， and a smaller number will lead to a reduction in the optimal solution search capability. To tackle this issue， an improved ant colony optimization algorithm， named ACO-ANDA （ACO algorithm based on Ant Number Dynamic Adjustment） was proposed， which introduced a novel ant number dynamic adjustment mechanism. At the end of each round of feasible solution search， the ant number was adjusted for the next round based on the relationship between feasible solutions and historical optimal solutions in recent rounds to achieve a balance between time consumption and optimal solution search capability. Some experiments on the benchmark testing set of MKP SAC-94 were performed to compare with the original ACO algorithm. The results showed that the proposed algorithm could reduce the time consumption by 77.85% while the profit of the optimal solution was only reduced by 0.02% on average.

Key words: meta-heuristic algorithm, Ant Colony Optimization (ACO) algorithm, Multi-dimensional Knapsack Problem (MKP), ant number, dynamic adjustment

中图分类号:

TP301.6

白玮, 王成, 王彩玲, 詹熙, 张磊. 基于蚁群数量动态调整的改进蚁群优化算法[J]. 计算机应用, 2023, 43(S1): 163-168.

Wei BAI, Cheng WANG, Cailing WANG, Xi ZHAN, Lei ZHANG. Improved ant colony optimization algorithm based on ant number dynamic adjustment[J]. Journal of Computer Applications, 2023, 43(S1): 163-168.

图/表 9

参考文献 30

1	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. 10.1109/3477.484436
2	FRÉVILLE A. The multidimensional 0-1 knapsack problem： an overview［J］. European Journal of Operational Research， 2004， 155（1）： 1-21. 10.1016/s0377-2217(03)00274-1
3	REZOUG A， BOUGHACI D， BADR-EL-DEN M. Memetic algorithm for solving the 0-1 multidimensional knapsack problem［C］// Proceedings of the 2015 Portuguese Conference on Artificial Intelligence. Cham： Springer， 2015： 298-304. 10.1007/978-3-319-23485-4_31
4	BALAS E. An additive algorithm for solving linear programs with zero-one variables［J］. Operations Research， 1965， 13（4）： 517-546. 10.1287/opre.13.4.517
5	MANSINI R， SPERANZA M G. CORAL： an exact algorithm for the multidimensional knapsack problem［J］. INFORMS Journal on Computing， 2012， 24（3）： 399-415. 10.1287/ijoc.1110.0460
6	BALEV S， YANEV N， FRÉVILLE A， et al. A dynamic programming based reduction procedure for the multidimensional 0⁃1 knapsack problem［J］. European Journal of Operational Research， 2008， 186（1）： 63-76. 10.1016/j.ejor.2006.02.058
7	CHU P C， BEASLEY J E. A genetic algorithm for the multidimensional knapsack problem［J］. Journal of Heuristics， 1998， 4（1）： 63-86. 10.1023/a:1009642405419
8	MANSOUR I B， ALAYA I. Indicator based ant colony optimization for multi-objective knapsack problem［J］. Procedia Computer Science， 2015， 60： 448-457. 10.1016/j.procs.2015.08.165
9	GLOVER F， KOCHENBERGER G A. Critical Event Tabu Search for Multidimensional Knapsack Problems［M］. 1st ed. Boston： Springer， 1996： 407-427. 10.1007/978-1-4613-1361-8_25
10	CHO J H， KIM Y D. A simulated annealing algorithm for resource constrained project scheduling problems［J］. Journal of the Operational Research Society， 1997， 48（7）： 736-744. 10.1038/sj.jors.2600416
11	YAN H F， CAI C Y， LIU D H， et al. Water wave optimization for the multidimensional knapsack problem［C］// Proceedings of the 2019 International Conference on Intelligent Computing. Cham： Springer， 2019： 688-699. 10.1007/978-3-030-26969-2_65
12	SETZER T， BLANC S M. Empirical orthogonal constraint generation for multidimensional 0/1 knapsack problems［J］. European Journal of Operational Research， 2020， 282（1）： 58-70. 10.1016/j.ejor.2019.09.016
13	NAKBI W， ALAYA I， ZOUARI W. A hybrid Lagrangian search ant colony optimization algorithm for the multidimensional knapsack problem［J］. Procedia Computer Science， 2015， 60： 1109-1119. 10.1016/j.procs.2015.08.158
14	GARG H. A hybrid GSA-GA algorithm for constrained optimization problems［J］. Information Sciences， 2019， 478： 499-523. 10.1016/j.ins.2018.11.041
15	GARG H. A hybrid PSO-GA algorithm for constrained optimization problems［J］. Applied Mathematics and Computation， 2016， 274： 292-305. 10.1016/j.amc.2015.11.001
16	GARG H. A Hybrid GA-GSA Algorithm for Optimizing the Performance of an Industrial System by Utilizing Uncertain Data［M］. 1st ed. Hershey： IGI Global， 2015： 620-654. 10.4018/978-1-4666-7258-1.ch020
17	SHIH W. A branch and bound method for the multiconstraint zero-one knapsack problem［J］. Journal of the Operational Research Society， 1979， 30（4）： 369-378. 10.1057/jors.1979.78
18	VIMONT Y， BOUSSIER S， VASQUEZ M. Reduced costs propagation in an efficient implicit enumeration for the 0-1 multidimensional knapsack problem［J］. Journal of Combinatorial Optimization， 2008， 15（2）： 165-178. 10.1007/s10878-007-9074-4
19	PATHAN S R， PANWAR D. A smart channel estimation approach for LTE systems using PSO algorithm［J］. Annals of Optimization Theory and Practice， 2020， 3（3）： 1-13.
20	ZAPATA H， PEROZO N， ANGULO W， et al. A hybrid swarm algorithm for collective construction of 3D structures［J］. International Journal of Artificial Intelligence， 2020， 18（1）： 1-18.
21	RAHIMIAN M. Measuring efficiency in DEA by differential evolution algorithm［J］. Annals of Optimization Theory and Practice， 2019， 2（1）： 19-26.
22	PRECUP R E， DAVID R C， PETRIU E M， et al. Grey wolf optimizer-based approach to the tuning of PI-fuzzy controllers with a reduced process parametric sensitivity ［J］. IFAC-PapersOnLine， 2016， 49（5）： 55-60. 10.1016/j.ifacol.2016.07.089
23	FINGLER H， CÁCERES E N， MONGELLI H， et al. A CUDA based solution to the multidimensional knapsack problem using the ant colony optimization［J］. Procedia Computer Science， 2014， 29： 84-94. 10.1016/j.procs.2014.05.008
24	胡小兵，黄席樾. 基于ACO的0-1背包问题求解［J］. 系统工程学报， 2005， 20（5）： 520-523.
25	LEGUIZAMON G， MICHALEWICZ Z. A new version of ant system for subset problems［C］// Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway： IEEE， 1999， 2： 1459-1464.
26	PARRA-HERNANDEZ R， DIMOPOULOS N. Heuristic approaches for solving the Multidimensional Knapsack Problem （MKP）［J］. WSEAS Transactions on Systems， 2002， 1（2）： 248-253.
27	KONG M， TIAN P， KAO Y. A new ant colony optimization algorithm for the multidimensional knapsack problem［J］. Computers & Operations Research， 2008， 35（8）： 2672-2683. 10.1016/j.cor.2006.12.029
28	JI J， HUANG Z， LIU C， et al. An ant colony optimization algorithm for solving the multidimensional knapsack problems［C］// Proceedings of the 2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology. Piscataway： IEEE， 2007： 10-16. 10.1109/iat.2007.26
29	CHANGDAR C， MAHAPATRA G S， PAL R K. An ant colony optimization approach for binary knapsack problem under fuzziness［J］. Applied Mathematics and Computation， 2013， 223： 243-253. 10.1016/j.amc.2013.07.077
30	姜道银，葛洪伟，袁罗. 一种动态划分的混合连续域ACO［J］. 计算机工程与应用， 2018， 54（7）： 144-151.

数据文件	背包维度	已知最优解
weish06.dat	40	5 557
weish14.dat	60	6 954
weigh28.dat	90	9 492

数据文件	背包维度	已知最优解
weish06.dat	40	5 557
weish14.dat	60	6 954
weigh28.dat	90	9 492

初始蚁群数量	weish06数据集				weish14数据集				weish28数据集
	平均时间耗费/s		平均最优解		平均时间耗费/s		平均最优解		平均时间耗费/s		平均最优解
	ACO	ACO-ANDA	ACO	ACO-ANDA	ACO	ACO-ANDA	ACO	ACO-ANDA	ACO	ACO-ANDA	ACO	ACO-ANDA
100	80.58	28.47	5 551.80	5 552.17	171.88	59.08	6 954.00	6 954.00	341.84	182.42	9 488.59	9 490.47
200	158.84	32.05	5 556.13	5 552.33	328.77	88.18	6 954.00	6 954.00	650.54	276.83	9 492.00	9 491.23
300	239.25	47.53	5 556.13	5 551.73	481.04	112.52	6 954.00	6 954.00	942.29	328.89	9 491.15	9 492.00
400	316.53	43.34	5 556.57	5 552.17	625.92	128.71	6 954.00	6 954.00	1 242.01	395.61	9 492.00	9 492.00
500	388.87	58.18	5 557.00	5 553.20	771.63	145.50	6 954.00	6 954.00	1 519.52	442.06	9 492.00	9 491.23
600	461.72	63.33	5 557.00	5 553.80	919.35	159.93	6 954.00	6 954.00	1 811.56	478.90	9 492.00	9 490.47
700	538.15	50.57	5 557.00	5 554.40	1 060.41	173.49	6 954.00	6 954.00	2 072.66	500.47	9 492.00	9 489.70
800	614.27	63.81	5 557.00	5 555.27	1 201.13	175.64	6 954.00	6 954.00	2 367.31	559.72	9 492.00	9 490.47
900	688.90	54.88	5 557.00	5 553.63	1 344.73	201.49	6 954.00	6 954.00	2 649.54	573.03	9 492.00	9 488.93
1 000	760.94	65.35	5 557.00	5 553.30	1 482.58	210.32	6 954.00	6 954.00	2 912.87	616.97	9 492.00	9 489.70

初始蚁群数量	weish06数据集				weish14数据集				weish28数据集
	平均时间耗费/s		平均最优解		平均时间耗费/s		平均最优解		平均时间耗费/s		平均最优解
	ACO	ACO-ANDA	ACO	ACO-ANDA	ACO	ACO-ANDA	ACO	ACO-ANDA	ACO	ACO-ANDA	ACO	ACO-ANDA
100	80.58	28.47	5 551.80	5 552.17	171.88	59.08	6 954.00	6 954.00	341.84	182.42	9 488.59	9 490.47
200	158.84	32.05	5 556.13	5 552.33	328.77	88.18	6 954.00	6 954.00	650.54	276.83	9 492.00	9 491.23
300	239.25	47.53	5 556.13	5 551.73	481.04	112.52	6 954.00	6 954.00	942.29	328.89	9 491.15	9 492.00
400	316.53	43.34	5 556.57	5 552.17	625.92	128.71	6 954.00	6 954.00	1 242.01	395.61	9 492.00	9 492.00
500	388.87	58.18	5 557.00	5 553.20	771.63	145.50	6 954.00	6 954.00	1 519.52	442.06	9 492.00	9 491.23
600	461.72	63.33	5 557.00	5 553.80	919.35	159.93	6 954.00	6 954.00	1 811.56	478.90	9 492.00	9 490.47
700	538.15	50.57	5 557.00	5 554.40	1 060.41	173.49	6 954.00	6 954.00	2 072.66	500.47	9 492.00	9 489.70
800	614.27	63.81	5 557.00	5 555.27	1 201.13	175.64	6 954.00	6 954.00	2 367.31	559.72	9 492.00	9 490.47
900	688.90	54.88	5 557.00	5 553.63	1 344.73	201.49	6 954.00	6 954.00	2 649.54	573.03	9 492.00	9 488.93
1 000	760.94	65.35	5 557.00	5 553.30	1 482.58	210.32	6 954.00	6 954.00	2 912.87	616.97	9 492.00	9 489.70

指标	最大值/%	最小值/%	平均值/%	标准差
时间耗费平均降低比例	92.03	46.63	77.85	0.10
最优解利润平均提升比例	0.02	-0.08	-0.02	<0.01

基于蚁群数量动态调整的改进蚁群优化算法

Improved ant colony optimization algorithm based on ant number dynamic adjustment

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 30

相关文章 15

编辑推荐

Metrics

[1]	肖智豪, 胡志华, 朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2926-2935.
[2]	张新明, 温少晨, 刘尚旺. 差分扰动的堆优化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2519-2527.
[3]	聂方鑫, 王宇嘉, 贾欣. 教与学信息交互粒子群优化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 874-882.
[4]	李开荣, 刘爽, 胡倩倩, 唐亦媛. 基于转角约束的改进蚁群优化算法路径规划[J]. 计算机应用, 2021, 41(9): 2560-2568.
[5]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[6]	樊小毛, 熊红林, 赵淦森. 带约束的清洁排班问题模型及其求解[J]. 计算机应用, 2021, 41(2): 577-582.
[7]	汪虹余, 张彧, 杨恒, 穆楠. 基于蚁群优化算法的弱光图像显著性目标检测[J]. 计算机应用, 2021, 41(10): 2970-2978.
[8]	熊勇, 张加, 余嘉俊, 张本任, 梁萱卓, 朱奇舸. 船舶三维管路智能布局优化算法[J]. 计算机应用, 2020, 40(7): 2164-2170.
[9]	杨艳, 刘生建, 周永权. 贪心二进制狮群优化算法求解多维背包问题[J]. 计算机应用, 2020, 40(5): 1291-1294.
[10]	许英鑫, 孙磊, 赵建成, 郭松辉. 基于蚁群优化算法的虚拟现场可编程门阵列部署策略[J]. 计算机应用, 2020, 40(3): 747-752.
[11]	刘晓明, 沈明玉, 侯整风. 基于Levy飞行的萤火虫模糊聚类算法[J]. 计算机应用, 2019, 39(11): 3257-3262.
[12]	王庆荣, 王瑞峰. 基于改进粒子群算法的配电网重构策略[J]. 计算机应用, 2018, 38(9): 2720-2724.
[13]	陈暄, 徐见炜, 龙丹. 基于蚁群优化蛙跳算法的云计算资源调度算法[J]. 计算机应用, 2018, 38(6): 1670-1674.
[14]	南敬昌, 张云雪, 高明明. 融合BFGS的自适应蜂群算法在谐波平衡分析中的应用[J]. 计算机应用, 2017, 37(5): 1516-1520.
[15]	陈闯, Ryad Chellali, 邢尹. 采用动态权重和概率扰动策略改进的灰狼优化算法[J]. 计算机应用, 2017, 37(12): 3493-3497.