# A Heuristics-Guided Simplified Discrete Harmony Search Algorithm for Solving 0-1 Knapsack Problem
## 2 Preliminaries
### Discrete HS Algorithms for the 0-1 KP  
In the ABHS algorithm [41], two strategies, the bit selection strategy and the individual selection strategy, are designed to implement the memory consideration operator. The bit selection strategy implements the classical memory consideration operator, and the individual selection strategy implements a new memory consideration operator as the following:  
\[x_{j}^{new}=\left\{\begin{array}{ll}x_{j}^{p},&\text{if }rand()<hmcr\\ round(rand()),&\text{otherwise}\end{array}\right. \tag{7}\]  
where \(x^{p}\) is a random harmony which is fixed for all items of \(x^{new}\), and the _round_ function rounds a number to the nearest integer. The random search operator of the ABHS algorithm randomly selects a new value (0 or 1) for \(x_{j}^{new}\). The pitch adjustment operator of the ABHS algorithm is designed to learn from the global best harmony with probability \(par\).  
In the BMHS algorithm [42], the pitch adjustment operator is designed to learn from the global best harmony or to produce a new value randomly as the following:  
\[x_{j}^{new}=\left\{\begin{array}{ll}x_{j}^{best},&\text{if }rand()<0.5\\ round(rand()),&\text{otherwise}\end{array}\right. \tag{8}\]  
where \(x^{best}\) is the best harmony in the harmony memory. The random search operator of the BMHS algorithm randomly selects a new value (0 or 1) for \(x_{j}^{new}\).  
In order to enhance the local search ability of HS algorithm for the 0-1 KP, the DGHS algorithm [44] heavily uses the best harmony to guide the improvisation of new solution. In the DGHS algorithm, a new solution is improvised as the following:  
\[x_{j}^{new}=\left\{\begin{array}{ll}x_{j}^{best},&\text{if }rand()<hmcr \\ x_{j}^{i},&\text{otherwise}\end{array}\right. \tag{9}\]  
where \(x^{best}\) is the best harmony in the harmony memory, and \(x^{i}\) is randomly selected from the harmony memory. Furthermore, the \(x_{j}^{new}\), which is not selected from \(x_{j}^{best}\), is flipped with probability \(par\).  
In order to appropriately balance the intensification and diversification of the HS algorithm, the SBHS algorithm [45] proposes an ingenious improvisation scheme as the following:  
\[x_{j}^{new}=x_{j}^{r1}+(-1)^{x_{j}^{r1}}\times(x_{j}^{best}\oplus x_{j}^{r2}), j\in\{1,2,\ldots,n\} \tag{10}\]  
where \(r1\) and \(r2\) are two distinct random integers between 1 and \(hms\) for each dimension \(j\). Equation (10) combines the memory consideration and the pitch adjustment to improvise each bit of a new harmony, so the SBHS algorithm does not need parameter \(par\). On the right-hand side of Equation (10), the first term represents the memory consideration operator, and the second term represents the pitch adjustment operator. The exclusive OR of \(x_{j}^{best}\) and \(x_{j}^{r2}\) determines the value of \(x_{j}^{new}\). If \(x_{j}^{best}\oplus x_{j}^{r2}\) is equal to 0, then \(x_{j}^{r1}\) is assigned to \(x_{j}^{new}\) directly; otherwise, \(1-x_{j}^{r1}\) is assigned to \(x_{j}^{new}\). The SBHS algorithm has only two parameters, i.e., \(hms\) and \(hmcr\), which greatly simplifies the fine-tuning of parameters.