INTRODUCTION
In the industry, optimization problems are relevant, particularly at the level of decision making. Behind a decision-making process, there is always an optimization problem. Many of these problems have their domain in binary spaces. For example, we can find binary space problems in Civil Engineering, Bio-Informatics (Barman and Kwon, 2017), Operational Research (Crawford et al., 2017, September; 2018; Garcia and Măntoiu, 2014; García et al., 2019a), resource allocation (Astorga et al., 2018; García et al., 2017, September, 2019b; Valenzuela et al., 2019, June) scheduling problems (García et al., 2017, February, 2018a), routing problems among others.
Another line of research that has had an important impact is the design of algorithms inspired by natural phenomena to solve optimization problems. Many natural phenomena are developed in continuous spaces, so it is common to find a large number of these algorithms that work properly continuously, As examples of these algorithms we have Cuckoo Search, Black Hole, Bat Algorithm, and Multi-verse Optimization Algorithm (Mirjalili et al., 2016) among others. It is a challenge to transform a continuous algorithm into its binary version without altering the exploration and exploitation processes characteristic of each metaheuristic and that subsequently it adequately performs in combinatorial problems.
When a state of the art is realized, there are several techniques that give a solution to the complexity of passing an algorithm designed for continuous spaces in an algorithm that solves binary problems. We have general and specific techniques. However, these techniques work well for some problems and not for others. In general, the main techniques are transfer functions, angle modulation and the design of quantum operators. If you want to deepen this line, we recommend reading (Crawford et al., 2017). The objective of this article is to use the binarization technique that uses the percentile method and performs a binarization process. The multiverse optimizer (MVO) technique was chosen because it has been used in several continuous problems but in few combinatorial problems. MVO has been applied to voltage stability and voltage deviation problems in Trivedi et al. (2016, March). In Kumar and Suhag (2017), they applied MVO to control multi source hydrothermal power system.
Three concepts use the MVO algorithm, the white hole, the black hole who performs the exploration in the search space and wormholes that are in charge of performing the exploitation. The analogy says that each solution corresponds to a universe and associates a parameter called inflation rate which is proportional to the value of its fitness function. The black and white holes allow to exchange of objects of the universes and the probability that an exchange is made is handled by the inflation rate indicator. The solutions are ordered at the end of their inflation rate after each solution generates a white hole and the solution that is sent through the white hole is selected randomly. The replacement of the different objects is regulated by Equation 1. According to this equation, the lower the inflation rate, the greater the probability that the objects of that solution are replaced. However, there is only an exchange between universes, but there is no concept of mutation or disturbance of a universe.
| |
\[x_{j} = \left\{ \begin{matrix} x_{k}^{j}\ r_{1} < NI\left( U_{i} \right) \\ x_{i}^{j}\ r_{1} > NI\left( U_{i} \right) \\ \end{matrix} \right.\ \] |
(1) |
where \(x_{i}^{j}\) indicates the \(j\)th parameter of the ith solution, \(U_{i}\) corresponds to \(i\)th solution, \(\text{NI}\left( U_{i} \right)\) is normalized inflation rate of the \(i\)th solution, \(r_{1}\) is a random number in [0,1], and \(x_{k}^{j}\) indicates the \(j\)th parameter of \(k\)th solution selected by roulette wheel selection.
To mutate the objects, the concept of wormhole is used. The whormhole is established between each of the solutions and the best solution. The exchange of objects is produced from the best solution and a perturbation of the original object is made. The mechanism that regulates this perturbation is shown in Equation 2.
| |
\[x_{i}^{j} = \left\{ \begin{matrix} \left\{ \begin{matrix} x_{j} + TDR_{x}\left( \left( ub_{j} - lb_{j} \right)xr_{4} + lb_{j} \right)\ r_{3} < 0.5 \\ x_{j} - TDR_{x}\left( \left( ub_{j} - lb_{j} \right)xr_{4} + lb_{j} \right)\ r_{3} \geq 0.5 \\ \end{matrix} \right.\ & r_{2} < WEP \\ x_{i}^{j} & r_{2} \geq WEP \\ \end{matrix} \right.\ \] |
(2) |
In this expression WPE and TDR correspond to coefficients defined in Equations 3 and 4 respectively. lbj corresponds to the lower bound and ubj to the upper bound of the jth variable. xij represents to the variable of the jth dimension of the i solution. The numbers r2, r3 and r4 correspond to a random numbers between [0,1].
| |
\[\operatorname{WEP=min}{+ \ lx\left( \frac{max - min}{L} \right)}\] |
(3) |
| |
\[TDR = 1 - \left( \frac{l^{\frac{1}{p}}}{L^{\frac{1}{p}}} \right)\] |
(4) |
To check the binary multi-verse optimizer algorithm (BMVO) using percentile technique, we use the well-known knapsack problem. Experiments were developed using a random operator to validate the contribution of the percentile technique in the binarization pro-cess of the multi-verse optimizer algorithm. In addition, local search operator is used to strengthen the results. Moreover, the binary artificial algae (BAAA) and K-means transition ranking (KMTR) algorithms were used to compare our results. (BAAA) was developed in Zhang et al. (2016) and uses transfer functions to perform the binarization process. KMTR was developed in García et al. (2018b) and uses a K-means algorithm to perform the binarization. The results show that the percentile technique obtains results superior to those obtained by the random operator and that our BMVO algorithm shows competitive results against the BAAA and KMTR algorithms.
KnapSack PROBLEM
One of the NP-hard problems that has been studied most, corresponds to the Knapsack problem considering the large number of variants that it has. In this article, we will use the multidimensional knapsack problem to test our percentile binarization. The problem of the multidimensional knapsack (MKP) focuses on resource allocation problems. The objective is to find a subset of objects that produce greater benefit satisfying the different restrictions of the problem. Despite a large number of studies, this problem remains a challenge due to the difficulties in solving medium and large-sized instances. Performing a small state of the art of MKP, we find that this has been addressed in Haddar et al. (2016) using a quantum binarization technique, in García et al. (2018b) they applied the technique of grouping k-means to perform binarization, an improved optimization of The fruit fly in Meng and Pan (2017), in Liu et al. (2016) a differential algorithm with transfer functions was used, and in Bansal and Deep (2012) a modification of the PSO equations was used. MKP can be configured as:
| |
\[\text{Maximize}\sum_{j = 1}^{n}{p_{j}x_{j}}\] |
(5) |
| |
\[\text{subject to }\sum_{}^{}{c_{\text{ij}}x_{\text{ij}} \leq b_{i},\ i \in \left\{ 1,\ \ldots,\ m \right\}}\] |
(6) |
with \(x_{j} \in \left\{ 1,\ \ldots,\ m \right\}\). \(p_{j}\) corresponds to the profit of element \(j\). \(c_{\text{ij}}\) represents a cost associated with dimension \(i\) and element \(j\). The constraints in each dimension \(i\) are represented by \(b_{i}\). The solution can be modelled using a binary representation, in this representation a 0 means the element is not included in the knapsack.
BINARY MULTI-VERSE OPTIMIZER ALGORITHM
Due to the high computational complexity of MKP, the binary multi-verse optimization algorithm (BMVO) is composed of 4 operators to successfully solve the MKP. The operators corresponding to an initialization operator, a local search operator, the binary operator that uses the percentile technique and a repair operator in the case of solutions that do not meet any of the restrictions. The general flow chart of the algorithm is shown in Figure 1. The first stage corresponds to the initiation of solutions which will be detailed in section III-A. Subsequently, it is verified if the algorithm meets the detention conditions which is associated with a maximum number of iterations. In case of not complying with them, the MVO algorithm is executed in its original form and the solutions obtained by MVO are binarized by the percentile operator, this part of the algorithm is detailed in III-B. After having performed the binarization, we must verify the consistency of the solutions with their constraints and the results obtained are compared against the best solution generated so far. If the new solution is superior, it is replaced and a local search operator is executed.
Initialization and Element Weighting
As BMVO is a swarm algorithm, to begin the exploration and exploitation of the search space, the list of solutions must be initialized. For the generation of each solution, an element is randomly chosen first. The next step is to check if other elements can be incorporated, for this we must evaluate the constraints of our problem. To select the new element, we generate a list of possible elements that comply with the constraints. For each element is calculated its weight and the element which has the best weight is selected. This procedure is repeated until no additional element can be incorporated. In Figure 2, the initialization algorithm is displayed.
To calculate the weight of each element, several methods have been developed. In Pirkul (1987) a pseudo-utility in the surrogate duality approach was proposed. The way to calculate it is shown in the equation 7. In this equation the variable \(w_{j}\) corresponds to the surrogate multiplier whose value is between 0 and 1. This multiplier can be interpreted as a shadow prices of the \(j\)th constraint.
| |
\[\delta_{i} = \frac{p_i}{\sum_{j = 1}^{m}{(w_{j}c_{\text{ij}})}}\] |
(7) |
A more intuitive measure focused on the avergage resource occupancy was proposed by García et al. (2017, September). It is shown in equation 8.
| |
\[\delta_{i} = \frac{\sum_{j = 1}^{m}\left( \frac{c_{\text{ij}}}{m_{\text{bj}}} \right)}{p_{i}}\] |
(8) |
In this article we used a variation of this last measure focused on the average occupation and proposed in García et al. (2018b). this variation considers the elements that exist in knapsacks to calculate the average occupancy. In each iteration depending on the selected items in the solution the measure is calculated again. The expression of this new measure is shown in equation 9.
| |
\[\delta_{i} = \frac{\sum_{j = 1}^{m}\left( \frac{c_{\text{ij}}}{m\left( b_{j} - \ \sum_{}^{}{\begin{matrix} \\ i \in S \\ \end{matrix}(c_{\text{ij}})} \right)} \right)}{p_{i}}\] |
(9) |
Percentile Binary Operator
Due to the iterative nature of swarm intelligence algorithms and considering that MVO works in continuous space. The velocity and position of the solutions are updated in \(\mathbb{R}^{n}\). a general way of writing the update is shown in the equation 10. In this equation \(x_{t = 1}\) represents the position of the particle \(x\) at time \(t + 1\). To obtain the position, we consider the function \(\mathrm{\Delta}\), which is specific to each algorithm. For example in black hole \(\mathrm{\Delta}\left( x \right) = \alpha\bigoplus_{}^{}{\text{levy }\left( \lambda \right)\left( x \right)}\), and in PSO, Firefly, and Bat algorithm \(\mathrm{\Delta}\) can be written in simplified form as \(\mathrm{\Delta}(x)\ = \ v\ (x)\).
| |
\[x_{t = 1}\ = \ \mathrm{\Delta}_{t + 1}(x(t))\] |
(10) |
For the case of MVO, it is considered a binary percentile operator to perform the passage of the continuous space to the binary space. Given the particle \(x\), let us consider the magnitude of the displacement \(Deltai(x)\) in the \(i\)th component and we group these magnitudes for all solutions in order to obtain the values for the percentiles 20, 40, 60, 80, 100. At each percentile, we will assign a transition probability where the values are shown in the Equation 11. Using these transition probabilities together with the Equation 12, binarization of the solutions is performed. The algorithm is detailed in Algorithm 1.
| |
\[P_{\text{tr}}\left( x^{i} \right) = \left\{ \begin{matrix} 0.1 & \text{if}\ x^{i} \in \text{group}\left\{ 0,1 \right\} \\ 0.5 & \text{if}\ x^{i} \in \text{group}\left\{ 2,3,4 \right\} \\ \end{matrix} \right.\ \] |
(11) |
| |
\[x^{i}\left( t + 1 \right) = \left\{ \begin{matrix} x^{i}\left( t \right) & \text{if}\ \text{rand} < P_{\text{tg}}\left( x^{2} \right) \\ x^{i}\left( t \right) & \text{otherwise} \\ \end{matrix} \right.\ \] |
(12) |
|
Algorithm 1. Percentile binary operator
1: Function percentilebinary (vList, pList)
2: Input vList, pList
3 Output pGroup Value
4: pValue = getPercentileValue (vList, pList)
5: for each value in vList do
6: pGroup Value = getPercentileGroupValue(pValue, vList)
8: end for
9: return pGroupValue
|
Repair Operator
Local search and binary percentile operators can generate infeasible solutions. There are different mechanisms to address these infeasible solutions. In this article, the repair of the solutions was considered. To perform the repair, the measure described in the equation 9 was used. If the solution requires repair, the element with the maximum measure is chosen and it is removed from the solution, this process is iterated until a valid solution is obtained. The solution is then improved by exploring the possibility of incorporating new elements. This stage of improvement is iterated until there are no elements that can be incorporated without violating the constraints. The pseudocode is shown in Algorithm 2.
|
Algorithm 2. Repair Algorithm
1: Function Repair (Sin)
2: Input Input Solution Sin
3: Output The repair solution Sout
4: S ←Sin
5: While needRepair (S) = True do
6 : smax ← getMaxWeight(S)
7 : Smax ← removeElement (S, smax)
8: end while
9: state ← False
10: while state == False do
11: smin ← getMinWeight(S)
12: if smin == Ø then
13: state ← True
14: else
15: S ← addElement(S, smin)
16: end if
17: end while
18: Sout ← S
19: return Sout
|
RESULTS
Insight of BMVO Algorithm
This section aims to find out the contribution of the per- centile binary operator to the performance of the algorithm. To carry out the comparison problems cb.5.250 from the OR-library were selected. Violin charts and the Wilcoxon non-parametric signed-rank test were used to perform the statistical analyzes. In the charts, the X axis identifies the studied instances and the Y axis the % -Gap described in the equation 13. The Wilcoxon test is run to determine if the results obtained by BMVO have significant difference with respect to other algorithms. The parameter settings and browser ranges are shown in Table 1.
\[\% - GAP = 100\ (\frac{Bestknown - SolutioValue}{\text{Bestknown}})\]
|
Table 1. Setting of parameters for binary multi-verse search algorithm
|
Parameters
|
Description
|
Value
|
Range
|
|
N
|
Number of solutions
|
30
|
[20, 25, 30]
|
|
G
|
Number of percentiles
|
5
|
[4,5,6]
|
|
Iteration Number
|
Maximum iterations
|
1000
|
[1000]
|
|
max
|
Maximum for WEP coefficient
|
1
|
1
|
|
min
|
Minimum for WEP coefficient
|
0.2
|
0.2
|
|
p
|
p parameter for TDR coefficient
|
6
|
6
|
|
1) Evaluation of percentile binary operator: A random operator was designed to evaluate the contribution of the percentile binary operator. This random operator has the pe- culiarity of performing the transitions with a fixed probability of 0.5 without considering in which percentile the variable is located. Two configurations were studied: The first one where the local search operator is included and the second where the local operator is not considered. BMVO corresponds to our standard algorithm. random.ls is the random variant that includes the local search operator. BMVO.wls corresponds to the version with percentile binary operator without local search operator. Finally, random.wls describes the random algorithm without local search operator.
When we compared the Best Values between BMVO and random.ls which are shown in Table 2. BMVO outperforms to random.ls. However, the Best Values between both algorithms are very close. In the Average comparison, BMVO outper- forms random.ls almost in all problems. The comparison of distributions is shown in Figure 3. We see the dispersion of the random.ls distributions are bigger than the dispersions of BMVO. In particular, this can be appreciated in the problems 1, 2, 4, 5, 6, and 9. Therefore, the percentile binary operator together with local search operators, contribute to the precision of the results. Finally, the BMVO distributions are closer to zero than random.ls distributions, indicating that BMVO has consistently better results than random.ls. When we evaluate the behaviour of the algorithms through the Wilcoxon test, this indicates that there is a significant difference between the two algorithms.
|
Table 2. Evaluation of percentile binary operator
|
Set
|
Best
|
best
|
best
|
best
|
best
|
avg
|
avg
|
avg
|
avg
|
|
|
Known
|
random.ls
|
BMVO
|
random.wls
|
wls
|
random.ls
|
BMVO
|
random.wls
|
wls
|
|
cb.5.250-0
|
59312
|
59211
|
59225
|
59158
|
59175
|
59132.1
|
59146.2
|
59071.8
|
59131.4
|
|
cb.5.250-1
|
61472
|
61435
|
61435
|
61409
|
61409
|
61324.6
|
61391.3
|
61288.3
|
61372.1
|
|
cb.5.250-2
|
62130
|
62036
|
62074
|
61969
|
61969
|
61894.4
|
61971.1
|
61801.6
|
61923.2
|
|
cb.5.250-3
|
59463
|
59367
|
59446
|
59365
|
59349
|
59257.8
|
59324.6
|
59136.1
|
59271.7
|
|
cb.5.250-4
|
58951
|
58914
|
58951
|
58883
|
58930
|
58725.6
|
58821.1
|
58693.6
|
58757.1
|
|
cb.5.250-5
|
60077
|
60015
|
60056
|
59990
|
60015
|
59904.6
|
59963.1
|
59837.8
|
59943.1
|
|
cb.5.250-6
|
60414
|
60355
|
60355
|
60348
|
60349
|
60208.2
|
60325.8
|
60230.6
|
60310.2
|
|
cb.5.250-7
|
61472
|
61436
|
61436
|
61407
|
61407
|
61290.8
|
61337.6
|
61233.9
|
61341.7
|
|
cb.5.250-8
|
61885
|
61829
|
61885
|
61790
|
61782
|
61737.1
|
61795.3
|
61644.9
|
61739.8
|
|
cb.5.250-9
|
58959
|
58832
|
58866
|
58822
|
58787
|
58769.1
|
58789.2
|
58653.7
|
58771.6
|
|
Average
p-value
|
60413.5
|
60343
|
60372.9
|
60314.1
|
60317.2
|
60224.4
|
60286.5
4.16 e-05
|
60159.2
|
60256.2
1.16 e-05
|
|
Our next step is trying to separate the contribution of local search operator from the percentile binary operator. For this, we compared the algorithms wls and random.wls.
When we check the Best Values shown in the Table 2, we note that wpe performs better than 05.wpe in all problems except 1, 6 and 7. However the results are quite close. In the case of the average indicator, wpe outperforms in all problems to 05.wpe. The Wilcoxon test indicates that the difference is significant. This suggests that wpe is consistently better than 05.wpe. In the violin chart shown in the Figure 4 it is further observed that the dispersion of the solutions for the case of 05.wpe is much larger than in the case of wpe. This indicates that the percentile binary operator plays an important role in the precision of the results.
BMVO Comparisons
In this section we evaluate the performance of our BMVO with the algorithm BAAA developed in Zhang et al. (2016). BAAA uses transfer functions as a general mechanism of binarization. In particular BAAA used the \(\tanh{= \frac{e^{t\left| x \right|} - 1}{e^{t\left| x \right|} + 1}}\) function to perform the transference. The parameter τ of the tanh function was set to a value 1.5. Additionally, a elite local search procedure was used by BAAA to improve solutions. As maximum number of iterations BAAA used 35000. The computer configuration used to run the BAAA algorithm was: PC Intel Core(TM) 2 dual CPU Q9300@2.5GHz, 4GB RAM and 64-bit Windows 7 operating system. In our BMVO algorithm, the configurations are the same used in the previous experiments. These are described in the Table 1. Additionally we made the comparison with KMTR-BH and KMTR-Cuckoo binarizations. KMTR uses the unsupervised K-means learning technique to perform the binarization process. In the article García et al. (2018b), the Black Hole and Cuckoo Search algorithms were binarized using KMTR.
The results are shown in Table 3. The comparison was per- formed for the set cb.5.500 of the OR-library. The results for BMVO were obtained from 30 executions for each problem. In black, the best results are marked for both indicators the Best Value and the Average. For the best value indicator BAAA was higher in 4, KMTR-BH in 11, KMTR-Cuckoo in 7 and BMVO in 11. We should note that the sum is greater than 30 because in some cases there was a tie between some of the algorithms. In the Average indicator BAAA was higher in 2 instances, KMTR-BH in 9, KMTR-Cuckoo in 4 and BMVO in 15. We should also note that the standard deviation in most problems was quite low, indicating that BMVO has good accuracy.
|
Table 3. OR-Library benchmarks MKP CB.5.500
|
Instance
|
Best
Known
|
BAAA
Best
|
Avg
|
KMTR-BH
Best
|
Avg
|
KMTR-Cuckoo
Best
|
Avg
|
BMVO
Best
|
Avg
|
Time(s)
|
std
|
|
0
|
120148
|
120066
|
120013.7
|
120096
|
120029.9
|
120082
|
120036.8
|
120082
|
120022.6
|
438
|
37.1
|
|
1
|
117879
|
117702
|
117560.5
|
117730
|
117617.5
|
117656
|
117570.6
|
117656
|
117617.2
|
486
|
43.6
|
|
2
|
121131
|
120951
|
120782.9
|
121039
|
120937.9
|
120923
|
120855.1
|
120923
|
120891.1
|
457
|
47.9
|
|
3
|
120804
|
120572
|
120340.6
|
120683
|
120522.8
|
120683
|
120455.7
|
120683
|
120516.4
|
514
|
49.1
|
|
4
|
122319
|
122231
|
122101.8
|
122280
|
122165.2
|
122212
|
122136.4
|
122212
|
122134.2
|
521
|
49.6
|
|
5
|
122024
|
121957
|
121741.8
|
121982
|
121868.7
|
121946
|
121824.6
|
121982
|
121856.3
|
531
|
52.1
|
|
6
|
119127
|
119070
|
118913.4
|
119068
|
118950.0
|
118956
|
118895.5
|
118956
|
118923.1
|
487
|
27.8
|
|
7
|
120568
|
120472
|
120331.2
|
120463
|
120336.6
|
120392
|
120320.4
|
120487
|
120317.4
|
443
|
66.9
|
|
8
|
121586
|
121052
|
120683.6
|
121377
|
121161.9
|
121201
|
121126.3
|
121295
|
121201.4
|
431
|
55.8
|
|
9
|
120717
|
120499
|
120296.3
|
120524
|
120362.9
|
120467
|
120335.5
|
120467
|
120391.1
|
465
|
42.1
|
|
10
|
218428
|
218185
|
217984.7
|
218296
|
218163.7
|
218291
|
218208.9
|
218291
|
218203.1
|
437
|
30.9
|
|
11
|
221202
|
220852
|
220527.5
|
220951
|
220813.9
|
220969
|
220862.3
|
220951
|
220842.1
|
436
|
50.1
|
|
12
|
217542
|
217258
|
217056.7
|
217349
|
217254.3
|
217356
|
217293.0
|
217356
|
217297.1
|
441
|
46.1
|
|
13
|
223560
|
223510
|
223450.9
|
223518
|
223455.2
|
223516
|
223455.6
|
223516
|
223458.1
|
437
|
42.3
|
|
14
|
218966
|
218811
|
218634.3
|
218848
|
218771.5
|
218884
|
218794.0
|
218848
|
218814.4
|
471
|
32.7
|
|
15
|
220530
|
220429
|
220375.9
|
220441
|
220342.2
|
220433
|
220352.7
|
220410
|
220362.7
|
442
|
36.1
|
|
16
|
219989
|
219785
|
219619.3
|
219858
|
219717.9
|
219943
|
219732.8
|
219858
|
219767.2
|
431
|
57.2
|
|
17
|
218215
|
218032
|
217813.2
|
218010
|
217890.1
|
218094
|
217928.7
|
218010
|
217957.1
|
428
|
46.2
|
|
18
|
216976
|
216940
|
216862.0
|
216866
|
216798.8
|
216873
|
216829.8
|
216866
|
216823.1
|
418
|
28.2
|
|
19
|
219719
|
219602
|
219435.1
|
219631
|
219520.0
|
219693
|
219558.9
|
219631
|
219581.3
|
399
|
31.6
|
|
20
|
295828
|
295652
|
295505.0
|
295717
|
295628.4
|
295688
|
295608.8
|
295688
|
295643.1
|
389
|
22.7
|
|
21
|
308086
|
307783
|
307577.5
|
307924
|
307860.6
|
308065
|
307914.8
|
307924
|
307889.1
|
365
|
22.4
|
|
22
|
299796
|
299727
|
299664.1
|
299796
|
299717.8
|
299684
|
299660.9
|
299796
|
299713.2
|
321
|
33.2
|
|
23
|
306480
|
306469
|
306385.0
|
306480
|
306445.2
|
306415
|
306397.3
|
306415
|
306382.1
|
327
|
23.1
|
|
24
|
300342
|
300240
|
300136.7
|
300245
|
300202.5
|
300207
|
300184.4
|
300245
|
300223.2
|
273
|
27.5
|
|
25
|
302571
|
302492
|
302376.0
|
302481
|
302442.3
|
302474
|
302435.6
|
302481
|
302480.2
|
347
|
24.8
|
|
26
|
301339
|
301272
|
301158.0
|
301284
|
301238.3
|
301284
|
301239.7
|
301284
|
301249.1
|
357
|
20.5
|
|
27
|
306454
|
306290
|
306138.4
|
306325
|
306264.2
|
306331
|
306276.4
|
306331
|
306308.1
|
327
|
21.1
|
|
28
|
302828
|
302769
|
302690.1
|
302749
|
302721.4
|
302781
|
302716.9
|
302771
|
302731.2
|
337
|
25.3
|
|
29
|
299910
|
299757
|
299702.3
|
299774
|
299722.7
|
299828
|
299766.0
|
299828
|
299771.2
|
316
|
47.1
|
|
Average
|
214168.8
|
214014.2
|
213862.0
|
214059.5
|
213964.1
|
214044.2
|
213959.1
|
214041.4
|
213978.9
|
415.7
|
38.0
|
|
Additionally, to evaluate the robustness of BMVO, we experiment with the problems cb.10.500 and cb.30.500. These problems correspond to the most difficult problems of the OR- library. A summary of the results are shown in Table 4. In this table we also incorporate the results for KMTR-BH and KMTR-Cuckoo algorithm.
|
Table 4. Summary of OR-Library benchmarks MKP CB.10.500 and CB.30.500
|
Problem Set
|
KMTR-BH
Average %-Gap
|
std
|
KMTR-Cuckoo Average %-Gap
|
std
|
BMVO
Average %-Gap
|
std
|
|
cb.10.500.25
|
0.34
|
0.08
|
0.37
|
0.1
|
0.39
|
0.12
|
|
cb.10.500.50
|
0.22
|
0.03
|
0.20
|
0.03
|
0.21
|
0.06
|
|
cb.10.500.75
|
0.11
|
0.03
|
0.09
|
0.03
|
0.10
|
0.04
|
|
cb.30.500.25
|
0.62
|
0.12
|
0.59
|
0.10
|
0.64
|
0.09
|
|
cb.30.500.50
|
0.27
|
0.05
|
0.26
|
0.05
|
0.24
|
0.04
|
|
cb.30.500.75
|
0.17
|
0.03
|
0.16
|
0.03
|
0.18
|
0.03
|
|
Average
|
0.24
|
0.1
|
245.6
|
0.22
|
0.29
|
0.06
|
|
CONCLUSIONS
In this article, a general binarization technique which use the percentile concept is used to perform the binarization of the MVO algorithm. It should be noted that the percentile technique can be applied in the binarization of any continuous swarm-intelligence algorithm. To test the binarization obtained, we used the knapsack problem to evaluate our binary algorithm. The contribution of the percentile binary operator was studied, observing that this operator contributes to the precision and quality of the solutions obtained. Improving the interquartile range of solutions and best values when we compare the percentile algorithm against a random operator. Additionally, we develop a comparison with the BAAA and KMTR algorithms, showing that BMVO has a good performance.
As a future line of research, it is interesting to compare the performance of the percentile operator with the K-means operator used in KMTR and with the transfer functions used in BAAA, all applied in the binarization of the MVO algorithm. Another interesting line of research is to explore adaptive techniques to automate the selection of parameters. From the theoretical point of view, it would also be interesting to understand how the exploration and exploitation of space are altered when we present the percentile operator. Also, we believe that the incorporation of reinforcement learning techniques for decision making in the binarization mechanism can be an interesting line to explore and that integrates two areas that are developing strongly. Finally, it is interesting to use the percentile operator to binarize other swarm intelligence algorithms in addition to solving other NP-hard problems.