INTRODUCTION
In the industry, optimization problems are relevant, particularly at the level of decision making. Behind a decisionmaking 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, BioInformatics (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 Multiverse 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. lb_{j} corresponds to the lower bound and ub_{j} to the upper bound of the jth variable. x_{i}^{j} 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 multiverse optimizer algorithm (BMVO) using percentile technique, we use the wellknown knapsack problem. Experiments were developed using a random operator to validate the contribution of the percentile technique in the binarization process of the multiverse optimizer algorithm. In addition, local search operator is used to strengthen the results. Moreover, the binary artificial algae (BAAA) and Kmeans 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 Kmeans 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 NPhard 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 largesized 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 kmeans 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 MULTIVERSE OPTIMIZER ALGORITHM
Due to the high computational complexity of MKP, the binary multiverse 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 IIIA. 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 IIIB. 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 pseudoutility 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 (S_{in})
2: Input Input Solution S_{in}
3: Output The repair solution S_{out}
4: S ←S_{in}
5: While needRepair (S) = True do
6 : s_{max} ← getMaxWeight(S)
7 : S_{max} ← removeElement (S, s_{max})
8: end while
9: state ← False
10: while state == False do
11: s_{min} ← getMinWeight(S)
12: if s_{min ==} Ø then
13: state ← True
14: else
15: S ← addElement(S, s_{min})
16: end if
17: end while
18: S_{out} ← S
19: return S_{out}

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 ORlibrary were selected. Violin charts and the Wilcoxon nonparametric signedrank 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 multiverse 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.2500

59312

59211

59225

59158

59175

59132.1

59146.2

59071.8

59131.4

cb.5.2501

61472

61435

61435

61409

61409

61324.6

61391.3

61288.3

61372.1

cb.5.2502

62130

62036

62074

61969

61969

61894.4

61971.1

61801.6

61923.2

cb.5.2503

59463

59367

59446

59365

59349

59257.8

59324.6

59136.1

59271.7

cb.5.2504

58951

58914

58951

58883

58930

58725.6

58821.1

58693.6

58757.1

cb.5.2505

60077

60015

60056

59990

60015

59904.6

59963.1

59837.8

59943.1

cb.5.2506

60414

60355

60355

60348

60349

60208.2

60325.8

60230.6

60310.2

cb.5.2507

61472

61436

61436

61407

61407

61290.8

61337.6

61233.9

61341.7

cb.5.2508

61885

61829

61885

61790

61782

61737.1

61795.3

61644.9

61739.8

cb.5.2509

58959

58832

58866

58822

58787

58769.1

58789.2

58653.7

58771.6

Average
pvalue

60413.5

60343

60372.9

60314.1

60317.2

60224.4

60286.5
4.16 e05

60159.2

60256.2
1.16 e05


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 64bit 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 KMTRBH and KMTRCuckoo binarizations. KMTR uses the unsupervised Kmeans 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 ORlibrary. 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, KMTRBH in 11, KMTRCuckoo 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, KMTRBH in 9, KMTRCuckoo 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. ORLibrary benchmarks MKP CB.5.500
Instance

Best
Known

BAAA
Best

Avg

KMTRBH
Best

Avg

KMTRCuckoo
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 KMTRBH and KMTRCuckoo algorithm.
Table 4. Summary of ORLibrary benchmarks MKP CB.10.500 and CB.30.500
Problem Set

KMTRBH
Average %Gap

std

KMTRCuckoo 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 swarmintelligence 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 Kmeans 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 NPhard problems.