# A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack Problem
## 4 Experiments and Results
### Discussion  
We would like to discuss the rationale behind the proposed model and why it may be useful for other problem domains besides the one studied in this document.  
As with other packing problems, the iterative nature of KP makes it a great candidate for a hyper-heuristic approach. The inherent mapping of problem states to decisions (or, in this case, packing heuristics) can lead to an optimal item selection by overfitting if the relationship were to be searched exhaustively. A generalization of this item selection is the basis of the rationale behind this approach. Furthermore, the advantages of mixing heuristics have previously been discussed in detail for various optimization and search problems [27; 58].  
The evidence obtained from the experiments confirms that it is possible to produce a sequence of heuristics that provides an acceptable performance when tested on a set of instances. Allow us to explain this in more detail. Let us assume that a hyper-heuristic HH\({}_{1}\) is to be produced for solving only one KP instance with \(n\) items, KP\({}_{1}\). If the cardinality of the hyper-heuristic is equal to the number of items to pack (\(\omega=n\)), then HH\({}_{1}\) can  
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline  & \multicolumn{4}{c}{**Heuristics**} & \multicolumn{4}{c}{**Hyper-Heuristics**} \\ \cline{2-7}
**Rank** & Def & MaxP & MaxPW & MinW & Best-HH & Median-HH & Worst-HH \\ \hline
1.0 & 10 & 20 & 0 & 15 & 10 & 4 & 15 \\
1.5 & 1 & 1 & 4 & 2 & 8 & 6 & 2 \\
2.0 & 10 & 12 & 14 & 2 & 23 & 19 & 7 \\
2.5 & 0 & 1 & 81 & 2 & 80 & 82 & 80 \\
3.0 & 14 & 25 & 62 & 33 & 62 & 71 & 63 \\
3.5 & 1 & 2 & 31 & 3 & 29 & 30 & 26 \\
4.0 & 3 & 5 & 9 & 9 & 8 & 6 & 16 \\
4.5 & 0 & 0 & 17 & 6 & 10 & 11 & 12 \\
5.0 & 25 & 27 & 4 & 44 & 2 & 3 & 4 \\
5.5 & 3 & 2 & 15 & 8 & 7 & 8 & 9 \\
6.0 & 140 & 34 & 2 & 27 & 1 & 0 & 5 \\
6.5 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\
7.0 & 32 & 110 & 0 & 89 & 0 & 0 & 0 \\ \hline Profit & 3,752,072 & 3,631,322 & 4,046,715 & 3,930,092 & **4,052,501** & 4,052,039 & 4,045,794 \\ \hline \hline \end{tabular}
\end{table}
Table 9: Ranks and total profit obtained by the four heuristics and the best, median, and worst hyper-heuristics trained on 60% of set \(\beta_{2}\) and tested on the remaining 40% of set \(\beta_{2}\). The best result, measured in terms of total profit, is highlighted in bold.  
decide which heuristic to use for packing each item. Among all the possible HHs that could be produced, there is one where all the decisions are correct, \(\mathrm{HH}_{1}^{*}\), which represents the optimal sequence to pack the items in \(\mathrm{KP}_{1}\), given the available heuristics. Now, let us produce a new hyper-heuristic \(\mathrm{HH}_{2}^{*}\), the best sequence of heuristics for solving a second KP instance, \(\mathrm{KP}_{2}\), also containing \(n\) items (the simplest case for the analysis). There is no guarantee that the previous hyper-heuristic, \(\mathrm{HH}_{1}^{*}\), will also represent the optimal sequence of heuristics for solving \(\mathrm{KP}_{2}\). If we keep the idea of having one individual decision per item, only a few of these decisions will be the same for both sequences, \(\mathrm{HH}_{1}^{*}\) and \(\mathrm{HH}_{2}^{*}\). In order to merge the two sequences, some errors must be accepted. The task of the evolutionary framework is to decide which errors to accept so that the performance is the best among all the instances in the training set. Overall, the model is not looking for the best sequence of heuristics for each particular instance but the best sequence to solve, acceptably, all the instances in the training set.