Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (9): 2855-2867.DOI: 10.11772/j.issn.1001-9081.2022081189
• Advanced computing • Previous Articles Next Articles
Bin LI1,2(), Zhibin TANG3
Received:
2022-08-15
Revised:
2022-10-31
Accepted:
2022-11-25
Online:
2023-01-11
Published:
2023-09-10
Contact:
Bin LI
About author:
TANG Zhibin, born in 1998, M. S. candidate. His research interests include intelligent transportation system, swarm intelligence.
Supported by:
通讯作者:
李斌
作者简介:
唐志斌(1998—),男,江西抚州人,硕士研究生,主要研究方向:智能交通系统、群集智能。
基金资助:
CLC Number:
Bin LI, Zhibin TANG. Multiple level binary imperialist competitive algorithm for solving heterogeneous multiple knapsack problem[J]. Journal of Computer Applications, 2023, 43(9): 2855-2867.
李斌, 唐志斌. 面向异构多背包问题的多级二进制帝国竞争算法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2855-2867.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2022081189
算法 | 时间复杂度 | 算法 | 时间复杂度 |
---|---|---|---|
BICA | HGGA | ||
DSCA | OMBO |
Tab. 1 Comparison of maximum time complexity of different algorithms for a single iteration
算法 | 时间复杂度 | 算法 | 时间复杂度 |
---|---|---|---|
BICA | HGGA | ||
DSCA | OMBO |
参数 | 符号 | 值 |
---|---|---|
帝国主义国家(王国)的数量 | 8 | |
殖民地的数量 | 72 | |
殖民地执行TPAS操作的概率 | 0.5 | |
帝国主义国家(王国)循环执行TPAS的次数 | 50 | |
殖民地移动偏角 | ||
JLOA中连续最优解未更新的最大迭代次数 | 20 |
Tab. 2 Parameters of algorithms
参数 | 符号 | 值 |
---|---|---|
帝国主义国家(王国)的数量 | 8 | |
殖民地的数量 | 72 | |
殖民地执行TPAS操作的概率 | 0.5 | |
帝国主义国家(王国)循环执行TPAS的次数 | 50 | |
殖民地移动偏角 | ||
JLOA中连续最优解未更新的最大迭代次数 | 20 |
算例 | 理想值 | BLDE | DBDE | Nbin-DE | BICA |
---|---|---|---|---|---|
KP01 | 1 807 | 1 807 | 1 807 | 1 807 | 1 807 |
KP02 | 3 403 | 3 401 | 3 403 | 3 403 | 3 403 |
KP03 | 5 444 | 5 441 | 5 444 | 5 444 | 5 444 |
KP04 | 9 495 | 9 484 | 9 495 | 9 495 | 9 495 |
KP05 | 18 844 | 18 492 | 18 843 | 18 844 | 18 844 |
KP06 | 659 | 658 | 659 | 659 | 659 |
KP07 | 1 332 | 1 329 | 1 332 | 1 332 | 1 332 |
KP08 | 1 963 | 1 961 | 1 963 | 1 963 | 1 963 |
KP09 | 3 250 | 3 247 | 3 247 | 3 250 | 3 250 |
KP10 | 6 482 | 6 458 | 6 463 | 6 482 | 6 482 |
KP11 | 813 | 812 | 813 | 813 | 813 |
KP12 | 1 631 | 1 626 | 1 631 | 1 631 | 1 631 |
KP13 | 2 433 | 2 426 | 2 433 | 2 433 | 2 433 |
KP14 | 4 078 | 4 051 | 4 070 | 4 078 | 4 078 |
KP15 | 8 228 | 8 073 | 8 109 | 8 228 | 8 228 |
KP16 | 493 | 493 | 493 | 493 | 493 |
KP17 | 1 001 | 1 001 | 1 001 | 1 001 | 1 001 |
KP18 | 1 523 | 1 523 | 1 523 | 1 523 | 1 523 |
KP19 | 2 518 | 2 518 | 2 518 | 2 518 | 2 518 |
KP20 | 5 068 | 5 068 | 5 068 | 5 068 | 5 068 |
Tab. 3 Comparison of test results of BICA and other three meta-heuristic algorithms on test set 1
算例 | 理想值 | BLDE | DBDE | Nbin-DE | BICA |
---|---|---|---|---|---|
KP01 | 1 807 | 1 807 | 1 807 | 1 807 | 1 807 |
KP02 | 3 403 | 3 401 | 3 403 | 3 403 | 3 403 |
KP03 | 5 444 | 5 441 | 5 444 | 5 444 | 5 444 |
KP04 | 9 495 | 9 484 | 9 495 | 9 495 | 9 495 |
KP05 | 18 844 | 18 492 | 18 843 | 18 844 | 18 844 |
KP06 | 659 | 658 | 659 | 659 | 659 |
KP07 | 1 332 | 1 329 | 1 332 | 1 332 | 1 332 |
KP08 | 1 963 | 1 961 | 1 963 | 1 963 | 1 963 |
KP09 | 3 250 | 3 247 | 3 247 | 3 250 | 3 250 |
KP10 | 6 482 | 6 458 | 6 463 | 6 482 | 6 482 |
KP11 | 813 | 812 | 813 | 813 | 813 |
KP12 | 1 631 | 1 626 | 1 631 | 1 631 | 1 631 |
KP13 | 2 433 | 2 426 | 2 433 | 2 433 | 2 433 |
KP14 | 4 078 | 4 051 | 4 070 | 4 078 | 4 078 |
KP15 | 8 228 | 8 073 | 8 109 | 8 228 | 8 228 |
KP16 | 493 | 493 | 493 | 493 | 493 |
KP17 | 1 001 | 1 001 | 1 001 | 1 001 | 1 001 |
KP18 | 1 523 | 1 523 | 1 523 | 1 523 | 1 523 |
KP19 | 2 518 | 2 518 | 2 518 | 2 518 | 2 518 |
KP20 | 5 068 | 5 068 | 5 068 | 5 068 | 5 068 |
算法对比 | Better | Equal | Worse | p值 |
---|---|---|---|---|
BICA vs. BLDE | 14 | 6 | 0 | 0.001 |
BICA vs. DBDE | 5 | 15 | 0 | 0.430 |
BICA vs. Nbin-DE | 0 | 20 | 0 | null |
Tab. 4 Results of non-parametric Wilcoxon rank sum test based on performance of BICA and three comparison algorithms
算法对比 | Better | Equal | Worse | p值 |
---|---|---|---|---|
BICA vs. BLDE | 14 | 6 | 0 | 0.001 |
BICA vs. DBDE | 5 | 15 | 0 | 0.430 |
BICA vs. Nbin-DE | 0 | 20 | 0 | null |
相关性 | 算例 | 物品数量 | 理想值 | 算法 | 最优解 | 最差解 | 均值解 | 中位数解 | 标准差 | 迭代次数 | 成功率/% |
---|---|---|---|---|---|---|---|---|---|---|---|
无 相 关 | KP21 | 800 | 40 686 | BICA-DisEA | 40 686 | 40 685 | 40 686 | 40 686 | 0.370 3 | 1 327.60 | 84 |
BICA-BMV | 40 686 | 40 685 | 40 686 | 40 686 | 0.418 4 | 955.46 | 78 | ||||
KP22 | 1 000 | 50 592 | BICA-DisEA | 50 592 | 50 591 | 50 592 | 50 592 | 0.197 9 | 416.38 | 96 | |
BICA-BMV | 50 592 | 50 592 | 50 592 | 50 592 | 0.000 0 | 14.16 | 100 | ||||
KP23 | 1 200 | 61 846 | BICA-DisEA | 61 846 | 61 845 | 61 845 | 61 845 | 0.504 7 | 1 063.50 | 48 | |
BICA-BMV | 61 846 | 61 846 | 61 846 | 61 846 | 0.000 0 | 12.56 | 100 | ||||
KP24 | 1 500 | 77 033 | BICA-DisEA | 77 033 | 77 033 | 77 033 | 77 033 | 0.000 0 | 222.24 | 100 | |
BICA-BMV | 77 033 | 77 033 | 77 033 | 77 033 | 0.000 0 | 10.80 | 100 | ||||
KP25 | 2 000 | 102 316 | BICA-DisEA | 102 316 | 102 316 | 102 316 | 102 316 | 0.000 0 | 468.24 | 100 | |
BICA-BMV | 102 316 | 102 316 | 102 316 | 102 316 | 0.000 0 | 23.20 | 100 | ||||
弱 相 关 | KP26 | 800 | 35 069 | BICA-DisEA | 35 069 | 35 069 | 35 069 | 35 069 | 0.000 0 | 334.02 | 100 |
BICA-BMV | 35 069 | 35 069 | 35 069 | 35 069 | 0.000 0 | 71.68 | 100 | ||||
KP27 | 1 000 | 43 786 | BICA-DisEA | 43 786 | 43 786 | 43 786 | 43 786 | 0.000 0 | 598.38 | 100 | |
BICA-BMV | 43 786 | 43 786 | 43 786 | 43 786 | 0.000 0 | 67.64 | 100 | ||||
KP28 | 1 200 | 53 553 | BICA-DisEA | 53 553 | 53 552 | 53 552 | 53 552 | 0.503 4 | 1 281.44 | 46 | |
BICA-BMV | 53 553 | 53 553 | 53 553 | 53 553 | 0.000 0 | 299.94 | 100 | ||||
KP29 | 1 500 | 65 710 | BICA-DisEA | 65 709 | 65 709 | 65 709 | 65 709 | 0.000 0 | 667.86 | 0 | |
BICA-BMV | 65 710 | 65 709 | 65 709 | 65 709 | 0.274 1 | 331.12 | 8 | ||||
KP30 | 2 000 | 108 200 | BICA-DisEA | 118 200 | 118 199 | 118 200 | 118 200 | 0.141 4 | 724.60 | 98 | |
BICA-BMV | 118 200 | 118 200 | 118 200 | 118 200 | 0.000 0 | 16.76 | 100 | ||||
强 相 关 | KP31 | 800 | 40 167 | BICA-DisEA | 40 167 | 40 157 | 40 166 | 40 167 | 2.740 4 | 1 146.24 | 92 |
BICA-BMV | 40 167 | 40 167 | 40 167 | 40 167 | 0.000 0 | 1.42 | 100 | ||||
KP32 | 1 000 | 49 443 | BICA-DisEA | 49 442 | 49 432 | 49 432 | 49 432 | 1.414 2 | 175.42 | 0 | |
BICA-BMV | 49 442 | 49 442 | 49 442 | 49 442 | 0.000 0 | 2.46 | 0 | ||||
KP33 | 1 200 | 60 640 | BICA-DisEA | 60 640 | 60 630 | 60 633 | 60 630 | 4.430 8 | 878.58 | 26 | |
BICA-BMV | 60 640 | 60 640 | 60 640 | 60 640 | 0.000 0 | 1.84 | 100 | ||||
KP34 | 1 500 | 74 932 | BICA-DisEA | 74 922 | 74 912 | 74 921 | 74 922 | 3.282 6 | 1 580.20 | 0 | |
BICA-BMV | 74 932 | 74 932 | 74 932 | 74 932 | 0.000 0 | 2.56 | 100 | ||||
KP35 | 2 000 | 99 683 | BICA-DisEA | 99 673 | 99 663 | 99 668 | 99 663 | 5.034 5 | 1 029.82 | 0 | |
BICA-BMV | 99 683 | 99 683 | 99 683 | 99 683 | 0.000 0 | 3.76 | 100 |
Tab. 5 Test results of BICA on test set 2
相关性 | 算例 | 物品数量 | 理想值 | 算法 | 最优解 | 最差解 | 均值解 | 中位数解 | 标准差 | 迭代次数 | 成功率/% |
---|---|---|---|---|---|---|---|---|---|---|---|
无 相 关 | KP21 | 800 | 40 686 | BICA-DisEA | 40 686 | 40 685 | 40 686 | 40 686 | 0.370 3 | 1 327.60 | 84 |
BICA-BMV | 40 686 | 40 685 | 40 686 | 40 686 | 0.418 4 | 955.46 | 78 | ||||
KP22 | 1 000 | 50 592 | BICA-DisEA | 50 592 | 50 591 | 50 592 | 50 592 | 0.197 9 | 416.38 | 96 | |
BICA-BMV | 50 592 | 50 592 | 50 592 | 50 592 | 0.000 0 | 14.16 | 100 | ||||
KP23 | 1 200 | 61 846 | BICA-DisEA | 61 846 | 61 845 | 61 845 | 61 845 | 0.504 7 | 1 063.50 | 48 | |
BICA-BMV | 61 846 | 61 846 | 61 846 | 61 846 | 0.000 0 | 12.56 | 100 | ||||
KP24 | 1 500 | 77 033 | BICA-DisEA | 77 033 | 77 033 | 77 033 | 77 033 | 0.000 0 | 222.24 | 100 | |
BICA-BMV | 77 033 | 77 033 | 77 033 | 77 033 | 0.000 0 | 10.80 | 100 | ||||
KP25 | 2 000 | 102 316 | BICA-DisEA | 102 316 | 102 316 | 102 316 | 102 316 | 0.000 0 | 468.24 | 100 | |
BICA-BMV | 102 316 | 102 316 | 102 316 | 102 316 | 0.000 0 | 23.20 | 100 | ||||
弱 相 关 | KP26 | 800 | 35 069 | BICA-DisEA | 35 069 | 35 069 | 35 069 | 35 069 | 0.000 0 | 334.02 | 100 |
BICA-BMV | 35 069 | 35 069 | 35 069 | 35 069 | 0.000 0 | 71.68 | 100 | ||||
KP27 | 1 000 | 43 786 | BICA-DisEA | 43 786 | 43 786 | 43 786 | 43 786 | 0.000 0 | 598.38 | 100 | |
BICA-BMV | 43 786 | 43 786 | 43 786 | 43 786 | 0.000 0 | 67.64 | 100 | ||||
KP28 | 1 200 | 53 553 | BICA-DisEA | 53 553 | 53 552 | 53 552 | 53 552 | 0.503 4 | 1 281.44 | 46 | |
BICA-BMV | 53 553 | 53 553 | 53 553 | 53 553 | 0.000 0 | 299.94 | 100 | ||||
KP29 | 1 500 | 65 710 | BICA-DisEA | 65 709 | 65 709 | 65 709 | 65 709 | 0.000 0 | 667.86 | 0 | |
BICA-BMV | 65 710 | 65 709 | 65 709 | 65 709 | 0.274 1 | 331.12 | 8 | ||||
KP30 | 2 000 | 108 200 | BICA-DisEA | 118 200 | 118 199 | 118 200 | 118 200 | 0.141 4 | 724.60 | 98 | |
BICA-BMV | 118 200 | 118 200 | 118 200 | 118 200 | 0.000 0 | 16.76 | 100 | ||||
强 相 关 | KP31 | 800 | 40 167 | BICA-DisEA | 40 167 | 40 157 | 40 166 | 40 167 | 2.740 4 | 1 146.24 | 92 |
BICA-BMV | 40 167 | 40 167 | 40 167 | 40 167 | 0.000 0 | 1.42 | 100 | ||||
KP32 | 1 000 | 49 443 | BICA-DisEA | 49 442 | 49 432 | 49 432 | 49 432 | 1.414 2 | 175.42 | 0 | |
BICA-BMV | 49 442 | 49 442 | 49 442 | 49 442 | 0.000 0 | 2.46 | 0 | ||||
KP33 | 1 200 | 60 640 | BICA-DisEA | 60 640 | 60 630 | 60 633 | 60 630 | 4.430 8 | 878.58 | 26 | |
BICA-BMV | 60 640 | 60 640 | 60 640 | 60 640 | 0.000 0 | 1.84 | 100 | ||||
KP34 | 1 500 | 74 932 | BICA-DisEA | 74 922 | 74 912 | 74 921 | 74 922 | 3.282 6 | 1 580.20 | 0 | |
BICA-BMV | 74 932 | 74 932 | 74 932 | 74 932 | 0.000 0 | 2.56 | 100 | ||||
KP35 | 2 000 | 99 683 | BICA-DisEA | 99 673 | 99 663 | 99 668 | 99 663 | 5.034 5 | 1 029.82 | 0 | |
BICA-BMV | 99 683 | 99 683 | 99 683 | 99 683 | 0.000 0 | 3.76 | 100 |
算法 | 无相关算例排名 | 弱相关算例排名 | 强相关算例排名 |
---|---|---|---|
CMBO | 4.97 | 4.33 | 4.20 |
OMBO | 4.90 | 3.93 | 3.13 |
GMBO | 7.00 | 6.07 | 6.73 |
BICA-BMV | 2.37 | 2.70 | 3.07 |
HGGA | 2.77 | 2.97 | 2.67 |
BICA-DisEA | 2.70 | 3.40 | 5.53 |
NM | 3.17 | 3.30 | 2.67 |
Tab. 6 Average ranking of comparison algorithms on large-scale numerical examples
算法 | 无相关算例排名 | 弱相关算例排名 | 强相关算例排名 |
---|---|---|---|
CMBO | 4.97 | 4.33 | 4.20 |
OMBO | 4.90 | 3.93 | 3.13 |
GMBO | 7.00 | 6.07 | 6.73 |
BICA-BMV | 2.37 | 2.70 | 3.07 |
HGGA | 2.77 | 2.97 | 2.67 |
BICA-DisEA | 2.70 | 3.40 | 5.53 |
NM | 3.17 | 3.30 | 2.67 |
算法 | CMBO | OMBO | GMBO | HGGA | NM |
---|---|---|---|---|---|
BICA-BMV | 0.022 | 0.213 | 0.001 | 0.900 | 0.900 |
BICA-DisEA | 0.879 | 0.900 | 0.004 | 0.606 | 0.804 |
Tab. 7 Results of non-parametric Wilcoxon rank sum test based on performance of BICA and 5 comparison algorithms
算法 | CMBO | OMBO | GMBO | HGGA | NM |
---|---|---|---|---|---|
BICA-BMV | 0.022 | 0.213 | 0.001 | 0.900 | 0.900 |
BICA-DisEA | 0.879 | 0.900 | 0.004 | 0.606 | 0.804 |
算例 | HGGA | BICA-BMV | 算例 | HGGA | BICA-BMV |
---|---|---|---|---|---|
KP22 | 15 603 | 14 | KP31 | 4 297 | 1 |
KP24 | 18 507 | 11 | KP33 | 7 281 | 2 |
KP26 | 8 671 | 72 | KP34 | 10 549 | 3 |
KP27 | 12 050 | 68 | KP35 | 17 054 | 4 |
KP30 | 22 551 | 17 |
Tab. 8 Comparison of ierations between HGGA and BICA-BMV
算例 | HGGA | BICA-BMV | 算例 | HGGA | BICA-BMV |
---|---|---|---|---|---|
KP22 | 15 603 | 14 | KP31 | 4 297 | 1 |
KP24 | 18 507 | 11 | KP33 | 7 281 | 2 |
KP26 | 8 671 | 72 | KP34 | 10 549 | 3 |
KP27 | 12 050 | 68 | KP35 | 17 054 | 4 |
KP30 | 22 551 | 17 |
算例 | 算法 | 最优解 | 最差解 | 均值解 | 标准差 |
---|---|---|---|---|---|
KP03 | ICA | 5 444 | 5 443 | 5 443.28 | 0.45 |
BICA-A | 5 444 | 5 443 | 5 443.86 | 0.35 | |
BICA-B | 5 444 | 5 443 | 5 443.80 | 0.40 | |
BICA | 5 444 | 5 443 | 5 443.92 | 0.27 | |
KP21 | ICA | 40 685 | 40 683 | 40 684.86 | 0.40 |
BICA-A | 40 686 | 40 685 | 40 685.38 | 0.49 | |
BICA-B | 40 686 | 40 685 | 40 685.36 | 0.48 | |
BICA | 40 686 | 40 685 | 40 685.78 | 0.41 | |
KP22 | ICA | 50 592 | 50 590 | 50 591.80 | 0.53 |
BICA-A | 50 592 | 50 592 | 50 592.00 | 0.00 | |
BICA-B | 50 592 | 50 592 | 50 592.00 | 0.00 | |
BICA | 50 592 | 50 592 | 50 592.00 | 0.00 | |
KP23 | ICA | 61 846 | 61 844 | 61 845.84 | 0.42 |
BICA-A | 61 846 | 61 846 | 61 846.00 | 0.00 | |
BICA-B | 61 846 | 61 846 | 61 846.00 | 0.00 | |
BICA | 61 846 | 61 846 | 61 846.00 | 0.00 | |
KP24 | ICA | 77 033 | 77 029 | 77 032.64 | 1.00 |
BICA-A | 77 033 | 77 033 | 77 033.00 | 0.00 | |
BICA-B | 77 033 | 77 033 | 77 033.00 | 0.00 | |
BICA | 77 033 | 77 033 | 77 033.00 | 0.00 | |
KP25 | ICA | 102 316 | 102 309 | 102 315.28 | 1.37 |
BICA-A | 102 316 | 102 316 | 102 316.00 | 0.00 | |
BICA-B | 102 316 | 102 316 | 102 316.00 | 0.00 | |
BICA | 102 316 | 102 316 | 102 316.00 | 0.00 | |
KP29 | ICA | 65 709 | 65 705 | 65 708.40 | 0.94 |
BICA-A | 65 710 | 65 709 | 65 709.04 | 0.20 | |
BICA-B | 65 710 | 65 709 | 65 709.08 | 0.27 | |
BICA | 65 710 | 65 709 | 65 709.08 | 0.27 |
Tab. 9 Test results of ICA,BICA-A,BICA-B and BICA
算例 | 算法 | 最优解 | 最差解 | 均值解 | 标准差 |
---|---|---|---|---|---|
KP03 | ICA | 5 444 | 5 443 | 5 443.28 | 0.45 |
BICA-A | 5 444 | 5 443 | 5 443.86 | 0.35 | |
BICA-B | 5 444 | 5 443 | 5 443.80 | 0.40 | |
BICA | 5 444 | 5 443 | 5 443.92 | 0.27 | |
KP21 | ICA | 40 685 | 40 683 | 40 684.86 | 0.40 |
BICA-A | 40 686 | 40 685 | 40 685.38 | 0.49 | |
BICA-B | 40 686 | 40 685 | 40 685.36 | 0.48 | |
BICA | 40 686 | 40 685 | 40 685.78 | 0.41 | |
KP22 | ICA | 50 592 | 50 590 | 50 591.80 | 0.53 |
BICA-A | 50 592 | 50 592 | 50 592.00 | 0.00 | |
BICA-B | 50 592 | 50 592 | 50 592.00 | 0.00 | |
BICA | 50 592 | 50 592 | 50 592.00 | 0.00 | |
KP23 | ICA | 61 846 | 61 844 | 61 845.84 | 0.42 |
BICA-A | 61 846 | 61 846 | 61 846.00 | 0.00 | |
BICA-B | 61 846 | 61 846 | 61 846.00 | 0.00 | |
BICA | 61 846 | 61 846 | 61 846.00 | 0.00 | |
KP24 | ICA | 77 033 | 77 029 | 77 032.64 | 1.00 |
BICA-A | 77 033 | 77 033 | 77 033.00 | 0.00 | |
BICA-B | 77 033 | 77 033 | 77 033.00 | 0.00 | |
BICA | 77 033 | 77 033 | 77 033.00 | 0.00 | |
KP25 | ICA | 102 316 | 102 309 | 102 315.28 | 1.37 |
BICA-A | 102 316 | 102 316 | 102 316.00 | 0.00 | |
BICA-B | 102 316 | 102 316 | 102 316.00 | 0.00 | |
BICA | 102 316 | 102 316 | 102 316.00 | 0.00 | |
KP29 | ICA | 65 709 | 65 705 | 65 708.40 | 0.94 |
BICA-A | 65 710 | 65 709 | 65 709.04 | 0.20 | |
BICA-B | 65 710 | 65 709 | 65 709.08 | 0.27 | |
BICA | 65 710 | 65 709 | 65 709.08 | 0.27 |
算例 | 最优解 | 最差解 | 均值解 | 标准差 | |
---|---|---|---|---|---|
KP03 | 20 | 5 444 | 5 443 | 5 443.92 | 0.27 |
40 | 5 444 | 5 443 | 5 443.82 | 0.38 | |
60 | 5 444 | 5 443 | 5 443.94 | 0.24 | |
80 | 5 444 | 5 443 | 5 443.92 | 0.27 | |
100 | 5 444 | 5 443 | 5 443.94 | 0.24 | |
KP21 | 20 | 40 686 | 40 685 | 40 685.78 | 0.41 |
40 | 40 686 | 40 685 | 40 685.46 | 0.50 | |
60 | 40 686 | 40 685 | 40 685.54 | 0.50 | |
80 | 40 686 | 40 685 | 40 685.62 | 0.49 | |
100 | 40 686 | 40 685 | 40 685.52 | 0.50 | |
KP29 | 20 | 65 710 | 65 709 | 65 709.08 | 0.27 |
40 | 65 709 | 65 709 | 65 709.00 | 0.00 | |
60 | 65 710 | 65 709 | 65 709.06 | 0.24 | |
80 | 65 710 | 65 709 | 65 709.08 | 0.27 | |
100 | 65 710 | 65 709 | 65 709.02 | 0.14 | |
KP32 | 20 | 49 442 | 49 442 | 49 442.00 | 0.00 |
40 | 49 442 | 49 442 | 49 442.00 | 0.00 | |
60 | 49 442 | 49 442 | 49 442.00 | 0.00 | |
80 | 49 442 | 49 442 | 49 442.00 | 0.00 | |
100 | 49 442 | 49 442 | 49 442.00 | 0.00 |
Tab. 10 Test results of BICA-BMV under different u values
算例 | 最优解 | 最差解 | 均值解 | 标准差 | |
---|---|---|---|---|---|
KP03 | 20 | 5 444 | 5 443 | 5 443.92 | 0.27 |
40 | 5 444 | 5 443 | 5 443.82 | 0.38 | |
60 | 5 444 | 5 443 | 5 443.94 | 0.24 | |
80 | 5 444 | 5 443 | 5 443.92 | 0.27 | |
100 | 5 444 | 5 443 | 5 443.94 | 0.24 | |
KP21 | 20 | 40 686 | 40 685 | 40 685.78 | 0.41 |
40 | 40 686 | 40 685 | 40 685.46 | 0.50 | |
60 | 40 686 | 40 685 | 40 685.54 | 0.50 | |
80 | 40 686 | 40 685 | 40 685.62 | 0.49 | |
100 | 40 686 | 40 685 | 40 685.52 | 0.50 | |
KP29 | 20 | 65 710 | 65 709 | 65 709.08 | 0.27 |
40 | 65 709 | 65 709 | 65 709.00 | 0.00 | |
60 | 65 710 | 65 709 | 65 709.06 | 0.24 | |
80 | 65 710 | 65 709 | 65 709.08 | 0.27 | |
100 | 65 710 | 65 709 | 65 709.02 | 0.14 | |
KP32 | 20 | 49 442 | 49 442 | 49 442.00 | 0.00 |
40 | 49 442 | 49 442 | 49 442.00 | 0.00 | |
60 | 49 442 | 49 442 | 49 442.00 | 0.00 | |
80 | 49 442 | 49 442 | 49 442.00 | 0.00 | |
100 | 49 442 | 49 442 | 49 442.00 | 0.00 |
算例 | 参数 | 最优解 | 最差解 | 均值解 | 中位数解 | 标准差 | 迭代次数 | 成功率/% |
---|---|---|---|---|---|---|---|---|
KP36 | 0.00 | 1.00 | 0.48 | 0.00 | 0.50 | 127.72 | 52 | |
0.00、0.00 | 1.00、0.00 | 0.00、0.00 | ||||||
KP37 | 0.00 | 2.00 | 0.96 | 1.00 | 0.28 | 101.76 | 6 | |
0.00、0.00 | 1.00、1.00 | 0.00、1.00 | ||||||
KP38 | 0.00 | 3.00 | 0.94 | 1.00 | 0.47 | 162.14 | 12 | |
0.00、0.00、0.00 | 0.00、2.00、1.00 | 0.00、1.00、0.00 | ||||||
KP39 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 10.58 | 100 | |
0.00、0.00、0.00 | 0.00、0.00、0.00 | 0.00、0.00、0.00 | ||||||
KP40 | 0.00 | 2.00 | 1.46 | 1.00 | 0.57 | 222.32 | 4 | |
0.00、0.00、0.00 0.00 | 1.00、0.00、0.00 1.00 | 0.00、0.00、0.00 1.00 | ||||||
KP41 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 4.10 | 100 | |
0.00、0.00、0.00 0.00 | 0.00、0.00、0.00 0.00 | 0.00、0.00、0.00 0.00 | ||||||
KP42 | 0.00 | 1.00 | 0.02 | 0.00 | 0.14 | 65.36 | 98 | |
0.00、0.00、0.00 0.00、0.00 | 0.00、0.00、0.00 0.00、1.00 | 0.00、0.00、0.00 0.00、0.00 | ||||||
KP43 | 0.00 | 1.00 | 0.34 | 0.00 | 0.47 | 161.70 | 66 | |
0.00、0.00、0.00 0.00、0.00 | 0.00、0.00、1.00 0.00、0.00 | 0.00、0.00、0.00 0.00、0.00 | ||||||
KP44 | 0.00 | 2.00 | 0.94 | 1.00 | 0.31 | 142.46 | 8 | |
0.00、0.00、0.00 0.00、0.00、0.00 | 0.00、0.00、0.00 0.00、2.00、0.00 | 0.00、0.00、0.00 0.00、1.00、0.00 | ||||||
KP45 | 0.00 | 2.00 | 1.38 | 1.00 | 0.52 | 266.62 | 2 | |
0.00、0.00、0.00 0.00、0.00、0.00 | 1.00、0.00、0.00 0.00、1.00、0.00 | 0.00、0.00、0.00 0.00、1.00、0.00 |
Tab. 11 Test results of MLB-ICA on test set 3
算例 | 参数 | 最优解 | 最差解 | 均值解 | 中位数解 | 标准差 | 迭代次数 | 成功率/% |
---|---|---|---|---|---|---|---|---|
KP36 | 0.00 | 1.00 | 0.48 | 0.00 | 0.50 | 127.72 | 52 | |
0.00、0.00 | 1.00、0.00 | 0.00、0.00 | ||||||
KP37 | 0.00 | 2.00 | 0.96 | 1.00 | 0.28 | 101.76 | 6 | |
0.00、0.00 | 1.00、1.00 | 0.00、1.00 | ||||||
KP38 | 0.00 | 3.00 | 0.94 | 1.00 | 0.47 | 162.14 | 12 | |
0.00、0.00、0.00 | 0.00、2.00、1.00 | 0.00、1.00、0.00 | ||||||
KP39 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 10.58 | 100 | |
0.00、0.00、0.00 | 0.00、0.00、0.00 | 0.00、0.00、0.00 | ||||||
KP40 | 0.00 | 2.00 | 1.46 | 1.00 | 0.57 | 222.32 | 4 | |
0.00、0.00、0.00 0.00 | 1.00、0.00、0.00 1.00 | 0.00、0.00、0.00 1.00 | ||||||
KP41 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 4.10 | 100 | |
0.00、0.00、0.00 0.00 | 0.00、0.00、0.00 0.00 | 0.00、0.00、0.00 0.00 | ||||||
KP42 | 0.00 | 1.00 | 0.02 | 0.00 | 0.14 | 65.36 | 98 | |
0.00、0.00、0.00 0.00、0.00 | 0.00、0.00、0.00 0.00、1.00 | 0.00、0.00、0.00 0.00、0.00 | ||||||
KP43 | 0.00 | 1.00 | 0.34 | 0.00 | 0.47 | 161.70 | 66 | |
0.00、0.00、0.00 0.00、0.00 | 0.00、0.00、1.00 0.00、0.00 | 0.00、0.00、0.00 0.00、0.00 | ||||||
KP44 | 0.00 | 2.00 | 0.94 | 1.00 | 0.31 | 142.46 | 8 | |
0.00、0.00、0.00 0.00、0.00、0.00 | 0.00、0.00、0.00 0.00、2.00、0.00 | 0.00、0.00、0.00 0.00、1.00、0.00 | ||||||
KP45 | 0.00 | 2.00 | 1.38 | 1.00 | 0.52 | 266.62 | 2 | |
0.00、0.00、0.00 0.00、0.00、0.00 | 1.00、0.00、0.00 0.00、1.00、0.00 | 0.00、0.00、0.00 0.00、1.00、0.00 |
算例 | MLB-ICA | Gurobi | ||
---|---|---|---|---|
均值解 | 求解时间/s | 均值解 | 求解时间/s | |
Avg | 0.65 | 801.18 | 0.90 | 0.70 |
KP36 | 0.48 | 791.95 | 0.00 | 1.09 |
KP37 | 0.96 | 599.44 | 1.00 | 0.56 |
KP38 | 0.94 | 723.89 | 2.00 | 0.97 |
KP39 | 0.00 | 590.58 | 0.00 | 0.25 |
KP40 | 1.46 | 634.88 | 1.00 | 0.52 |
KP41 | 0.00 | 397.36 | 0.00 | 0.09 |
KP42 | 0.02 | 870.09 | 1.00 | 0.61 |
KP43 | 0.34 | 1 069.07 | 1.00 | 0.66 |
KP44 | 0.94 | 1 016.85 | 1.00 | 0.83 |
KP45 | 1.38 | 1 317.73 | 2.00 | 1.37 |
Tab. 12 Mean solutions and solving time of MLB-ICA and Gurobi on test set 3
算例 | MLB-ICA | Gurobi | ||
---|---|---|---|---|
均值解 | 求解时间/s | 均值解 | 求解时间/s | |
Avg | 0.65 | 801.18 | 0.90 | 0.70 |
KP36 | 0.48 | 791.95 | 0.00 | 1.09 |
KP37 | 0.96 | 599.44 | 1.00 | 0.56 |
KP38 | 0.94 | 723.89 | 2.00 | 0.97 |
KP39 | 0.00 | 590.58 | 0.00 | 0.25 |
KP40 | 1.46 | 634.88 | 1.00 | 0.52 |
KP41 | 0.00 | 397.36 | 0.00 | 0.09 |
KP42 | 0.02 | 870.09 | 1.00 | 0.61 |
KP43 | 0.34 | 1 069.07 | 1.00 | 0.66 |
KP44 | 0.94 | 1 016.85 | 1.00 | 0.83 |
KP45 | 1.38 | 1 317.73 | 2.00 | 1.37 |
1 | DANTZIG G B. Discrete-variable extremum problems[J]. Operations Research, 1957, 5(2): 266-288. 10.1287/opre.5.2.266 |
2 | HAN K H, KIM J H. Genetic quantum algorithm and its application to combinatorial optimization problem[C]// Proceedings of the 2000 Congress on Evolutionary Computation - Volume 2. Piscataway: IEEE, 2000: 1354-1360. |
3 | 杨艳,刘生建,周永权. 贪心二进制狮群优化算法求解多维背包问题[J]. 计算机应用, 2020, 40(5): 1291-1294. |
YANG Y, LIU S J, ZHOU Y Q. Greedy binary lion swarm optimization algorithm for solving multidimensional knapsack problem[J]. Journal of Computer Applications, 2020, 40(5): 1291-1294. | |
4 | 张清勇,钱浩,雷德明. 基于核问题的果蝇优化算法求解多维背包问题[J]. 华中科技大学学报(自然科学版), 2019, 47(2): 92-97. |
ZHANG Q Y, QIAN H, LEI D M. Core-based fruit fly optimization algorithm for solving multidimensional knapsack problem[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2019, 47(2): 92-97. | |
5 | 崔建双,王憧憬. 求解多重背包问题的限速粒子群算法[J]. 计算机工程与应用, 2015, 51(9): 244-247. 10.3778/j.issn.1002-8331.1305-0531 |
CUI J S, WANG C J. Solving multiple knapsack problem with speed limit particle swarm algorithm[J]. Computer Engineering and Applications, 2015, 51(9): 244-247. 10.3778/j.issn.1002-8331.1305-0531 | |
6 | 贺毅朝,王熙照,李文斌,等. 基于遗传算法求解折扣{0-1}背包问题的研究[J]. 计算机学报, 2016, 39(12): 2614-2630. 10.11897/SP.J.1016.2016.02614 |
HE Y C, WANG X Z, LI W B, et al. Research on genetic algorithms for the discounted {0-1} knapsack problem[J]. Chinese Journal of Computers, 2016, 39(12): 2614-2630. 10.11897/SP.J.1016.2016.02614 | |
7 | 杨洋. 改进帕累托算法求解超大规模多选择背包问题[J]. 电子学报, 2020, 48(6): 1205-1212. 10.3969/j.issn.0372-2112.2020.06.023 |
YANG Y. Improved Pareto algorithm for solving very large scale multiple-choice knapsack problem[J]. Acta Electronica Sinica, 2020, 48(6): 1205-1212. 10.3969/j.issn.0372-2112.2020.06.023 | |
8 | 贺毅朝,田海燕,张新禄,等. 基于动态规划法求解动态0-1背包问题[J]. 计算机科学, 2012, 39(7): 237-241. 10.3969/j.issn.1002-137X.2012.07.054 |
HE Y C, TIAN H Y, ZHANG X L, et al. Solving dynamic 0-1 knapsack problems based on dynamic programming algorithm[J]. Computer Science, 2012, 39(7): 237-241. 10.3969/j.issn.1002-137X.2012.07.054 | |
9 | 苗世清,高岳林. 求解0/1背包问题的离散差分进化算法[J]. 小型微型计算机系统, 2009, 30(9): 1828-1830. |
MIAO S Q, GAO Y L. Discrete differential evolution algorithm for solving 0/1 knapsack problem[J]. Journal of Chinese Computer Systems, 2009, 30(9): 1828-1830. | |
10 | 吴聪聪,贺毅朝,赵建立. 求解折扣{0-1}背包问题的新遗传算法[J]. 计算机工程与应用, 2020, 56(7): 57-66. |
WU C C, HE Y C, ZHAO J L. New Genetic algorithm for discounted {0-1} knapsack problem[J]. Computer Engineering and Applications, 2020, 56(7): 57-66. | |
11 | 赵新超,杨婷婷.求解背包问题的更贪心粒子群算法[J].计算机工程与应用, 2009, 45(36): 32-34. 10.3778/j.issn.1002-8331.2009.36.010 |
ZHAO X C, YANG T T. Very greedy particle swarm optimization algorithm for knapsack problem[J]. Computer Engineering and Applications, 2009, 45(36): 32-34. 10.3778/j.issn.1002-8331.2009.36.010 | |
12 | 吴虎胜,张凤鸣,战仁军,等. 求解0-1背包问题的二进制狼群算法[J]. 系统工程与电子技术, 2014, 36(8): 1660-1667. |
WU H S, ZHANG F M, ZHAN R J, et al. A binary wolf pack algorithm for solving 0-1 knapsack problem[J]. Systems Engineering and Electronics, 2014, 36(8): 1660-1667. | |
13 | 刘生建,杨艳,周永权. 求解0-1背包问题的二进制狮群算法[J]. 计算机工程与科学, 2019, 41(11): 2079-2087. 10.3969/j.issn.1007-130X.2019.11.024 |
LIU S J, YANG Y, ZHOU Y Q. A binary lion swarm algorithm for solving 0-1 knapsack problem[J]. Computer Engineering and Science, 2019, 41(11): 2079-2087. 10.3969/j.issn.1007-130X.2019.11.024 | |
14 | LI Y, HE Y C, LIU X J, et al. A novel discrete whale optimization algorithm for solving knapsack problems[J]. Applied Intelligence, 2020, 50(10): 3350-3366. 10.1007/s10489-020-01722-3 |
15 | ATASHPAZ-GARGARI E, LUCAS C. Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition[C]// Proceedings of the 2007 IEEE Congress on Evolutionary Computation. Piscataway: IEEE, 2007: 4661-4667. 10.1109/cec.2007.4425083 |
16 | TRUONG T K, LI K L, XU Y M. Chemical reaction optimization with greedy strategy for the 0-1 knapsack problem[J]. Applied Soft Computing, 2013, 13(4): 1774-1780. 10.1016/j.asoc.2012.11.048 |
17 | 高思齐,邢玉轩,肖侬,等. 求解01背包问题的贪婪蛙跳算法[J]. 计算机科学, 2018, 45(7): 73-77. |
GAO S Q, XING Y X, XIAO N, et al. Greedy frog leaping algorithm for 01 knapsack problem[J]. Computer Science, 2018, 45(7): 73-77. | |
18 | 陈桢,钟一文,林娟. 求解0-1背包问题的混合贪婪遗传算法[J]. 计算机应用, 2021, 41(1): 87-94. |
CHEN Z, ZHONG Y W, LIN J. Hybrid greedy genetic algorithm for solving 0-1 knapsack problem[J]. Journal of Computer Applications, 2021, 41(1): 87-94. | |
19 | 郑健. 离散正弦余弦算法求解大规模0-1背包问题[J]. 山东大学学报(理学版), 2020, 55(11): 87-95. |
ZHENG J. Discrete sine cosine algorithm for solving large-scale 0-1 knapsack problems[J]. Journal of Shandong University (Natural Science), 2020, 55(11): 87-95. | |
20 | 朱颢东,李红婵. 求解0-1背包问题的基于双禁忌对象的TS算法[J]. 微电子学与计算机, 2011, 28(5): 148-151. |
ZHU H D, LI H C. TS to solve 0-1 knapsack problem based on double-tabu objects[J]. Microelectronics and Computer, 2011, 28(5): 148-151. | |
21 | ALI I M, ESSAM D, KASMARIK K. Novel binary differential evolution algorithm for knapsack problems[J]. Information Sciences, 2021, 542: 177-194. 10.1016/j.ins.2020.07.013 |
22 | 李迎,张璟,刘庆,等. 求解大规模多背包问题的高级人工鱼群算法[J]. 系统工程与电子技术, 2018, 40(3): 710-716. 10.3969/j.issn.1001-506X.2018.03.34 |
LI Y, ZHANG J, LIU Q, et al. Advanced artificial fish swarm algorithm for large scale multiple knapsack problem[J]. Systems Engineering and Electronics, 2018, 40(3): 710-716. 10.3969/j.issn.1001-506X.2018.03.34 | |
23 | 贺毅朝,寇应展,陈致明. 求解多选择背包问题的改进差分演化算法[J]. 小型微型计算机系统, 2007, 28(9):1682-1685. 10.3969/j.issn.1000-1220.2007.09.027 |
HE Y C, KOU Y Z, CHEN Z M. A modified differential evolution algorithm for multiple-choice knapsack problem[J]. Journal of Chinese Computer Systems, 2007, 28(9):1682-1685. 10.3969/j.issn.1000-1220.2007.09.027 | |
24 | DELL’AMICO M, DELORME M, IORI M, et al. Mathematical models and decomposition methods for the multiple knapsack problem[J]. European Journal of Operational Research, 2019, 274(3): 886-899. 10.1016/j.ejor.2018.10.043 |
25 | 李斌,李文锋. 基于MAS的集装箱码头物流系统协同生产调度体系[J]. 计算机集成制造系统, 2011, 17(11): 2502-2513. |
LI B, LI W F. Container terminal logistics systems collaborative scheduling based on multi-agent systems[J]. Computer Integrated Manufacturing Systems, 2011, 17(11): 2502-2513. | |
26 | 贺毅朝,王熙照,赵书良,等. 基于编码转换的离散演化算法设计与应用[J]. 软件学报, 2018, 29(9): 2580-2594. |
HE Y C, WANG X Z, ZHAO S L, et al. Design and applications of discrete evolutionary algorithm based on encoding transformation[J]. Journal of Software, 2018, 29(9): 2580-2594. | |
27 | LI B, TANG Z B. Double-assimilation of prosperity and destruction oriented improved imperialist competitive algorithm with computational thinking[C]// Proceedings of the 2022 IEEE Congress on Evolutionary Computation. Piscataway: IEEE, 2022:1-8. 10.1109/cec55065.2022.9870296 |
28 | FENG Y H, WANG G G, DONG J Y, et al. Opposition-based learning monarch butterfly optimization with Gaussian perturbation for large-scale 0-1 knapsack problem[J]. Computers and Electrical Engineering, 2018, 67: 454-468. 10.1016/j.compeleceng.2017.12.014 |
29 | FENG Y H, WANG G G, GAO X Z. A novel hybrid cuckoo search algorithm with global harmony search for 0-1 knapsack problems[J]. International Journal of Computational Intelligence Systems, 2016, 9(6): 1174-1190. 10.1080/18756891.2016.1256577 |
30 | 李斌,李文锋. 基于仿真的优化的粒子群算法参数选取研究[J]. 计算机工程与应用, 2011, 47(33): 30-35. 10.3778/j.issn.1002-8331.2011.33.009 |
LI B, LI W F. Simulation based optimization for parameter selection in PSO[J]. Computer Engineering and Applications, 2011, 47(33): 30-35. 10.3778/j.issn.1002-8331.2011.33.009 | |
31 | CHEN Y, XIE W C, ZOU X F. A binary differential evolution algorithm learning from explored solutions[J]. Neurocomputing, 2015, 149(Pt B): 1038-1047. 10.1016/j.neucom.2014.07.030 |
32 | PENG H, WU Z J, SHAO P, et al. Dichotomous binary differential evolution for knapsack problems[J]. Mathematical Problems in Engineering, 2016, 2016: No.5732489. 10.1155/2016/5732489 |
33 | FENG Y H, YANG J, WU C C, et al. Solving 0-1 knapsack problems by chaotic monarch butterfly optimization algorithm with Gaussian mutation[J]. Memetic Computing, 2018, 10(2): 135-150. 10.1007/s12293-016-0211-4 |
34 | FENG Y H, YU X, WANG G G. A novel monarch butterfly optimization with global position updating operator for large-scale 0-1 knapsack problems[J]. Mathematics, 2019, 7(11): No.1056. 10.3390/math7111056 |
35 | ZHAN S H, WANG L J, ZHANG Z J, et al. Noising methods with hybrid greedy repair operator for 0-1 knapsack problem[J]. Memetic Computing, 2020, 12(1): 37-50. 10.1007/s12293-019-00288-z |
36 | XU S H, WANG Y, LU P C. Improved imperialist competitive algorithm with mutation operator for continuous optimization problems[J]. Neural Computing and Applications, 2017, 28(7): 1667-1682. 10.1007/s00521-015-2138-y |
[1] | ZHANG Guohui, LU Xixi, HU Yifan, SUN Jinghe. Machine breakdown rescheduling of flexible job shop based on improved imperialist competitive algorithm [J]. Journal of Computer Applications, 2021, 41(8): 2242-2248. |
[2] | WANG Guilin, LI Bin. Improved imperialist competitive algorithm inspired by historical facts of Spring and Autumn Period [J]. Journal of Computer Applications, 2021, 41(2): 470-478. |
[3] | CHEN Zhen, ZHONG Yiwen, LIN Juan. Hybrid greedy genetic algorithm for solving 0-1 knapsack problem [J]. Journal of Computer Applications, 2021, 41(1): 87-94. |
[4] | LYU Cong, WEI Kanglin. Cooperative hybrid imperialist competitive algorithm for flexible job-shop scheduling problem [J]. Journal of Computer Applications, 2018, 38(7): 1882-1887. |
[5] | YANG Xiaodong, KANG Yan, LIU Qing, SUN Jinwen. Hybrid imperialist competitive algorithm for solving job-shop scheduling problem [J]. Journal of Computer Applications, 2017, 37(2): 517-522. |
[6] | SONG Xiaoxiao, WANG Jun. Improved artificial bee colony algorithm based on P system for 0-1 knapsack problem [J]. Journal of Computer Applications, 2015, 35(7): 2088-2092. |
[7] | ZHANG Liang XU ChengCheng TIAN Zheng LI Tao. Hardware/software partitioning based on greedy algorithm and simulated annealing algorithm [J]. Journal of Computer Applications, 2013, 33(07): 1898-1902. |
[8] | LIU Lei XIONG Xiaopeng. Least cache value replacement algorithm [J]. Journal of Computer Applications, 2013, 33(04): 1018-1022. |
[9] | LI Ning LIU Jian-qin HE Yi-chao. Solving combinational optimization problems based on harmony search algorithm [J]. Journal of Computer Applications, 2012, 32(04): 1041-1044. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||