Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (S1): 163-168.DOI: 10.11772/j.issn.1001-9081.2022081155
• Advanced computing • Previous Articles
Wei BAI1(), Cheng WANG2, Cailing WANG1, Xi ZHAN1, Lei ZHANG1
Received:
2022-08-07
Revised:
2022-10-22
Accepted:
2022-11-03
Online:
2023-07-04
Published:
2023-06-30
Contact:
Wei BAI
通讯作者:
白玮
作者简介:
白玮(1983—),男,河北张家口人,讲师,博士,主要研究方向:人工智能、网络智能管理.baiwei_lgdx@126.com基金资助:
CLC Number:
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.
白玮, 王成, 王彩玲, 詹熙, 张磊. 基于蚁群数量动态调整的改进蚁群优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(S1): 163-168.
Add to citation manager EndNote|Ris|BibTeX
URL: http://www.joca.cn/EN/10.11772/j.issn.1001-9081.2022081155
数据文件 | 背包维度 | 已知最优解 |
---|---|---|
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 |
指标 | 最大值/% | 最小值/% | 平均值/% | 标准差 |
---|---|---|---|---|
时间耗费平均降低比例 | 92.03 | 46.63 | 77.85 | 0.10 |
最优解利润平均提升比例 | 0.02 | -0.08 | -0.02 | <0.01 |
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. |
[1] | Xinming ZHANG, Shaochen WEN, Shangwang LIU. Differential disturbed heap-based optimizer [J]. Journal of Computer Applications, 2022, 42(8): 2519-2527. |
[2] | Rongrong DAI, Honghui LI, Xueliang FU. Data center flow scheduling mechanism based on differential evolution and ant colony optimization algorithm [J]. Journal of Computer Applications, 2022, 42(12): 3863-3869. |
[3] | LI Kairong, LIU Shuang, HU Qianqian, TANG Yiyuan. Improved ant colony optimization algorithm for path planning based on turning angle constraint [J]. Journal of Computer Applications, 2021, 41(9): 2560-2568. |
[4] | LI Mengmeng, QIN Wei, LIU Yi, DIAO Xingchun. Hybrid ant colony optimization algorithm with brain storm optimization [J]. Journal of Computer Applications, 2021, 41(8): 2412-2417. |
[5] | FAN Xiaomao, XIONG Honglin, ZHAO Gansen. Cleaning scheduling model with constraints and its solution [J]. Journal of Computer Applications, 2021, 41(2): 577-582. |
[6] | WANG Hongyu, ZHANG Yu, YANG Heng, MU Nan. Salient object detection in weak light images based on ant colony optimization algorithm [J]. Journal of Computer Applications, 2021, 41(10): 2970-2978. |
[7] | XIONG Yong, ZHANG Jia, YU Jiajun, ZHANG Benren, LIANG Xuanzhuo, ZHU Qige. Intelligent layout optimization algorithm for 3D pipelines of ships [J]. Journal of Computer Applications, 2020, 40(7): 2164-2170. |
[8] | XU Yingxin, SUN Lei, ZHAO Jiancheng, GUO Songhui. Virtual field programmable gate array placement strategy based on ant colony optimization algorithm [J]. Journal of Computer Applications, 2020, 40(3): 747-752. |
[9] | LIU Xiaoming, SHEN Mingyu, HOU Zhengfeng. Firefly fuzzy clustering algorithm based on Levy flight [J]. Journal of Computer Applications, 2019, 39(11): 3257-3262. |
[10] | WANG Qingrong, WANG Ruifeng. Reconfiguration strategy of distribution network based on improved particle swarm optimization [J]. Journal of Computer Applications, 2018, 38(9): 2720-2724. |
[11] | CHEN Xuan, XU Jianwei, LONG Dan. Resource scheduling algorithm of cloud computing based on ant colony optimization-shuffled frog leading algorithm [J]. Journal of Computer Applications, 2018, 38(6): 1670-1674. |
[12] | XU Kaibo, LU Haiyan, CHENG Biyun, HUANG Yang. Ant colony optimization algorithm based on improved pheromones double updating and local optimization for solving TSP [J]. Journal of Computer Applications, 2017, 37(6): 1686-1691. |
[13] | BAO Zhenhua, KANG Baosheng, ZHANG Lei, ZHANG Jing. Sketch-based image retrieval method using local geometry moment invariant [J]. Journal of Computer Applications, 2017, 37(6): 1753-1758. |
[14] | NAN Jingchang, ZHANG Yunxue, GAO Mingming. Adaptive bee colony algorithm combined with BFGS algorithm for microwave circuit harmonic balance analysis [J]. Journal of Computer Applications, 2017, 37(5): 1516-1520. |
[15] | CHEN Chuang, Ryad CHELLALI, XING Yin. Improved grey wolf optimizer algorithm using dynamic weighting and probabilistic disturbance strategy [J]. Journal of Computer Applications, 2017, 37(12): 3493-3497. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||