# A Hybrid Harmony Search Algorithm with Distribution Estimation for Solving the 0-1 Knapsack Problem

Authors: Kang Liu; Haibin Ouyang; Steven Li; Liqun Gao
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Many optimization algorithms have been applied to solve high-dimensional instances of the 0-1 knapsack problem. However, these algorithms often fall into a local optimization trap and thus fail to obtain the global optimal solutions. To circumvent this shortcoming, a hybrid harmony search algorithm with distribution estimation is proposed in this paper. A few important features of the proposed algorithm are as follows: (i) the idea of probability distribution estimation is employed to design the adaptive search strategy, (ii) a fixed improvisation process is presented to improve the algorithm searching ability, (iii) a new method of initialization is used to ensure that the initialization is feasible harmony and (iv) an improved remediation approach is proposed to effectively repair the infeasible solutions. To assess the effectiveness of the proposed algorithm, some experiments are carried out. The experimental results reveal that the proposed algorithm is a reliable and promising alternative for solving the 0-1 knapsack problem.


---

## Body

## 1. Introduction

With the development of digitization, a large number of discrete optimization problems are emerging, which has attracted the attention of many scholars [1–4]. Combinatorial optimization problem is a typical problem, including integer programming, 0-1 programming. The 0-1 knapsack problem proposed by Fayard in 1975, is a typical combinatorial optimization problem [5] and a NP problem. It is widely applied in many areas such as investment decision making problems [6], cutting stock problem [7], the housing problem [8], cryptography [9], adaptive multimedia system [10], the portfolio choice [11, 12], the computer memory [13], the allocation of resources [14], energy minimization [15, 16], cargo load problem [17–19], real estate property maintenance optimization [20], the main budget [21] and blanking problem [7]. Many real-world optimization problems are similar to 0-1 knapsack problem, therefore, exploring approaches to effectively solve 0-1 knapsack problem is important and it can offer new methods for some complex engineering optimization problems. Without loss of generality, 0-1 knapsack problem can be expressed as(1)Maxfx=∑i=1npi⋅xi,s.t.∑i=1nvi⋅xi≤vmax,xiε0,1,i=1,2,…,n,where n is the total number of objects. Each object has a separate profit value pi and weight vi, Vmax is the largest weight the knapsack can accommodate, xi depends on the state of the object i. If the object comes into the knapsack, xi is 1, otherwise, xi is 0.The 0-1 knapsack problem is about maximizing the value of the items in the knapsack under the condition of meeting the requirement of knapsack capacity. Many scholars have studied 0-1 knapsack problems and various algorithms have been proposed. These algorithms can be classified into two categories: deterministic algorithms which include dynamic programming [22], backtracking algorithm, branch and bound algorithm [23], and intelligent optimization algorithms. Because dynamic programming method as well as branch and bound algorithm are often used in solving 0-1 knapsack problem, the computation time increases rapidly and the accuracy decreases as the dimension increases. Thus, the metaheuristic algorithms imitating natural phenomena in intelligent optimization algorithms have attracted more and more attention [24–29].In recent years, many metaheuristics have been proposed to solve 0-1 knapsack problems. Lim proposed a monogamous genetic algorithm with different offspring for the 0-1 knapsack problems [30]. The immune genetic algorithm (NIGA) can quickly recognize antigen characteristics by injecting vaccine. Experimental results show that NIGA algorithm can effectively prevent the algorithm from degradation in the process of genetic algorithm optimization and can improve the convergence speed [31]. Eberhart and Kennedy proposed a binary particle swarm optimization algorithm (BPSO), which largely transforms the continuous problem into a discrete problem by sigmoid [32]. The main shortcomings are that the change of probability becomes smaller with the increase of speed, which will lead to evolution into local optimum. An improved binary particle swarm optimization (MBPSO) was presented by Kennedy, in which a new probability function was designed to ensure the diversity of the population. Compared with some classic binary particle swarm optimization algorithms, MBPSO is more efficient in solving the 0-1 knapsack problem [33]. He et al. proposed a greedy particle swarm optimization (GPSO). In GPSO, a new greedy transformation method is proposed, and then it is combined with the binary particle swarm optimization algorithm with two-layer structure coding. The simulation results reveal that GPSO algorithm is more effective [34]. Wang proposed monarch butterfly optimization algorithm [35], and then Feng et al. proposed chaotic monarch butterfly optimization [36] and a new binary monarch butterfly optimization algorithm [37] to solve 0-1 knapsack problems. Marinakis proposed a hybrid algorithm based on the concepts of artificial bee colony (BABC-DE) and greedy random adaptive search (GRASP) [38]. The algorithm is a two-stage algorithm, which combines the artificial bee colony optimization algorithm for feature selection and grasp algorithm for clustering. Cao proposed a binary differential evolution artificial bee algorithm (BABC-DE) to solve 0-1 knapsack problem. In the phase of employing bees, a binary search operator is designed, which considers memory and neighbor information. In the phase of observing bees, the mutation and crossover operations of differential evolution are used [39]. In 2021, Wang et al. presented A hybridization of dragonfly algorithm optimization and angle modulation mechanism for 0-1 knapsack problems [40]. Abdel-basset et al. proposed a binary flower pollination algorithm to solve 0-1 knapsack problem [41]. The algorithm uses the conversion function to convert the continuous values generated by FPA into binary values. The penalty function is added to the evaluation function to give negative value to the infeasible solution. Finally, the infeasible solution is repaired by a two-stage repair operation. Abdel-basset et al. proposed a binary equilibrium optimization method (BEO) to solve the 0-1 knapsack problem, which mainly uses v-shaped and S-shaped transfer functions to transform the continuous function into discrete function, uses penalty function to screen out the infeasible solution from the problem, and applies repair function (RA) to transform it into feasible solution. Results show that the algorithm has better performance than other algorithms [42]. In 2020, Abdel-basset et al. also presented New binary marine predators optimization algorithms for 0-1 knapsack problems [43]. In 2021, Moradi et al. designed an efficient population-based simulated annealing algorithm for 0-1 knapsack problem [44].Harmony search algorithm is an optimization algorithm proposed by Geem with a relatively simple structure and relatively fewer adjustable parameters [45]. Harmony search imitates the harmony produced by musicians adjusting the pitch of an instrument. Zou et al. [46] proposed a new global harmony search algorithm (NGHS). The algorithm is improved in position update and genetic mutation, which makes the worst harmony in harmony memory change to the global optimum and prevents the algorithm from falling into the local optimum. Wang proposed an improved adaptive binary harmony search algorithm (ABHS), which enhanced the search ability and robustness of the algorithm [47]. Kong et al. proposed a new simplified binary harmony search (SBHS) algorithm, which modified the improvisation process and adaptive harmony memory rate [48]. For the infeasible solution, the algorithm proposes a two-stage greedy process to repair. Wang et al. proposed an improved differential harmony search (IDHS) algorithm to solve numerical function optimization problems [49]. Mahmoudi et al. proposed a combination of fuzzy logic controller and harmonic search algorithm (HS) for PWR load mode optimization. In the work, the parameters such as bandwidth and pitch adjustment rate are adjusted by a fuzzy logic controller to improve the performance of the proposed algorithm. Finally, the superiority of the algorithm is proved by a case study [50].Despite the above improvements of the harmony algorithm, they still fall into a local optimum for high-dimensional problems. According to the characteristics of 0-1 knapsack problem, this paper proposes a hybrid harmony search algorithm with distribution estimation. It mainly solves the problem that it is easy to fall into local optimum in high dimensional 0-1 knapsack problem, and also carries out low dimensional tests to verify the reliability of the algorithm.The main features of the proposed algorithm are as follows:(1)
A feasible harmony discrete initialization method is used to increase the randomness of the initial solution, and the initial harmony is 0-1 distribution, and all harmony is feasible(2)
In the distribution estimation algorithm, the idea of probability is used to adjust the selected harmony, which makes the direction of harmony change approach to the optimal direction and enhances the search ability of the algorithm(3)
The improvisation of harmony search algorithm is improved to a discrete form(4)
A greedy repair mechanism is designed to repair the harmony that does not meet the constraints, and try to optimize the harmony that meets the constraintsThe rest of this paper is organized as follows. Section2 mainly introduces the basic harmony search algorithm, including harmony search algorithm and other related improved version. In Section 3, we introduce the distribution estimation and harmony search hybrid algorithm in detail. Section 4 offers the experimental results and evaluate the optimization performance of the proposed hybrid algorithm. The conclusions and the directions for further research are summarized in Section 5.


## 2. Related Works

### 2.1. The Harmony Search Algorithm

Harmony search algorithm is a metaheuristic algorithm proposed by the Korean scholar Geem in 2001 [45]. It is an algorithm imitating the principle of music performance. Harmony search algorithm is different from a genetic algorithm, a differential evolution algorithm or a particle swarm optimization algorithm in that it is guided by probability. The key idea of the harmony search algorithm is to initialize a harmony memory first, and then choose the harmony memory for improvisation, which includes the harmony memory, tone adjustment and random search. The iteration is done by comparing the value of the fitness: if the new fitness is better than the worst fitness in harmony memory, they are replaced by new generation cycle until the stop condition is satisfied. The detailed steps of harmony search algorithm are as follows:Step 1.
Initialize algorithm parameters. HS generally needs to set five parameters which are harmony memory size (HMS), harmony memory consideration probability (HMCR), gene adjustment probability (PAR), harmony fine-tuning step size (BW), the maximum number of iterationsK.Step 2.
The harmony memory library HM is randomly initialized according to Formula is (3), and memory bank HM (4). HerexiL and xiU are the upper and lower limits of the ith-dimensional variables.(2)xi=xiL+rand×xiU−xiL,HM=x11x21...xn1fx1x12x22...xn2fx2x13x23...xn3fx3...............x1HMSx2HMS...xnHMSfxHMS.Step 3.
Improvisation to generate new harmonies improvisation is performed with given parameters HMCR, PAR and BW to generate a new harmony memory bank. The specific process is as follows (Algorithms1–5).Algorithm 1: Harmony search algorithm.
fori = 1 to N doIf rand < HMCR% Determine whether to perform a harmony memory consideration operationxinew=xir;rϵ1,2,3,…,HMSIfrand < PAR then% Determine whether to perform genetic manipulationxinew=xir±rand×bw%pitchadjustmentend ifelsexinew=xiL±rand×xiU−xiL%Conduct random mutation operationend ifend forAlgorithm 2: Initialization phase.
fori = 1: HMSForj = 1: NIf rand < randxi,j=1;elsexi,j=0;end ifend forCalculate the total weight of the harmonyGiwhileGi > C % Determine whether the constraint satisfies the conditionReinitialize the harmony vectorEnd whileEnd forAlgorithm 3: Distribution estimation algorithm.
Initialize the harmony libraryCalculate fitnessFori = 1 to HMSThe fitness value of the harmony is obtained by adding the unit price of the value of the harmony that meets the conditionsEnd% Sort harmonies by fitness value[Fitness, index] = sort (Fitness_ Value);%Select the dominant harmonyfori = 1 to Advantages of harmonyNumAccording to the sorted fitness value, the harmony with relatively high fitness value is searched and selectedend%Update Probability ModelA mathematical model is used to update the probability, and new probability values are generated.% Determine if the conditions are metIf the stop condition is not met, the updated probability is substituted into the loop until the condition is metAlgorithm 4: A novel form of directed improvisation.
(1)
forj = 1: N(2)
Calculate the probability of each dimension of the population being selected(3)
ifrand < HMCR% Consideration of harmony memory bank(4)
Operate on a harmonic vector randomly selected from the harmony memory library(5)
ifrand < PAR% Determine whether to make pitch adjustment(6)
If rand < probability %The probability generated by the distribution estimation algorithm is used for judgment(7)
B (j) = 1;(8)
Else(9)
B (j) = 0;(10)
end if(11)
end if(12)
else(13)
xnewj=roundrand;%Random variation produces a harmony(14)
End if(15)
End forAlgorithm 5: Repair operator.
(1)
Whileg > C(2)
Randomly select a certain number of dimensions(3)
Sorts the selected dimensions out of order(4)
IfB (dd(i)) == 1(5)
B (dd(i)) = 0;(6)
g = g − W (dd(i));(7)
end(8)
Determines whether the selected dimension is exceeded(9)
endwhere rand is a random number generated in the range (0, 1):Step 4.
Update and remember repository
If the newly generatedxnew is better than the xworst in the harmony memory bank, then the worst harmony xworst in the harmony memory bank is replaced with xnew.Step 5.
Stop the inspection.
If the current iteration numberk is greater than the maximum iteration number K, the algorithm will be terminated and the optimal harmony vector will be output in HM as the final result; Otherwise, Step 3 and Step 4 will be repeated.
Harmony search algorithm can solve some problems encountered in real life, but there are some shortcomings due to the simplicity of its principle. In the iteration of the algorithm, its local search ability is poor, and it is easy to fall into the local optimal.
Many attempts have been made to improve the performance of the original algorithm. The directions of improvements include: changing the algorithm parameters, changing algorithm strategy and the combination of these two improvements. Experiments show that the parameter variation of the algorithm can play an important role in the optimization results.


### 2.2. Binary-Coding Harmony Search Algorithm (BHS)

Geem proposed a binary harmony search algorithm to solve the pump switching problem [51]. Compared with the classical harmony search algorithm, a binary harmony search algorithm selects the new harmony from HM harmony library or random 0 or 1.The following is the improvisation process of BHS:(3)xinew←xinew∈xi1,xi2,…,xiHMS;if rand<HMCR,xinew;∈0,1;otherwise.In the above equation,xinew is a newly generated harmony, and Rand is a random choice in the range of 0 to 1.


### 2.3. Discrete Binary Harmony Search Algorithm (DBHS)

Because the standard harmony search algorithm cannot solve the discrete problem, Wang et al. [52] proposed a new discrete binary harmony search (DBHS) algorithm. DBHS proposes a special way of tone adjustment, which selects only one harmony from the harmony to form a new harmony.The following is the improvisation process of DBHS:(4)xinew=xit,if and≤HMCRZ,otherwise.tϵ1,2,…,HMS,Z=0,if rand≤0.5,1,otherwise.In the above formula,t is a value randomly selected from 1,HMS. xit represents the ith element of the harmony selected in HM.In the specific 0-1 knapsack problem, harmony can only be 0 or 1. The new harmony generation formula is as(5)xinew=xibest,if rand≤PARxinew,otherwise,where xibest represents the ith corresponding element of the global optimal harmony vector xbest. This formula can improve the local search ability of the DBHS algorithm.


### 2.4. A Novel Global Harmony Search Algorithm (NGHS)

Zou et al. proposed a new global harmony search algorithm, which is inspired by the swarm intelligence algorithm [46]. The improvements are mainly made in two aspects: location updating and genetic variation. The improvisation process of NGHS as follow:The improvisation process of NGHS(6)for eachiϵ1,NdoxR=2×xibest−xiworstifxR>x_iUxR=xiUelseifxR<xiUxR=xiLendxi′=xiworst+rand×xR−xiworstif rand≤pmthenxi′=xiL+rand×XiU−iLendend .In the above process, best and worst represent the global best harmony and the global worst harmony in HM, respectively. Rand is a random selection from 0 to 1. It can be seen that in NGHS, harmony always moves in the direction of the best harmony, and it can be prevented from falling into the local optimum by a certain probability of producing a new solution.


### 2.5. Adaptive Binary Harmony Search Algorithm (ABHS)

Wang et al. proposed an improved adaptive binary harmony search algorithm (ABHS) in order to solve the degradation problem of pitch adjustment operator in the harmony search algorithm [47]. The algorithm uses a position selection strategy for harmony memory operation and the same tone adjustment rules by DBHS. The innovation of the algorithm is mainly on adapting HMCR and par. The following is the adaptive formula for HMCR.(7)HMCR=1−cn+lnnn+lnnn×kK,where K and k are the maximum number of iterations and the current number of iterations respectively, and c is a constant. [x] is an operator that takes the largest integer less than x. The above HMCR is dynamically changing according to the dimension and the current iteration number.


## 2.1. The Harmony Search Algorithm

Harmony search algorithm is a metaheuristic algorithm proposed by the Korean scholar Geem in 2001 [45]. It is an algorithm imitating the principle of music performance. Harmony search algorithm is different from a genetic algorithm, a differential evolution algorithm or a particle swarm optimization algorithm in that it is guided by probability. The key idea of the harmony search algorithm is to initialize a harmony memory first, and then choose the harmony memory for improvisation, which includes the harmony memory, tone adjustment and random search. The iteration is done by comparing the value of the fitness: if the new fitness is better than the worst fitness in harmony memory, they are replaced by new generation cycle until the stop condition is satisfied. The detailed steps of harmony search algorithm are as follows:Step 1.
Initialize algorithm parameters. HS generally needs to set five parameters which are harmony memory size (HMS), harmony memory consideration probability (HMCR), gene adjustment probability (PAR), harmony fine-tuning step size (BW), the maximum number of iterationsK.Step 2.
The harmony memory library HM is randomly initialized according to Formula is (3), and memory bank HM (4). HerexiL and xiU are the upper and lower limits of the ith-dimensional variables.(2)xi=xiL+rand×xiU−xiL,HM=x11x21...xn1fx1x12x22...xn2fx2x13x23...xn3fx3...............x1HMSx2HMS...xnHMSfxHMS.Step 3.
Improvisation to generate new harmonies improvisation is performed with given parameters HMCR, PAR and BW to generate a new harmony memory bank. The specific process is as follows (Algorithms1–5).Algorithm 1: Harmony search algorithm.
fori = 1 to N doIf rand < HMCR% Determine whether to perform a harmony memory consideration operationxinew=xir;rϵ1,2,3,…,HMSIfrand < PAR then% Determine whether to perform genetic manipulationxinew=xir±rand×bw%pitchadjustmentend ifelsexinew=xiL±rand×xiU−xiL%Conduct random mutation operationend ifend forAlgorithm 2: Initialization phase.
fori = 1: HMSForj = 1: NIf rand < randxi,j=1;elsexi,j=0;end ifend forCalculate the total weight of the harmonyGiwhileGi > C % Determine whether the constraint satisfies the conditionReinitialize the harmony vectorEnd whileEnd forAlgorithm 3: Distribution estimation algorithm.
Initialize the harmony libraryCalculate fitnessFori = 1 to HMSThe fitness value of the harmony is obtained by adding the unit price of the value of the harmony that meets the conditionsEnd% Sort harmonies by fitness value[Fitness, index] = sort (Fitness_ Value);%Select the dominant harmonyfori = 1 to Advantages of harmonyNumAccording to the sorted fitness value, the harmony with relatively high fitness value is searched and selectedend%Update Probability ModelA mathematical model is used to update the probability, and new probability values are generated.% Determine if the conditions are metIf the stop condition is not met, the updated probability is substituted into the loop until the condition is metAlgorithm 4: A novel form of directed improvisation.
(1)
forj = 1: N(2)
Calculate the probability of each dimension of the population being selected(3)
ifrand < HMCR% Consideration of harmony memory bank(4)
Operate on a harmonic vector randomly selected from the harmony memory library(5)
ifrand < PAR% Determine whether to make pitch adjustment(6)
If rand < probability %The probability generated by the distribution estimation algorithm is used for judgment(7)
B (j) = 1;(8)
Else(9)
B (j) = 0;(10)
end if(11)
end if(12)
else(13)
xnewj=roundrand;%Random variation produces a harmony(14)
End if(15)
End forAlgorithm 5: Repair operator.
(1)
Whileg > C(2)
Randomly select a certain number of dimensions(3)
Sorts the selected dimensions out of order(4)
IfB (dd(i)) == 1(5)
B (dd(i)) = 0;(6)
g = g − W (dd(i));(7)
end(8)
Determines whether the selected dimension is exceeded(9)
endwhere rand is a random number generated in the range (0, 1):Step 4.
Update and remember repository
If the newly generatedxnew is better than the xworst in the harmony memory bank, then the worst harmony xworst in the harmony memory bank is replaced with xnew.Step 5.
Stop the inspection.
If the current iteration numberk is greater than the maximum iteration number K, the algorithm will be terminated and the optimal harmony vector will be output in HM as the final result; Otherwise, Step 3 and Step 4 will be repeated.
Harmony search algorithm can solve some problems encountered in real life, but there are some shortcomings due to the simplicity of its principle. In the iteration of the algorithm, its local search ability is poor, and it is easy to fall into the local optimal.
Many attempts have been made to improve the performance of the original algorithm. The directions of improvements include: changing the algorithm parameters, changing algorithm strategy and the combination of these two improvements. Experiments show that the parameter variation of the algorithm can play an important role in the optimization results.


## 2.2. Binary-Coding Harmony Search Algorithm (BHS)

Geem proposed a binary harmony search algorithm to solve the pump switching problem [51]. Compared with the classical harmony search algorithm, a binary harmony search algorithm selects the new harmony from HM harmony library or random 0 or 1.The following is the improvisation process of BHS:(3)xinew←xinew∈xi1,xi2,…,xiHMS;if rand<HMCR,xinew;∈0,1;otherwise.In the above equation,xinew is a newly generated harmony, and Rand is a random choice in the range of 0 to 1.


## 2.3. Discrete Binary Harmony Search Algorithm (DBHS)

Because the standard harmony search algorithm cannot solve the discrete problem, Wang et al. [52] proposed a new discrete binary harmony search (DBHS) algorithm. DBHS proposes a special way of tone adjustment, which selects only one harmony from the harmony to form a new harmony.The following is the improvisation process of DBHS:(4)xinew=xit,if and≤HMCRZ,otherwise.tϵ1,2,…,HMS,Z=0,if rand≤0.5,1,otherwise.In the above formula,t is a value randomly selected from 1,HMS. xit represents the ith element of the harmony selected in HM.In the specific 0-1 knapsack problem, harmony can only be 0 or 1. The new harmony generation formula is as(5)xinew=xibest,if rand≤PARxinew,otherwise,where xibest represents the ith corresponding element of the global optimal harmony vector xbest. This formula can improve the local search ability of the DBHS algorithm.


## 2.4. A Novel Global Harmony Search Algorithm (NGHS)

Zou et al. proposed a new global harmony search algorithm, which is inspired by the swarm intelligence algorithm [46]. The improvements are mainly made in two aspects: location updating and genetic variation. The improvisation process of NGHS as follow:The improvisation process of NGHS(6)for eachiϵ1,NdoxR=2×xibest−xiworstifxR>x_iUxR=xiUelseifxR<xiUxR=xiLendxi′=xiworst+rand×xR−xiworstif rand≤pmthenxi′=xiL+rand×XiU−iLendend .In the above process, best and worst represent the global best harmony and the global worst harmony in HM, respectively. Rand is a random selection from 0 to 1. It can be seen that in NGHS, harmony always moves in the direction of the best harmony, and it can be prevented from falling into the local optimum by a certain probability of producing a new solution.


## 2.5. Adaptive Binary Harmony Search Algorithm (ABHS)

Wang et al. proposed an improved adaptive binary harmony search algorithm (ABHS) in order to solve the degradation problem of pitch adjustment operator in the harmony search algorithm [47]. The algorithm uses a position selection strategy for harmony memory operation and the same tone adjustment rules by DBHS. The innovation of the algorithm is mainly on adapting HMCR and par. The following is the adaptive formula for HMCR.(7)HMCR=1−cn+lnnn+lnnn×kK,where K and k are the maximum number of iterations and the current number of iterations respectively, and c is a constant. [x] is an operator that takes the largest integer less than x. The above HMCR is dynamically changing according to the dimension and the current iteration number.


## 3. Hybrid Harmony Search Algorithm with Distribution Estimation

In this section, we introduce the hybrid algorithm based on distribution estimation and harmony search. We consider the initialization, distribution estimation algorithm, improvisation operation and improved repair algorithm.


### 3.1. An Initialization Method under Constraints

The 0-1 knapsack problem is a discrete problem with a knapsack state represented by 0 or 1. 1 means that the object is loaded into the knapsack, and 0 means that the object is not loaded into the knapsack. The proposed method can initialize random harmonies and ensure that the harmonies are feasible, see the description below. The advantage of the proposed initialization is that if the constraint is not satisfied, it is repeated until the constraint is satisfied.Here, theG (i) is the total weight of backpack, x (i, j) as the independent state of harmony variable.


### 3.2. The Distribution Estimation Algorithm

The distribution estimation algorithm was proposed in 1996 and it has been rapidly studied thereafter [53]. In the traditional genetic algorithm, a candidate solution, is generated by iterating through selection, crossover and mutation and other operations that simulate the natural evolution. Unlike the traditional algorithm, the distribution estimation algorithm uses a profile model and a sampling procedure. In essence, the distribution estimation algorithm describes the spatial distribution of the candidate solutions through a probability model describing the distribution of the solution from the perspective of population macroscopic by means of statistical learning. Then, the probability model is randomly sampled to generate new populations, and repeated iterations are carried out to update the populations until the termination condition. The specific steps are as follows:Step 1.
Randomly generateM individuals as the initial population.Step 2.
Calculate the individual fitness for theL generation population, and judge whether the conditions are met. If so, the cycle is terminated. If not, proceed to the next step.Step 3.
Select the first N dominant individuals from the population according to the fitness value to form the dominant subpopulation of theL + 1 generation.Step 4.
Update probability model according to dominant subpopulation (N ≤ M),Step 5.
Conduct random sampling of the probability model to generate a new population (sizeM) and return to Step2.
From the above description we can understand the basic process of the distribution estimation algorithm. Figure1 summarizes the general process of distribution estimation algorithm. In the distribution estimation algorithm, there is no operation such as crossover and mutation for the genetic algorithm. Instead, through learning probability model and sampling operation, the population distribution is made to evolve towards the direction of better individuals. From the perspective of biological evolution, genetic algorithm simulates the microscopic changes among individuals, while distribution estimation algorithm models and simulates the overall distribution of biological population.Figure 1
The general process of distribution estimation algorithm.


### 3.3. A Directed Improvisation

In HS, the improvisation stage is important and the change of harmony vector mainly takes place in this part. There are three important operation processes in the improvisation process. Since 0-1 knapsack problem is a discrete problem, the operation needs to be adapted to its discrete nature: (1) The consideration of harmony memory library is to compare HMCR with random numbers and select a harmony vector from harmony memory library HM for subsequent operations. (2) Gene adjustment process, that is, PAR is compared with random numbers, and then the probability obtained by distribution estimation algorithm is compared with random numbers if needed, and 0 or 1 is selected for harmony. (3) Random variation, that is, random perturbation strategy to explore new harmonic variables, which only have two choices of 0 or 1.In this paper, the idea of using probability in the distribution estimation algorithm is used to guide the tendency of the whole harmony memory database, and the harmony is optimized and adjusted by using the numerical distribution probability. According to the characteristics of 0-1 knapsack problem, the random correction process is used to carry out mutation operation, which is called a novel instructional improvisation.According to the instructional improvisation process, in the process of genetic adjustment, the probability used is the 0-1 distribution probability in the harmony memory bank, which can make the newly generated harmony overall change for a better result. After many iterations, the harmony in the harmony memory bank will be closer to the best harmony.


### 3.4. An Improved Repair Operator

In problems with constraints, only feasible solutions can be assigned to the feasible region, and infeasible solutions will lead to search stagnation in the infeasible region. Therefore, it is necessary to ensure that all the harmonic vectors contained in HM satisfy the constraints. If the newly created harmony does not meet the criteria, a random repair mechanism is used to repair the harmony. First, select a certain number of dimensions independently and randomly, and arrange the dimensions out of order and judge whether the first dimension harmony is selected. If it is selected, remove it from the knapsack and judge whether it meets the requirements of knapsack capacity.If the newly generated harmonies meet the conditions, an improved method is used to optimize the harmonies under the constraints as described in Algorithm6 below. In this way, the harmony that does not meet the constraint is repaired or improved, so that the harmony vector stored in the harmony memory library HM can maximize the value of the items loaded in the knapsack as much as possible, and meet the constraint condition of the knapsack capacity.Algorithm 6: Improved repair operator.
(1)
Whileg < C(2)
Randomly select a certain number of dimensions(3)
Sort the selected dimensions out of order(4)
L = g; % Total weight held(5)
IfB (dd (i)) == 0(6)
B (dd(i)) = 1;(7)
g= g + W (dd (i));(8)
end(9)
ifg > C(10)
B (dd(i)) = 0;(11)
L = g − W (dd(i));(12)
end(13)
Determines whether the selected dimension is exceeded(14)
end(15)
g = L;Here, theB (dd (i)) for the corresponding state of harmony, W (dd (i)) for the corresponding to the object weight of harmony solution.


### 3.5. The HHSEDA Algorithm Flow

The proposed HHSEDA algorithm can be described as follows.Step 1.
Initialize the parameters of the HHSEDA algorithm including: the size of harmony memory bank (HMS), the probability of harmony memory bank considering (HMCR), the number of excellent population (YouxiuNum), the maximum number of iterations (J1) and the probability of population distribution (probability)Step 2.
The harmonic memory library is initialized according to an initialization method satisfying the constraints, and the fitness value is calculated.Step 3.
Based on an improved improvisation of the idea of the distribution estimation algorithm, new harmonies are generated.Step 4.
The newly generated solution is repaired or improved by the improved repair operator.Step 5.
Update the harmony memory to determine whether the new harmony generated is greater than the worst harmony in HM. If so, the worst harmony is replaced. If not, it is not replaced.Step 6.
Check whether the termination conditions are met. If yes, the termination is effected. If no, repeat Steps2 to Step 5.
The pseudocode of the HHSEDA algorithm is given in Algorithm7, in which J1 is the maximum number of iterations. In this process, the global dominant population is selected, the probability of knapsack being selected is calculated by using the distribution estimation algorithm, and then the harmony memory is considered, and the pitch is adjusted. Whenever a new harmony is generated, the greedy operators are used to repair or improve it.
The flow chart of the algorithm of HHSEDA is shown in Figure2.Algorithm 7: The HHSEDA algorithm for the 0-1 knapsack problem.
(1)
Initialize the algorithm and problem parameters.(2)
The harmony memory library should be initialized according to the feasible solution initialization method and the requirement of knapsack capacity to be met.(3)
Calculate the fitness value after initialization.(4)
fori = 1 to J1 do(5)
Find the worst and best harmony in the harmony memory database as p(6)
Calculate fitness values and sort them(7)
Fori = 1: K% select the dominant population(8)
The number ofK populations with the highest fitness value was selected(9)
end(10)
Forj = 1: N%% Generates new harmonies based on Guided Improvisation(11)
Count the number of bags selected in each column(12)
if rand < HMCR(13)
r = ceil (HMS ∗ rand) Randomly select the harmonic vector(14)
if rand < PAR(15)
If rand < probability(16)
Update the corresponding harmonies(17)
end(18)
end(19)
else Random mutation produces new harmonies(20)
end(21)
end for(22)
The total capacity of the newly produced harmony is calculated(23)
If the knapsack capacity requirement is met, the greedy selection is made under the constraint(24)
If the knapsack capacity requirement is not met, the harmony is repaired(25)
if fit (B) > fit (p)(26)
Update the global lowest harmony(27)
end(28)
end forFigure 2
The whole process of hybrid harmony search and distribution estimation algorithm.


## 3.1. An Initialization Method under Constraints

The 0-1 knapsack problem is a discrete problem with a knapsack state represented by 0 or 1. 1 means that the object is loaded into the knapsack, and 0 means that the object is not loaded into the knapsack. The proposed method can initialize random harmonies and ensure that the harmonies are feasible, see the description below. The advantage of the proposed initialization is that if the constraint is not satisfied, it is repeated until the constraint is satisfied.Here, theG (i) is the total weight of backpack, x (i, j) as the independent state of harmony variable.


## 3.2. The Distribution Estimation Algorithm

The distribution estimation algorithm was proposed in 1996 and it has been rapidly studied thereafter [53]. In the traditional genetic algorithm, a candidate solution, is generated by iterating through selection, crossover and mutation and other operations that simulate the natural evolution. Unlike the traditional algorithm, the distribution estimation algorithm uses a profile model and a sampling procedure. In essence, the distribution estimation algorithm describes the spatial distribution of the candidate solutions through a probability model describing the distribution of the solution from the perspective of population macroscopic by means of statistical learning. Then, the probability model is randomly sampled to generate new populations, and repeated iterations are carried out to update the populations until the termination condition. The specific steps are as follows:Step 1.
Randomly generateM individuals as the initial population.Step 2.
Calculate the individual fitness for theL generation population, and judge whether the conditions are met. If so, the cycle is terminated. If not, proceed to the next step.Step 3.
Select the first N dominant individuals from the population according to the fitness value to form the dominant subpopulation of theL + 1 generation.Step 4.
Update probability model according to dominant subpopulation (N ≤ M),Step 5.
Conduct random sampling of the probability model to generate a new population (sizeM) and return to Step2.
From the above description we can understand the basic process of the distribution estimation algorithm. Figure1 summarizes the general process of distribution estimation algorithm. In the distribution estimation algorithm, there is no operation such as crossover and mutation for the genetic algorithm. Instead, through learning probability model and sampling operation, the population distribution is made to evolve towards the direction of better individuals. From the perspective of biological evolution, genetic algorithm simulates the microscopic changes among individuals, while distribution estimation algorithm models and simulates the overall distribution of biological population.Figure 1
The general process of distribution estimation algorithm.


## 3.3. A Directed Improvisation

In HS, the improvisation stage is important and the change of harmony vector mainly takes place in this part. There are three important operation processes in the improvisation process. Since 0-1 knapsack problem is a discrete problem, the operation needs to be adapted to its discrete nature: (1) The consideration of harmony memory library is to compare HMCR with random numbers and select a harmony vector from harmony memory library HM for subsequent operations. (2) Gene adjustment process, that is, PAR is compared with random numbers, and then the probability obtained by distribution estimation algorithm is compared with random numbers if needed, and 0 or 1 is selected for harmony. (3) Random variation, that is, random perturbation strategy to explore new harmonic variables, which only have two choices of 0 or 1.In this paper, the idea of using probability in the distribution estimation algorithm is used to guide the tendency of the whole harmony memory database, and the harmony is optimized and adjusted by using the numerical distribution probability. According to the characteristics of 0-1 knapsack problem, the random correction process is used to carry out mutation operation, which is called a novel instructional improvisation.According to the instructional improvisation process, in the process of genetic adjustment, the probability used is the 0-1 distribution probability in the harmony memory bank, which can make the newly generated harmony overall change for a better result. After many iterations, the harmony in the harmony memory bank will be closer to the best harmony.


## 3.4. An Improved Repair Operator

In problems with constraints, only feasible solutions can be assigned to the feasible region, and infeasible solutions will lead to search stagnation in the infeasible region. Therefore, it is necessary to ensure that all the harmonic vectors contained in HM satisfy the constraints. If the newly created harmony does not meet the criteria, a random repair mechanism is used to repair the harmony. First, select a certain number of dimensions independently and randomly, and arrange the dimensions out of order and judge whether the first dimension harmony is selected. If it is selected, remove it from the knapsack and judge whether it meets the requirements of knapsack capacity.If the newly generated harmonies meet the conditions, an improved method is used to optimize the harmonies under the constraints as described in Algorithm6 below. In this way, the harmony that does not meet the constraint is repaired or improved, so that the harmony vector stored in the harmony memory library HM can maximize the value of the items loaded in the knapsack as much as possible, and meet the constraint condition of the knapsack capacity.Algorithm 6: Improved repair operator.
(1)
Whileg < C(2)
Randomly select a certain number of dimensions(3)
Sort the selected dimensions out of order(4)
L = g; % Total weight held(5)
IfB (dd (i)) == 0(6)
B (dd(i)) = 1;(7)
g= g + W (dd (i));(8)
end(9)
ifg > C(10)
B (dd(i)) = 0;(11)
L = g − W (dd(i));(12)
end(13)
Determines whether the selected dimension is exceeded(14)
end(15)
g = L;Here, theB (dd (i)) for the corresponding state of harmony, W (dd (i)) for the corresponding to the object weight of harmony solution.


## 3.5. The HHSEDA Algorithm Flow

The proposed HHSEDA algorithm can be described as follows.Step 1.
Initialize the parameters of the HHSEDA algorithm including: the size of harmony memory bank (HMS), the probability of harmony memory bank considering (HMCR), the number of excellent population (YouxiuNum), the maximum number of iterations (J1) and the probability of population distribution (probability)Step 2.
The harmonic memory library is initialized according to an initialization method satisfying the constraints, and the fitness value is calculated.Step 3.
Based on an improved improvisation of the idea of the distribution estimation algorithm, new harmonies are generated.Step 4.
The newly generated solution is repaired or improved by the improved repair operator.Step 5.
Update the harmony memory to determine whether the new harmony generated is greater than the worst harmony in HM. If so, the worst harmony is replaced. If not, it is not replaced.Step 6.
Check whether the termination conditions are met. If yes, the termination is effected. If no, repeat Steps2 to Step 5.
The pseudocode of the HHSEDA algorithm is given in Algorithm7, in which J1 is the maximum number of iterations. In this process, the global dominant population is selected, the probability of knapsack being selected is calculated by using the distribution estimation algorithm, and then the harmony memory is considered, and the pitch is adjusted. Whenever a new harmony is generated, the greedy operators are used to repair or improve it.
The flow chart of the algorithm of HHSEDA is shown in Figure2.Algorithm 7: The HHSEDA algorithm for the 0-1 knapsack problem.
(1)
Initialize the algorithm and problem parameters.(2)
The harmony memory library should be initialized according to the feasible solution initialization method and the requirement of knapsack capacity to be met.(3)
Calculate the fitness value after initialization.(4)
fori = 1 to J1 do(5)
Find the worst and best harmony in the harmony memory database as p(6)
Calculate fitness values and sort them(7)
Fori = 1: K% select the dominant population(8)
The number ofK populations with the highest fitness value was selected(9)
end(10)
Forj = 1: N%% Generates new harmonies based on Guided Improvisation(11)
Count the number of bags selected in each column(12)
if rand < HMCR(13)
r = ceil (HMS ∗ rand) Randomly select the harmonic vector(14)
if rand < PAR(15)
If rand < probability(16)
Update the corresponding harmonies(17)
end(18)
end(19)
else Random mutation produces new harmonies(20)
end(21)
end for(22)
The total capacity of the newly produced harmony is calculated(23)
If the knapsack capacity requirement is met, the greedy selection is made under the constraint(24)
If the knapsack capacity requirement is not met, the harmony is repaired(25)
if fit (B) > fit (p)(26)
Update the global lowest harmony(27)
end(28)
end forFigure 2
The whole process of hybrid harmony search and distribution estimation algorithm.


## 4. Computational Results

In this section, a large number of experimental studies are carried out to assess the performance of the proposed hybrid algorithm. Based on 10 low dimensional instances and 3 groups of high-dimensional instances, the advantages of the proposed hybrid harmony search algorithm with distribution estimation are confirmed. The algorithm is written in MATLAB 2018a and runs on a computer with Intel Core i5-6300 (2.3 GHz) processor, 8 GB ram and windows 10 operating system.


### 4.1. The Parameter Data

This paper use BHS [51], DBHS [52], NGHS [46], ABHS [47] and other algorithms related to HHSEDA and harmony search to solve the 0-1 knapsack problem, and compare them with GA, PSO, BFPA [41], BABC-DE [54]. In order to ensure the comparability and effectiveness of the simulation experiments, the relevant parameters of the above nine algorithms are listed in Table 1.Table 1
The parameters.
VariantParameter settingHHSEDAHMCR = 0.99; HMS = 30; youxiunum = 10;ABHSCC = 8; GNC = 1; HMS = 30; PAR = 0.2;NGHSPm = 0.005; HMS = 30;DBHSHMCR = 0.99; PAR = 0.1; HMS = 30;BHSHMCR = 0.99; HMS = 30;GANP = 30;Pc = 0.8; Pm = 0.05; afa = 2;PSOWmax=0.8; Wmin = 04; Vmax = 10; Vmin = -10; c1 = 1.5; c2 = 1.5; N = 30;BFPAp = 0.8; λ = 1.5;BABC-DECR = 0.9;Note: the GA and PSO algorithms mentioned above are obtained by modifying the classical form to the binary form.


### 4.2. Comparison Based on Low Dimensional Instances of the 0-1 Knapsack Problem

In this section, 10 low dimensional instances of the 0-1 knapsack problem are selected to study the performance of the proposed algorithm. Table2 lists the information needed for the test including the dimension, weight, value and knapsack capacity of each data. The maximum number of iterations is 3000, and each instance has 30 experiments independently. In order to more comprehensively compare the performance of the improved harmony search algorithm in solving 0-1 knapsack problem, we consider statistical indicators such as “best,” “worst,” “average” and “standard deviation.” The best value and the worst value can indicate the advantages and disadvantages of each algorithm. Moreover, the average value and standard deviation can intuitively show the robustness of the algorithm.Table 2
Description of 10 low-dimensional 0–1 instances of the knapsack problem.
InstanceDimensionOptimal capacityParametersKP110295v = (95, 4, 60, 32, 23, 72, 80, 62, 65, 46), Vmax = 269， p = (55, 10, 47, 5, 4, 50, 8, 61, 85, 87)KP2201024v = (92, 4, 43, 83, 84, 68, 92, 82, 6, 44, 32, 18, 56, 83, 25, 96, 70, 48, 14, 58), Vmax = 878, p = (44, 46, 90, 72, 91, 40, 75, 35, 8, 54, 78, 40, 77, 15, 61, 17, 75, 29, 75, 63)KP3435v = (6, 5, 9, 7), Vmax = 20, p = (9, 11, 13, 15)KP4423v = (2, 4, 6, 7), Vmax = 11, p = (6, 10, 12, 13)KP515481.0694v = (56.358531, 80.874050, 47.987304, 89.596240, 74.660482, 85.894345, 51.353496, 1.498459, 36.445204, 16.589862, 44.569231, 0.466933, 37.788018, 57.118442, 60.716575), Vmax = 375, p = (0.125126, 19.330424, 58.500931, 35.029145, 82.284005, 17.410810, 71.050142, 30.399487, 9.140294, 14.731285, 98.852504, 11.908322, 0.891140, 53.166295, 60.176397)KP61052v = (30, 25, 20, 18, 17, 11, 5, 2, 1, 1), Vmax = 60, p = (20, 18, 17, 15, 15, 10, 5, 3, 1, 1)KP77107v = (31, 10, 20, 19, 4, 3, 6), Vmax = 50, p = (70, 20, 39, 37, 7, 5, 10)KP8239767v = (983, 982, 981, 980, 979, 978, 488, 976, 972, 486, 486, 972, 972, 485, 485, 969, 966, 483, 964, 963, 961, 958, 959), Vmax = 10000, p = (981, 980, 979, 978, 977, 976, 487, 974, 970, 485, 485, 970, 970, 484, 484, 976, 974, 482, 962, 961, 959, 958, 857)KP95130v = (15, 20, 17, 8, 31), Vmax = 80, p = (33, 24, 36, 37, 12)KP10201025v = (84, 83, 43, 4, 44, 6, 82, 92, 25, 83, 56, 18, 58, 14, 48, 70, 96, 32, 68, 92), Vmax = 879, p = (91, 72, 90, 46, 55, 8, 35, 75, 61, 15, 77, 40, 63, 75, 29, 75, 17, 78, 40, 44)The performance of the algorithm is compared with other six different algorithms. The comparison results with NGHS [46], BHS [51], DBHS [52], ABHS [47] are in Table 3, and the comparison results with GA, PSO, BFPA [41], BABC-DE [54] are in Table 4.Table 3
Comparison with harmony search algorithm variants for low dimensional instances.
InstanceMeasureHHSEDABHSDBHSNGHSABHSKP1Best130130130130130Median130130130130130Worst130130130130130Mean130130130130130Std00000KP2Best107107107107107Median107107107107107Worst107105107107107Mean107106.93107107107Std00.3651000KP3Best2323232323Median2323232323Worst2323232323Mean2323232323Std00000KP4Best3535353535Median3535353535Worst3535353535Mean3535353535Std00000KP5Best10251025101710251025Median102510259611012.501025Worst1025101991310251025Mean10251024.80963.731004.801025Std01.1027.0922.890KP6Best5252525252Median5252525252Worst5252525152Mean52525251.9352Std0000.25370KP7Best295295295295295Median295295295295295Worst295293295287295Mean295294.7295293.87295Std00.651302.31540KP8Best10241024101010241024Median1024102496010161024Worst102410189209401024Mean10241023.4959.87999.871024Std01.830822.4128.110KP9Best481.07481.07481.07481.07481.07Median481.07481.07481.16481.07481.07Worst481.07481.07437.93481.01481.07Mean481.07481.07469.13481.50481.07Std0010.6126.190KP10Best97679767976497679767Median97679767975897649767Worst97679763975297559767Mean97679766.79758.19763.69767Std00.87693.203.46010Table 4
Comparison with nonharmony search algorithm variants for low dimensional instances.
InstanceMeasureHHSEDAGAPSOBFPABABC-DEKP1Best130130130130130Median130130130130130Worst130130130130130Mean130130130130130Std00000KP2Best107107107107107Median107107107107107Worst107107107107107Mean107107107107107Std00000KP3Best23NANA2323Median23NANA2323Worst23NANA2323Mean23NANA2323Std0NANA00KP4Best35NANA3535Median35NANA3535Worst35NANA3535Mean35NANA3535Std0NANA00KP5Best10251025102510251025Median1025102510259951025Worst1025102510259221025Mean102510251025989.771025Std00028.980KP6Best5252525252Median5252525252Worst5252525252Mean5252525252Std00000KP7Best295295295295295Median295295295295295Worst295295295295295Mean295295295295295Std00000KP8Best10241024102410241024Median10241024102410131024Worst1024102410249221024Mean1024102410241003.11024Std00024.350KP9Best481.07481.07481.07481.07481.07Median481.07481.07481.07481.07481.07Worst481.07481.07481.07481.07481.07Mean481.07481.07481.07481.07481.07Std00000KP10Best9767NANA97679767Median9767NANA97659767Worst9767NANA97619767Mean9767NANA9764.79767Std0NANA1.82570Table3 contains experimental results for the 10 low dimensional instances of the knapsack problem with known optimal values. Each algorithm of HHSEDA, ABHS, NGHS, DBHS and BHS is set to have 3000 iterations. The number of population is 30 and the number of independent runs is 30.According to Table3, HHSEDA and ABHS have the best performance: the optimal value, median, worst value and average value are the same as the optimum and the standard deviation of 30 independent runs is 0 for each instance. The other three algorithms do not perform so well. The probability of NGHS algorithm reaching the optimum for the optimal value, median, worst, average and standard deviation is 100%, 70%, 40%, and 40%, respectively. The probability of DBHS reaching the optimum for the optimal value in the five evaluation criteria is 70%, 60%, 60%, and 60%, respectively. The probability of BHS reaching the optimum for the optimal value in the five evaluation criteria is 100%, 100%, 50%, 50%, and 50%, respectively.In Table4, GA, PSO, BFPA and BABC-DE are set with the same iteration times, population number and independent test times as those in Table 3. According to Table 4, BABC-DE can achieve the same results as HHSEDA. GA and PSO have a good performance overall, but they cannot produce the result satisfying the knapsack capacity constraint for KP3, KP4 and KP10. The reason is that in the process of algorithm repair for both GA and PSO, the penalty method cannot be solved for relatively complex data. The probability of BFPA algorithm reaching the optimum for the optimal value, median, worst value, mean, and standard deviation is 100%, 70%, 70%, and 70%, respectively.In sum, based on the above experiments on the low dimensional instances, HHSEDA, ABHS and BABC-DE are better than other algorithms, and they can achieve the optimal value for 5 instances.


### 4.3. Comparison Based on High Dimensional Instances of the 0-1 Knapsack Problem

Based on the above experiments on 10 low dimensional instances of 0-1 knapsack problem, HHSEDA performs better than other algorithms in most cases. These low dimensional instances relatively simple. In the above experiments, the highest dimension is only 23. As the dimension increases, 0-1 knapsack problem becomes more and more complex.


#### 4.3.1. Uncorrelation High-Dimensional Experimental

In order to further assess the performance of the proposed HHSEDA algorithm, we use nine high-dimensional instances of 0-1 knapsack problem. The dimensions of these instances include 100, 200, 300, 500, 700, 1000, 1200, 1500, and 2000. The generation of each uncorrelated high-dimensional instances (KP25-KP33) is as follows: the volume of each knapsack is randomly selected from 5 to 20, the corresponding random profit range is 50 to 100, and the maximum capacity of the knapsack is 0.75 of the total capacity of the items generated according to the above procedure. The above examples only need to be generated randomly once, and remain unchanged in the later experiments. The maximum number of iterations for solving the above 9 instances is 10000, 10000, 10000, 20000, 30000, 50000, 50000, 70000 and 100000, respectively. The number of population is set to 30 in all experiments, and the number of independent experiments is 30.Tables5 and 6 report the performance metrics for each instance for HHSEDA and other comparison algorithms with the best results highlighted in bold face. The optimal profit of KP25-KP33 is unknown, and the best value, median, worst value, average and standard deviation are all considered in the table.Table 5
Comparison with HS variants for high dimensional instances with no correlation.
InstanceMeasureHHSEDAABHSNGHSDBHSBHSKP11Time1.93511.960.210.220.18Best64236423613156346423Median6419.564015952.55292.56400.5Worst63996388577451306385Mean6416.66402.85947.35313.36402.8Std7.83759.2165106.28116.239.93KP12Time3.6128.250.32116.230.35Best1296012954119551051412949Median1295512904115419816012935Worst1294712859107349609412864Mean1295.512899115619900212930Std4.020.98239.34210.5018.17KP13Time5.7643.440.410.500.55Best1954019493174251472119531Median1953419445167761419019496Worst1951319366152721391019373Mean1953119441167381425919490Std7.5629.62520.38227.0029.55KP14Time20.31191.961.241.601.88Best3207831958275622339832049Median3205931911263872265631998Worst3203131816255972231331941Mean3205631896264712270331996Std10.529741.48551.19248.6226.0169KP15Time47.10580.852.573.333.57Best4494244800370043108144882Median4492744720352793053844857Worst4490944658336803013544782Mean4492644721353143056944851Std9.647238.69723.59242.9424.83KP16Time126.622009.005.47927.1910.27Best6460464482508644461564498Median6457264358419564350064457Worst6455164288473714291064395Mean6457264360490064351664457Std13.3566.34922.25427.8723.25KP17Time133.212398.706.728.1912.75Best7700576515592815159776888Median7695676337570935106576812Worst7688976207561155066276635Mean7695376350573415110476797Std29.0085.40907.81266.7657.07KP18Time366.725715.7011.9414.4322.14Best9636495971729146445196233Median9630295667702986354596084Worst9624695385682666282695985Mean9629995660703046355396091Std27.20122.511313.4457.1156.51KP19Time545.2414870.0025.5627.0636.64Best1272601265689395384341126978Median1271941264389152283182126860Worst1271051262508885782488126710Mean1271901264309119583306126870Std31.8578.811437475.0756.78Bold shows the best result.Table 6
Comparison with non-HS variants for high dimensional instances with no correlation.
InstanceMeasureHHSEDAGAPSOBFPABABC-DEKP11Time1.94NA4.013.177.57Best6423NA638552946423Median6419.5NA62544537.56421Worst6399NA613142276413Mean6416.6NA6269.24555.86419.7Std7.8375NA62.83223.973.35KP12Time3.61NA6.5212.1211.01Best12960NA11820943612921Median12955NA11612862612890Worst12947NA11479830312875Mean1295.5NA116378671.412892Std4.0NA91.2328312.84KP13Time5.7642.3810.5823.9815.60Best1954019405171041336319461Median1953419127164371275419396Worst1951318870162401214819363Mean1953119123165211274719402Std7.56124.90217.87318.9222.29KP14Time20.31124.4033.41104.2647.13Best3207830686266212106731807Median3205930169257562056031711Worst3203129911254241972531667Mean3205630193258242055331716Std10.5297186.70262.49294.533.76KP15Time47.10222.2666.95298.56224.20Best4494241261355172988844401Median4492740851347712845744339Worst4490940473343672756844269Mean4492640847347922847344339Std9.6472208.89251.70594.9229.85KP16Time126.62551.19154.20875.33491.93Best6460457392488594155164115Median6457256320482614018863749Worst6455155726477113946163691Mean6457256427483014033163760Std13.35443.72286.87631.6572.79KP17Time133.21708.01178.141176.40614.70Best7700566543574324910976026Median7695665757564594771475872Worst7688965148560354671875788Mean7695365757565774782875886Std29.00321.30351.11575.458.32KP18Time366.721209.30301.622342.51239.90Best9636481365703626159795144Median9630280220695885960094969Worst9624679387687855855194910Mean9629980263696195982694979Std27.20506.60342.00787.951.80KP19Time545.242452.50562.591958.605568.00Best1272601039049098480234125521Median1271941027799009278365125341Worst1271051018438951976813125228Mean127190102719009778388125350Std31.85554.35315.43813.2168.36Bold shows the best result.In many cases, the worst values obtained by HHSEDA are far better than the worst values obtained by other algorithms. In terms of optimal value, HHSEDA performs the same as ABHS, BHS and BABC-DE algorithm except for KP11 (100-dimensional). Compared with the suboptimal values achieved by other algorithms, the corresponding improvement rates of HHSEDA are 0%, 0.05%, 0.09%, 0.133%, 0.16%, 0.15%, 0.14% and 0.22%, respectively (When GA algorithm applied to the 100-dimensional KP11 and 200-dimensional KP12, the results generated do not meet the constraints and are deleted). In terms of the worst value, HHSEDA shows better performance in all cases except KP11 (HHSEDA100 dimension) which is slightly lower than BABC-DE algorithm. Compared with the worst value achieved by other algorithms, the corresponding improvement rates are 51.38%, 55.93%, 53.16%, 62.38%, 57.72%, 63.58%, 64.58%, 64.38%, 65.47%, respectively. Among these data, the biggest improvement is 65.47% of BFPA algorithm in the case of 2000 dimension. In general, the improvement rate will become more obvious as the dimension increases. In terms of average value, the corresponding improvements rates are 0.5%, 25.26%, 42.22%, 0.20%, 13.37%, 26.27%, 56.56% and 1.03%, respectively.


#### 4.3.2. Low Correlation High-Dimensional Experimental

In order to further evaluate the performance of HHSEDA, nine instances of 0-1 knapsack problem with dimensions of 100, 200, 300, 500, 700, 1000, 1200, 1500 and 2000 are randomly generated. The nine instances are generated according to the following conditions: the volume of each object is randomly selected from 10 to 50, the corresponding profit value is randomly selected from 10 of the corresponding object volume, and the maximum capacity of the knapsack is one-half of the total weight of the items generated according to the above procedure.BHS, DBHS, NGHS, ABHS, GA, PSO, BFPA, BABC-DE and HHSEDA are applied to these instances. The results are reported in Tables7 and 8.Table 7
Comparison with HS variants for high dimensional instances with low correlation.
InstanceMeasureHHSEDAABHSNGHSDBHSBHSKP20Time1.8611.710.200.470.28Best16651665162715361665Median16651663158815231661Worst16601656156115061654Mean16641662159315231661Std1.002.5215.777.282.48KP21Time3.2937.860.381.130.53Best34953491337631903494Median34933486330031463489Worst34853473324231263479Mean34933484330631483489Std2.095.0937.6412.993.56KP22Time5.0933.240.452.090.88Best54015387511148875398Median53975374502248235388Worst53895352490747935377Mean53965372501948245387Std3.269.0845.8918.585.33KP23Time16.67211.811.347.924.29Best86958658820777868690Median86908646801077458677Worst86838615790577118664Mean86908639801977438677Std3.3914.8972.6118.466.19KP24Time35.88556.702.6219.839.93Best1216412112112991080012158Median1215712080111131074112141Worst1214612042109491070612132Mean1215612079111151074412142Std4.0618.8069.9320.706.11KP25Time95.821201.276.6654.2637.79Best1758117430159851551017572Median1757017380158581542017556Worst1756315112157491536917534Mean1757017245158571542517556Std5.0032.9467.4031.068.97KP26Time105.62497.866.9056.7930.54Best2100020798190751842220971Median2098420741188941836720959Worst2096520662187531832320939Mean2098120742188961836620957Std8.5140.9387.6427.118.45KP27Time176.705811.0611.76106.1537.01Best2637926146238592318026343Median2635826101236042307026326Worst2634226048234092302226311Mean2635926097236192307826326Std9.1433.98121.7847.0611.48KP28Time348.51351422.64207.4576.04Best3454534267311133027734489Median3451534206308073015834479Worst3449234154306173014134455Mean3451634213308243017734476Std11.4541.81120.2040.9411.66Bold shows the best result.Table 8
Comparison with non-HS variants for high dimensional instances with low correlation.
InstanceMeasureHHSEDAGAPSOBFPABABC-DEKP20Time1.8612.194.983.0326.03Best16651657160815541636Median16651648158915351618Worst16601639157715001607Mean16641648158815311619Std1.004.196.8914.696.59KP21Time3.2926.137.8912.3244.58Best34953406326632493371Median34933379324931733331Worst34853357322730913314Mean34933379324731753333Std2.0912.2610.0532.9514.35KP22Time5.0939.7811.8722.9870.96Best54015181498849335092Median53975128495148275065Worst53895087492347575038Mean53965128495448305065Std3.2624.4616.8844.0913.35KP23Time16.67111.8534.78116.82131.58Best86958233795178988323Median86908175791177848080Worst86838139788076928045Mean86908179791277858087Std3.3925.6817.5548.2549.59KP24Time35.88229.8266.59353.11148.32Best1216411344110071092611368Median1215711288109571080011178Worst1214611245109201075311141Mean1215611290109561081711186Std4.0622.7724.2865.2444.81KP25Time95.82593.82146.321136.50343.02Best1758116232157821564516079Median1757016169156971548715987Worst1756316055156351537615932Mean1757016162156991549515988Std5.0040.7331.6277.3338.30KP26Time105.6832.52198.751205.96500.89Best2100019219187431865919149Median2098419182186921849419025Worst2096519147186281838818969Mean2098119180186911849319027Std8.5121.4226.2679.5641.01KP27Time176.701419.12318.232414.701426.00Best2637924107234872345524220Median2635824024234012316223820Worst2634223964233442301523769Mean2635924022234062318223851Std9.1445.7339.86111.00106.67KP28Time348.52133.43616.436333.802677.90Best3454531453306533057931258Median3451531312305863033131098Worst3449231211305233015431057Mean3451631314305873033131117Std11.4566.1332.72101.2551.79Bold shows the best result.In terms of optimal value, HHSEDA obtains the same optimal value as ABHS and BHS algorithms except for KP20 (dimension = 100). Compared with the suboptimal value achieved by other algorithms, the corresponding improvement rates of HHSEDA are 0%, 0.03%, 0.06%, 0.06%, 0.05%, 0.05%, 0.14%, 0.14%, and 0.16%, respectively. In terms of average value, the corresponding improvement rates of HHSEDA are 0.78%, 8.98%, 12.69%, 0.13%, 6.84%, 10.19%, 11.99%, and 7.98%, respectively. Compared with the worst value achieved by other algorithms, the corresponding improvement rates are 10.67%, 12.75%, 13.29%, 12.88%, 13.45%, 14.28%, 14.42%, 14.46%, and 14.44% respectively.


#### 4.3.3. High Correlation High-Dimensional Experimental

In order to further evaluate the performance of HHSEDA, nine instances of 0-1 knapsack problem with dimensions of 100, 200, 300, 500, 700, 1000, 1200, 1500 and 2000 are randomly generated. The instances with strong correlation between value and weight are generated under the following conditions: the volume of each object is randomly selected from 10 to 50, the corresponding profit value is added with a random number of 0 to 10, and the maximum capacity of the knapsack is half of the total weight of the items generated according to the above procedure. BHS, DBHS, NGHS, ABHS, GA, PSO, BFPA, BABC-DE, and HHSEDA are used for comparison. The experimental results are presented in Tables9 and 10.Table 9
Comparison with HS variants for high dimensional instances with high correlation.
InstanceMeasureHHSEDAABHSNGHSDBHSBHSKP29Time1.8012.540.250.490.29Best17691769173516871769Median17681765171616771766Worst17661759165816711761Mean17811765171116771766Std0.82772.4317.094.671.94KP30Time3.5822.980.381.140.66Best38573851374336603854Median38553844371436413849Worst38513831367436263837Mean3854.638433713.536423847Std1.35444.8915.196.414.11KP31Time4.9834.130.591.881.11Best54985486532152065491Median54945471527951925479Worst54875454524651815462Mean5493.65470527851935479Std2.63517.1119.687.266.75KP32Time17.58227.231.667.553.99Best94359409908889329426Median94309376903389099418Worst94249346896288849400Mean9429.89378902789079417Std2.478615.4328.7812.685.82KP33Time38.80564.623.3219.338.87Best1321413174126111245813203Median1321013133125481240113192Worst1320413095124801238313183Mean1320913133125481240413192Std3.410818.1431.6016.065.52KP34Time92.952072.706.9252.9623.85Best1905118982181481787619037Median1904218945180391784919018Worst1902818906179411783119002Mean1904318940180391785319018Std5.006219.1943.3712.878.16KP35Time108.292483.38.562652.0222.79Best2270022468216182132522674Median2268522397215132128622654Worst2267422342214122124922638Mean2268522407215112128622653Std5.424131.7848.5616.058.27KP36Time195.27529.513.94132.7040.38Best2817527851267042645828149Median2816627835265852636228132Worst2815127799264772633528118Mean2816527827265842636828133Std6.450523.0360.6526.218.17KP37Time361.391376528.79291.1981.75Best3802137654360323569937983Median3800337617359113565137964Worst3798537597357573561737943Mean3800337626359063565037964Std7.965823.5970.2923.798.76Bold shows the best result.Table 10
Comparison with non-HS variants for high dimensional instances with high correlation.
InstanceMeasureHHSEDAGAPSOBFPABABC-DEKP29Time1.804812.15824.6123.419014.1013Best17691761173316951757Median17681754172216691748Worst17661747171016441742Mean17811753.91721.81667.731748.2Std0.82773.994.9610.213.5785KP30Time3.5823.319.7612.3523.02Best38573794372236623785Median38553773.537063617.53772.5Worst38513753369635913763Mean3854.637723707.43622.263773.23Std1.3510.256.2719.685.63KP31Time4.9834.7810.9624.9631.00Best54985377528552135391Median549453525265.551635367Worst54875321525451195355Mean5493.65309.35266.45169.735367.63Std2.6414.428.0924.258.88KP32Time17.58127.732.95112.2668.62Best94359167902189539189Median94309140900788709167Worst94249094899188309146Mean9429.89138.19006.78875.29165.3Std2.4816.767.4327.0811.01KP33Time38.80268.473.93297.6198.70Best1321412732125701244612782Median1321012702125291236012747Worst1320412677125081229312728Mean1320912703125301236212751Std3.4114.4110.3936.3714.56KP34Time92.94549164.93888.2420Best1905118303180411787118371Median1904218259180121780918339Worst1902818220179931772218312Mean1904318258180111780918338Std5.0120.5512.4138.3816.83KP35Time108.29815.68179.69120.2432.4Best2270021771215102133021904Median22685217232145721216.521836.5Worst2267421678214222110121805Mean226852172321455.521219.2621842.2Std5.4225.1415.9646.4824.85KP36Time195.271224316.332416.5746.8Best2817526944266132644127042Median281662687726561262872699.6Worst2815126821265342620826938Mean2816526873265622629026997Std6.4530.6020.7849.7325.63KP37Time361.392078.4596.386315.52283Best3802136318359353569736524Median38003362563587335540.536420Worst3798536188358503547736361Mean3800336250358803555736427Std7.9732.2023.0153.2736.33Bold shows the best result.In terms of the optimal value, because the weight of the object loaded into the knapsack is highly related to the value, the improvement of the optimal value is not obvious. In terms of the suboptimal value, the corresponding improvement rates of HHSEDA are 0%, 0.08%, 0.01%, 0.10%, 0.08%, 0.07%, 0.11%, 0.09%, and 0.01%, respectively. In terms of the mean value, the corresponding improvement rates of HHSEDA are 0.75%, 4.95%, 6.32%, 0.23%, 3.64%, 4.39%, 6.71%, and 3.25%, respectively. In terms of the worst value, the corresponding improvement rates of HHSEDA are 6.51%, 7.24%, 7.19%, 6.74%, 7.41%, 7.37%, 7.45%, 7.41%, and 7.07%, respectively. Among these data, the largest rate is 7.45% from BFPA algorithm for the instance with a dimension of 1200.According to Table11, HHSEDA algorithm runs slower than NGHS, DBHS and BHS among the harmony search variants algorithms. This is because the HHSEDA algorithm needs to calculate the probability of the harmony distribution in the harmony memory bank in each iteration, which increases the time loss to some extent. However, compared with other nonharmony search variants algorithms in time consumption, it has some advantages.Table 11
Comparison of running time across different algorithms and different dimensions.
DimensionHHSEDAABHSNGHSDBHSBHSGAPSOBFPABABCDE1004813296572004913256873004912385765004912395867004912365871000491237586120049123758615004912365872000491237568HHSEDA algorithm has a maximum standard deviation less than 32, 8, 12 for instances with no correlation, low and high and correlation, respectively. In terms of standard deviation, HHSEDA algorithm has an advantage over other algorithms. This is because the HHSEDA algorithm generalizes the harmony memory from the macro level, and then feeds back to a single harmony, and makes the result more accurate by improving and repairing the operator.BABC-DE, ABHS, HHSEDA, BFPA, GA, and PSO are compared in simulation graphs for the 27 instances in Figure3. Except in Experiment 1 (unrelated 100-dimensional) and Experiment 2 (unrelated 200-dimensional) where GA algorithm violates the constraints, the average convergence speed and accuracy of HHSEDA algorithm are obviously better than other algorithms.Figure 3
Curves of the optimization results.
(a)(b)(c)(d)(e)From the simulation curves in Figure3, BABC-DE can achieve fast convergence and good results in general. However, for Experiments 8-27, it is easy to fall into the local optimal, because the repair operator of BABC-DE cannot jump out of the local optimal when processing the data with high correlation. Observing the convergence diagram of BFPA, it can be seen that the algorithm is always ineffective for solving high-dimensional problems, and it takes a lot of time to search globally (Levy flight) and locally, and the repair operator it uses makes it easy to fall into local optimal. By observing the convergence graph of particle swarm optimization (PSO) and genetic algorithm (GA), we can see that the results are not good when solving high-dimensional problems, and they are easy to fall into local optimal. This is because their efficiency are not very good, and the penalty function method used is not obvious in the repair of experimental results, and some constraints are violated in some data.Observing the convergence diagram of ABHS in Figure3, it can be seen that ABHS has relatively good results in all experiments. For Experiments 1-9, the convergence diagram of ABHS algorithm is the closest to HHSEDA, and the parameter adjustment of this algorithm makes it better. But compared with HHSEDA, the effect of adjusting the harmony vector through the probability of harmony distribution in the harmony memory bank is relatively poor.In order to evaluate the dispersion of HHSEDA algorithm, a total of 9 instances with low-correlation are selected, and they are run independently for 10 times. The generated results are presented by the box diagrams, as shown in Figure4. It can be seen from the figure that the minimum value, maximum value and median of HHSEDA algorithm are closer and better than other algorithms. In conclusion, HHSEDA algorithm has better accuracy and computational stability.Figure 4
The boxplots of the algorithms.
(a)(b)It can be analyzed from Tables1–11 and Figures 1–4 that HHSEDA is an excellent HS variant with fast convergence and excellent stability. Therefore, HHSEDA is a more efficient and reliable algorithm for solving the 0-1 knapsack problem of high dimension. The reason may include the better initialization, enhanced local search based on the hybrid strategies, and the infeasible solution repair strategy.


## 4.1. The Parameter Data

This paper use BHS [51], DBHS [52], NGHS [46], ABHS [47] and other algorithms related to HHSEDA and harmony search to solve the 0-1 knapsack problem, and compare them with GA, PSO, BFPA [41], BABC-DE [54]. In order to ensure the comparability and effectiveness of the simulation experiments, the relevant parameters of the above nine algorithms are listed in Table 1.Table 1
The parameters.
VariantParameter settingHHSEDAHMCR = 0.99; HMS = 30; youxiunum = 10;ABHSCC = 8; GNC = 1; HMS = 30; PAR = 0.2;NGHSPm = 0.005; HMS = 30;DBHSHMCR = 0.99; PAR = 0.1; HMS = 30;BHSHMCR = 0.99; HMS = 30;GANP = 30;Pc = 0.8; Pm = 0.05; afa = 2;PSOWmax=0.8; Wmin = 04; Vmax = 10; Vmin = -10; c1 = 1.5; c2 = 1.5; N = 30;BFPAp = 0.8; λ = 1.5;BABC-DECR = 0.9;Note: the GA and PSO algorithms mentioned above are obtained by modifying the classical form to the binary form.


## 4.2. Comparison Based on Low Dimensional Instances of the 0-1 Knapsack Problem

In this section, 10 low dimensional instances of the 0-1 knapsack problem are selected to study the performance of the proposed algorithm. Table2 lists the information needed for the test including the dimension, weight, value and knapsack capacity of each data. The maximum number of iterations is 3000, and each instance has 30 experiments independently. In order to more comprehensively compare the performance of the improved harmony search algorithm in solving 0-1 knapsack problem, we consider statistical indicators such as “best,” “worst,” “average” and “standard deviation.” The best value and the worst value can indicate the advantages and disadvantages of each algorithm. Moreover, the average value and standard deviation can intuitively show the robustness of the algorithm.Table 2
Description of 10 low-dimensional 0–1 instances of the knapsack problem.
InstanceDimensionOptimal capacityParametersKP110295v = (95, 4, 60, 32, 23, 72, 80, 62, 65, 46), Vmax = 269， p = (55, 10, 47, 5, 4, 50, 8, 61, 85, 87)KP2201024v = (92, 4, 43, 83, 84, 68, 92, 82, 6, 44, 32, 18, 56, 83, 25, 96, 70, 48, 14, 58), Vmax = 878, p = (44, 46, 90, 72, 91, 40, 75, 35, 8, 54, 78, 40, 77, 15, 61, 17, 75, 29, 75, 63)KP3435v = (6, 5, 9, 7), Vmax = 20, p = (9, 11, 13, 15)KP4423v = (2, 4, 6, 7), Vmax = 11, p = (6, 10, 12, 13)KP515481.0694v = (56.358531, 80.874050, 47.987304, 89.596240, 74.660482, 85.894345, 51.353496, 1.498459, 36.445204, 16.589862, 44.569231, 0.466933, 37.788018, 57.118442, 60.716575), Vmax = 375, p = (0.125126, 19.330424, 58.500931, 35.029145, 82.284005, 17.410810, 71.050142, 30.399487, 9.140294, 14.731285, 98.852504, 11.908322, 0.891140, 53.166295, 60.176397)KP61052v = (30, 25, 20, 18, 17, 11, 5, 2, 1, 1), Vmax = 60, p = (20, 18, 17, 15, 15, 10, 5, 3, 1, 1)KP77107v = (31, 10, 20, 19, 4, 3, 6), Vmax = 50, p = (70, 20, 39, 37, 7, 5, 10)KP8239767v = (983, 982, 981, 980, 979, 978, 488, 976, 972, 486, 486, 972, 972, 485, 485, 969, 966, 483, 964, 963, 961, 958, 959), Vmax = 10000, p = (981, 980, 979, 978, 977, 976, 487, 974, 970, 485, 485, 970, 970, 484, 484, 976, 974, 482, 962, 961, 959, 958, 857)KP95130v = (15, 20, 17, 8, 31), Vmax = 80, p = (33, 24, 36, 37, 12)KP10201025v = (84, 83, 43, 4, 44, 6, 82, 92, 25, 83, 56, 18, 58, 14, 48, 70, 96, 32, 68, 92), Vmax = 879, p = (91, 72, 90, 46, 55, 8, 35, 75, 61, 15, 77, 40, 63, 75, 29, 75, 17, 78, 40, 44)The performance of the algorithm is compared with other six different algorithms. The comparison results with NGHS [46], BHS [51], DBHS [52], ABHS [47] are in Table 3, and the comparison results with GA, PSO, BFPA [41], BABC-DE [54] are in Table 4.Table 3
Comparison with harmony search algorithm variants for low dimensional instances.
InstanceMeasureHHSEDABHSDBHSNGHSABHSKP1Best130130130130130Median130130130130130Worst130130130130130Mean130130130130130Std00000KP2Best107107107107107Median107107107107107Worst107105107107107Mean107106.93107107107Std00.3651000KP3Best2323232323Median2323232323Worst2323232323Mean2323232323Std00000KP4Best3535353535Median3535353535Worst3535353535Mean3535353535Std00000KP5Best10251025101710251025Median102510259611012.501025Worst1025101991310251025Mean10251024.80963.731004.801025Std01.1027.0922.890KP6Best5252525252Median5252525252Worst5252525152Mean52525251.9352Std0000.25370KP7Best295295295295295Median295295295295295Worst295293295287295Mean295294.7295293.87295Std00.651302.31540KP8Best10241024101010241024Median1024102496010161024Worst102410189209401024Mean10241023.4959.87999.871024Std01.830822.4128.110KP9Best481.07481.07481.07481.07481.07Median481.07481.07481.16481.07481.07Worst481.07481.07437.93481.01481.07Mean481.07481.07469.13481.50481.07Std0010.6126.190KP10Best97679767976497679767Median97679767975897649767Worst97679763975297559767Mean97679766.79758.19763.69767Std00.87693.203.46010Table 4
Comparison with nonharmony search algorithm variants for low dimensional instances.
InstanceMeasureHHSEDAGAPSOBFPABABC-DEKP1Best130130130130130Median130130130130130Worst130130130130130Mean130130130130130Std00000KP2Best107107107107107Median107107107107107Worst107107107107107Mean107107107107107Std00000KP3Best23NANA2323Median23NANA2323Worst23NANA2323Mean23NANA2323Std0NANA00KP4Best35NANA3535Median35NANA3535Worst35NANA3535Mean35NANA3535Std0NANA00KP5Best10251025102510251025Median1025102510259951025Worst1025102510259221025Mean102510251025989.771025Std00028.980KP6Best5252525252Median5252525252Worst5252525252Mean5252525252Std00000KP7Best295295295295295Median295295295295295Worst295295295295295Mean295295295295295Std00000KP8Best10241024102410241024Median10241024102410131024Worst1024102410249221024Mean1024102410241003.11024Std00024.350KP9Best481.07481.07481.07481.07481.07Median481.07481.07481.07481.07481.07Worst481.07481.07481.07481.07481.07Mean481.07481.07481.07481.07481.07Std00000KP10Best9767NANA97679767Median9767NANA97659767Worst9767NANA97619767Mean9767NANA9764.79767Std0NANA1.82570Table3 contains experimental results for the 10 low dimensional instances of the knapsack problem with known optimal values. Each algorithm of HHSEDA, ABHS, NGHS, DBHS and BHS is set to have 3000 iterations. The number of population is 30 and the number of independent runs is 30.According to Table3, HHSEDA and ABHS have the best performance: the optimal value, median, worst value and average value are the same as the optimum and the standard deviation of 30 independent runs is 0 for each instance. The other three algorithms do not perform so well. The probability of NGHS algorithm reaching the optimum for the optimal value, median, worst, average and standard deviation is 100%, 70%, 40%, and 40%, respectively. The probability of DBHS reaching the optimum for the optimal value in the five evaluation criteria is 70%, 60%, 60%, and 60%, respectively. The probability of BHS reaching the optimum for the optimal value in the five evaluation criteria is 100%, 100%, 50%, 50%, and 50%, respectively.In Table4, GA, PSO, BFPA and BABC-DE are set with the same iteration times, population number and independent test times as those in Table 3. According to Table 4, BABC-DE can achieve the same results as HHSEDA. GA and PSO have a good performance overall, but they cannot produce the result satisfying the knapsack capacity constraint for KP3, KP4 and KP10. The reason is that in the process of algorithm repair for both GA and PSO, the penalty method cannot be solved for relatively complex data. The probability of BFPA algorithm reaching the optimum for the optimal value, median, worst value, mean, and standard deviation is 100%, 70%, 70%, and 70%, respectively.In sum, based on the above experiments on the low dimensional instances, HHSEDA, ABHS and BABC-DE are better than other algorithms, and they can achieve the optimal value for 5 instances.


## 4.3. Comparison Based on High Dimensional Instances of the 0-1 Knapsack Problem

Based on the above experiments on 10 low dimensional instances of 0-1 knapsack problem, HHSEDA performs better than other algorithms in most cases. These low dimensional instances relatively simple. In the above experiments, the highest dimension is only 23. As the dimension increases, 0-1 knapsack problem becomes more and more complex.


### 4.3.1. Uncorrelation High-Dimensional Experimental

In order to further assess the performance of the proposed HHSEDA algorithm, we use nine high-dimensional instances of 0-1 knapsack problem. The dimensions of these instances include 100, 200, 300, 500, 700, 1000, 1200, 1500, and 2000. The generation of each uncorrelated high-dimensional instances (KP25-KP33) is as follows: the volume of each knapsack is randomly selected from 5 to 20, the corresponding random profit range is 50 to 100, and the maximum capacity of the knapsack is 0.75 of the total capacity of the items generated according to the above procedure. The above examples only need to be generated randomly once, and remain unchanged in the later experiments. The maximum number of iterations for solving the above 9 instances is 10000, 10000, 10000, 20000, 30000, 50000, 50000, 70000 and 100000, respectively. The number of population is set to 30 in all experiments, and the number of independent experiments is 30.Tables5 and 6 report the performance metrics for each instance for HHSEDA and other comparison algorithms with the best results highlighted in bold face. The optimal profit of KP25-KP33 is unknown, and the best value, median, worst value, average and standard deviation are all considered in the table.Table 5
Comparison with HS variants for high dimensional instances with no correlation.
InstanceMeasureHHSEDAABHSNGHSDBHSBHSKP11Time1.93511.960.210.220.18Best64236423613156346423Median6419.564015952.55292.56400.5Worst63996388577451306385Mean6416.66402.85947.35313.36402.8Std7.83759.2165106.28116.239.93KP12Time3.6128.250.32116.230.35Best1296012954119551051412949Median1295512904115419816012935Worst1294712859107349609412864Mean1295.512899115619900212930Std4.020.98239.34210.5018.17KP13Time5.7643.440.410.500.55Best1954019493174251472119531Median1953419445167761419019496Worst1951319366152721391019373Mean1953119441167381425919490Std7.5629.62520.38227.0029.55KP14Time20.31191.961.241.601.88Best3207831958275622339832049Median3205931911263872265631998Worst3203131816255972231331941Mean3205631896264712270331996Std10.529741.48551.19248.6226.0169KP15Time47.10580.852.573.333.57Best4494244800370043108144882Median4492744720352793053844857Worst4490944658336803013544782Mean4492644721353143056944851Std9.647238.69723.59242.9424.83KP16Time126.622009.005.47927.1910.27Best6460464482508644461564498Median6457264358419564350064457Worst6455164288473714291064395Mean6457264360490064351664457Std13.3566.34922.25427.8723.25KP17Time133.212398.706.728.1912.75Best7700576515592815159776888Median7695676337570935106576812Worst7688976207561155066276635Mean7695376350573415110476797Std29.0085.40907.81266.7657.07KP18Time366.725715.7011.9414.4322.14Best9636495971729146445196233Median9630295667702986354596084Worst9624695385682666282695985Mean9629995660703046355396091Std27.20122.511313.4457.1156.51KP19Time545.2414870.0025.5627.0636.64Best1272601265689395384341126978Median1271941264389152283182126860Worst1271051262508885782488126710Mean1271901264309119583306126870Std31.8578.811437475.0756.78Bold shows the best result.Table 6
Comparison with non-HS variants for high dimensional instances with no correlation.
InstanceMeasureHHSEDAGAPSOBFPABABC-DEKP11Time1.94NA4.013.177.57Best6423NA638552946423Median6419.5NA62544537.56421Worst6399NA613142276413Mean6416.6NA6269.24555.86419.7Std7.8375NA62.83223.973.35KP12Time3.61NA6.5212.1211.01Best12960NA11820943612921Median12955NA11612862612890Worst12947NA11479830312875Mean1295.5NA116378671.412892Std4.0NA91.2328312.84KP13Time5.7642.3810.5823.9815.60Best1954019405171041336319461Median1953419127164371275419396Worst1951318870162401214819363Mean1953119123165211274719402Std7.56124.90217.87318.9222.29KP14Time20.31124.4033.41104.2647.13Best3207830686266212106731807Median3205930169257562056031711Worst3203129911254241972531667Mean3205630193258242055331716Std10.5297186.70262.49294.533.76KP15Time47.10222.2666.95298.56224.20Best4494241261355172988844401Median4492740851347712845744339Worst4490940473343672756844269Mean4492640847347922847344339Std9.6472208.89251.70594.9229.85KP16Time126.62551.19154.20875.33491.93Best6460457392488594155164115Median6457256320482614018863749Worst6455155726477113946163691Mean6457256427483014033163760Std13.35443.72286.87631.6572.79KP17Time133.21708.01178.141176.40614.70Best7700566543574324910976026Median7695665757564594771475872Worst7688965148560354671875788Mean7695365757565774782875886Std29.00321.30351.11575.458.32KP18Time366.721209.30301.622342.51239.90Best9636481365703626159795144Median9630280220695885960094969Worst9624679387687855855194910Mean9629980263696195982694979Std27.20506.60342.00787.951.80KP19Time545.242452.50562.591958.605568.00Best1272601039049098480234125521Median1271941027799009278365125341Worst1271051018438951976813125228Mean127190102719009778388125350Std31.85554.35315.43813.2168.36Bold shows the best result.In many cases, the worst values obtained by HHSEDA are far better than the worst values obtained by other algorithms. In terms of optimal value, HHSEDA performs the same as ABHS, BHS and BABC-DE algorithm except for KP11 (100-dimensional). Compared with the suboptimal values achieved by other algorithms, the corresponding improvement rates of HHSEDA are 0%, 0.05%, 0.09%, 0.133%, 0.16%, 0.15%, 0.14% and 0.22%, respectively (When GA algorithm applied to the 100-dimensional KP11 and 200-dimensional KP12, the results generated do not meet the constraints and are deleted). In terms of the worst value, HHSEDA shows better performance in all cases except KP11 (HHSEDA100 dimension) which is slightly lower than BABC-DE algorithm. Compared with the worst value achieved by other algorithms, the corresponding improvement rates are 51.38%, 55.93%, 53.16%, 62.38%, 57.72%, 63.58%, 64.58%, 64.38%, 65.47%, respectively. Among these data, the biggest improvement is 65.47% of BFPA algorithm in the case of 2000 dimension. In general, the improvement rate will become more obvious as the dimension increases. In terms of average value, the corresponding improvements rates are 0.5%, 25.26%, 42.22%, 0.20%, 13.37%, 26.27%, 56.56% and 1.03%, respectively.


### 4.3.2. Low Correlation High-Dimensional Experimental

In order to further evaluate the performance of HHSEDA, nine instances of 0-1 knapsack problem with dimensions of 100, 200, 300, 500, 700, 1000, 1200, 1500 and 2000 are randomly generated. The nine instances are generated according to the following conditions: the volume of each object is randomly selected from 10 to 50, the corresponding profit value is randomly selected from 10 of the corresponding object volume, and the maximum capacity of the knapsack is one-half of the total weight of the items generated according to the above procedure.BHS, DBHS, NGHS, ABHS, GA, PSO, BFPA, BABC-DE and HHSEDA are applied to these instances. The results are reported in Tables7 and 8.Table 7
Comparison with HS variants for high dimensional instances with low correlation.
InstanceMeasureHHSEDAABHSNGHSDBHSBHSKP20Time1.8611.710.200.470.28Best16651665162715361665Median16651663158815231661Worst16601656156115061654Mean16641662159315231661Std1.002.5215.777.282.48KP21Time3.2937.860.381.130.53Best34953491337631903494Median34933486330031463489Worst34853473324231263479Mean34933484330631483489Std2.095.0937.6412.993.56KP22Time5.0933.240.452.090.88Best54015387511148875398Median53975374502248235388Worst53895352490747935377Mean53965372501948245387Std3.269.0845.8918.585.33KP23Time16.67211.811.347.924.29Best86958658820777868690Median86908646801077458677Worst86838615790577118664Mean86908639801977438677Std3.3914.8972.6118.466.19KP24Time35.88556.702.6219.839.93Best1216412112112991080012158Median1215712080111131074112141Worst1214612042109491070612132Mean1215612079111151074412142Std4.0618.8069.9320.706.11KP25Time95.821201.276.6654.2637.79Best1758117430159851551017572Median1757017380158581542017556Worst1756315112157491536917534Mean1757017245158571542517556Std5.0032.9467.4031.068.97KP26Time105.62497.866.9056.7930.54Best2100020798190751842220971Median2098420741188941836720959Worst2096520662187531832320939Mean2098120742188961836620957Std8.5140.9387.6427.118.45KP27Time176.705811.0611.76106.1537.01Best2637926146238592318026343Median2635826101236042307026326Worst2634226048234092302226311Mean2635926097236192307826326Std9.1433.98121.7847.0611.48KP28Time348.51351422.64207.4576.04Best3454534267311133027734489Median3451534206308073015834479Worst3449234154306173014134455Mean3451634213308243017734476Std11.4541.81120.2040.9411.66Bold shows the best result.Table 8
Comparison with non-HS variants for high dimensional instances with low correlation.
InstanceMeasureHHSEDAGAPSOBFPABABC-DEKP20Time1.8612.194.983.0326.03Best16651657160815541636Median16651648158915351618Worst16601639157715001607Mean16641648158815311619Std1.004.196.8914.696.59KP21Time3.2926.137.8912.3244.58Best34953406326632493371Median34933379324931733331Worst34853357322730913314Mean34933379324731753333Std2.0912.2610.0532.9514.35KP22Time5.0939.7811.8722.9870.96Best54015181498849335092Median53975128495148275065Worst53895087492347575038Mean53965128495448305065Std3.2624.4616.8844.0913.35KP23Time16.67111.8534.78116.82131.58Best86958233795178988323Median86908175791177848080Worst86838139788076928045Mean86908179791277858087Std3.3925.6817.5548.2549.59KP24Time35.88229.8266.59353.11148.32Best1216411344110071092611368Median1215711288109571080011178Worst1214611245109201075311141Mean1215611290109561081711186Std4.0622.7724.2865.2444.81KP25Time95.82593.82146.321136.50343.02Best1758116232157821564516079Median1757016169156971548715987Worst1756316055156351537615932Mean1757016162156991549515988Std5.0040.7331.6277.3338.30KP26Time105.6832.52198.751205.96500.89Best2100019219187431865919149Median2098419182186921849419025Worst2096519147186281838818969Mean2098119180186911849319027Std8.5121.4226.2679.5641.01KP27Time176.701419.12318.232414.701426.00Best2637924107234872345524220Median2635824024234012316223820Worst2634223964233442301523769Mean2635924022234062318223851Std9.1445.7339.86111.00106.67KP28Time348.52133.43616.436333.802677.90Best3454531453306533057931258Median3451531312305863033131098Worst3449231211305233015431057Mean3451631314305873033131117Std11.4566.1332.72101.2551.79Bold shows the best result.In terms of optimal value, HHSEDA obtains the same optimal value as ABHS and BHS algorithms except for KP20 (dimension = 100). Compared with the suboptimal value achieved by other algorithms, the corresponding improvement rates of HHSEDA are 0%, 0.03%, 0.06%, 0.06%, 0.05%, 0.05%, 0.14%, 0.14%, and 0.16%, respectively. In terms of average value, the corresponding improvement rates of HHSEDA are 0.78%, 8.98%, 12.69%, 0.13%, 6.84%, 10.19%, 11.99%, and 7.98%, respectively. Compared with the worst value achieved by other algorithms, the corresponding improvement rates are 10.67%, 12.75%, 13.29%, 12.88%, 13.45%, 14.28%, 14.42%, 14.46%, and 14.44% respectively.


### 4.3.3. High Correlation High-Dimensional Experimental

In order to further evaluate the performance of HHSEDA, nine instances of 0-1 knapsack problem with dimensions of 100, 200, 300, 500, 700, 1000, 1200, 1500 and 2000 are randomly generated. The instances with strong correlation between value and weight are generated under the following conditions: the volume of each object is randomly selected from 10 to 50, the corresponding profit value is added with a random number of 0 to 10, and the maximum capacity of the knapsack is half of the total weight of the items generated according to the above procedure. BHS, DBHS, NGHS, ABHS, GA, PSO, BFPA, BABC-DE, and HHSEDA are used for comparison. The experimental results are presented in Tables9 and 10.Table 9
Comparison with HS variants for high dimensional instances with high correlation.
InstanceMeasureHHSEDAABHSNGHSDBHSBHSKP29Time1.8012.540.250.490.29Best17691769173516871769Median17681765171616771766Worst17661759165816711761Mean17811765171116771766Std0.82772.4317.094.671.94KP30Time3.5822.980.381.140.66Best38573851374336603854Median38553844371436413849Worst38513831367436263837Mean3854.638433713.536423847Std1.35444.8915.196.414.11KP31Time4.9834.130.591.881.11Best54985486532152065491Median54945471527951925479Worst54875454524651815462Mean5493.65470527851935479Std2.63517.1119.687.266.75KP32Time17.58227.231.667.553.99Best94359409908889329426Median94309376903389099418Worst94249346896288849400Mean9429.89378902789079417Std2.478615.4328.7812.685.82KP33Time38.80564.623.3219.338.87Best1321413174126111245813203Median1321013133125481240113192Worst1320413095124801238313183Mean1320913133125481240413192Std3.410818.1431.6016.065.52KP34Time92.952072.706.9252.9623.85Best1905118982181481787619037Median1904218945180391784919018Worst1902818906179411783119002Mean1904318940180391785319018Std5.006219.1943.3712.878.16KP35Time108.292483.38.562652.0222.79Best2270022468216182132522674Median2268522397215132128622654Worst2267422342214122124922638Mean2268522407215112128622653Std5.424131.7848.5616.058.27KP36Time195.27529.513.94132.7040.38Best2817527851267042645828149Median2816627835265852636228132Worst2815127799264772633528118Mean2816527827265842636828133Std6.450523.0360.6526.218.17KP37Time361.391376528.79291.1981.75Best3802137654360323569937983Median3800337617359113565137964Worst3798537597357573561737943Mean3800337626359063565037964Std7.965823.5970.2923.798.76Bold shows the best result.Table 10
Comparison with non-HS variants for high dimensional instances with high correlation.
InstanceMeasureHHSEDAGAPSOBFPABABC-DEKP29Time1.804812.15824.6123.419014.1013Best17691761173316951757Median17681754172216691748Worst17661747171016441742Mean17811753.91721.81667.731748.2Std0.82773.994.9610.213.5785KP30Time3.5823.319.7612.3523.02Best38573794372236623785Median38553773.537063617.53772.5Worst38513753369635913763Mean3854.637723707.43622.263773.23Std1.3510.256.2719.685.63KP31Time4.9834.7810.9624.9631.00Best54985377528552135391Median549453525265.551635367Worst54875321525451195355Mean5493.65309.35266.45169.735367.63Std2.6414.428.0924.258.88KP32Time17.58127.732.95112.2668.62Best94359167902189539189Median94309140900788709167Worst94249094899188309146Mean9429.89138.19006.78875.29165.3Std2.4816.767.4327.0811.01KP33Time38.80268.473.93297.6198.70Best1321412732125701244612782Median1321012702125291236012747Worst1320412677125081229312728Mean1320912703125301236212751Std3.4114.4110.3936.3714.56KP34Time92.94549164.93888.2420Best1905118303180411787118371Median1904218259180121780918339Worst1902818220179931772218312Mean1904318258180111780918338Std5.0120.5512.4138.3816.83KP35Time108.29815.68179.69120.2432.4Best2270021771215102133021904Median22685217232145721216.521836.5Worst2267421678214222110121805Mean226852172321455.521219.2621842.2Std5.4225.1415.9646.4824.85KP36Time195.271224316.332416.5746.8Best2817526944266132644127042Median281662687726561262872699.6Worst2815126821265342620826938Mean2816526873265622629026997Std6.4530.6020.7849.7325.63KP37Time361.392078.4596.386315.52283Best3802136318359353569736524Median38003362563587335540.536420Worst3798536188358503547736361Mean3800336250358803555736427Std7.9732.2023.0153.2736.33Bold shows the best result.In terms of the optimal value, because the weight of the object loaded into the knapsack is highly related to the value, the improvement of the optimal value is not obvious. In terms of the suboptimal value, the corresponding improvement rates of HHSEDA are 0%, 0.08%, 0.01%, 0.10%, 0.08%, 0.07%, 0.11%, 0.09%, and 0.01%, respectively. In terms of the mean value, the corresponding improvement rates of HHSEDA are 0.75%, 4.95%, 6.32%, 0.23%, 3.64%, 4.39%, 6.71%, and 3.25%, respectively. In terms of the worst value, the corresponding improvement rates of HHSEDA are 6.51%, 7.24%, 7.19%, 6.74%, 7.41%, 7.37%, 7.45%, 7.41%, and 7.07%, respectively. Among these data, the largest rate is 7.45% from BFPA algorithm for the instance with a dimension of 1200.According to Table11, HHSEDA algorithm runs slower than NGHS, DBHS and BHS among the harmony search variants algorithms. This is because the HHSEDA algorithm needs to calculate the probability of the harmony distribution in the harmony memory bank in each iteration, which increases the time loss to some extent. However, compared with other nonharmony search variants algorithms in time consumption, it has some advantages.Table 11
Comparison of running time across different algorithms and different dimensions.
DimensionHHSEDAABHSNGHSDBHSBHSGAPSOBFPABABCDE1004813296572004913256873004912385765004912395867004912365871000491237586120049123758615004912365872000491237568HHSEDA algorithm has a maximum standard deviation less than 32, 8, 12 for instances with no correlation, low and high and correlation, respectively. In terms of standard deviation, HHSEDA algorithm has an advantage over other algorithms. This is because the HHSEDA algorithm generalizes the harmony memory from the macro level, and then feeds back to a single harmony, and makes the result more accurate by improving and repairing the operator.BABC-DE, ABHS, HHSEDA, BFPA, GA, and PSO are compared in simulation graphs for the 27 instances in Figure3. Except in Experiment 1 (unrelated 100-dimensional) and Experiment 2 (unrelated 200-dimensional) where GA algorithm violates the constraints, the average convergence speed and accuracy of HHSEDA algorithm are obviously better than other algorithms.Figure 3
Curves of the optimization results.
(a)(b)(c)(d)(e)From the simulation curves in Figure3, BABC-DE can achieve fast convergence and good results in general. However, for Experiments 8-27, it is easy to fall into the local optimal, because the repair operator of BABC-DE cannot jump out of the local optimal when processing the data with high correlation. Observing the convergence diagram of BFPA, it can be seen that the algorithm is always ineffective for solving high-dimensional problems, and it takes a lot of time to search globally (Levy flight) and locally, and the repair operator it uses makes it easy to fall into local optimal. By observing the convergence graph of particle swarm optimization (PSO) and genetic algorithm (GA), we can see that the results are not good when solving high-dimensional problems, and they are easy to fall into local optimal. This is because their efficiency are not very good, and the penalty function method used is not obvious in the repair of experimental results, and some constraints are violated in some data.Observing the convergence diagram of ABHS in Figure3, it can be seen that ABHS has relatively good results in all experiments. For Experiments 1-9, the convergence diagram of ABHS algorithm is the closest to HHSEDA, and the parameter adjustment of this algorithm makes it better. But compared with HHSEDA, the effect of adjusting the harmony vector through the probability of harmony distribution in the harmony memory bank is relatively poor.In order to evaluate the dispersion of HHSEDA algorithm, a total of 9 instances with low-correlation are selected, and they are run independently for 10 times. The generated results are presented by the box diagrams, as shown in Figure4. It can be seen from the figure that the minimum value, maximum value and median of HHSEDA algorithm are closer and better than other algorithms. In conclusion, HHSEDA algorithm has better accuracy and computational stability.Figure 4
The boxplots of the algorithms.
(a)(b)It can be analyzed from Tables1–11 and Figures 1–4 that HHSEDA is an excellent HS variant with fast convergence and excellent stability. Therefore, HHSEDA is a more efficient and reliable algorithm for solving the 0-1 knapsack problem of high dimension. The reason may include the better initialization, enhanced local search based on the hybrid strategies, and the infeasible solution repair strategy.


## 4.3.1. Uncorrelation High-Dimensional Experimental

In order to further assess the performance of the proposed HHSEDA algorithm, we use nine high-dimensional instances of 0-1 knapsack problem. The dimensions of these instances include 100, 200, 300, 500, 700, 1000, 1200, 1500, and 2000. The generation of each uncorrelated high-dimensional instances (KP25-KP33) is as follows: the volume of each knapsack is randomly selected from 5 to 20, the corresponding random profit range is 50 to 100, and the maximum capacity of the knapsack is 0.75 of the total capacity of the items generated according to the above procedure. The above examples only need to be generated randomly once, and remain unchanged in the later experiments. The maximum number of iterations for solving the above 9 instances is 10000, 10000, 10000, 20000, 30000, 50000, 50000, 70000 and 100000, respectively. The number of population is set to 30 in all experiments, and the number of independent experiments is 30.Tables5 and 6 report the performance metrics for each instance for HHSEDA and other comparison algorithms with the best results highlighted in bold face. The optimal profit of KP25-KP33 is unknown, and the best value, median, worst value, average and standard deviation are all considered in the table.Table 5
Comparison with HS variants for high dimensional instances with no correlation.
InstanceMeasureHHSEDAABHSNGHSDBHSBHSKP11Time1.93511.960.210.220.18Best64236423613156346423Median6419.564015952.55292.56400.5Worst63996388577451306385Mean6416.66402.85947.35313.36402.8Std7.83759.2165106.28116.239.93KP12Time3.6128.250.32116.230.35Best1296012954119551051412949Median1295512904115419816012935Worst1294712859107349609412864Mean1295.512899115619900212930Std4.020.98239.34210.5018.17KP13Time5.7643.440.410.500.55Best1954019493174251472119531Median1953419445167761419019496Worst1951319366152721391019373Mean1953119441167381425919490Std7.5629.62520.38227.0029.55KP14Time20.31191.961.241.601.88Best3207831958275622339832049Median3205931911263872265631998Worst3203131816255972231331941Mean3205631896264712270331996Std10.529741.48551.19248.6226.0169KP15Time47.10580.852.573.333.57Best4494244800370043108144882Median4492744720352793053844857Worst4490944658336803013544782Mean4492644721353143056944851Std9.647238.69723.59242.9424.83KP16Time126.622009.005.47927.1910.27Best6460464482508644461564498Median6457264358419564350064457Worst6455164288473714291064395Mean6457264360490064351664457Std13.3566.34922.25427.8723.25KP17Time133.212398.706.728.1912.75Best7700576515592815159776888Median7695676337570935106576812Worst7688976207561155066276635Mean7695376350573415110476797Std29.0085.40907.81266.7657.07KP18Time366.725715.7011.9414.4322.14Best9636495971729146445196233Median9630295667702986354596084Worst9624695385682666282695985Mean9629995660703046355396091Std27.20122.511313.4457.1156.51KP19Time545.2414870.0025.5627.0636.64Best1272601265689395384341126978Median1271941264389152283182126860Worst1271051262508885782488126710Mean1271901264309119583306126870Std31.8578.811437475.0756.78Bold shows the best result.Table 6
Comparison with non-HS variants for high dimensional instances with no correlation.
InstanceMeasureHHSEDAGAPSOBFPABABC-DEKP11Time1.94NA4.013.177.57Best6423NA638552946423Median6419.5NA62544537.56421Worst6399NA613142276413Mean6416.6NA6269.24555.86419.7Std7.8375NA62.83223.973.35KP12Time3.61NA6.5212.1211.01Best12960NA11820943612921Median12955NA11612862612890Worst12947NA11479830312875Mean1295.5NA116378671.412892Std4.0NA91.2328312.84KP13Time5.7642.3810.5823.9815.60Best1954019405171041336319461Median1953419127164371275419396Worst1951318870162401214819363Mean1953119123165211274719402Std7.56124.90217.87318.9222.29KP14Time20.31124.4033.41104.2647.13Best3207830686266212106731807Median3205930169257562056031711Worst3203129911254241972531667Mean3205630193258242055331716Std10.5297186.70262.49294.533.76KP15Time47.10222.2666.95298.56224.20Best4494241261355172988844401Median4492740851347712845744339Worst4490940473343672756844269Mean4492640847347922847344339Std9.6472208.89251.70594.9229.85KP16Time126.62551.19154.20875.33491.93Best6460457392488594155164115Median6457256320482614018863749Worst6455155726477113946163691Mean6457256427483014033163760Std13.35443.72286.87631.6572.79KP17Time133.21708.01178.141176.40614.70Best7700566543574324910976026Median7695665757564594771475872Worst7688965148560354671875788Mean7695365757565774782875886Std29.00321.30351.11575.458.32KP18Time366.721209.30301.622342.51239.90Best9636481365703626159795144Median9630280220695885960094969Worst9624679387687855855194910Mean9629980263696195982694979Std27.20506.60342.00787.951.80KP19Time545.242452.50562.591958.605568.00Best1272601039049098480234125521Median1271941027799009278365125341Worst1271051018438951976813125228Mean127190102719009778388125350Std31.85554.35315.43813.2168.36Bold shows the best result.In many cases, the worst values obtained by HHSEDA are far better than the worst values obtained by other algorithms. In terms of optimal value, HHSEDA performs the same as ABHS, BHS and BABC-DE algorithm except for KP11 (100-dimensional). Compared with the suboptimal values achieved by other algorithms, the corresponding improvement rates of HHSEDA are 0%, 0.05%, 0.09%, 0.133%, 0.16%, 0.15%, 0.14% and 0.22%, respectively (When GA algorithm applied to the 100-dimensional KP11 and 200-dimensional KP12, the results generated do not meet the constraints and are deleted). In terms of the worst value, HHSEDA shows better performance in all cases except KP11 (HHSEDA100 dimension) which is slightly lower than BABC-DE algorithm. Compared with the worst value achieved by other algorithms, the corresponding improvement rates are 51.38%, 55.93%, 53.16%, 62.38%, 57.72%, 63.58%, 64.58%, 64.38%, 65.47%, respectively. Among these data, the biggest improvement is 65.47% of BFPA algorithm in the case of 2000 dimension. In general, the improvement rate will become more obvious as the dimension increases. In terms of average value, the corresponding improvements rates are 0.5%, 25.26%, 42.22%, 0.20%, 13.37%, 26.27%, 56.56% and 1.03%, respectively.


## 4.3.2. Low Correlation High-Dimensional Experimental

In order to further evaluate the performance of HHSEDA, nine instances of 0-1 knapsack problem with dimensions of 100, 200, 300, 500, 700, 1000, 1200, 1500 and 2000 are randomly generated. The nine instances are generated according to the following conditions: the volume of each object is randomly selected from 10 to 50, the corresponding profit value is randomly selected from 10 of the corresponding object volume, and the maximum capacity of the knapsack is one-half of the total weight of the items generated according to the above procedure.BHS, DBHS, NGHS, ABHS, GA, PSO, BFPA, BABC-DE and HHSEDA are applied to these instances. The results are reported in Tables7 and 8.Table 7
Comparison with HS variants for high dimensional instances with low correlation.
InstanceMeasureHHSEDAABHSNGHSDBHSBHSKP20Time1.8611.710.200.470.28Best16651665162715361665Median16651663158815231661Worst16601656156115061654Mean16641662159315231661Std1.002.5215.777.282.48KP21Time3.2937.860.381.130.53Best34953491337631903494Median34933486330031463489Worst34853473324231263479Mean34933484330631483489Std2.095.0937.6412.993.56KP22Time5.0933.240.452.090.88Best54015387511148875398Median53975374502248235388Worst53895352490747935377Mean53965372501948245387Std3.269.0845.8918.585.33KP23Time16.67211.811.347.924.29Best86958658820777868690Median86908646801077458677Worst86838615790577118664Mean86908639801977438677Std3.3914.8972.6118.466.19KP24Time35.88556.702.6219.839.93Best1216412112112991080012158Median1215712080111131074112141Worst1214612042109491070612132Mean1215612079111151074412142Std4.0618.8069.9320.706.11KP25Time95.821201.276.6654.2637.79Best1758117430159851551017572Median1757017380158581542017556Worst1756315112157491536917534Mean1757017245158571542517556Std5.0032.9467.4031.068.97KP26Time105.62497.866.9056.7930.54Best2100020798190751842220971Median2098420741188941836720959Worst2096520662187531832320939Mean2098120742188961836620957Std8.5140.9387.6427.118.45KP27Time176.705811.0611.76106.1537.01Best2637926146238592318026343Median2635826101236042307026326Worst2634226048234092302226311Mean2635926097236192307826326Std9.1433.98121.7847.0611.48KP28Time348.51351422.64207.4576.04Best3454534267311133027734489Median3451534206308073015834479Worst3449234154306173014134455Mean3451634213308243017734476Std11.4541.81120.2040.9411.66Bold shows the best result.Table 8
Comparison with non-HS variants for high dimensional instances with low correlation.
InstanceMeasureHHSEDAGAPSOBFPABABC-DEKP20Time1.8612.194.983.0326.03Best16651657160815541636Median16651648158915351618Worst16601639157715001607Mean16641648158815311619Std1.004.196.8914.696.59KP21Time3.2926.137.8912.3244.58Best34953406326632493371Median34933379324931733331Worst34853357322730913314Mean34933379324731753333Std2.0912.2610.0532.9514.35KP22Time5.0939.7811.8722.9870.96Best54015181498849335092Median53975128495148275065Worst53895087492347575038Mean53965128495448305065Std3.2624.4616.8844.0913.35KP23Time16.67111.8534.78116.82131.58Best86958233795178988323Median86908175791177848080Worst86838139788076928045Mean86908179791277858087Std3.3925.6817.5548.2549.59KP24Time35.88229.8266.59353.11148.32Best1216411344110071092611368Median1215711288109571080011178Worst1214611245109201075311141Mean1215611290109561081711186Std4.0622.7724.2865.2444.81KP25Time95.82593.82146.321136.50343.02Best1758116232157821564516079Median1757016169156971548715987Worst1756316055156351537615932Mean1757016162156991549515988Std5.0040.7331.6277.3338.30KP26Time105.6832.52198.751205.96500.89Best2100019219187431865919149Median2098419182186921849419025Worst2096519147186281838818969Mean2098119180186911849319027Std8.5121.4226.2679.5641.01KP27Time176.701419.12318.232414.701426.00Best2637924107234872345524220Median2635824024234012316223820Worst2634223964233442301523769Mean2635924022234062318223851Std9.1445.7339.86111.00106.67KP28Time348.52133.43616.436333.802677.90Best3454531453306533057931258Median3451531312305863033131098Worst3449231211305233015431057Mean3451631314305873033131117Std11.4566.1332.72101.2551.79Bold shows the best result.In terms of optimal value, HHSEDA obtains the same optimal value as ABHS and BHS algorithms except for KP20 (dimension = 100). Compared with the suboptimal value achieved by other algorithms, the corresponding improvement rates of HHSEDA are 0%, 0.03%, 0.06%, 0.06%, 0.05%, 0.05%, 0.14%, 0.14%, and 0.16%, respectively. In terms of average value, the corresponding improvement rates of HHSEDA are 0.78%, 8.98%, 12.69%, 0.13%, 6.84%, 10.19%, 11.99%, and 7.98%, respectively. Compared with the worst value achieved by other algorithms, the corresponding improvement rates are 10.67%, 12.75%, 13.29%, 12.88%, 13.45%, 14.28%, 14.42%, 14.46%, and 14.44% respectively.


## 4.3.3. High Correlation High-Dimensional Experimental

In order to further evaluate the performance of HHSEDA, nine instances of 0-1 knapsack problem with dimensions of 100, 200, 300, 500, 700, 1000, 1200, 1500 and 2000 are randomly generated. The instances with strong correlation between value and weight are generated under the following conditions: the volume of each object is randomly selected from 10 to 50, the corresponding profit value is added with a random number of 0 to 10, and the maximum capacity of the knapsack is half of the total weight of the items generated according to the above procedure. BHS, DBHS, NGHS, ABHS, GA, PSO, BFPA, BABC-DE, and HHSEDA are used for comparison. The experimental results are presented in Tables9 and 10.Table 9
Comparison with HS variants for high dimensional instances with high correlation.
InstanceMeasureHHSEDAABHSNGHSDBHSBHSKP29Time1.8012.540.250.490.29Best17691769173516871769Median17681765171616771766Worst17661759165816711761Mean17811765171116771766Std0.82772.4317.094.671.94KP30Time3.5822.980.381.140.66Best38573851374336603854Median38553844371436413849Worst38513831367436263837Mean3854.638433713.536423847Std1.35444.8915.196.414.11KP31Time4.9834.130.591.881.11Best54985486532152065491Median54945471527951925479Worst54875454524651815462Mean5493.65470527851935479Std2.63517.1119.687.266.75KP32Time17.58227.231.667.553.99Best94359409908889329426Median94309376903389099418Worst94249346896288849400Mean9429.89378902789079417Std2.478615.4328.7812.685.82KP33Time38.80564.623.3219.338.87Best1321413174126111245813203Median1321013133125481240113192Worst1320413095124801238313183Mean1320913133125481240413192Std3.410818.1431.6016.065.52KP34Time92.952072.706.9252.9623.85Best1905118982181481787619037Median1904218945180391784919018Worst1902818906179411783119002Mean1904318940180391785319018Std5.006219.1943.3712.878.16KP35Time108.292483.38.562652.0222.79Best2270022468216182132522674Median2268522397215132128622654Worst2267422342214122124922638Mean2268522407215112128622653Std5.424131.7848.5616.058.27KP36Time195.27529.513.94132.7040.38Best2817527851267042645828149Median2816627835265852636228132Worst2815127799264772633528118Mean2816527827265842636828133Std6.450523.0360.6526.218.17KP37Time361.391376528.79291.1981.75Best3802137654360323569937983Median3800337617359113565137964Worst3798537597357573561737943Mean3800337626359063565037964Std7.965823.5970.2923.798.76Bold shows the best result.Table 10
Comparison with non-HS variants for high dimensional instances with high correlation.
InstanceMeasureHHSEDAGAPSOBFPABABC-DEKP29Time1.804812.15824.6123.419014.1013Best17691761173316951757Median17681754172216691748Worst17661747171016441742Mean17811753.91721.81667.731748.2Std0.82773.994.9610.213.5785KP30Time3.5823.319.7612.3523.02Best38573794372236623785Median38553773.537063617.53772.5Worst38513753369635913763Mean3854.637723707.43622.263773.23Std1.3510.256.2719.685.63KP31Time4.9834.7810.9624.9631.00Best54985377528552135391Median549453525265.551635367Worst54875321525451195355Mean5493.65309.35266.45169.735367.63Std2.6414.428.0924.258.88KP32Time17.58127.732.95112.2668.62Best94359167902189539189Median94309140900788709167Worst94249094899188309146Mean9429.89138.19006.78875.29165.3Std2.4816.767.4327.0811.01KP33Time38.80268.473.93297.6198.70Best1321412732125701244612782Median1321012702125291236012747Worst1320412677125081229312728Mean1320912703125301236212751Std3.4114.4110.3936.3714.56KP34Time92.94549164.93888.2420Best1905118303180411787118371Median1904218259180121780918339Worst1902818220179931772218312Mean1904318258180111780918338Std5.0120.5512.4138.3816.83KP35Time108.29815.68179.69120.2432.4Best2270021771215102133021904Median22685217232145721216.521836.5Worst2267421678214222110121805Mean226852172321455.521219.2621842.2Std5.4225.1415.9646.4824.85KP36Time195.271224316.332416.5746.8Best2817526944266132644127042Median281662687726561262872699.6Worst2815126821265342620826938Mean2816526873265622629026997Std6.4530.6020.7849.7325.63KP37Time361.392078.4596.386315.52283Best3802136318359353569736524Median38003362563587335540.536420Worst3798536188358503547736361Mean3800336250358803555736427Std7.9732.2023.0153.2736.33Bold shows the best result.In terms of the optimal value, because the weight of the object loaded into the knapsack is highly related to the value, the improvement of the optimal value is not obvious. In terms of the suboptimal value, the corresponding improvement rates of HHSEDA are 0%, 0.08%, 0.01%, 0.10%, 0.08%, 0.07%, 0.11%, 0.09%, and 0.01%, respectively. In terms of the mean value, the corresponding improvement rates of HHSEDA are 0.75%, 4.95%, 6.32%, 0.23%, 3.64%, 4.39%, 6.71%, and 3.25%, respectively. In terms of the worst value, the corresponding improvement rates of HHSEDA are 6.51%, 7.24%, 7.19%, 6.74%, 7.41%, 7.37%, 7.45%, 7.41%, and 7.07%, respectively. Among these data, the largest rate is 7.45% from BFPA algorithm for the instance with a dimension of 1200.According to Table11, HHSEDA algorithm runs slower than NGHS, DBHS and BHS among the harmony search variants algorithms. This is because the HHSEDA algorithm needs to calculate the probability of the harmony distribution in the harmony memory bank in each iteration, which increases the time loss to some extent. However, compared with other nonharmony search variants algorithms in time consumption, it has some advantages.Table 11
Comparison of running time across different algorithms and different dimensions.
DimensionHHSEDAABHSNGHSDBHSBHSGAPSOBFPABABCDE1004813296572004913256873004912385765004912395867004912365871000491237586120049123758615004912365872000491237568HHSEDA algorithm has a maximum standard deviation less than 32, 8, 12 for instances with no correlation, low and high and correlation, respectively. In terms of standard deviation, HHSEDA algorithm has an advantage over other algorithms. This is because the HHSEDA algorithm generalizes the harmony memory from the macro level, and then feeds back to a single harmony, and makes the result more accurate by improving and repairing the operator.BABC-DE, ABHS, HHSEDA, BFPA, GA, and PSO are compared in simulation graphs for the 27 instances in Figure3. Except in Experiment 1 (unrelated 100-dimensional) and Experiment 2 (unrelated 200-dimensional) where GA algorithm violates the constraints, the average convergence speed and accuracy of HHSEDA algorithm are obviously better than other algorithms.Figure 3
Curves of the optimization results.
(a)(b)(c)(d)(e)From the simulation curves in Figure3, BABC-DE can achieve fast convergence and good results in general. However, for Experiments 8-27, it is easy to fall into the local optimal, because the repair operator of BABC-DE cannot jump out of the local optimal when processing the data with high correlation. Observing the convergence diagram of BFPA, it can be seen that the algorithm is always ineffective for solving high-dimensional problems, and it takes a lot of time to search globally (Levy flight) and locally, and the repair operator it uses makes it easy to fall into local optimal. By observing the convergence graph of particle swarm optimization (PSO) and genetic algorithm (GA), we can see that the results are not good when solving high-dimensional problems, and they are easy to fall into local optimal. This is because their efficiency are not very good, and the penalty function method used is not obvious in the repair of experimental results, and some constraints are violated in some data.Observing the convergence diagram of ABHS in Figure3, it can be seen that ABHS has relatively good results in all experiments. For Experiments 1-9, the convergence diagram of ABHS algorithm is the closest to HHSEDA, and the parameter adjustment of this algorithm makes it better. But compared with HHSEDA, the effect of adjusting the harmony vector through the probability of harmony distribution in the harmony memory bank is relatively poor.In order to evaluate the dispersion of HHSEDA algorithm, a total of 9 instances with low-correlation are selected, and they are run independently for 10 times. The generated results are presented by the box diagrams, as shown in Figure4. It can be seen from the figure that the minimum value, maximum value and median of HHSEDA algorithm are closer and better than other algorithms. In conclusion, HHSEDA algorithm has better accuracy and computational stability.Figure 4
The boxplots of the algorithms.
(a)(b)It can be analyzed from Tables1–11 and Figures 1–4 that HHSEDA is an excellent HS variant with fast convergence and excellent stability. Therefore, HHSEDA is a more efficient and reliable algorithm for solving the 0-1 knapsack problem of high dimension. The reason may include the better initialization, enhanced local search based on the hybrid strategies, and the infeasible solution repair strategy.


## 5. Conclusions

This paper presents a hybrid harmonic search and distribution estimation algorithm for 0-1 knapsack problem. Firstly, a new initialization method under constraints is proposed. Compared with the classical initialization method, the advantage is that it can directly generate harmonies conforming to the constraints. In addition, the hybrid algorithm mainly combines the probability idea in the distribution estimation algorithm with the harmony search algorithm to find the population with better fitness, analyze the distribution profile of its excellent harmony, and make the subsequent improvement direction develop in a more optimal direction, which greatly improves the probability of finding the optimal value. Finally, in order to correct the infeasible solutions in the iterative process, a new improved repair operator is proposed. The new repair operator can transform the infeasible solutions into feasible solutions and optimize the feasible solutions under the conditions of satisfying the constraints to produce better solutions. This repair operator can not only guarantee the availability of solution, but also improve the accuracy and convergence of HHSEDA algorithm.In general, HHSEDA has the following three advantages:(i)
In the initialization stage, a population conforming to the constraints can be generated to prepare for the subsequent iteration of the algorithm(ii)
In the process of improvisation, the idea of probability in distribution estimation algorithm is added to harmony search, which makes it difficult to fall into local optimum(iii)
In solving the problem of infeasible solutions, a newly proposed infeasible solution repair strategy is added, which can repair infeasible solutions into feasible solutions more efficiently, so as to optimize the overall fitness valueExperiments on 10 classic low-dimensional instances of 0-1 knapsack problem, 9 high-dimensional instances with low-correlation, 9 high-dimensional instances with high-correlation, and 9 high-dimensional instances with no-correlation are conducted. The simulation results show that HHSEDA possesses a good optimization potential and stability for solving 0-1 knapsack problem. Especially for the large-scale 0-1 knapsack problem, it shows a much better performance than ABHS, BABC-DE, BFPA, and other algorithms. In sum, the HHSEDA algorithm perform better than other algorithms in low-dimensional, large-scale with no correlation, low-correlation or and high-correlation 0-1 knapsack problem. In addition, the application of the algorithm is further expanded based on the characteristics of the algorithm, such as multi-dimensional knapsacks, discounted knapsacks, and even path planning related problems.



---

*Source: 8440165-2022-05-12.xml*