# A Heuristics-Guided Simplified Discrete Harmony Search Algorithm for Solving 0-1 Knapsack Problem
## 2 Preliminaries
### The Harmony Search Algorithm  
The HS algorithm is a metaheuristic that mimics the improvisation process of music players to obtain better harmony. The basic HS algorithm uses three operators, i.e., the memory consideration operator, the pitch adjustment operator, and the random search operator, to cooperatively construct a new solution. Given a solution represented as a vector \(x\) with \(n\) elements, Algorithm 1 describes the steps of the basic HS algorithm, in which lines 4 to 13 are used to construct a new solution \(x^{new}\) until the stop condition is met (i.e., the maximum number of iterations or no improvement for certain iterations). Line 6, line 8, and line 11 are the memory consideration operator, the pitch adjustment operator, and the random search operator, respectively. In line 14, the newly produced solution \(x^{new}\) is used to update the harmony memory if necessary. ```
1:Initialize the parameters of the HS algorithm
2:Initialize the harmonies (solutions) in harmony memory
3:while Stop condition is not met do
4:for each dimension \(j\) from 1 to \(n\)do
5:ifrand() \(<\)\(l\)\(l\)\(m\)cr then // Memory Consideration Operator
6:\(x_{i}^{new}=x_{i}^{i}\), where \(i\) is randomly selected from 1 to \(l\)\(h\)ms
7:ifrand() \(<\)\(par\)then // Pitch Adjustment Operator
8: Adjust \(x_{j}^{new}\)
9:endif
10:else // Random Search Operator
11: Randomly create a value for \(x_{j}^{new}\)
12:endif
13:endfor
14: Use \(x^{new}\) to update harmony memory
15:endwhile
```  
**Algorithm 1** The basic HS algorithm. The HS algorithm stores several historical solutions in the harmony memory (HM), which can be represented by a matrix as Equation (4):  
\[HM=\left( \begin{array}{ccccc}x_{1}^{1}&x_{2}^{1}&\ldots&x_{n-1}^{1}&x_{n}^{1}\\ x_{1}^{2}&x_{2}^{2}&\ldots&x_{n-1}^{2}&x_{n}^{2}\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ x_{1}^{lms-1}&x_{2}^{lms-1}&\ldots&x_{n-1}^{lms-1}&x_{n}^{lms-1}\\ x_{1}^{lms}&x_{2}^{lms}&\ldots&x_{n-1}^{lms}&x_{n}^{lms}\end{array} \right) \tag{4}\]  
where _lms_ is a parameter which represents the size of the harmony memory, and \(n\) is the number of decision variables of the problem at hand. Except for the _lms_, the basic HS algorithm has two additional intrinsic parameters, harmony memory consideration rate (_lnmcr_) and pitch adjustment rate (_par_), which control the probability of selecting a solution component from the harmony memory and the probability of enhancing the selected component, respectively. The basic HS algorithm is a general framework which may be implemented as continuous HS (CHS) algorithm or discrete HS (DHS) algorithm. For the CHS algorithm, another parameter _bw_, which represents an arbitrary distance bandwidth, is introduced to implement the pitch adjustment operator as the following:  
\[x_{j}^{new}=x_{j}^{new}\pm rand()\times bw \tag{5}\]  
In order to implement random search operator for the CHS algorithm, the value of \(x_{j}^{new}\) can be randomly created as the following:  
\[x_{j}^{new}=x_{j,min}+rand()\times(x_{j,max}-x_{j,min}) \tag{6}\]  
where \(x_{j,min}\) and \(x_{j,max}\) represent the minimum value and the maximum value of the _j_th dimension, respectively. For the implementation of the DHS algorithm, the random search operator can simply select a new value from all possible values for \(x_{j}^{new}\), and the pitch adjustment operator may be abolished or redesigned according to the characteristics of the optimization problem at hand. Both the CHS algorithm and the DHS algorithm can be used to solve the combinatorial optimization problem. In the field of the 0-1 KP, the novel global harmony search (NGHS) algorithm [39] and the harmony search algorithm based on teaching-learning strategies (HSTL) [43] belong to the CHS algorithm. In order to use the CHS algorithm for the 0-1 KP, a mapping strategy must be specified to map a real number into 0 or 1. In the NGHS algorithm, because the position updating equations are defined for real numbers in the range of 0 to 1, every variable is replaced by the nearest integer to obtain 0 or 1.