# Journal of Information Systems Engineering and Management

A Percentile Methodology Applied to Binarization of Swarm Intelligence Metaheuristics
, , , ,
More Detail
1 Pontificia Universidad Católica de Valparaíso, Valparaíso, CHILE
* Corresponding Author
Research Article

Journal of Information Systems Engineering and Management, 2019 - Volume 4 Issue 4, Article No: em0104
https://doi.org/10.29333/jisem/6348

Published Online: 07 Dec 2019

APA 6th edition
In-text citation: (Valenzuela et al., 2019)
Reference: Valenzuela, M., Pinto, H., Moraga, P., Altimiras, F., & Villavicencio, G. (2019). A Percentile Methodology Applied to Binarization of Swarm Intelligence Metaheuristics. Journal of Information Systems Engineering and Management, 4(4), em0104. https://doi.org/10.29333/jisem/6348
Vancouver
In-text citation: (1), (2), (3), etc.
Reference: Valenzuela M, Pinto H, Moraga P, Altimiras F, Villavicencio G. A Percentile Methodology Applied to Binarization of Swarm Intelligence Metaheuristics. J INFORM SYSTEMS ENG. 2019;4(4):em0104. https://doi.org/10.29333/jisem/6348
AMA 10th edition
In-text citation: (1), (2), (3), etc.
Reference: Valenzuela M, Pinto H, Moraga P, Altimiras F, Villavicencio G. A Percentile Methodology Applied to Binarization of Swarm Intelligence Metaheuristics. J INFORM SYSTEMS ENG. 2019;4(4), em0104. https://doi.org/10.29333/jisem/6348
Chicago
In-text citation: (Valenzuela et al., 2019)
Reference: Valenzuela, Matias, Hernan Pinto, Paola Moraga, Francisco Altimiras, and Gabriel Villavicencio. "A Percentile Methodology Applied to Binarization of Swarm Intelligence Metaheuristics". Journal of Information Systems Engineering and Management 2019 4 no. 4 (2019): em0104. https://doi.org/10.29333/jisem/6348
Harvard
In-text citation: (Valenzuela et al., 2019)
Reference: Valenzuela, M., Pinto, H., Moraga, P., Altimiras, F., and Villavicencio, G. (2019). A Percentile Methodology Applied to Binarization of Swarm Intelligence Metaheuristics. Journal of Information Systems Engineering and Management, 4(4), em0104. https://doi.org/10.29333/jisem/6348
MLA
In-text citation: (Valenzuela et al., 2019)
Reference: Valenzuela, Matias et al. "A Percentile Methodology Applied to Binarization of Swarm Intelligence Metaheuristics". Journal of Information Systems Engineering and Management, vol. 4, no. 4, 2019, em0104. https://doi.org/10.29333/jisem/6348
ABSTRACT
The binarization mechanisms of continuous metaheuristics are of interest in operational research. This is mainly due to the fact that there are a lot of combinatorial problems that are NP-hard. In this article, we exploit the concept of percentile as a mechanism of binarization of swarm intelligence continuous metaheuristics. To evaluate the behavior of our binary operator, the Multi-verse metaheuristic is used and applied to solve the combinatorial problem of the knapsack. The binary algorithm obtained, the binary multi-verse Optimizer (BMVO) shows good performance in solving the most difficult problems of the knapsack.
KEYWORDS
Show / Hide HTML Content

# 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.

REFERENCES
• Astorga, G., Crawford, B., Soto, R., Monfroy, E., García, J. and Cortes, E. (2018). A meta-optimization approach to solve the set covering problem. Ingeniería, 23(3), 1-14.
• Bansal, J. C. and Deep, K. (2012). A modified binary particle swarm optimization for knapsack problems. Applied Mathematics and Computation, 218(22), 11042-11061. https://doi.org/10.1016/j.amc.2012.05.001
• Barman, S. and Kwon, Y. K. (2017). A novel mutual information-based Boolean network inference method from time-series gene expression data. PloS one, 12(2), e0171097. https://doi.org/10.1371/journal.pone.0171097
• Crawford, B., Soto, R., Astorga, G., García, J., Castro, C. and Paredes, F. (2017). Putting continuous metaheuristics to work in binary search spaces. Complexity. https://doi.org/10.1155/2017/8404231
• Crawford, B., Soto, R., Monfroy, E., Astorga, G., García, J. and Cortes, E. (2018). A meta-optimization approach to solve the set covering problem. Ingeniería, 23(3), 274-288. https://doi.org/10.14483/23448393.13247
• Crawford, B., Soto, R., Monfroy, E., Astorga, G., García, J. and Cortes, E. (2017, September). A meta-optimization approach for covering problems in facility location. In Workshop on Engineering Applications (pp. 565-578). Springer, Cham. https://doi.org/10.1007/978-3-319-66963-2_50
• Garcia, J. and Măntoiu, M. (2014). Localization results for zero order pseudodifferential operators. Journal of Pseudo-Differential Operators and Applications, 5(2), 255-276. https://doi.org/10.1007/s11868-013-0084-y
• García, J. and Peña, A. (2018). Robust optimization: concepts and applications. Nature-inspired Methods for Stochastic, Robust and Dynamic Optimization, 7. https://doi.org/10.5772/intechopen.75381
• García, J., Altimiras, F., Peña, A., Astorga, G. and Peredo, O. (2018a). A binary cuckoo search big data algorithm applied to large-scale crew scheduling problems. Complexity. https://doi.org/10.1155/2018/8395193
• García, J., Crawford, B., Soto, R. and Astorga, G. (2017, September). A percentile transition ranking algorithm applied to knapsack problem. In Proceedings of the Computational Methods in Systems and Software (pp. 126-138). Springer, Cham. https://doi.org/10.1007/978-3-319-67621-0_11
• García, J., Crawford, B., Soto, R. and Astorga, G. (2019a). A clustering algorithm applied to the binarization of swarm intelligence continuous metaheuristics. Swarm and evolutionary computation, 44, 646-664. https://doi.org/10.1016/j.swevo.2018.08.006
• García, J., Crawford, B., Soto, R. and García, P. (2017, February). A multi dynamic binary black hole algorithm applied to set covering problem. In International Conference on Harmony Search Algorithm (pp. 42-51). Springer, Singapore. https://doi.org/10.1007/978-981-10-3728-3_6
• García, J., Crawford, B., Soto, R., Castro, C. and Paredes, F. (2018b). A k-means binarization framework applied to multidimensional knapsack problem. Applied Intelligence, 48(2), 357-380. https://doi.org/10.1007/s10489-017-0972-6
• García, J., Moraga, P., Valenzuela, M., Crawford, B., Soto, R., Pinto, H., ... Astorga, G. (2019b). A Db-Scan Binarization Algorithm Applied to Matrix Covering Problems. Computational intelligence and neuroscience. https://doi.org/10.1155/2019/3238574
• García, J., Pope, C. and Altimiras, F. (2017). A Distributed-Means Segmentation Algorithm Applied to Lobesia botrana Recognition. Complexity. https://doi.org/10.1155/2017/5137317
• Graells-Garrido, E. and García, J. (2015, December). Visual exploration of urban dynamics using mobile data. In International Conference on Ubiquitous Computing and Ambient Intelligence (pp. 480-491). Springer, Cham. https://doi.org/10.1007/978-3-319-26401-1_45
• Graells-Garrido, E., Peredo, O. and García, J. (2016). Sensing urban patterns with antenna mappings: the case of Santiago, Chile. Sensors, 16(7), 1098. https://doi.org/10.3390/s16071098
• Haddar, B., Khemakhem, M., Hanafi, S. and Wilbaut, C. (2016). A hybrid quantum particle swarm optimization for the multidimensional knapsack problem. Engineering Applications of Artificial Intelligence, 55, 1-13. https://doi.org/10.1016/j.engappai.2016.05.006
• Kong, X., Gao, L., Ouyang, H. and Li, S. (2015). Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm. Computers & Operations Research, 63, 7-22. https://doi.org/10.1016/j.cor.2015.04.018
• Kumar, A. and Suhag, S. (2017). Multiverse optimized fuzzy-PID controller with a derivative filter for load frequency control of multisource hydrothermal power system. Turkish Journal of Electrical Engineering & Computer Sciences, 25(5), 4187-4199. https://doi.org/10.3906/elk-1612-176
• Liu, J., Wu, C., Cao, J., Wang, X. and Teo, K. L. (2016). A binary differential search algorithm for the 0–1 multidimensional knapsack problem. Applied Mathematical Modelling, 40(23-24), 9788-9805. https://doi.org/10.1016/j.apm.2016.06.002
• Meng, T. and Pan, Q. K. (2017). An improved fruit fly optimization algorithm for solving the multidimensional knapsack problem. Applied Soft Computing, 50, 79-93. https://doi.org/10.1016/j.asoc.2016.11.023
• Mirjalili, S., Mirjalili, S. M. and Hatamlou, A. (2016). Multi-verse optimizer: a nature-inspired algorithm for global optimization. Neural Computing and Applications, 27(2), 495-513. https://doi.org/10.1007/s00521-015-1870-7
• Peredo, O. F., García, J. A., Stuven, R. and Ortiz, J. M. (2017). Urban dynamic estimation using mobile phone logs and locally varying anisotropy. In Geostatistics Valencia 2016 (pp. 949-964). Springer, Cham. https://doi.org/10.1007/978-3-319-46819-8_66
• Pirkul, H. (1987). A heuristic solution procedure for the multiconstraint zero‐one knapsack problem. Naval Research Logistics (NRL), 34(2), 161-172. https://doi.org/10.1002/1520-6750(198704)34:2<161::AID-NAV3220340203>3.0.CO;2-A
• Trivedi, I. N., Jangir, P., Jangir, N., Parmar, S. A., Bhoye, M. and Kumar, A. (2016, March). Voltage stability enhancement and voltage deviation minimization using multi-verse optimizer algorithm. In 2016 International conference on circuit, power and computing technologies (ICCPCT) (pp. 1-5). IEEE. https://doi.org/10.1109/ICCPCT.2016.7530136
• Valenzuela, M., Valenzuela, P., Cáceres, C., Jorquera, L. and Pinto, H. (2019, June). A Percentile Multi-Verse Optimizer Algorithm applied to the Knapsack problem. In 2019 14th Iberian Conference on Information Systems and Technologies (CISTI) (pp. 1-8). IEEE. https://doi.org/10.23919/CISTI.2019.8760613
• Zhang, X., Wu, C., Li, J., Wang, X., Yang, Z., Lee, J. M. and Jung, K. H. (2016). Binary artificial algae algorithm for multidimensional knapsack problems. Applied Soft Computing, 43, 583-595. https://doi.org/10.1016/j.asoc.2016.02.027