# A Heuristics-Guided Simplified Discrete Harmony Search Algorithm for Solving 0-1 Knapsack Problem
## 5 Comparative Experiments
### Experiment on the Third Set of Large-Scale 0-1 KP Instances
\begin{table}
\begin{tabular}{l l l l l l l l l} \hline \hline
**Ins** & **Opt** & **Method** & **Best** & **Worst** & **Mean** & **Median** & **Std** & **Time (s)** \\ \hline KP12 & 49,443 & CSGHS & 49,403 & 49,383 & 49,393 & 49,393 & 6.52 & - \\  & & BMBO & 49,393 & 49,353 & 49,378 & 49,382 & 10.12 & - \\  & & CMBO & 49,433 & 49,433 & 49,422 & 49,433 & 2.49 & - \\  & & OMBO & \(\mathbf{49}\)**,443** & 49,441 & \(\mathbf{49}\)**,443** & \(\mathbf{49}\)**,443** & 0.34 & - \\  & & NM & \(\mathbf{49}\)**,443** & \(\mathbf{49}\)**,443** & \(\mathbf{49}\)**,443** & \(\mathbf{49}\)**,443** & \(\mathbf{0}\) & - \\  & & LBSA & \(\mathbf{49}\)**,443** & \(\mathbf{49}\)**,443** & \(\mathbf{49}\)**,443** & \(\mathbf{49}\)**,443** & \(\mathbf{0}\) & - \\  & & SDHS & \(\mathbf{49}\)**,443** & \(\mathbf{49}\)**,443** & \(\mathbf{49}\)**,443** & \(\mathbf{49}\)**,443** & \(\mathbf{0}\) & 0.85 \\ KP13 & 60,640 & CSGHS & 60,587 & 60,567 & 60,573 & 60,570 & 5.32 & - \\  & & BMBO & 60,588 & 60,530 & 60,562 & 60,560 & 11.98 & - \\  & & CMBO & \(\mathbf{60}\)**,640** & 60,639 & \(\mathbf{60}\)**,640** & \(\mathbf{60}\)**,640** & 0.14 & - \\  & & OMBO & \(\mathbf{60}\)**,640** & 60,640 & 60,640 & \(\mathbf{60}\)**,640** & \(\mathbf{0}\) & - \\  & & NM & \(\mathbf{60}\)**,640** & 60,640 & 60,640 & 60,640 & 0 & - \\  & & LBSA & \(\mathbf{60}\)**,640** & 60,640 & 60,640 & 60,640 & 0 & - \\  & & SDHS & \(\mathbf{60}\)**,640** & 60,640 & 60,640 & 60,640 & 0 & 0.74 \\ KP14 & 74,932 & CSGHS & 74,858 & 74,817 & 74,835 & 74,832 & 9.31 & - \\  & & BMBO & 74,842 & 74,772 & 74,818 & 74,821 & 15.80 & - \\  & & CMBO & \(\mathbf{74}\)**,932** & 74,931 & \(\mathbf{74}\)**,932** & \(\mathbf{74}\)**,932** & 0.27 & - \\  & & OMBO & \(\mathbf{74}\)**,932** & 74,931 & \(\mathbf{74}\)**,932** & \(\mathbf{74}\)**,932** & 0.14 & - \\  & & NM & \(\mathbf{74}\)**,932** & **74,932** & \(\mathbf{74}\)**,932** & \(\mathbf{74}\)**,932** & 0 & - \\  & & LBSA & \(\mathbf{74}\)**,932** & 74,932 & \(\mathbf{74}\)**,932** & \(\mathbf{74}\)**,932** & 0 & - \\  & & SDHS & \(\mathbf{74}\)**,932** & 74,932 & \(\mathbf{74}\)**,932** & \(\mathbf{74}\)**,932** & 0 & 0.88 \\ KP15 & 99,683 & CSGHS & - & - & - & - & - & - \\  & & BMBO & - & - & - & - & - & - \\  & & CMBO & \(\mathbf{99}\)**,683** & 99,672 & 99,682 & 99,683 & 2.23 & - \\  & & OMBO & \(\mathbf{99}\)**,683** & 99,679 & \(\mathbf{99}\)**,683** & \(\mathbf{99}\)**,683** & 0.58 & - \\  & & NM & \(\mathbf{99}\)**,683** & **99,683** & **99,683** & \(\mathbf{99}\)**,683** & 0 & - \\  & & LBSA & \(\mathbf{99}\)**,683** & **99,683** & **99,683** & \(\mathbf{99}\)**,683** & \(\mathbf{0}\) & - \\  & & SDHS & \(\mathbf{99}\)**,683** & **99,683** & **99,683** & \(\mathbf{99}\)**,683** & \(\mathbf{0}\) & 1.25 \\ \hline \hline \end{tabular} Note: Bold numbers indicate the algorithm found the relatively best solution.  
\end{table} 
Table 12: _Cont._Table 14 shows that, on the five weakly correlated instances, the SDHS algorithm finds a new best solution on the three instances with 500, 800, and 1000 items. In terms of worst value and mean value, the SDHS algorithm obtains better results than the other four algorithms on all five instances. Table 15 shows that only the SDHS algorithm can always find the best-known solutions on all five strongly correlated instances. Table 16 shows that, on the five multiple strongly correlated instances, the SDHS algorithm finds a new best solution on the two instances with 800 and 1000 items. Except the instance with 1000 items, the SDHS algorithm can always find best-known solutions on the other four multiple strongly correlated instances. Table 17 shows that the HSOSHS algorithm and the SDHS algorithm can always find best-known solutions on all profit ceiling instances. Table 18 shows that the SDHS algorithm finds a new best solution on all the four uncorrelated instances. In terms of best value, worst value, mean value, median value, and standard deviation, the SDHS algorithm obtains better results than the other four algorithms on all four instances.