Introduction
Preliminaries
Problem description
Mathematical description
Overview of bat algorithm (BA) and rough set theory (RST)
Real behavior algorithm
Bat algorithm (BA)
Velocity and position
Loudness and pulse emission
The implementation steps of bat algorithm
Rough set theory (RST)
-
\(\text {POS}_B (X)={\underline{B}}X\Rightarrow \) certainly member of X
-
\(\text {NEG}_B (X)=U-\bar{{B}}X\Rightarrow \) certainly nonmember of X
-
\(BN_B (X)={\bar{B}}X-{\underline{B}}X\Rightarrow \) possibly the member of X.
The proposed algorithm (IBBA-RSS)
Binary position scheme
Binary velocity scheme
Evaluation
Rough set scheme (RSS)
Problem | Parameter | Dimension | Optimum |
---|---|---|---|
KP\(_{1}\)
|
\(w=(95,4,60,32,23,72,80,62,65,46),\)
\(C=269,\)
\(p=(55,10,47,5,4,50,8,61,85,87)\)
| 10 | 295 |
KP\(_{2}\)
|
\(w= (92,\) 4, 43, 83, 84, 68, 92, 82, 6, 44, 32, 18, 56, 83, 25, 96, 70, 48, 14, 58), \(C = 878,\) \(p = (44,\) 46, 90, 72, 91, 40, 75, 35, 8, 54, 78, 40, 77, 15, 61, 17, 75, 29, 75, 63) | 20 | 1024 |
KP\(_{3}\)
|
\(w=(6,5,9,7),\)
\(C =20,\)
\(p=(9,11,13,15)\)
| 4 | 35 |
KP\(_{4}\)
|
\(w=(2,4,6,7),\)
\(C =11,\)
\(p=(6,10,12,13)\)
| 4 | 23 |
KP\(_{5}\)
|
\(w= (56.358531,\) 80.874050, 47.987304, 89.596240, 74.660482, 85.894345, 51.353496, 1.498459, 36.445204, 16.589862, 44.569231, 0.466933, 37.788018, 57.118442, 60.716575), \(C = 375,\) \(p = (0.125126,\) 19.330424, 58.500931, 35.029145, 82.284005, 17.410810, 71.050142, 30.399487, 9.140294, 14.731285, 98.852504, 11.908322, 0.891140, 53.166295, 60.176397) | 15 | 481.07 |
KP\(_{6}\)
|
\(w=(30,25,20,18,17,11,5,2,1,1),\)
\(C =60,\)
\(p=(20,18,17,15,15,10,5,3,1,1)\)
| 10 | 52 |
KP\(_{7}\)
|
\(w=(31,10,20,19,4,3,6),\)
\(C =50,\)
\(p=(70,20,39,37,7,5,10)\)
| 7 | 107 |
KP\(_{8}\)
|
\(w=(983, 982,\) 981, 980, 979, 978, 488, 976, 972, 486, 486, 972, 972, 485, 485, 969, 966, 483, 964, 963, 961, 958, 959), \(C = 10{,}000,\) \(p = (981, 980,\) 979, 978, 977, 976, 487, 974, 970, 485, 485, 970, 970, 484, 484, 976, 974, 482, 962, 961, 959, 958, 857) | 23 | 9767 |
KP\(_{9}\)
|
\(w=(15,20,17,8,31),\)
\(C=80,\)
\(p=(33,24,36,37,12)\)
| 5 | 130 |
KP\(_{10}\)
|
\(w= (84, 83,\) 43, 4, 44, 6, 82, 92, 25, 83, 56, 18, 58, 14, 48, 70, 96, 32, 68, 92), \(C = 879,\) \(p = (91, 72, 90,\) 46, 55, 8, 35, 75, 61, 15, 77, 40, 63, 75, 29, 75, 17, 78, 40, 44) | 20 | 1025 |
KP\(_1\)
| KP\(_2\)
| KP\(_3\)
| KP\(_4\)
| KP\(_5\)
| KP\(_6\)
| KP\(_7\)
| KP\(_8\)
| KP\(_9\)
| KP\(_{10}\)
| TSR | |
---|---|---|---|---|---|---|---|---|---|---|---|
BHS | |||||||||||
SR | 0.78 | 0.92 | 0.98 | 1 | 0.96 | 0.9 | 0.56 | 0.82 | 0.98 | 0.94 | 1 |
Best | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Median | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Worst | 293 | 1018 | 28 | 23 | 437.94 | 50 | 93 | 9762 | 118 | 1019 | |
Mean | 294.58 | 1023.52 | 34.86 | 23 | 479.55 | 51.84 | 104.34 | 9766.34 | 129.76 | 1024.64 | |
Std | 0.81 | 1.64 | 0.99 | 0 | 7.59 | 0.51 | 4.5 | 1.52 | 1.7 | 1.44 | |
DBHS | |||||||||||
SR | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 10 |
Best | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Median | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Worst | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Mean | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Std | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
NGHS1 | |||||||||||
SR | 1 | 1 | 1 | 1 | 1 | 0.96 | 1 | 0.94 | 1 | 1 | 8 |
Best | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Median | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Worst | 295 | 1024 | 35 | 23 | 481.07 | 51 | 107 | 9765 | 130 | 1025 | |
Mean | 295 | 1024 | 35 | 23 | 481.07 | 51.96 | 107 | 9766.88 | 130 | 1025 | |
Std | 0 | 0 | 0 | 0 | 0 | 0.2 | 0 | 0.48 | 0 | 0 | |
ABHS | |||||||||||
SR | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 10 |
Best | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Median | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Worst | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Mean | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Std | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
ABHS1 | |||||||||||
SR | 0.86 | 0.96 | 1 | 0.98 | 0.98 | 0.84 | 0.48 | 0.82 | 1 | 1 | 3 |
Best | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Median | 295 | 1024 | 35 | 23 | 481.07 | 52 | 105 | 9767 | 130 | 1025 | |
Worst | 293 | 1018 | 35 | 22 | 475.48 | 49 | 96 | 9762 | 130 | 1025 | |
Mean | 294.72 | 1023.76 | 35 | 22.98 | 480.96 | 51.68 | 105.18 | 9766.44 | 130 | 1025 | |
Std | 0.7 | 1.19 | 0 | 0.14 | 0.8 | 0.82 | 2.95 | 1.33 | 0 | 0 | |
SBHS | |||||||||||
SR | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 10 |
Best | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Median | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Worst | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Mean | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Std | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
IBBA-RSS | |||||||||||
SR | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 10 |
Best |
295
|
1024
|
35
|
23
|
481.07
|
52
|
107
|
9767
|
130
|
1025
| |
Median | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Worst | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Mean | 295 | 1024 | 35 | 23 | 481.07 | 52 | 107 | 9767 | 130 | 1025 | |
Std | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Problem | Parameter | Dimension | Optimum |
---|---|---|---|
KP\(_{11}\)
|
\(w=[46,\) 17, 35, 1, 26, 17, 17, 48, 38, 17, 32, 21, 29, 48, 31, 8, 42, 37, 6, 9, 15, 22, 27, 14, 42, 40, 14, 31, 6, 34], \(p=[57,\) 64, 50, 6, 52, 6, 85, 60, 70, 65, 63, 96, 18, 48, 85, 50, 77, 18, 70, 92, 17, 43, 5, 23, 67, 88, 35, 3, 91, 48], \(C=577\)
| 30 | 1437 |
KP\(_{12}\)
|
\(w=[7,\) 4, 36, 47, 6, 33, 8, 35, 32, 3, 40, 50, 22, 18, 3, 12, 30, 31,13, 33, 4, 48, 5, 17, 33, 26, 27, 19, 39, 15, 33, 47, 17, 41, 40], \(p=[35,\) 67, 30, 69, 40, 40, 21, 73, 82, 93, 52, 20, 61, 20, 42, 86, 43, 93, 38, 70, 59, 11, 42, 93, 6, 39, 25, 23, 36, 93, 51, 81, 36, 46, 96], \( C= 655\)
| 35 | 1689 |
KP\(_{13}\)
|
\(w=[28,\) 23, 35, 38, 20, 29, 11, 48, 26, 14, 12, 48, 35, 36, 33, 39, 30, 26, 44, 20, 13, 15, 46, 36, 43, 19, 32, 2, 47, 24, 26, 39, 17, 32, 17, 16, 33, 22, 6, 12], \(p=[13,\) 16, 42, 69, 66, 68, 1, 13, 77, 85, 75, 95, 92, 23, 51, 79, 53, 62, 56, 74, 7, 50, 23, 34, 56, 75, 42, 51, 13, 22, 30, 45, 25, 27, 90, 59, 94, 62, 26, 11], \(C=819\)
| 40 | 1816 |
KP\(_{14}\)
|
\(w=[18,\) 12, 38, 12, 23, 13, 18, 46, 1, 7, 20, 43, 11, 47, 49, 19, 50, 7, 39, 29, 32, 25, 12, 8, 32, 41, 34, 24, 48, 30, 12, 35, 17, 38, 50, 14, 47, 35, 5, 13, 47, 24, 45, 39, 1], \(p=[98,\) 70, 66, 33, 2, 58, 4, 27, 20, 45, 77, 63, 32, 30, 8, 18, 73, 9, 92, 43, 8, 58, 84, 35, 78, 71, 60, 38, 40, 43, 43, 22, 50, 4, 57, 5, 88, 87, 34, 98, 96, 99, 16, 1, 25], \( C=907\)
| 45 | 2020 |
KP\(_{15}\)
|
\(w=[15,\) 40, 22, 28, 50, 35, 49, 5, 45, 3, 7, 32, 19, 16, 40, 16, 31, 24, 15, 42, 29, 4, 14, 9, 29, 11, 25, 37, 48, 39, 5, 47, 49, 31, 48, 17, 46, 1, 25, 8, 16, 9, 30, 33, 18, 3, 3, 3, 4,1], \(p=[78,\) 69, 87, 59, 63, 12, 22, 4, 45, 33, 29, 50, 19, 94, 95, 60, 1, 91, 69, 8, 100, 84, 100, 32, 81, 47, 59, 48, 56, 18, 59, 16, 45, 54, 47, 98, 75, 20, 4, 19, 58, 63, 37, 64, 90, 26, 29, 13, 53, 83], \(C=882\)
| 50 | 2440 |
KP\(_{16}\)
|
\(w=[27,\) 15, 46, 5, 40, 9, 36, 12, 11, 11, 49, 20, 32, 3, 12, 44, 24, 1, 24, 42, 44, 16, 12, 42, 22, 26, 10, 8, 46, 50, 20, 42, 48, 45, 43, 35, 9, 12, 22, 2, 14, 50, 16, 29, 31, 46, 20, 35, 11, 4, 32, 35, 15, 29, 16], \(p=[98,\) 74, 76, 4, 12, 27, 90, 98, 100, 35, 30, 19, 75, 72, 19, 44, 5, 66, 79, 87, 79, 44, 35, 6, 82, 11, 1, 28, 95, 68, 39, 86, 68, 61, 44, 97, 83, 2, 15, 49, 59, 30, 44, 40, 14, 96, 37, 84, 5, 43, 8, 32, 95, 86, 18], \(C=1050\)
| 55 | 2643 |
KP\(_{17}\)
|
\(w=[7,\) 13, 47, 33, 38, 41, 3, 21, 37, 7, 32, 13, 42, 42, 23, 20, 49, 1, 20, 25, 31, 4, 8, 33, 11, 6, 3, 9, 26, 44, 39, 7, 4, 34, 25, 25, 16, 17, 46, 23, 38, 10, 5, 11, 28, 34, 47, 3, 9, 22, 17, 5, 41, 20, 33, 29, 1, 33, 16, 14], \(p=[81,\) 37, 70, 64, 97, 21, 60, 9, 55, 85, 5, 33, 71, 87, 51, 100, 43, 27, 48, 17, 16,27, 76, 61, 97, 78, 58, 46, 29, 76, 10, 11, 74, 36, 59, 30, 72, 37, 72, 100, 9, 47, 10, 73, 92, 9, 52, 56, 69, 30, 61, 20, 66, 70, 46, 16, 43, 60, 33, 84], \(C=1006\)
| 60 | 2917 |
KP\(_{18}\)
|
\(w=[47,\) 27, 24, 27, 17, 17, 50, 24, 38, 34, 40, 14, 15, 36, 10, 42, 9, 48, 37, 7, 43, 47, 29, 20, 23, 36, 14, 2, 48, 50, 39, 50, 25, 7, 24, 38, 34, 44, 38, 31, 14, 17, 42, 20, 5, 44, 22, 9, 1, 33, 19, 19, 23, 26, 16, 24, 1, 9, 16, 38, 30, 36, 41, 43, 6], \(p=[47,\) 63, 81, 57, 3, 80, 28, 83, 69, 61, 39, 7, 100, 67, 23, 10, 25, 91, 22, 48, 91, 20, 45, 62, 60, 67, 27, 43, 80, 94, 47, 31, 44, 31, 28, 14, 17, 50, 9, 93, 15, 17, 72, 68, 36, 10, 1, 38, 79, 45, 10, 81, 66, 46, 54, 53, 63, 65, 20, 81, 20, 42, 24, 28, 1], \(C=1319\)
| 65 | 2814 |
KP\(_{19}\)
|
\(w=[4,\) 16, 16, 2, 9, 44, 33, 43, 14, 45, 11, 49, 21, 12, 41, 19, 26, 38, 42, 20, 5, 14, 40, 47, 29, 47, 30, 50, 39, 10, 26, 33, 44, 31, 50, 7, 15, 24, 7, 12, 10, 34, 17, 40, 28, 12, 35, 3, 29, 50, 19, 28, 47, 13, 42, 9, 44, 14, 43, 41, 10, 49, 13, 39, 41, 25, 46, 6, 7, 43], \(p=[66,\) 76, 71, 61, 4, 20, 34, 65, 22, 8, 99, 21, 99, 62, 25, 52, 72, 26, 12, 55, 22, 32, 98, 31, 95, 42, 2, 32, 16, 100, 46, 55, 27, 89, 11, 83, 43, 93, 53, 88, 36, 41, 60, 92, 14, 5, 41, 60, 92, 30, 55, 79, 33, 10, 45, 3, 68, 12, 20, 54, 63, 38, 61, 85, 71, 40, 58, 25, 73, 35], \(C=1426\)
| 70 | 3221 |
KP\(_{20}\)
|
\(w=[24,\) 45, 15, 40, 9, 37, 13, 5, 43, 35, 48, 50, 27, 46, 24, 45, 2, 7, 38, 20, 20, 31, 2, 20, 3, 35, 27, 4, 21, 22, 33, 11, 5, 24, 37, 31, 46, 13, 12, 12, 41, 36, 44, 36, 34, 22, 29, 50, 48, 17, 8, 21, 28, 2, 44, 45, 25, 11, 37, 35, 24, 9, 40, 45, 8, 47, 1, 22, 1, 12, 36, 35, 14, 17, 5], \(p=[2,\) 73, 82, 12, 49, 35, 78, 29, 83, 18, 87, 93, 20, 6, 55, 1, 83, 91, 71, 25, 59, 94, 90, 61, 80, 84, 57, 1, 26, 44, 44, 88, 7, 34, 18, 25, 73, 29, 24, 14, 23, 82, 38, 67, 94, 43, 61, 97, 37, 67, 32, 89, 30, 30, 91, 50, 21, 3, 18, 31, 97, 79, 68, 85, 43, 71, 49, 83, 44, 86, 1, 100, 28, 4,16], \( C=1433\)
| 75 | 3614 |
Fun | Algorithm | Obtained solution | Best | Mean | Worst | Std |
---|---|---|---|---|---|---|
KP\(_{11}\)
| IBBA-RSS | 111110111111001110110101111011 |
1437
| 1437 | 1437 | 0 |
BBA | 111110111111001110110101111011 | 1437 | 1437 | 1437 | 0 | |
CI | NA | 1437 | 1418 | 1398 | 11.79 | |
B&B | NA | 1437 | NA | NA | NA | |
KP\(_{12}\)
| IBBA-RSS | 11011111111010111111101101110111111 |
1689
| 1689 | 1689 | 0 |
BBA | 11011111111010111111101101110111111 | 1689 | 1689 | 1689 | 0 | |
CI | NA | 1689 | 1686.5 | 1679 | 3.8188 | |
B&B | NA | 1689 | NA | NA | NA | |
KP\(_{13}\)
| IBBA-RSS | 0011110011111011111101011111001111111111 |
1821
| 1821 | 1821 | 0 |
BBA | 0011110011111011111101011111001111111111 | 1821 | 1821 | 1821 | 0 | |
CI | NA | 1816 | 1807.5 | 1791 | 9.604 | |
B&B | NA | 1821 | NA | NA | NA | |
KP\(_{14}\)
| IBBA-RSS | 11110100111111011111011111111111101011111 1001 |
2033
| 2033 | 2033 | 0 |
BBA | 11110100111111011111011111111111101011111 1001 | 2033 | 2030.3333 | 2016 | 6.0988 | |
CI | NA | 2020 | 2017 | 2007 | 4.749 | |
B&B | NA | 2033 | NA | NA | NA | |
KP\(_{15}\)
| IBBA-RSS | 11111001111111110110111111111010111111011101111111 |
2448
| 2448 | 2448 | 0 |
BBA | 11111001111111110110111111111010011111011111111111 | 2440 | 2439.633333 | 2435 | 1.1591 | |
CI | NA | 2440 | 2436.166 | 2421 | 6.841 | |
B&B | NA | 2440 | NA | NA | NA | |
KP\(_{16}\)
| IBBA-RSS | 1110011111011111011111101001111111111001101101110101111 |
2643
| 2642.6000 | 2632 | 2.0103 |
BBA | 1111011111011111011111101001111111111001101101111101110 | 2642 | 2640.4000 | 2614 | 5.5930 | |
CI | NA | 2643 | 2605 | 2581 | 22.018 | |
B&B | NA | 2440 | NA | NA | NA | |
KP\(_{17}\)
| IBBA-RSS | 1111101011011111011001111111110111111111011 11011111111101111 |
2917
| 2917 | 2917 | 0 |
BBA | 111110101101111101100111111111011111111101111011111111101111 | 2917 | 2915 | 2893 | 6.1923 | |
CI | NA | 2917 | 2915 | 2905 | 4.472 | |
B&B | NA | 2917 | NA | NA | NA | |
KP\(_{18}\)
| IBBA-RSS | 11110101111011101111101111111111111001011111100111011111111101010 |
2818
| 2817.6333 | 2814 | 1.0661 |
BBA | 11111101111011101101101111111111111001011111100111111111111101010 | 2809 | 2808.3333 | 2802 | 1.881549 | |
CI | NA | 2814 | 2773.66 | 2716, | 18.273 | |
B&B | NA | 2818 | NA | NA | NA | |
KP\(_{19}\)
| IBBA-RSS | 1111101110101101110111111101011101011111111100111111111011011111111111 |
3223
| 3222.6000 | 3219 | 1.1017 |
BBA | 1111101110101101100111111101011111011111111111111011111011011111111111 | 3213 | 3212.9000 | 3209 | 1.4936 | |
CI | NA | 3221 | 3216 | 3211 | 4.3589 | |
B&B | NA | 3223 | NA | NA | NA | |
KP\(_{20}\)
| IBBA-RSS | 011011111011001011111111111011111100111101111111011111111001111111111101101 |
3614
| 3613.2333 | 3605 | 2.4166 |
BBA | 011011111011001011111111111011111100111101111111111111110100111111111101101 | 3602 | 3600.3793 | 3588 | 4.1611 | |
CI | NA | 3614 | 3603.8 | 3591 | 8.035 | |
B&B | NA | 3614 | NA | NA | NA |
IBBA-RSS | BBA | SBHS | IHS | GHS | SAHS | EHS | NGHS | NDHS | |
---|---|---|---|---|---|---|---|---|---|
KP\(_{21}\)
| |||||||||
Best |
63.2149
| 62.3101 | 62.08 | 61.99 | 61.81 | 62.02 | 61.78 | 61.82 | 61.61 |
Median | 63.2149 | 62.3101 | 62.04 | 61.81 | 61.3 | 61.86 | 61.25 | 61.5 | 61.02 |
Worst | 62.0222 | 61.1074 | 61.97 | 61.23 | 60.94 | 61.65 | 60.63 | 61.11 | 59.59 |
Mean | 63.1545 | 62.2322 | 62.04 | 61.77 | 61.29 | 61.85 | 61.22 | 61.5 | 60.86 |
Std | 0.2418 | 0.2964 | 0.03 | 0.15 | 0.19 | 0.11 | 0.3 | 0.2 | 0.45 |
Best |
131.1273
| 129.7232 | 129.44 | 128.89 | 127.09 | 127.99 | 128.43 | 128.34 | 127.82 |
Median | 131.1273 | 129.7232 | 129.38 | 128.42 | 125.7 | 127.21 | 127.88 | 127.7 | 127 |
KP\(_{22}\)
| |||||||||
Worst | 129.2422 | 128.3646 | 129.27 | 127.61 | 124.47 | 126.39 | 127.08 | 126.87 | 125.72 |
Mean | 130.9917 | 129.6492 | 129.37 | 128.4 | 125.69 | 127.16 | 127.81 | 127.66 | 126.86 |
Std | 0.4352 | 0.2890 | 0.04 | 0.31 | 0.61 | 0.41 | 0.36 | 0.42 | 0.54 |
Best |
195.0331
| 192.5467 | 192.02 | 189.94 | 187.28 | 188.15 | 190.96 | 190.18 | 189.97 |
Median | 195.0331 | 192.5467 | 192.02 | 189.35 | 185.77 | 187.36 | 190.43 | 189.31 | 189.04 |
KP\(_{23}\)
| |||||||||
Worst | 193.2210 | 192.4450 | 191.85 | 188.27 | 184.16 | 186.05 | 189.27 | 187.9 | 187.85 |
Mean | 194.9348 | 192.5431 | 192.01 | 189.14 | 185.77 | 187.27 | 190.28 | 189.23 | 188.97 |
Std | 0.3587 | 0.0186 | 0.03 | 0.51 | 0.72 | 0.53 | 0.43 | 0.58 | 0.61 |
Best |
316.3039
| 312.5521 | 314.23 | 306.89 | 301.03 | 302.92 | 312.04 | 310.16 | 309.49 |
Median | 316.1211 | 312.5521 | 314.2 | 305.11 | 299.78 | 300.72 | 311.32 | 308.28 | 308.28 |
KP\(_{24}\)
| |||||||||
Worst | 315.8936 | 312.2119 | 314.1 | 303.55 | 297.25 | 299.14 | 310.29 | 305.67 | 305.94 |
Mean | 316.1044 | 312.5294 | 314.19 | 305.1 | 299.6 | 300.79 | 311.25 | 308.33 | 308.07 |
Std | 0.0789 | 0.0863 | 0.03 | 0.92 | 0.91 | 1.03 | 0.49 | 1.06 | 0.93 |
Best |
448.8721
| 446.9679 | 448.65 | 434.04 | 429.02 | 431.63 | 444.91 | 442.32 | 442.85 |
Median | 448.8721 | 446.9679 | 448.63 | 431.74 | 425.75 | 428.99 | 443.64 | 441.13 | 439.39 |
KP\(_{25}\)
| |||||||||
Worst | 447.2503 | 446.2406 | 448.46 | 429.63 | 423.35 | 427.08 | 442.13 | 436.45 | 436.01 |
Mean | 448.7179 | 446.9049 | 448.6 | 431.73 | 425.68 | 428.93 | 443.53 | 440.83 | 439.43 |
Std | 0.4232 | 0.1947 | 0.05 | 1.13 | 1.28 | 1.23 | 0.64 | 1.23 | 1.37 |
Best |
639.4001
| 635.0750 | 638.14 | 605.88 | 602.29 | 606.5 | 629.29 | 626.77 | 621.15 |
Median | 639.4001 | 635.0750 | 638.08 | 603.42 | 599.07 | 601.31 | 626.62 | 623.9 | 618.41 |
KP\(_{26}\)
| |||||||||
Worst | 639.0579 | 632.6213 | 638 | 599.53 | 594.34 | 597.84 | 624.99 | 619.15 | 614.86 |
Mean | 639.3884 | 634.8336 | 638.09 | 603.26 | 598.83 | 601.78 | 626.76 | 623.87 | 618.09 |
Std | 0.0624 | 0.7367 | 0.04 | 1.56 | 1.9 | 2.34 | 1.13 | 1.37 | 1.48 |
Best |
767.0228
| 764.3262 | 763.81 | 722.52 | 721.23 | 724.4 | 751.73 | 750.67 | 744.72 |
Median | 767.0228 | 764.3262 | 763.72 | 718.39 | 716.92 | 721.53 | 749.16 | 747.88 | 739.88 |
KP\(_{27}\)
| |||||||||
Worst | 766.9989 | 764.1197 | 763.39 | 714.39 | 713.17 | 716.46 | 746.38 | 745.05 | 735.02 |
Mean | 767.0219 | 764.3177 | 763.71 | 718.29 | 716.69 | 721.38 | 749.15 | 747.66 | 739.76 |
Std | 0.0043 | 0.0383 | 0.08 | 1.98 | 1.84 | 1.95 | 1.33 | 1.41 | 2.14 |
Best |
966.0450
| 962.6650 | 964.91 | 902.36 | 903.31 | 908.1 | 944.09 | 945.2 | 932.32 |
Median | 966.0450 | 962.6650 | 964.86 | 897.78 | 901.26 | 904.01 | 940.76 | 942.09 | 926.48 |
KP\(_{28}\)
| |||||||||
Worst | 965.5550 | 962.6020 | 964.7 | 891.26 | 895.58 | 899.04 | 937.07 | 938.31 | 923.45 |
Mean | 966.0164 | 962.661 | 964.85 | 897.62 | 900.63 | 903.83 | 940.72 | 941.97 | 926.62 |
Std | 0.1099 | 0.0152 | 0.06 | 2.68 | 1.77 | 2.54 | 1.68 | 1.7 | 2 |
Best |
1157.2337
| 1153.0032 | 1155.65 | 1073.93 | 1080.1 | 1086.57 | 1128.25 | 1133.44 | 1110.98 |
Median | 1157.2337 | 1153.0032 | 1155.58 | 1066.02 | 1076.49 | 1080.71 | 1122.29 | 1128.77 | 1106.13 |
KP\(_{29}\)
| |||||||||
Worst | 1155.6659 | 1152.8484 | 1155.35 | 1058.6 | 1072.65 | 1074.16 | 1119.25 | 1125.69 | 1099.5 |
Mean | 1157.1784 | 1152.9942 | 1155.57 | 1066.1 | 1076.58 | 1080.58 | 1122.61 | 1129.02 | 1105.73 |
Std | 0.2861 | 0.0344 | 0.08 | 3.29 | 2.02 | 2.83 | 2.33 | 1.94 | 2.86 |
Best |
1289.5521
| 1284.7260 | 1283.92 | 1182.55 | 1198.69 | 1202.7 | 1247.95 | 1257.45 | 1229.87 |
Median | 1289.5521 | 1284.7260 | 1283.81 | 1177.52 | 1192.03 | 1196.75 | 1243.8 | 1252.9 | 1223.25 |
KP\(_{30}\)
| |||||||||
Worst | 1285.6171 | 1283.6650 | 1283.26 | 1172.02 | 1188.27 | 1190.05 | 1238.26 | 1249.74 | 1218.14 |
Mean | 1289.4157 | 1284.6381 | 1283.79 | 1177.59 | 1192.71 | 1196.71 | 1243.07 | 1252.86 | 1223.5 |
Std | 0.7177 | 0.2760 | 0.12 | 2.34 | 2.66 | 3.34 | 2.55 | 1.83 | 2.94 |
Best |
1668.4021
| 1661.2185 | 1653.72 | 1500.31 | 1534.74 | 1536.25 | 1592.68 | 1615.64 | 1570.24 |
Median | 1668.4021 | 1661.2185 | 1653.66 | 1492.52 | 1526.73 | 1528.71 | 1587.53 | 1611.05 | 1561.41 |
KP\(_{31}\)
| |||||||||
Worst | 1661.4592 | 1651.3906 | 1653.43 | 1481.67 | 1521.56 | 1521.65 | 1582.16 | 1604.28 | 1553.61 |
Mean | 1668.0197 | 1660.5869 | 1653.64 | 1492.57 | 1527.06 | 1528.66 | 1587.06 | 1610.5 | 1561.24 |
Std | 1.3841 | 2.3466 | 0.06 | 4.25 | 3.2 | 3.33 | 2.93 | 2.71 | 3.68 |
Best |
1927.8000
| 1890.3517 | 1917.49 | 1731.78 | 1777.72 | 1785.64 | 1843.7 | 1877.6 | 1818.63 |
Median | 1921.7966 | 1890.3517 | 1917.44 | 1724.57 | 1771.48 | 1779.68 | 1838.22 | 1872.5 | 1809.24 |
KP\(_{32}\)
| |||||||||
Worst | 1917.3188 | 1884.0266 | 1917.23 | 1714.03 | 1767.32 | 1769.75 | 1830.47 | 1868.31 | 1800.95 |
Mean | 1921.3983 | 1890.07 | 1917.42 | 1724.16 | 1771.88 | 1779.06 | 1838.15 | 1872.43 | 1809.34 |
Std | 1.1391 | 1.323 | 0.06 | 3.81 | 2.78 | 4 | 3.09 | 2.26 | 4.06 |
Injective updating based on feasibility rule
Experimental results and analysis
Low-dimensional 0–1 knapsack problems
Medium size 0–1 knapsack problems
Large-scale 0–1 knapsack problems
PSFHS | BHS | DBHS | NGHS1 | ABHS | ABHS1 | ITHS | V-BBA | |
---|---|---|---|---|---|---|---|---|
KP\(_{21}\)
| ||||||||
Best | 56.3 | 62.05 | 59.99 | 61.76 | 62.01 | 62.08 | 62.06 | 59.7561 |
Median | 53.26 | 61.87 | 58.58 | 61.46 | 61.92 | 61.98 | 61.95 | 59.7561 |
Worst | 48.48 | 61.68 | 58.04 | 61.12 | 61.71 | 61.76 | 61.76 | 56.0839 |
Mean | 53.13 | 61.87 | 58.63 | 61.44 | 61.9 | 61.95 | 61.93 | 59.51 |
Std | 1.82 | 0.1 | 0.43 | 0.17 | 0.09 | 0.1 | 0.07 | 0.84 |
Best | 106.52 | 129.27 | 118.24 | 128.41 | 129.31 | 129.29 | 129.24 | 122.4199 |
Median | 99.89 | 129.06 | 115.95 | 127.72 | 129 | 128.95 | 128.88 | 121.1979 |
KP\(_{22}\)
| ||||||||
Worst | 94.25 | 128.76 | 113.32 | 125.66 | 128.51 | 128.56 | 128.45 | 120.6412 |
Mean | 100.15 | 129.06 | 115.88 | 127.59 | 128.94 | 128.95 | 128.87 | 122.16 |
Std | 2.92 | 0.13 | 1.12 | 0.6 | 0.21 | 0.18 | 0.19 | 0.60 |
Best | 147.08 | 191.54 | 166.55 | 190.83 | 191.49 | 191.46 | 191.41 | 190.2497 |
Median | 141.64 | 190.97 | 164.1 | 189.17 | 191.05 | 190.71 | 190.78 | 188.5120 |
KP\(_{23}\)
| ||||||||
Worst | 136.66 | 190.5 | 162.24 | 187.7 | 190.32 | 189.78 | 190.06 | 179.5679 |
Mean | 141.2 | 190.94 | 164.4 | 189.14 | 191.04 | 190.67 | 190.74 | 187.37 |
Std | 2.71 | 0.25 | 1.27 | 0.64 | 0.24 | 0.34 | 0.36 | 2.54 |
Best | 234.23 | 311.85 | 257.61 | 310.1 | 312.51 | 310.28 | 310.94 | 307.8299 |
Median | 224.64 | 310.6 | 252.58 | 308.39 | 311.92 | 309.32 | 309.85 | 307.7595 |
KP\(_{24}\)
| ||||||||
Worst | 218.81 | 309.56 | 249.16 | 306.91 | 310.67 | 307.82 | 308.44 | 292.0437 |
Mean | 225.45 | 310.52 | 252.87 | 308.38 | 311.79 | 309.23 | 309.82 | 306.52 |
Std | 4.26 | 0.6 | 1.86 | 0.83 | 0.48 | 0.61 | 0.61 | 4.13 |
Best | 323.93 | 443.43 | 355.45 | 442.2 | 446.3 | 441.51 | 442.35 | 441.2110 |
Median | 311.68 | 441.82 | 348.81 | 440.68 | 445.45 | 439.71 | 441.18 | 440.2339 |
KP\(_{25}\)
| ||||||||
Worst | 301.51 | 439.93 | 344.56 | 437.99 | 444.42 | 437.15 | 438.8 | 425.8292 |
Mean | 311.5 | 441.66 | 349.09 | 440.52 | 445.43 | 439.45 | 440.93 | 438.91 |
Std | 4.29 | 0.75 | 2.8 | 1.02 | 0.51 | 0.93 | 0.83 | 3.84 |
Best | 453.2 | 626.04 | 482.59 | 626.27 | 632.38 | 620.31 | 624.04 | 628.0995 |
Median | 431.71 | 623.09 | 475.73 | 623.07 | 630.33 | 618.12 | 621.68 | 628.0995 |
KP\(_{26}\)
| ||||||||
Worst | 420.42 | 621.53 | 470.08 | 619.09 | 628.65 | 615.83 | 618.81 | 610.5837 |
Mean | 431.97 | 623.18 | 475.33 | 623.17 | 630.34 | 617.96 | 621.7 | 626.62 |
Std | 6.68 | 1.25 | 3.15 | 1.64 | 1.02 | 1.28 | 1.18 | 4.30 |
Best | 526.59 | 746.55 | 570.95 | 750.32 | 756.08 | 741.27 | 745.77 | 749.8460 |
Median | 512.59 | 744.38 | 560.84 | 746.73 | 754.26 | 738.82 | 743.32 | 745.7390 |
KP\(_{27}\)
| ||||||||
Worst | 497.65 | 741.5 | 556.7 | 744.14 | 752.1 | 734.96 | 738.73 | 725.7928 |
Mean | 511.65 | 744.4 | 561.83 | 746.95 | 754.26 | 738.47 | 743.03 | 744.51 |
Std | 7 | 1.17 | 3.18 | 1.51 | 1.11 | 1.36 | 1.59 | 4.72 |
Best | 659.05 | 938.36 | 700.81 | 944.36 | 950.7 | 927.6 | 937.62 | 956.4658 |
Median | 631.94 | 935.21 | 693.91 | 941.18 | 949.42 | 924.15 | 933.82 | 956.4548 |
KP\(_{28}\)
| ||||||||
Worst | 615.25 | 932.94 | 687.84 | 937.3 | 947.36 | 920.73 | 930.6 | 946.4512 |
Mean | 633.31 | 935.18 | 694.53 | 941.14 | 949.17 | 924.25 | 933.7 | 955.73 |
Std | 8.37 | 1.29 | 3.87 | 2 | 1 | 1.64 | 1.8 | 2.15 |
Best | 780.89 | 1118.83 | 833.43 | 1129.81 | 1140.69 | 1106.12 | 1121.58 | 1150.6657 |
Median | 755.93 | 1115.78 | 819.96 | 1127.63 | 1136.71 | 1102.06 | 1115.3 | 1150.5952 |
KP\(_{29}\)
| ||||||||
Worst | 742.55 | 1112.07 | 813.31 | 1123.39 | 1133.22 | 1098.7 | 1111.32 | 1150.2488 |
Mean | 755.48 | 1115.23 | 821.07 | 1127.15 | 1136.57 | 1102.07 | 1115.39 | 1150.57 |
Std | 9.97 | 1.68 | 4.59 | 1.8 | 1.6 | 1.93 | 2.57 | 0.07 |
Best | 867.81 | 1238.16 | 916.07 | 1254.53 | 1263.67 | 1223.38 | 1240.66 | 1268.7089 |
Median | 835.85 | 1234.81 | 906.09 | 1252.63 | 1260.42 | 1220.21 | 1234.72 | 1266.2494 |
KP\(_{30}\)
| ||||||||
Worst | 818.62 | 1231.58 | 896.47 | 1247.62 | 1257.85 | 1214.94 | 1231.26 | 1263.4345 |
Mean | 835.23 | 1234.53 | 905.17 | 1252.08 | 1260.46 | 1219.88 | 1234.95 | 1266.23 |
Std | 9.72 | 1.85 | 5.44 | 1.71 | 1.54 | 2.07 | 2.26 | 1.05 |
Best | 1092.87 | 1579.8 | 1148.13 | 1613.95 | 1623.3 | 1559.19 | 1585.94 | 1644.1290 |
Median | 1061.59 | 1577.19 | 1140.14 | 1609.36 | 1618.89 | 1553.33 | 1579.92 | 1644.1290 |
KP\(_{31}\)
| ||||||||
Worst | 1044.6 | 1573.51 | 1129.41 | 1605.75 | 1613.54 | 1545.65 | 1572.33 | 1562.5883 |
Mean | 1062.7 | 1577.17 | 1139.77 | 1609.53 | 1618.77 | 1553.04 | 1579.7 | 1640.25 |
Std | 10.58 | 1.74 | 4.17 | 2.17 | 2.09 | 2.71 | 3.43 | 17.00 |
Best | 1269.54 | 1830.65 | 1332.06 | 1875.71 | 1879.12 | 1803.16 | 1839.01 | 1865.5547 |
Median | 1222.61 | 1826.22 | 1314.44 | 1871.05 | 1874.11 | 1797.45 | 1830.55 | 1865.5547 |
KP\(_{32}\)
| ||||||||
Worst | 1205.88 | 1821.17 | 1304.5 | 1866.99 | 1868.61 | 1792.59 | 1824.55 | 1851.2552 |
Mean | 1224.09 | 1825.98 | 1314.9 | 1870.91 | 1874.04 | 1797.55 | 1831.37 | 1864.60 |
Std | 12.96 | 2.38 | 7 | 2.28 | 2.65 | 2.75 | 3.88 | 3.0132 |
Performance assessment
Convergence analysis
Compared methods | Solution evaluations | ||||
---|---|---|---|---|---|
The proposed | Compared algorithms |
\(R^{-}\)
|
\(R^{+}\)
|
p Value | Winner |
IBBA-RSS | BHS | 45 | 0 | 0.007686 | IBBA-RSS |
IBBA-RSS | DBHS | 0 | 0 | – | – |
IBBA-RSS | NGHS1 | 3 | 0 | 0.179712 | IBBA-RSS |
IBBA-RSS | ABHS | 0 | 0 | – | – |
IBBA-RSS | ABHS1 | 28 | 0 | 0.017960 | IBBA-RSS |
IBBA-RSS | SBHS | 0 | 0 | – | – |
Compared methods | Solution evaluations | ||||
---|---|---|---|---|---|
The proposed | Compared algorithms |
\(R^{-}\)
|
\(R^{+}\)
|
p Value | Winner algorithm |
IBBA-RSS | BBA | 15 | 0 | 0.043114 | IBBA-RSS |
IBBA-RSS | CI | 12.5 | 8.5 | 0.674987 | IBBA-RSS |
IBBA-RSS | B&B | 6 | 4 | 0.715001 | IBBA-RSS |
Compared methods | Solution evaluations | ||||
---|---|---|---|---|---|
The proposed | Compared algorithms |
\(R^{-}\)
|
\(R^{+}\)
|
p Value | Winner algorithm |
IBBA-RSS | BBA | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | SBHS | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | IHS | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | GHS | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | SAHS | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | EHS | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | NGHS | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | NDHS | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | PSFHS | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | BHS | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | DBHS | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | NGHS1 | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | ABHS | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | ABHS1 | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | ITHS | 78 | 0 | 0.002218 | IBBA-RSS |
IBBA-RSS | V-BBA | 78 | 0 | 0.002218 | IBBA-RSS |