1 Introduction

The knapsack problem has multiple applications in science and engineering. For example capital budgeting and project selection applications [47, 54, 71]. The MKP has also been introduced to model problems like cutting stock [25], loading problems [62], allocation of processors in a distributed data processing [22], delivery in vehicles with multiple compartments [10] and self-sufficiency problems [64].

Numerous methods have been developed to solve the MKP. The exact methods were applied in the 80’s to solve MKP [5, 20, 46]. They generate a variety of methods including dynamic programming, branch-and-bound, network approach and reduction schemes. The exact methods have made possible the solution of middle size MKP instances. The major drawback of these methods remains the temporal complexity when dealing with large instances. Therefore, many researchers focus on heuristic and meta-heuristic search methods which can produce solutions of good qualities in a reasonable amount of time. In recent years, many bio-inspired methods, such as Genetic algorithms [45], Particle Swarm Optimization (PSO) [6, 14] Firefly algorithm [7], Ant Colony Optimization [12], and a binary Fruitfly [70] have been proposed to solve large instances of the MKP.

Many of these bio-inspired methods, are working in continuous spaces and they have had to be adapted to a binary version. Examples of these adaptations are found in Harmony Search (HS) [23], Swarm Intelligence [9], Wind driven optimization [83],Differential Evolution Algorithm (DE) [26, 82], PSO [33], Magnetic Optimization Algorithm (MOA) [68], and Gravitational Search Algorithm (GSA) [58], Swarm Intelligence [53], and Black Hole [21].

In many of these adaptations, the transfer functions are used as a general mechanism to perform binarization. Examples of using transfer functions are found in the firefly algorithm [50, 57], PSO [33, 35], Artificial Bee Colony [16], Cuckoo search [65], Teach learning [1]. In [80] a binary artificial algae algorithm (BAAA) solves medium and large MKP with very good results. This algorithm in addition to transfer function, used an interesting heuristics for solution repair, and elitist local search to improve the solutions. In [43] the authors propose a binary differencial search (BDS) algorithm also with good results to solve the knapsack problem based in Brownian motion and a v-shape transfer function. A hybrid harmony search-based algorithm (HHS) [78] obtained interesting results in problems of medium size.

In this paper, a general framework is proposed to binarize continuous metaheuristics. This framework is called k-means transition ranking (KMTR) which is composed of three operators. The main operator corresponds to k-means transition operator. This operator performs the binarization process and is complemented with local search and perturbation operators. The main goal of this work corresponds to evaluate our framework when dealing with an NP-hard combinatorial optimization problem such as the MKP. To develop the evaluation, we used two metaheuristics: Cuckoo Search and Black Hole. These metaheuristics were chosen by the difference between their iteration mechanisms. Cuckoo uses iteration through Lévy flights while Black Hole uses a simplified PSO mechanism. Additionally, it is interesting to use our framework in metaheuristics that have already solved the MKP as Cuckoo Search [24, 38] and others like Black Hole that to our knowledge have not been solved the MKP.

For appropriate evaluation of our framework, a method of estimating parameters is developed. Subsequently experiments were developed that shed light on the contribution of the different operators at the end result. Finally our framework was compared with recent algorithms that use transfer functions as binarization method. For this purpose we use different sets of tests problems from the OR-Library.Footnote 1 We compared our framework with the BAAA algorithm published by [80], and the algorithms TR-BDS and TE-BDS reported in [43], both algorithms are state of the art published in 2016. The numerical results show that KMTR achieves highly competitive results.

The remainder of this paper is organized as follows. Section 2 briefly introduces the Knapsack problem. In Section 3 other binarization works are presented. In Section 4 we explain the k-means transition ranking framework. The results of numerical experiment are presented in Section 5. Finally we provide the conclusions of our work.

2 KnapSack problem

The multidimensional knapsack problem [72] belongs to the class of NP-hard problems. MKP corresponds to a model of resource allocation, whose objective is to select a subset of objects that produce the greatest benefit considering certain capacity constraints. Each object j consumes a different amount of resources in each dimension. Also each object has a profit associated. Formally the MKP can be set as:

$$ \text{maximize } \sum\limits_{j=1}^{n} p_{j}x_{j} $$
(1)
$$ \text{subjected to } \sum\limits_{j=1}^{n} c_{ij}x_{j} \le b_{i} \text{ , } i \in \{1,...,m\} $$
(2)
$$ \text{with } x_{j} \in \{0,1\} \text{ , } j \in \{1,...,n\} $$
(3)

Where p j is the profit for the item j, c i j corresponds to the consumption of resources of item j in the dimension i, and b i is the capacity constraint of each dimension i. The representation of a solution of the problem is modelled naturally in binary form where 0 in the j-th position means that the j item is not included in the Knapsack and 1 indicates that j is included.

3 Related work

There is a set of metaheuristic techniques that were designed to operate in continuous spaces. Examples of these techniques are Artificial Bee Colony [34], Particle Swarm Optimization [61], Black Hole [29], Cuckoo Search [75], Bat Algorithm [74], FireFly Algorithm [73], FruitFly [52], Artificial Fish Swarm [42], Gravitational Search Algorithm [58]. Moreover, in operational research, there are a lot of problems that are combinatorial and non-polynomial type [37]. So naturally, the idea arises of applying these continuous metaheuristics to combinatorial problems which are solved in discrete spaces. These adaptations are generally not trivial and have given rise at different lines of research.

When a review is made in the literature of binarization techniques, two main groups appear. A first group corresponds to general binarization frameworks. In these frameworks there is a mechanism that allows to transform any continuous metaheuristics in a binary one, without altering the metaheuristics operators. In this category the main frameworks used are: Transfer Functions and Angle Modulation. The second group corresponds to binarizations developed specifically for a metaheuristic. Within this second group we found techniques such as Quantum Binary and Set based approach.

Transfer functions

The transfer function is the most used binarization method. It was introduced by [33]. The transfer function is a very cheap operator, his range provides probabilities values and tries to model the transition of the particle positions. This function is responsible for the first step of the binarization method which corresponds to map the \(\mathbb {R}^{n}\) solutions in [0,1]n solutions. Two types of functions have been used in the literature, the S-shaped [76], and V-shaped [17]. The Second Step is to apply a binarization rule to the result of the transfer function. Examples of binarization rules are complement, roulette, static probability, and elitist [17].

In [35], this framework was used to optimize sizing of Capacitor Banks in Radial Distribution Feeders. In [59], transfer functions were used for the analysis of bulk power systems. This approach has also been used to solve the set covering problem using Binary Firefly Algorithm [17]. Soto et al. [65] used Cuckoo Search Algorithm applied to the set covering problem. To solve the unit commitment problem Yang et al. in [76] used Firefly and PSO algorithms. The knapsack crystosystem was approached in [50]. Network and reliability constrained problems were solved in [11] and the Knapsack problem was solved by Zhang et al. [80] all using using Firefly algorithm.

Angle modulation

This method uses the trigonometric function shown in (4). This function has four parameters which control the frequency and shift of the trigonometric function.

$$ g_{i}(x_{j}) = \sin(2\pi(x_{j}-a_{i})b_{i}\cos(2\pi(x_{j}-a_{i})c_{i}))+d_{i} $$
(4)

This method was first applied in PSO, using a set of benchmark functions. Let a binary problem of n-dimension, and X = (x 1,x 2,...x n ) a solution. We start with a four dimensional search space. Each dimension represents a coefficient of the (4). Then every solution (a i ,b i ,c i ,d i ) is associated to a g i trigonometric function. For each element x j the rule (5) is applied:

$$ b_{ij} = \left\{\begin{array}{ll} 1 &\text{if } g_{i}(x_{j}) \ge 0 \\ 0 & \text{otherwise} \\ \end{array}\right. $$
(5)

Then for each initial 4-dimension solution (a i ,b i ,c i ,d i ), we get a binary n-dimension solution (b i1,b i2,...,b i n ). This is a feasible solution of our n-binary problem. The Angle modulate technique has been applied to network reconfiguration problems [44] using a binary PSO method, to multi-user detection technique [66] using a binary adaptive evolution algorithm, and to the antenna position problem using a angle modulate binary bat algorithm [77].

Quantum binary approach

In the line of research that involves the areas of Evolutionary Computing (EC) and Quantum Computing, there are three categories of algorithms [79]

  1. 1.

    Quantum evolutionary algorithms: These algorithms focus on the application of EC algorithms in a quantum computing environment.

  2. 2.

    Evolutionary-designed quantum algorithms: These algorithms try to automate the generation of new quantum algorithms using Evolutionary Algorithms.

  3. 3.

    Quantum-inspired evolutionary algorithms: These algorithms concentrate on the generation of new EC algorithms using some concepts and principles of Quantum Computing.

In particular the Quantum Binary Approach, belongs to Quantum-inspired evolutionary algorithms. In this sense these algorithms adapt the concepts of q-bits and superposition to work on normal computers.

In the quantum binary approach method, each feasible solution has a position X = (x 1,x 2,..,x n ) and the quantum q-bits vector Q = [Q 1,Q 2,...,Q n ]. Q represents the probability of x j take the value 1. For each dimension j, a random number between [0,1] is generated and compared with Q j , if r a n d < Q j , then x j = 1, else x j = 0. The upgrade mechanism of Q vector is specific to each metaheuristic.

The Quantum Swarm optimization algorithm has been applied to a combinatorial optimization in [69], cooperative approach in [81], knapsack problem in [63], and power quality monitor in [31]. The Quantum Differential Evolution algorithm was applied to the knapsack problem in [30], combinatorial problems [3], and image threshold methods in [18]. Using Cuckoo search metaheuristic a Quantum algorithm was applied to the knapsack problem [38], and bin packing problem [40]. A Quantum Ant Colony Optimization was applied to image threshold in [18]. Using Harmony Search in [39], and Monkey algorithm in [84], quantum binarizations were applied to the knapsack problem.

The general binarization frameworks have the difficulty of producing Spacial Disconnect [41]. The Spacial Disconnect, occurs when close solutions generated by metaheuristics in the continuous space, are not converted into close solutions in discrete space. Informally we can think in a loss of framework continuity. This phenomenon of Spacial Disconnect has the consequence that the properties of exploration and exploitation are altered and therefore the precision and convergence of the metaheuristic worsen. A study of how transfer functions affect exploration and exploitation properties was developed in [60]. For Angle Modulation the study was developed in [41].

On the other hand, specific binarization algorithms, which modify the operators of the metaheuristic, are susceptible to problems such as Hamming cliffs, loss of precision, search space discretization and the curse of dimension [41]. This was studied by Pampara in [51] and for the particular case of PSO by Chen in [13]. In the investigation of Chen, he observed that the parameters of the Binary PSO change the speed behavior of the original metaheuristic.

In this article, a k-means binarization framework is proposed which does not modify the original metaheuristic. The main operator of this framework, establishes a relation between the displacement of particles in the continuous space and the transition of probability in the discrete space. This relationship is established through the clustering of the displacements. To each group generated by clustering a transition probability is assigned. With this mechanism, it is expected that the exploration and exploitation properties will not be altered, and therefore to observe good results of convergence and precision of the binarized algorithms in the resolution of combinatorial problems.

4 k-means transition ranking framework

The Proposed KMTR framework has four main modules. The first module corresponds to the initialization of the feasible solutions (Section 4.1). Once the initialization of the particles is performed, it is consulted if the detention criterion is satisfied. This criterion includes a maximum of iterations. In the case that the optimal solution is known, this is also included as stopping criterion. Subsequently if the criterion is not satisfied, the transition ranking operator is executed (Section 4.2). This module is responsible for performing the iteration of solutions. Once the transitions of the different solutions are made, we compare the resulting solutions with the best solution previously obtained. In the event that a superior solution is found, this replaces the previous one. When a replacement occurs, the new solution is subjected to a local search operator. This operator corresponds to our third module (Section 4.4). Finally, having met a number of iterations where there has not been a replacement for the best solution, a perturbation operator is used (Section 4.5). The general algorithm scheme is detailed in Fig. 1.

Fig. 1
figure 1

Flowchart of general framework of k-means transition ranking algorithm

Full size image

4.1 Initialization and element weighting

KMTR framework uses a binarization of population-based metaheuristics to try to find the optimum. Each of these possible solutions, is generated as follows: First we select an item randomly. Subsequently we consulted the constraints of our problem if there are other elements that can be incorporated. The list of possible elements to be incorporated is obtained, the weight for each of these elements is calculated and the best element is selected. The procedure continues until no more elements can be incorporated. The initialization algorithm is detailed in Fig. 2.

Fig. 2
figure 2

Flowchart of generation of a new solution

Full size image

Several techniques were proposed in the literatures, to calculate the weight of each element. For example [55] introduced the pseudo-utility in the surrogate duality approach. The pseudo-utility of each variable was given in (6). The variable w j is the surrogate multiplier between 0 and 1 which can be viewed as shadow prices of the j-th constraint in the linear programming(LP) relaxation of the original MKP

$$ \delta_{i} = \frac{p_{i}}{{\sum}_{j=1}^{m} w_{j}c_{ij}} $$
(6)

Another more intuitive measure is proposed by [36]. This measure is focused on the average occupancy of resources. Its equation is shown in (7).

$$ \delta_{i} = \frac{{\sum}_{j=1}^{m} \frac{c_{ij}}{mb_{j}}}{p_{i}} $$
(7)

In this paper, we propose a variation of this last measure focused on the average occupation. However this variation considers the elements that exist in backpacks to calculate the average occupancy. In each iteration depending on the selected items in the solution the measure is calculated again. The equation of this new measure is shown in (8).

$$ \delta_{i} = \frac{{\sum}_{j=1}^{m} \frac{c_{ij}}{m (b_{j} - {\sum}_{i \in S}c_{ij})}}{p_{i}} $$
(8)

4.2 k-means transition ranking operator

Consider that our metaheuristic is continuous and population based. Due to its iterative nature, it needs to update the position of particles at each iteration. When the metaheuristic is continuous, this update is performed in \(\mathbb {R}^{n}\) space. In (9), the update position is presented in a general manner. The x t+1 variable represents the x position of the particle at time t+1. This position is obtained from the position x at time t plus a Δ function calculated at time t+1. The function Δ is proper to each metaheuristic and produces values in \(\mathbb {R}^{n}\). For example in Cuckoo Search Δ(x) = α ⊕ L e v y(λ)(x), in Black Hole Δ(x) = rand × (x b h (t) − x(t)) and in the Firefly, Bat and PSO algorithms Δ can be written in simplified form as Δ(x) = v(x).

$$ x_{t+1} = x_{t} + {\Delta}_{t+1}(x(t)) $$
(9)

In the k-means transition ranking operator, a model for transitions in a discrete space is proposed. This model is based on considering the movements generated by the metaheuristic in each dimension for all particles. Δi(x) corresponds to the magnitude of the displacement Δ(x) in the i-th position. Subsequently these displacement are grouped using the magnitude of the displacement Δi(x). This grouping is done using the k-means technique where k represents the number of clusters used. Finally, a generic P t r function given by the (10) is proposed to assign a transition probability.

$$ P_{tr}: \mathbb{Z}/k\mathbb{Z} \rightarrow [0,1] $$
(10)

A transition probability through the function P t r is assigned to each group. Naturally, this P t r function is modelled as a cumulative probability function. For the case of this study, we particularly use the linear function given in (11). In this equation, N(x i) indicates the location of the group to which Δi(x) belongs. The α coefficient, corresponds to the transition probability and β to the transition separation coefficient. Both parameters are estimated in each metaheuristic. For our particular case, N(x i) = 0 corresponds to elements belonging to the group that has the lowest Δi values. N(x i) = 7 corresponds to the group of elements that have the greatest Δi values.

$$ P_{tr}(x^{i})= P_{tr}(N(x^{i})) = \alpha + \beta N(x^{i})\alpha $$
(11)

The algorithm flow chart is described in Fig. 3, and an illustration is shown in Fig. 4. The k-means transition ranking operator starts calculating Δi for each of the particles. This step is specific in each metaheuristic. Subsequently the particles are grouped using k-means clustering technique and the magnitude of Δi as distance. With the group assigned to each particle we obtain the probability of transition using (11). Afterwards the transition of each particle is performed. In the case of Cuckoo search the rule (13) is used to perform the transition, where \(\hat {x}^{i}\) is the complement of x i. For the Black Hole the rule (12) is used, where \(x_{bh}^{i}\) is the position of the best solution obtained after the last perturbation. Finally, each solution is repaired using the repair operator shown in Algorithm 1.

$$ x^{i}(t+1) := \left\{\begin{array}{ll} x_{bh}^{i}(t) , &\text{if } rand < P_{tg}(x^{i}) \\ x^{i}(t) , & \text{otherwise} \\ \end{array}\right. $$
(12)
$$ x^{i}(t+1) := \left\{\begin{array}{ll} \hat{x}^{i}(t) , &\text{if } rand < P_{tg}(x^{i}) \\ x^{i}(t) , & \text{otherwise} \\ \end{array}\right. $$
(13)
Fig. 3
figure 3

Flowchart of transition ranking operator

Full size image
Fig. 4
figure 4

Mapping the continuous search space to a discrete search space

Full size image

4.3 Repair operator

In each movement performed by operators: transition ranking , local search and perturbation, it is possible to generate solutions that are infeasible. Therefore, each candidate solution must be checked and modified to meet every constraint. This verification and subsequent repairing is performed using the measure defined in Section 4.1 (8). The procedure is shown in Algorithm 1. As input the repair operator receives the solution S i n to repair, and the output of the repair operator gives the repaired solution S o u t . As a first step, the repair algorithm asks whether the solution needs to be repaired. In the case that the solution needs repair, a weight is calculated for each element of the solution using the measure defined in (8). The element of the solution with the largest measure is returned and removed from the solution. This element is named s m a x . This process is iterated until our solution does not require repair. The next step is to improve the solution. The (8) is again used for obtaining the element with the smallest measure that meets the constraints s m i n and add s m i n to the solution. In the case of absence of elements, empty is returned. The algorithm iterates until there are no elements that satisfy the constraints.

figure a

4.4 Local search operator

When the algorithm KMTR finds a solution having a fitness value higher than the best solution obtained until now, KMTR makes a call to the local search operator. This algorithm aims to perform a local search to improve the quality of the solution. The main idea of the local search operator is to add an element of the ones that are not in the solution, then to perform the repair of the solution using the repair operator. Finally it is evaluated if a better solution is obtained. To this new solution (S), another element of the complement is added, repeating the repair and comparison operations. This is iterated until incorporated all elements that were not in the initial solution. Subsequently we consider again our initial solution (S i n ), An element is removed from it, then the solution(S) is repaired and compared. In this case, it is iterated over all elements of the solution. The pseudo-code is shown in Algorithm 2.

figure b

4.5 Perturbation operator

The k-means transition ranking operator is responsible for performing the movements to find the optimum. However our algorithm can get trapped in a local optimum. To exit out of this local deep optimum, the transition ranking operator is complemented by a perturbation operator. This perturbation operator makes η ν random deletions. Later the perturbed solution is completed using the repair operator. The number η ν is obtained by considering the total length of the solution and multiplying by the factor ν. This factor ν is a parameter of the algorithm and must be estimated . This parameter controls the strength of the perturbation. This perturbation is applied to the x b e s t and to the list of feasible solutions. The procedure is outlined in Algorithm 3

figure c

5 Results

For an adequate evaluation of our framework, we present computational results of 270 instances of the OR-library [8]. As a starting point, the methodology for obtaining the parameters of metaheuritics and binarization is detailed. Later the analysis of the key ingredients of our framework is developed. Finally, comparisons were made with recently published algorithms that use transfer functions and Quantum approach as binarization techniques. To perform the statistical analysis in this study, the non-parametric test of wilcoxon signed-rank test and violin charts are used. The violin chart is a combination of Box Plot and Kernel Density Plot widely used in machine learning and data mining [4, 28, 32]. The analysis is performed by comparing the dispersion, median and the interquartile range of the distributions.

Benchmark instances

The problems were generated by varying the number of constraints m ∈{5,10,30} and the number of elements n ∈{100,250,500}. For each condition (n, m) 30 problems were generated. Each set of 30 problems is divided into groups associated with the capabilities b i where \(b_{i}= t\times {\sum }_{j\in N} a_{ij}\) . t ∈{0.25,0.5,0.75} corresponds to the tightness ratio. Each problem group used the following cb.n.m nomenclature. Where n corresponds to the total number of elements, and m the number of constraints.

For the execution of the instances we use a PC with windows 10, Intel Core i7-4770 processor with 16GB in RAM, and programmed in Python 2.7. The techniques used in the binarization were Black Hole and Cuckoo search which were named KMTR-BH and KMTR-Cuckoo respectively.

5.1 Parameter setting

As a starting point, we describe the methodology used to perform the estimation of parameters for each of the metaheuristics used. The parameters settings are shown in Tables 1 and 2. The Value column indicates the final value used by the parameter. The Range column indicates the scanned values to obtain the final setting. To perform the scan settings, three problems were chosen for each of the groups cb.100.5, cb.250.5, cb.500.5, cb.100.10, cb.250.10,cb.500.10, cb.100.30, cb.250.30,cb.500.30. In each problem and configuration, the KMTR algorithm was executed 10 times for each metaheuristics and combination. Four measures were defined for the setting selection of the algorithm.

Table 1 Setting of parameters for black hole algorithm
Full size table
Table 2 Setting of parameters for cuckoo search algorithm
Full size table
  1. 1.

    The percentage deviation of the best value obtained in the ten executions compared with the best known value, see (14)

    $$ bSolution = 1- \frac{KnownBestValue - BestValue}{KnownBestValue} $$
    (14)
  2. 2.

    The percentage deviation of the worst value obtained in the ten executions compared with the best known value, see (15)

    $$ wSolution = 1- \frac{KnownBestValue - WorstValue}{KnownBestValue} $$
    (15)
  3. 3.

    The percentage deviation of the average value obtained in the ten executions compared with the best known value, see (16)

    $$ aSolution = 1- \frac{KnownBestValue - AverageValue}{KnownBestValue} $$
    (16)
  4. 4.

    The convergence time for the best value in each experiment normalized according to the (17)

    $$ nTime = 1- \frac{convergenceTime - minTime}{maxTime -minTime} $$
    (17)

Because we have four distinct measures, we used the area of the radar charts to evaluate the best performance configuration. Radar charts are widely used in data mining and bioinformatic [2, 67]. Each axis of the chart corresponds to one of the measures defined above. These measures take values between 0 and 1 where 1 is the best value that can be obtained. Therefore the comparison between the different configurations is the area that contains the results of the four measures. The larger the area, the better the associated configuration performs. In Fig. 5 the four best configuration results are shown as an example for the KMTR-BH algorithm.

Fig. 5
figure 5

Radar graphics examples for the black hole configuration

Full size image

5.2 Insight of KMTR framework

In this section we investigate some important ingredients of KMTR to get insight into the behavior of the proposed algorithm. To carry out this comparison the first 10 problems of the set cb.5.250 of the OR library and KMTR-BH were chosen. The contribution of operators perturbation, k-means transition ranking and local search on the final performance of the algorithm was studied. To compare the distributions of the results of the different experiments we use a violin chart. The horizontal axis corresponds to the problems. The Y axis uses the measure % - Gap defined in (18)

$$ \%-Gap = 100\frac{Best Known - SolutionValue}{Best Known} $$
(18)

Furthermore, a non-parametric Wilcoxon signed-rank test is carried out to determine if the results of KMTR with respect to other algorithms have significant difference or not.

5.2.1 Evaluation of the element weighting

To evaluate the contribution of the element weighting to the performance of the algorithm we compared the KMTR-BH algorithm which includes Dynamic Average Occupancy given in (8) with KMRT-BH-AO algorithm which uses the average occupancy given in (7). The results are shown in Table 3 and in Fig. 6. The table shows that for both the best value and the average KMTR-BH is higher than KMTR- BH-AO. In Fig. 6, distributions of results are compared. It is observed that the dispersions are quite similar, however in the interquartile ranges KMTR-BH is superior in most cases. The Wilcoxon test indicates that this difference is significant therefore in the following experiments the Dynamic Average Occupancy will be used as element weight.

Fig. 6
figure 6

Evaluation of element weighting

Full size image
Table 3 Evaluation of element weighting
Full size table

5.2.2 Evaluation of perturbation operator

This section aims to investigate the contribution of perturbation operator in the result of our KMTR-BH algorithm. To do this research, the KMTR-BH algorithm is configured without the perturbation operator. This algorithm is denoted by KMTR-BH-wp. The KMTR-BH-wp algorithm is compared with our perturbation operator version KMTR-BH. In both cases default parameters are used (Section 5.1). The results are shown in Table 4 and Fig. 7.

Fig. 7
figure 7

Evaluation of perturbation operator

Full size image
Table 4 Evaluation of perturbation operator
Full size table

When we compare the results of the Table 4. We note that KMTR-BH is consistently better to obtain best values and averages than KMTR-wp. A Wilcoxon statistical test is performed to determine the difference between distributions of averages of both algorithms. The result indicates the distributions of the averages differ (p − v a l u e s < 0.05). The results of the difference between the distributions are shown in Fig. 7. In the violin chart, the median value and the interquartile range of KMTR-BH-wp are displaced toward larger values of the %-Gap indicator. This suggests that the perturbation operator contributes to get better values. Moreover when we observe the dispersion of the distributions, it is observed that only problems 1 and 3, KMTR-BH-wp have a greater dispersion than the KMTR-BH case.

5.2.3 Evaluation of k-means transition ranking operator

To evaluate the contribution of the k-mean transition ranking operator to the final result we designed a random operator. This random operator executes the transition with a fixed probability (0.5) without considering the ranking of the particle. Two scenarios were established. In the first one the perturbation and local search operators are included. In the second one these operators are excluded. KMTR-BH corresponds to our standard algorithm. 05.pe is the random variant that includes the perturbation and local search operators. wpe corresponds to the version with k-means transition operator without perturbation and local search operators. Finally 05.wpe describes the random algorithm without perturbation and local search operators.

When we compared the Best Values between KMTR-BH and 05.pe algorithms in Table 5. KMTR-BH outperforms to 05.pe except for problem 7. However the Best Values between both algorithms are very close. In the Averages comparison, KMTR outperforms 05.pe in all problems.

Table 5 Evaluation of k-means transition operator
Full size table

The comparison of distributions is shown in Fig. 8. We see the dispersion of the 05.pe distributions are bigger than the dispersions of KMTR. In particular this can be appreciated in the problems 3, 4, 5, 6 and 7. Then, the k-means transition ranking operator together with perturbation operators and local search contribute to the stability of the solution. Also, the KMTR distributions are closer to zero than 05.pe distributions, indicating that KMTR has a better performance than 05.pe.

Fig. 8
figure 8

Evaluation of k-means transition operator with perturbation and Local Search operators

Full size image

Our next step is trying to separate the contribution of local search and perturbation operator from the k-mean transition operator. For this, we compared the algorithms wpe and 05.wpe.

When we check the Best Values shown in the Table 5, We see that the wpe and random 05.wpe algorithms obtain similar results for the best indicator. However 05.wpe slightly outperforms wpe in some cases. When we compare the Averages, the situation is reversed obtaining a clear supremacy of wpe by about 05.wpe. Even more, when we compare the distributions shown in Fig. 9 we see that wpe has solutions dispersion much smaller than 05.wpe.

Fig. 9
figure 9

Evaluation of k-means transition operator without perturbation and local search operators

Full size image

5.2.4 Evaluation of local search operator

This section aims to understand the contribution of the local search operator on the final result in the optimal tracking. Again the comparison was made with the first 10 instances of the cb.5.250 group and the binarization of the Black Hole algorithm was used. We compared the KMTR-BH algorithm with the modified algorithm which did not execute the local search. To this modified algorithm, it was denoted by KMTR-BH-WLS. In the Table 6, the comparison is shown. KMTR-BH shows higher results than KMTR-BH-WLS for the Best Value and Average indicators in all tests. The statistical verification using the Wilcoxon signed rank test indicates that this difference is significant between both algorithms. When we compared the distributions through the graphic violin Fig. 10, we see that in general the distributions have similar dispersion ranges. However, the distributions of KMTR-BH-WLS are shifted towards greater values of %-Gap than in the case of KMTR-BH. This indicates that the contribution of our perturbation operator is to improve the final values, without affecting the dispersion of the solutions.

Fig. 10
figure 10

Evaluation of k-means transition operator without local search operator

Full size image
Table 6 Evaluation of local search operator
Full size table

5.3 KMTR framework comparisons

In this section, we describe the comparisons that were made of our framework with other recently published algorithms. Three groups of problems were chosen for the comparison. cb.5.500, cb.10.500 y cb.30.500 correspond to the larger problems of the OR-library. The first algorithm corresponds to Binary Artificial Algae Algorithm (BAAA) developed by Zhang [80]. This algorithm uses V-shape transfer function as a binarization mechanism. The set of problems cb.5.500 was used for comparison. The second algorithm is a Binary differential search algorithm (BDS) developed by Liu [43]. This algorithm also uses a V-shape transfer function as a binarization mechanism. The set of problems cb.10.500 was used for comparison. Finally, in the third comparison a Hybrid Quantum Particle Swarm Optimization (QPSO*) developed by Haddar [27] was used to compare the cb.30.500 group. The comparisons were made using the Best value indicator, which corresponds to the best value obtained by the algorithm in the different executions and the Average indicator which corresponds to the average of the results obtained considering all executions. For clarity of the comparisons between the algorithms, Table 7 is incorporated. This table summarizes the results of best values and averages, where the comparisons are made considering the algorithms in pairs. In the case that both algorithms have the same value, this is not considered in the accounting.

Table 7 Summary of comparisons
Full size table

5.3.1 Comparison with BAAA

In this section we evaluate the performance of our KMTR-framework with the algorithm BAAA developed in [80]. BAAA uses transfer functions as a general mechanism of binarization. In particular BAAA used the \(\tanh = \frac {e^{\tau |x|}-1}{e^{\tau |x|}+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 KMTR-framework, the configurations are the same used in the previous experiments. These are described in the Tables 1 and 2. In addition, in order to determine if KMTR average is significantly different than averages obtained by BAAA, we have performed Student’s t-test. The t statistic has the following form:

$$ t = \frac{\hat{X_{1}}- \hat{X_{2}}}{\sqrt{\frac{(n_{1}-1)S{D_{1}^{2}} + (n_{2}-1)S{D_{2}^{2}}}{n_{1}+n_{2}-2} \frac{n_{1}+n_{2}}{n_{1}n_{2}}}} $$
(19)

Where:

  • \(\hat {X_{1}}\): Average of BAAA for each instance

  • S D 1: Standard deviation of BAAA for each instance

  • n 1: number of test for BAAA for each instance

  • \(\hat {X_{2}}\): Average of KMTR-BH or KMTR-Cuckoo for each instance

  • S D 2: Standard deviation KMTR-BH or KMTR-Cuckoo for each instance

  • n 2: number of test for KMTR-BH or KMTR-Cuckoo for each instance

The t values can be positive, neutral, or negative. The double positive value (+ +) of t indicates that KMTR is significantly better than BAAA. In the opposite case (−−), KMTR obtains significant worse solutions. If t is single positive (+ ), KMTR shows to be better but not significantly. On the other hand, if the result is single negative (−), KMTR demonstrates to be worse, but not in a significant way. Finally, a neutral value of t depicts equality in the results. We stated confidence interval at the 95% confidence level. For the case of comparative summary shown in Table 7, we consider only the results that have significance.

The results are shown in Table 8. The comparison was performed for the set cb.5.500 of the OR-library. The results for KMTR-BH and KMTR-Cuckoo were obtained from 30 executions for each problem. In black, the best results are marked for both indicators the Best Value and the Average. We must emphasize that although BAAA has quite good results, KMTR-BH and KMTR-Cuckoo exceed it in practically all problems. In the Best Value indicator, BAAA was higher in three instances, KMTR-BH in 15 and KMTR-Cuckoo in 13. It should be noted that in instance 4 KMTR-BH and KMTR-Cuckoo obtained the same value. In the averages indicator BAAA was higher in 1 instance, KMTR-BH in 15 and KMTR-Cuckoo in 14.

Table 8 OR-Library benchmarks MKP cb.5.500
Full size table

By observing the execution times, we see that Cuckoo has better runtime than BH. Inquiring about the causes of this difference, a sampling of the displacements (Δ) of both metaheuristics was considered. With these sampling, histograms were constructed to quantify the amount of displacements assigned to the different transition groups obtained by k-means. The result is shown in Fig. 11. In the case of Black Hole, the distribution of transition groups is far more homogeneous than in Cuckoo. In Cuckoo most of the transitions are concentrated in the first 3 groups. This property has as a consequence that Cuckoo has fewer transitions than BH.

Fig. 11
figure 11

Transition group histograms

Full size image

Finally we compare KMTR-BH y KMTR-Cuckoo. For comparison, we organized the problems into three groups 0 to 9, 10 to 19 and 20 to 29. The Wilcoxon test shown in Table 8 and violin charts shown in Fig. 12 were used for comparison. In all three groups there are differences between distributions, KMTR-BH obtained better solutions for the first group and KMTR-Cuckoo in the second. Although the Wilcoxon test and the transition histograms shown in Fig. 11 indicates that the distributions of the KMTR-BH and KMTR-Cuckoo results are different, when we observe the distributions in detail with the violin graph, we observe that they are similar in form, values and dispersion. The main differences that distinguish both distributions correspond to the median values and interquartile range.

Fig. 12
figure 12

Comparison between KMTR-BH and KMTR-Cuckoo for cb.5.500 instances

Full size image

5.3.2 Comparison with DBS

In this section we evaluate the performance of our KMTR-framework with the algorithms TR-DBS (Tanh Random) and TE-DBS (Tanh Elitist) developed in [43]. DBS uses transfer functions as a general mechanism of binarization. In particular DBS used the \(\tanh = \frac {e^{\tau |x|}-1}{e^{\tau |x|}+1}\) function to perform the transference. The parameter τ of the tanh function was set to a value 2.5. As maximum number of iterations DBS used 10000. All computational experiments were conducted in Matlab 7.5 on a PC equipped with an Intel Pentium Dual-Core i7-4770 processor (3.40 GHz) with 16GB of RAM in the Windows OS. In our KMTR-framework, the configurations are the same used in the previous experiments. These are described in the Tables 1 and 2.

The results are shown in Table 9. The comparison was performed for the set cb.10.500 of the OR library. The results for KMTR-BH and KMTR-Cuckoo were obtained from 30 executions for each problem. The best results for the Best Value and Average indicators are marked in black.

Table 9 OR-Library benchmarks MKP cb.10.500
Full size table

When we compare the four algorithms, we see that TE-DBS obtained the biggest amount of Best Values with a total of 20 of the 30 problems. It was followed by KMTR-Cuckoo with 7, then TR-DBS with 3 and KMTR-BH with 0. When the average indicator is analyzed, the situation is different. KMTR-Cuckoo obtained 12, then TE-DBS with 9, KMTR-BH with 7 and finally TR-DBS with 4. When we compare the Average indicator by groups of problems, where group 1 corresponds to problems 0-9, group two problems 10-19 and group 3 problems 20-29, KMTR-Cuckoo scored better in Groups 2 and 3 for both Best Value and Average, TE-DBS for Best Value in Group 1 and KMTR-BH for Group 1 in Average indicator. This indicates that although the TR-DBS and TE-DBS algorithms obtain high Best Values, these algorithm are not consistent in obtaining them, considering that the number of maximum iterations is 10000. The average execution times in TR-DBS and TE-DBS cases are over 5000 (s) and 6000 (s) respectively, where KMTR-BH and KMTR-Cuckoo are below 600(s). The calculation was made on equivalent computers.

Finally we compare KMTR-BH and KMTR-Cuckoo, considering the three previously defined groups. The Wilcoxon test shown in Table 9 and violin charts shown in Fig. 13 were used for comparison. In all three groups there are differences between distributions, KMTR-BH obtained better solutions for the first group and KMTR-Cuckoo in the second and third groups. Although the Wilcoxon test indicates that the distributions of the KMTR-BH and KMTR-Cuckoo results are different, when we observe the distributions in detail with the violin graph, we observe that they are similar in form, values and dispersion. The main differences that distinguish both distributions correspond to the median values and interquartile range.

Fig. 13
figure 13

Comparison between KMTR-BH and KMTR-Cuckoo for cb.10.500 instances

Full size image

5.3.3 Comparison with QPSO*

In this section, we compare the performance of our KMTR-framework with the Quantum PSO (QPSO*) algorithm developed by [27]. This QPSO* algorithm additionally uses a local search method and a repair algorithm based on the notion of the pseudo-utility ratio. The algorithm was coded in C language, and experimental tests were performed on a Personal Computer with a 2.2 GHz Core 2 Duo processor and 3GB RAM. The number of iterations were 500, and the number of executions were 30. For our framework, the configuration was the same used in the previous experiments, described in the Tables 1 and 2.

The comparison was made using the set of problems cb.30.500 from the OR-library. The results are shown in the Table 10. In this case the superiority of QPSO* compared to our binarizations was complete in both indicators, Best Value and Average. Considering groups 0-9,10-19 and 20-29, we calculate the difference between QPSO* and our binarizations, for the Best Value and Average indicators. The maximum difference corresponds to group 1, where the comparison of the QPSO* Best Value indicator with KMTR-BH has a 0.43% deviation and KMTR-Cuckoo a 0.37%. For the case of the average indicator, group 1 obtained the difference of 0.46% for KMTR-BH 0.43% for KMTR-Cuckoo. In group 2, the differences for the Best value were 0.20 and 0.16. For the Average differences were 0.22% and 0.21% respectively. Finally for group 3 the differences in the Best Value were of 0.1% and 0.09%. For the average, 0.14% and 0.13%.

Table 10 OR-Library benchmarks MKP cb.30.500
Full size table

When we compared KMTR-BH and KMTR-Cuckoo, the results of the test Wilcoxon shown in the Table 10, indicate that there are differences between them. In the Fig. 14, their distributions are compared. It is observed that the difference is mainly due to the values of their medians and interquartile ranges. The dispersion and the shape of the distributions are similar in both binarizations.

Fig. 14
figure 14

Comparison between KMTR-BH and KMTR-Cuckoo for cb.30.500 instances

Full size image

5.3.4 Other comparisons

Finally, in the Table 11, the results are summarized for the 270 instances of OR-library, solved by the binarizations KMTR-BH and KMTR-Cuckoo. In addition to these results, we added Table 12. It is a comparative of different techniques that have solved the OR-library problems. We consider the results of the hyper-heuristic (CF-LAS, 2016) developed in [19], CPLEX (IBM, 2014) [48], which is a general-purpose mixed-integer programming (MIP) package used to solve linear optimisation problems. A Genetic Algorithm developed by Chu and Beasley [15], other Genetic algorithm developed by Raidl [56], and a Memetic algorihtm reported in [49].

Table 11 Detailed performance of KMTR-BH and KMTR-Cuckoo on OR-Library instances (based on average %-Gap)
Full size table
Table 12 Detailed performance of KMTR-BH and KMTR-Cuckoo on OR-Library instances (based on average %-Gap)
Full size table

Both k-means binarizations outperform the other methods. The average results for KMTR-BH was 0.24 and for KMTR-Cuckoo of 0.22. Regarding the mean times KMTR-BH obtained 245.6(s) and KMTR-Cuckoo 205.7(s). The configuration of the algorithms was the same as in previous executions. Every problem was executed in 30 instances.

6 Conclusion and future work

In this article, we proposed a framework whose main function is to binarize continuous population-based metaheuristics. the performance of our framework, and the multidimensional knapsack problem was used together with the Cuckoo Search and Black Hole metaheuristics. The contribution of the different operators of the framework was evaluated, finding that the k-means transition ranking operator contributes significantly to improve the precision of the solutions. Moreover the operators Perturbation and Local Search help to improve the quality and precision of the solutions. Finally, in comparison with state of the art algorithms our framework showed a good performance.

In future works we want to investigate the behaviour of other metaheuristics in the framework. Furthermore, the framework must be verified with other NP-hard problems. Moreover, to simplify the choice of the appropriate configuration, it is important to explore adaptive techniques. From an understanding point of view of how the framework performs binarization, it is interesting to understand how the framework alters the properties of exploration and exploitation. It is also interesting to study how the velocities and positions generated by continuous metaheuristics are mapped to positions in the discrete space. Finally, we wish to explore the possibility of adapting concepts of Quantum computing to incorporate them within the framework.