# A Heuristics-Guided Simplified Discrete Harmony Search Algorithm for Solving 0-1 Knapsack Problem
## 5 Comparative Experiments
### Experiment on the First Set of Large-Scale 0-1 KP Instances
\begin{table}
\begin{tabular}{l c c c c c c c c c c} \hline \hline
**Method** & **Ins** & **Best** & **Worst** & **Mean** & **Time (s)** & **Ins** & **Best** & **Worst** & **Mean** & **Time (s)** \\ \hline NSHS & LKP01 & 61.82 & 61.11 & 61.5 & - & LKP09 & 1133.44 & 1125.69 & 1129.02 & - \\ ABHS & & 62.01 & 61.71 & 61.9 & - & & 1140.69 & 1133.22 & 1136.57 & - \\ SBHS & & **62.08** & 61.97 & 62.04 & - & & 1155.65 & 1155.35 & 1155.57 & - \\ SDHS & & **62.08** & **62.08** & **62.08** & 0.02 & & **1155.68** & **1155.68** & **1155.68** & 1.04 \\ NGHS & LKP02 & 128.34 & 126.87 & 127.66 & - & LKP10 & 1257.45 & 1249.74 & 1252.86 & - \\ ABHS & & 129.31 & 128.51 & 128.94 & - & & 1263.67 & 1257.85 & 1260.46 & - \\ SBHS & & **129.44** & 129.27 & 129.37 & - & & **1283.92** & 1283.26 & 1283.79 & - \\ SDHS & & **129.44** & **129.44** & **129.44** & 0.04 & & **1283.92** & **1283.92** & **1283.92** & 1.16 \\ NGHS & LKP03 & 190.18 & 187.9 & 189.23 & - & LKP11 & 1615.64 & 1604.28 & 1610.5 & - \\ ABHS & & 191.49 & 190.32 & 191.04 & - & & 1623.3 & 1613.54 & 1618.77 & - \\ SBHS & & **192.02** & 191.85 & 192.01 & - & & 1653.72 & 1653.43 & 1653.64 & - \\ SDHS & & **192.02** & **192.02** & **192.02** & 0.07 & & **1653.76** & **1653.76** & **1653.76** & 1.64 \\ NGHS & LKP04 & 310.16 & 305.67 & 308.33 & - & LKP12 & 1877.66 & 1868.31 & 1872.43 & - \\ ABHS & & 312.51 & 310.67 & 311.79 & - & & 1879.12 & 1868.61 & 1874.04 & - \\ SBHS & & **314.23** & 314.1 & 314.19 & - & & 1917.49 & 1917.23 & 1917.42 & - \\ SDHS & & **314.23** & **314.23** & **314.23** & 0.12 & & **1917.58** & **1917.57** & **1917.57** & 1.96 \\ NGHS & LKP05 & 442.32 & 436.45 & 440.83 & - & LKP13 & 2200.57 & 2191.68 & 2196.15 & - \\ ABHS & & 446.3 & 444.42 & 445.43 & - & & 2203.56 & 2193.78 & 2199.31 & - \\ SBHS & & **448.65** & 448.46 & 448.6 & - & & 2248.27 & 2247.77 & 2248.12 & - \\ SDHS & & **448.65** & **448.65** & **448.65** & 0.27 & & **2248.30** & **2248.30** & **2248.30** & 2.42 \\ NGHS & LKP06 & 626.77 & 619.15 & 623.87 & - & LKP14 & 3061.12 & 3047.8 & 3054.33 & - \\ ABHS & & 632.38 & 628.65 & 630.34 & - & & 3055.47 & 3040.32 & 3046.91 & - \\ SBHS & & **638.14** & 638 & 638.09 & - & & 3135.71 & 3135.29 & 3135.58 & - \\ SDHS & & **638.14** & **638.14** & **638.14** & 0.45 & & **3135.77** & **3135.77** & **3135.77** & 3.83 \\ NGHS & LKP07 & 750.67 & 745.05 & 747.66 & - & LKP15 & 3625.86 & 3609.96 & 3617.04 & - \\ ABHS & & 756.08 & 752.10 & 754.26 & - & & 3615.85 & 3601.58 & 3607.61 & - \\ SBHS & & 763.81 & 763.39 & 763.71 & - & & 3707.39 & 3706.98 & 3707.29 & - \\ SDHS & & **763.83** & **763.83** & **763.83** & 0.68 & & **3707.45** & **3707.44** & **3707.44** & 4.99 \\ NGHS & LKP08 & 945.20 & 938.31 & 941.97 & - & LKP16 & 4009.33 & 3995.04 & 4003.40 & - \\ ABHS & & 950.70 & 947.36 & 949.17 & - & & 4009.08 & 3993.47 & 4001.41 & - \\ SBHS & & 964.91 & 964.70 & 964.85 & - & & 4090.83 & 4090.36 & 4090.64 & - \\ SDHS & & **964.92** & **964.91** & **964.92** & 0.97 & & **4090.87** & **4090.86** & **4090.87** & 5.64 \\ \hline \hline \end{tabular} Note: Bold numbers indicate the algorithm found the relatively best solution.  
\end{table} 
Table 8: Comparison of the SDHS algorithm with three HS algorithms. ranking. Specifically, compared with NGHS and ABHS, SDHS has a significant advantage. Although the performance difference is not significant compared with the SBHS algorithm, SDHS obtains a better ranking, and the average values are all better than those of other algorithms. The table also counts the percentage of improvement of SDHS compared with the reported approach, calculated as Equation (18):  
\[\text{Gap}(A)=\frac{\text{Mean}_{A}-\text{Mean}_{\text{SDHS}}}{\text{Mean}_{A}} \tag{18}\]