# 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
### Description of the SDHS Algorithm  
Accordingly, based on the aforementioned analysis, the random search operator is omitted from our SDHS algorithm. Consequently, the memory consideration operator prioritizes items based on their profit-to-weight ratio \(pw\), while the pitch adjustment operator is executed at the solution level. In the subsequent subsections, we detail the memory consideration operator, the solution-level pitch adjustment mechanism, and the comprehensive framework of the SDHS algorithm. And the pseudo code of the proposed SDHS algorithm for 0-1 KP is provided in Algorithm 2. Figure 1 shows the flowchart of the SDHS algorithm.  
```
0:\(m,lms\)
0: best solution found;
1: Initialize every \(x^{i}\) for the harmony memory, where \(i\in\{1,2,\ldots,lms\}\)
2:\(best\leftarrow\) the best harmony in harmony memory
3:while\(m>0\)do //Memory consideration
4: Call Algorithm 3 to construct a solution \(x^{new}\) //Pitch adjustment
5: Call Algorithm 4 to enhance the solution \(x^{new}\) //Update the harmony memory
6:if\(x^{new}\) is better than the worst solution in the harmony memory then
7: Remove the worst solution in the harmony memory
8: Append \(x^{new}\) into the harmony memory
9:endif
10:if\(x^{new}\) is better than \(best\)then
11:\(best=x^{new}\)
12:endif
13:\(m=m-1\)
14:endwhile
15:return\(bx\)
```  
**Algorithm 2** Pseudo code of the SDHS algorithm for the 0-1 KP.  
As shown in Algorithm 2, parameters \(m\) and \(lms\) represent the maximum generation of the SDHS algorithm and the size of the harmony memory. The initial solutions in the harmony memory are randomly created. The initialization of the harmony memory requires the random initialization of n items of the heap \(lms\) of harmonies, and its time complexity is \(O(lms\times n)\). In line 4, the SDHS algorithm calls the memory consideration operator to construct a new solution \(x^{new}\). In line 5, the SDHS algorithm calls the solution-level pitch adjustment operator to improve the solution \(x^{new}\). Lines 6 to 9 are used to update the harmony memory. We can use a heap to implement the harmony memory, so the time complexity to maintain the harmony memory is \(O(\log_{2}hms)\). Lines 10 to 12 are used to record the best solution. Because of the time complexity of both Algorithms 3 and 4 is \(O(n)\), the time complexity to construct a solution and maintain the harmony memory is \(O(n+\log_{2}hms)\). In Algorithm 2, \(m\) solutions are constructed in total, so the time complexity of the SDHS algorithm is \(O(hms\times n+m\times(n+\log_{2}hms))\).  
As illustrated in Table 1, a comparison is made between the time complexity and parameter settings of basic HS and SDHS. It is evident that both algorithms exhibit analogous initialization and memory consideration complexities. The adoption of a heap structure by SDHS results in a reduction in the complexity of the harmony memory update process from \(O(hms)\) to \(O(\log_{2}hms)\). The algorithm's enhanced adaptability and usability is attributable to the simple, flexible, and efficient operator design, which retains only a single parameter (\(hms\)).  
Figure 1: Flowchart of the SDHS algorithm.  
To facilitate the comparative study of metaheuristics for the 0-1 KP, the source code of the SDHS algorithm has been made publicly available in GitHub ([[https://github.com/14](https://github.com/14)]([https://github.com/14](https://github.com/14)) 97135676/SDHS4 KP (accessed on 8 May 2025)).