# A Heuristics-Guided Simplified Discrete Harmony Search Algorithm for Solving 0-1 Knapsack Problem
## 3 Simplified Discrete Harmony Search Algorithm for the 0-1 KP
### Discussions of the HS Algorithm  
The main purpose of the random search operator is to maintain enough diversity for the HS algorithm to have an optimization ability even in the late stage of the search. To obtain this objective, the CHS algorithm uses Equation (6) to randomly create a new value for \(x_{j}^{new}\). The 0-1 KP is a discrete optimization problem where the value of \(x_{j}^{new}\) can only be 0 or 1. Consequently, \(x_{j,min}\) and \(x_{j,max}\) are 0 and 1, respectively. A possible implementation of the random search operator is to randomly select a value from {0,1} for the \(x_{j}^{new}\) with probability 1-\(lmcr\), so both 0 and 1 can have a chance to be the value of \(x_{j}^{new}\). As a result, Equation (6) can be rewritten as represented as Equation (11):  
\[x_{j}^{new}=x_{j,min}+rand()\times(x_{j,max}-x_{j,min})=0+rand()*(1-0)\in\{0,1\} \tag{11}\]  
In the case of the 0-1 KP, the HM maintains a repository of historical solutions. Let \(\textbf{HM}(j)\) denote the historical solutions corresponding to the \(j\)-th dimension. When the harmony memory contains a sufficient number of solutions, new values \(x_{j}^{new}\) can be directly retrieved from \(\textbf{HM}(j)\) as shown in Equation (12). This approach achieves comparable outcomes to the random search operator, thereby rendering the parameter \(hmcr\) obsolete. Consequently, the random search operator is eliminated, and each \(x_{j}^{new}\) is consistently selected from the harmony memory:  
\[x_{j}^{new}\leftarrow\textbf{HM}(j)=\left(\begin{array}{c}x_{j}^{1}\\ x_{j}^{2}\\ \vdots\\ x_{j}^{lmns-1}\\ x_{j}^{lmns}\end{array}\right) \tag{12}\]  
The pitch adjustment operator of the standard HS aims to improve its local search ability. The classical pitch adjustment operator is implemented at the dimension level, and the binary solution space such as 0-1 KP, \(bw\) for the pitch adjustment operator is 1, and thus \(x_{j}^{new}\) can be adjusted according to Equation (13):  
\[x_{j}^{new}=(x_{j}^{new}\pm rand()\times bw)\in\{0,1\} \tag{13}\]  
As noted by [PERSON] et al. in [41], the pitch adjustment operator of the HS algorithm is degenerated in the binary space, necessitating the development of a new approach to enhance its intensification ability. In solving the 0-1 KP, most metaheuristics employ a greedy optimization operator to refine solutions. Unlike the classical pitch adjustment operator, which operates at the dimension level, the greedy optimization functions at the solution level. Specifically, for a \(n\)-dimensional solution \(x=(x_{1},x_{2},\ldots,x_{n})\), the new solution \(x^{new}\) is generated by applying a greedy optimization operator \(Opt(\cdot)\) as defined in Equation (14):  
\[x^{new}=Opt(x) \tag{14}\]  
Given that the greedy optimization operator substantially strengthens the intensification capability, the classical pitch adjustment operator is no longer required for the 0-1 knapsack problem (0-1 KP) and is therefore omitted.  
In the 0-1 KP, the capacity constraint of the knapsack introduces an indirect competitive relationship among items. For instance, incorporating an item \(\alpha\) with profit \(p_{\alpha}\) and weight \(w_{\alpha}\) may hinder the inclusion of another item \(\beta\) (with profit \(p_{\beta}\) and weight \(w_{\beta}\)) due to the limited capacity. To address this, we evaluate items based on their profit-to-weight ratio \((pw)\) or individual profit, where \(pw\) is defined as Equation (15):  
\[pw_{j}=\frac{p_{j}}{w_{j}} \tag{15}\]  
Given that the primary objective of the 0-1 KP is to maximize profit, the memory consideration operator processes items in non-ascending order of their profit-to-weight ratio or individual profit.