# A Heuristics-Guided Simplified Discrete Harmony Search Algorithm for Solving 0-1 Knapsack Problem
## 6 Conclusions  
This paper presents a simplified discrete HS algorithm for solving the 0-1 KP. The time complexity of the SDHS is \(O(hms\times n+m\times(n+\log_{2}hms))\), where \(m\) represents the number of iterations of the algorithm, \(n\) is the number of items in the problem instance, and \(hms\) is the capacity of the harmony memory. The proposed SDHS algorithm has three unique features: (1) the random search operator is discarded and there is only one intrinsic parameter, i.e., harmony memory size, which greatly simplifies the parameter tuning; (2) in the memory consideration operator, the profit-weight ratio is used to guide the processing order of items, which can effectively improve its intensification ability; (3) the pitch adjustment operator is implemented at the solution level and is greedily guided by the profit of items, which can provide an extra complement for the profit-weight ratio-guided memory consideration operator. Experiment results confirm the positive effect of these three features on the performance of the SDHS algorithm. Furthermore, the performance of the SDHS algorithm was tested on three sets of large-scale 0-1 KP instances and compared with thirteen state-of-the-art metaheuristics. The results of the comparative experiments confirm that the SDHS algorithm performs better than the 13 compared algorithms. The SDHS algorithm is not only very simple but is also very effective for the 0-1 KP. A meaningful research direction is to study whether the strategies used by the SDHS algorithm are still effective and efficient for other variants of KP. However, SDHS may still exhibit certain limitations: (1) The strict binary nature (each item is either 0 or 1) of the decision variables for the 0-1 knapsack problem may permit the SDHS to maintain adequate solution diversity through its harmony memory and pitch adjustment operator, even after discarding the random search operator. However, this simplification might pose challenges when extending the SDHS to other combinatorial optimization problems, such as those involving graph theory or variables with larger domains. In such instances, the algorithm could be susceptible to premature convergence towards local optima due to the absence of a random jumping mechanism, a crucial component for exploring disparate regions of the search space. (2) The efficacy of the algorithm is significantly dependent on the effectiveness of the two selected heuristics, the profit-weight ratio and the profit. Although these heuristics are generally quite effective for the knapsack problem, their optimality across all possible scenarios cannot be guaranteed. There may exist deceptive or specifically constructed knapsack instances in which these greedy rules could steer the search towards suboptimal regions. F.Z. : Writing--original draft, Software. K.C. : Writing--review and editing, Validation, Supervision, Methodology, Investigation, Formal analysis. K.Y. : Writing--review and editing, Investigation, Formal analysis. N.L. : Writing--review and editing, Investigation, Formal analysis. N.L. : Writing--review and editing, Investigation, Formal \begin{table}
\begin{tabular}{l l l l l l} \hline \hline
**Algorithm** & **Rank** & **Gap** & \(p\)**-Value** & \(p\)**-Holm** & **Sum of \(+\) / \(=\) / \(-\)** \\ \hline SDHS & 1.21 & - & - & - & - \\ CGMA & 3.02 & 0.257 & \(6.83\times\mathbf{10^{-4}}\) & \(1.37\times\mathbf{10^{-3}}\) & 0/2/22 \\ MBPOS & 3.81 & 0.491 & \(\mathbf{1.16\times 10^{-7}}\) & \(3.47\times\mathbf{10^{-7}}\) & 0/1/23 \\ DGHS & 5 & 0.685 & \(\mathbf{1.11\times 10^{-15}}\) & \(4.44\times\mathbf{10^{-15}}\) & 0/0/24 \\ HOSSHS & 1.96 & 0.111 & \(4.70\times 10^{-1}\) & \(4.70\times 10^{-1}\) & 0/6/18 \\ \hline \hline \end{tabular} Note: Bold values in the \(p\) columns indicate statistical significance (\(p<0.05\)).  
\end{table} 
Table 19: The performance summary between SDHS, CGMA, MBPOS, DGHS, and HOSSHS; the average ranks are computed by the Friedman test and the significance is assessed by [PERSON]’s post hoc method. analysis. Y.L.