2.1. 0–1 knapsack problem

0–1KP is one of the most intensively studied combinatorial optimization problem ⁶⁶. The researches of 0–1 knapsack problem have very large potential application background for capital budgeting problems, resource allocation, loading problems, project selection problems and so on ⁶⁷. The 0–1 knapsack problem can be generally described as follows: Given N objects, from which various possible objects will be selected to fill up a knapsack. Then, if p_j is a measure of the value given by object j, w_j its weight and c the capacity of the knapsack. The objective is to maximize the total value of the knapsack that the knapsack capacity constraint is satisfying. Formally, the problem can be formulated as follows:

2.2. Cuckoo search

CS ⁴¹ is one of bio-inspired algorithms for imitating the brood parasitism of some cuckoo species. Because of the complexity of natural systems, they cannot be built models exactly through computer algorithm in its basic form. In order to successfully apply this as optimization method, Yang and Deb ⁴¹ used the following three approximate rules:

1. (1)

   Each cuckoo lays only one egg at a time, and dumps its egg in a randomly chosen nest;

2. (2)

   The best nests with high-quality eggs will be carried over to the next generations;

3. (3)

   The number of available host nests is fixed, and the egg laid by the host bird with a probability p_a∈[0, 1]. In this case, the host bird can either throw the egg away or simply abandon the nest and build a completely new nest.

Based on these three rules, the basic steps of the CS are shown in Algorithm 1.

Begin

Step 1: Initialization. Set the discovery rate (pa); initialize the population of n host nests randomly and each egg in a nest corresponding to a potential solution to the given problem; Set stopping criterion or the generation counter (G=1).

Step 2: Generate new solutions x′ (but keep the current best), the procedure works as follows:

  for i=1 to d do

    xi′ = xi′ + α ⊕ Levy(λ)

    if (rand<pa) then

      xi′ = xi′+rand* (xr1 − xr2)

    endif

  end for

    where xi (i=1, 2,..., d) is the ith component of x′ and rand∼ U(0,1).

Step 3: Keep best solutions; Rank the solutions and find the current best (xbest, f(xbest))

Step 4: Check the stopping criterion. If the stopping criterion (maximum number of iterations G) is satisfied, computation is terminated. Otherwise, step 2 is repeated.

End.

2.3. The global-best harmony search

Harmony search (HS) ^43,68, as a relatively effective optimization technique, the optimization process is generally handled by three rules: memory consideration, pitch adjustment and random selection. The three key parameters which have a far-reaching effect on the performance of the HS are harmony memory consideration rate (HMCR), pitch adjustment rate (PAR), and distance bandwidth (bw). Additionally, the parameters also include harmony memory size (HMS), the number of improvisations (NI). In this paper, we employ GHS ⁴⁸ as a mutation operation to ensure convergence of the CSGHS and enhance its ability of optimization effectively. The GHS is presented in Algorithm 2.

Begin

Step 1: Initialize the HM. Set parameters HMS, HMCR, PAR, NI.

Step2: Improvise a new harmony: the new harmony vector x′ = (x1′, x2′,..., x′d) is generated as follows:

  for i =1 to d do

    if (rand ≤ HMCR) then //memory consideration

      xi′ = xij, where j∼ U (1, ... , HMS).

      if rand ≤ PAR then //pitch adjustment

        xi′ = xibest, where best is the index of the best harmony

      end if

    else //random selection

      xi′ =LBi +r× (UBi − LBi), where r∼ U(0,1), rand∼ U(0,1)

    end if

  end for

Step 3: Update harmony memory: if f (x′) < f (xworst), xworst = x′. (minimization objective)

  Update the best harmony vector.

Step 4: Check the stopping criterion. If the stopping criterion is satisfied, computation is terminated.

Otherwise, step 2 is repeated.

End.

3.1. Encoding scheme

It is generally known that the 0–1 knapsack problem is a special integer linear programming problem. Additionally, from formula (1), we can infer that the feasible solution of 0–1 knapsack problem is n-dimension 0–1 vector. Hence, the individual was naturally represented by binary coding. Since the standard CS algorithm operates in continuous space, we cannot use it directly for solving optimization problems in binary space. So hybrid encoding scheme ^{55, 69} was used for solving 0–1 knapsack problem with CSGHS. The formal description is as follows. Let two-tuples<X_i, Y_i> represent the ith cuckoo individual, where X_i = x_i1, x_i2,..., x_id) ∈[−3.0, 3.0]^d, and Y_i = (y_i1, y_i2,..., y_id) ∈{0,1}^d. Sigmoid function is used to create a mapping between X_i and Y_i. The conversion from d-dimensional real-valued vector to d-dimensional binary vector is as follows:

3.2. Repair operator

The 0–1 knapsack problem is also a constraint optimization problem. So constraint handling technique must be employed in order to handle the infeasible solution. Nowadays the more popular constraint handling technique is penalty function method and individual optimization method. In this paper, we adopt an effective greedy transform method (GTM) ⁵⁵ to modify the infeasible solution as well as optimize the feasible solution.

3.3. The proposed approach: CSGHS

In this section, we will give a reasonable explanation for how and why we combine the GHS with CS to form an effective CSGHS, which not only improves the quality of the solutions, but also increases the diversity of the population, and then the efficiency of the algorithm is improved.

Generally, the main advantages of CS algorithm are the diversity of population strategy via randomization and search strategy by Lévy flights, there are still some aspects to be improved.

For CS, the search process relies too much on random, although Lévy flights is most suitable for the randomization on the global scale 41, the way of generating new solutions by random walk is less efficient than Lévy flights, so a rapid convergence rate cannot be guaranteed and at times it cannot avoid falling into local optimal. In addition, there lacks information exchange between the individuals, moreover, new solutions are not influenced by the best individual in the swarm. To address the shortcomings of the CS and make full use of the advantages of GHS, a new hybrid algorithm, called CSGHS, is proposed in which the GHS is embedded into the CS. By intuition, this improvement makes the new approach work efficiently on both continuous and discrete problems. The distinct difference between CSGHS and CS is that GHS as the mutation operator is applied to improve the original CS generating a new solution for each nest. In this manner, this new approach can generate diverse solutions with a view to exploring the search space on the global scale by Lévy flights of the CS, and concentrate on the search in a local region where the current optimum is most likely found by the mutation of the GHS.

Several improvements of CSGHS are described as follows:

• The first improvement, and most important, is that the GHS completely replaces the random walk in CS in the stage of local search. As previously is mentioned, the GHS as a mutation operator was adopted in the CSGHS, with the aim of increasing diversity of the population and accelerating the convergence speed so as to enhance the performance.

• The second improvement is to add mutation operator of DE/Best/1/Bin scheme into CSGHS, as was inspired by the mutation operator in DE algorithm. Its purpose is to further strengthen the effects of global optimal information on the new nests and the information exchange between individuals.

Based on the above analysis, concretely speaking, the evolution mechanism of the CSGHS performs in two stages. The first stage is to get a cuckoo i randomly (generate a solution) by Lévy flights and then evaluate its quality F_i. Cuckoo j is chosen randomly and then it will be replaced by cuckoo i only if F_i is superior F_j. The second stage we tune each element xij (j=1, 2, ... , D) of x_i (i=1, 2, ... , N,) using mutation operator. If U(0, 1) ⩽HMCR, the element xij is replaced by xkj, where k∼U(1, ... , N). In this case, the element xij is updated by using pitch adjustment operation in GHS only if U(0, 1) ⩽PAR, the element xij is replaced by x_best^j; whereas when U(0, 1)>PAR, we update the element xij with the DE/Best/1/Bin scheme. If U(0, 1)>HMCR, the element xij is generated randomly.

With the above special design, the mainframe of the CSGHS for 0–1 knapsack problem is shown in Algorithm 3.

Begin

Step 1: Sorting. According to value-to-weight ratio pi / wi (i = 1, 2, 3, ... , m) in descending order, a queue {s1, s2, ..., sm} of length m is formed.

Step2: Initialization. Set the generation counter G=1; set the harmony memory consideration rate HMCR, the pitch adjustment rate PAR; Generate n cuckoo nests randomly {<X1, Y1>, <X2, Y2>, …, <Xn, Yn>}.

Calculate the fitness for each individual, f (Yi), 1 ⩽ i ⩽ n, determine the global optimal individual <Xgbest, Ygbest>.

Step 3: While the stopping criterion is not satisfied do

  for i=1 to n

    for j=1 to d

      xj′ = xj′ + α ⊕ Levy(λ) // Lévy flights

      if (rand<HMCR
) then //memory consideration

        xj′ = xji, where i ∼ U (1, n).

        if rand<PAR then //pitch adjustment

          xj′ = xjbest

        else

          xj′ = xjbest+F×(xjq − xjr
), where q∼U (1, n), r∼ U (1, n)

        end if

      else //random selection

        xj′ =LBj + r×(UBj −LBj
), where r∼ U(0,1
)

      end if

    end for

  Perform GTM method to repair and optimize the individuals

  end for

  Keep best solutions.

  Rank the solutions in descending order and find the current best (Ybest, f (Ybest)).

  G=G+1

Step 4: End while

End.

3.4. Algorithm complexity

CSGHS is composed of three stages: the sorting by value-to-weight ratio, the initialization and the iterative search. The quick sorting has time complexity O(n log(n)). The generation of the initial cuckoo nests has time complexity O(n×d). The iterative search consists of four steps (comment statements in Algorithm 3), i.e. the Levy flights, memory consideration, pitch adjustment, and random selection which costs the same time O(n×d). Further, the major time cost of GTM is the quick sort which has calculated at the start of this section. In summary, the overall complexity of the proposed CSGHS is O(n log (n))+O(n×d)+O(n×d)= O(n log(n))+O(n×d). It does not change compared with the original CS algorithm.

4.1. Experimental data set

Since the difficulty of knapsack problems is greatly affected by the correlation between profits and weights ^{66, 71}, six groups of 0–1 KP instances randomly generated are presented in Table 1. The correlation of six types of instances is shown in Fig. 1. Here we use the function Rand (a, b) to represent an integer uniformly distributed in [a, b]. Each group contains six 0–1 KP instances and the dimension is 300, 500, 800, 1000, 1200, and 1500. These thirty-six instances are marked as KP₁, KP₂, … , KP₃₆, respectively.

Fig. 1.

Six classes of instances with 300 items

4.2. Experimental setup and parameters setting

To better understand the CSGHS, we compared its performance on 36 knapsack problems (KP₁–KP₃₆) with three other optimization approaches, which are DE, SFLA and CS. DE ⁷² is a vector-based evolutionary algorithm with self-organizing tendency and does not use the information of derivatives. SFLA is a meta-heuristic optimization method that imitates the memetic evolution of a group of frogs while casting about for the location that has the maximum amount of available food ⁷³.

In our experiments, we set the parameters as follows. The proposed CSGHS includes four key parameters: the population size P=40, the harmony memory consideration rate HMCR=0.9, the pitch adjustment rate PAR=0.3 and amplification factor F=0.3. For DE, the population size P=40, crossover probability Cr=0.9, amplification factor F=0.3, basic DE/Rand/1/Bin scheme. For SFLA, the population size P=40, which is partitioned into M =4 memeplexes, each containing N=10 frogs (i.e. P=M×N).

In order to make a fair comparison, all computational experiments are conducted with Visual C++ 6.0. The test environment is set up on a PC with AMD Athlon(tm) II X2 250 Processor 3.01 GHz, 1.75G RAM, running on Windows 7. The experiment on each instance was repeated 30 times independently. Further, best solution, worst solution, mean, median, standard deviation (STD) for all the solutions are given in related tables. In addition, the maximum run-time was set to 5 seconds for 300-dimensional and 500-dimensional instances, 8 seconds for 800-dimensional, 1000-dimensional, and 1200-dimensional instances and 10 seconds for 1500-dimensional instances.

4.3. Numerical optimization

In order to make an overall investigation about the performance of CSGHS, a number of simulation and experiment research have been carried out. Six classes of 0–1 knapsack problems with large scales listed in Table 1. The number of items is set to 300, 500, 800, 1000, 1200, and 1500, respectively. The experimental results are reported in Tables 2–7. The best values are emphasized in boldface. In addition, comparisons of the best profits obtained from the CSGHS with those obtained from DE, SFLA and CS for six KP instances with 1500 items among 30 independent runs are shown in Figs 2–7, respectively. Specifically, the convergence curves of four algorithms on 1500 items are also graphically illustrated in Figs 8–13, respectively.

Fig. 2.

The best profits obtained in 30 runs for KP₆

Fig. 3.

The best profits obtained in 30 runs for KP₁₂

Fig. 4.

The best profits obtained in 30 runs for KP₁₈

Fig. 5.

The best profits obtained in 30 runs for KP₂₄

Fig. 6.

The best profits obtained in 30 runs for KP₃₀

Fig. 7.

The best profits obtained in 30 runs for KP₃₆

Fig. 8.

The convergence graphs of KP₆

Fig. 9.

The convergence graphs of KP₁₂

Fig. 10.

The convergence graphs of KP₁₈

Fig. 11.

The convergence graphs of KP₂₄

Fig. 12.

The convergence graphs of KP₃₀

Fig. 13.

The convergence graphs of KP₃₆

From the results of Tables 2, 4–7, we can plainly perceive that CSGHS achieves decisive advantage in performance over the other three algorithms and it obtains the best results on all the instances, as can be seen from the third column to the sixth column of Tables 2, 4–7. On closer inspection, the SFLA gains the smallest STD values on more than two-thirds cases. For the other ten cases, similar numerical stabilities are observable in CS and CSGHS. With regard to DE, it may not be adept in solving 0–1 KPs as its overall performance is obviously inferior to that of the other three algorithms.

Table 3 summarizes the experimental results obtained by the four methods to the weakly-correlated instances. From Table 3 we can infer that the performance of CSGHS, CS, SFLA and DE are comparable. DE obtained the best, mean, median results for KP₇, KP₈ and CS attained the best results for the last four cases. SFLA still showed the best stability among four methods. Although the optimal solutions obtained by the CSGHS are poorer than DE or CS, the CSGHS gets the worst, mean, median results on KP₉–KP₁₂. Unfortunately, although weakly correlated knapsack problem are closer to the real world situations 66, the CSGHS does not appear overwhelming superior to the other three algorithms in solving such knapsack problems.

Figs. 2–7 show a comparison of the best profits obtained by applying the four algorithms for six classes of problems with 1500-dimensional functions in 30 runs. The search space of the 1500-dimensional functions is expanded dramatically to 2¹⁵⁰⁰, which is a challenge for CSGHS, CS, SFLA and DE. Thus, DE failed to come at any global optima of all the six high-dimensional functions, while the results of SFLA fluctuated around certain value, as we had expected. Additionally, the CS can get the optimal solution occasionally, which shows it has poorer stabilization and is consistent with the STD value above. The CSGHS wins obvious advantages. As mentioned above, weakly correlated problem instances are difficult to solve in the case of CSGHS.

To investigate further the performance of the four approaches, the average convergence curves of CSGHS, CS, SFLA and DE are drawn in Figs. 8–13. The optimization of the small-size problems is simple. However, when the dimensionality is increased, the CSGHS takes the lead obviously and outperforms the other three methods. From Figs. 8–13, it is observed that CSGHS have a quick convergence speed, as is benefited from the GHS. SFLA performs the second best in hitting the optimum. DE shows premature phenomenon in the evolution and does not offer satisfactory performance.