# A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack Problem
## 3 Proposed Hyper-Heuristic Model  
The HH model developed in this work can be classified as an offline selection HH [56]. Internally, the HH model relies on a variant of the \((1+1)\) Evolutionary Algorithm (EA) to find the sequence of heuristics to apply. The original EA flipped each bit with probability \(1/\varpi\) (where \(\varpi\) is the chromosome length). Conversely, our approach chooses one among various available mutation operators based on a uniform random probability distribution. This EA implementation considers some of the features used by [PERSON] and [PERSON] [27]. However, the set of available operators is different as we work with constructive heuristics while they have used perturbative ones.  
We choose four simple packing heuristics due to their popularity: \(\mathfrak{H}=\{\texttt{Def},\texttt{MaxP},\texttt{MaxPW},\texttt{MinW}\}\). Before moving forward, we describe them below.  
**Default**: (Def) packs the items in the same order that they are contained in the instance, as long as they fit in the knapsack.
**Maximum profit**: (MaxP) sorts the items in descending order based on their profit and packs them in that order as long as they fit in the knapsack.
**Maximum profit per weight**: (MaxPW) calculates profit-over-weight ratio for each item and sorts them in descending order. Then, MaxPW follows this ordering until the knapsack is full or no more items are left to be packed.
**Minimum weight**: (MinW) favors lighter items, so it sorts items in ascending order based on their weight and packs them by following such order until they no longer fit.  
Should there be a tie, all heuristics will choose the first conflicting item. Among these heuristics, Def is the fastest one to execute as it involves no additional operations. On the contrary, MaxP, MaxPW, and MinW take longer to compute but usually yield better results than using no order at all (Def). We are aware that more complex heuristics are available in the literature. Still, at this point in the investigation, we consider it suitable to test the proposed HH approach on this set of simple heuristics.  
In our model, each HH represents a sequence of heuristics to apply to the problem in one specific order. For simplicity, we refer to its length as the cardinality of the HH. Let us consider the HH with cardinality of five (\(\mathbf{h}\in\beta^{5}\)) given by \(\mathbf{h}=\{\texttt{Def},\texttt{MaxP},\texttt{MaxP},\texttt{Def},\texttt{MinW}\}\) (Figure 1). Please note that one of the available heuristics is not contained within the HH, MaxPW. In this HH, Def occupies positions 0 and 3, MaxP occupies positions 1 and 2, and MinW occupies position 4. Let us assume that \(\mathbf{h}\) will solve a 12-item knapsack instance. In this case, there are 12 decisions to be made for solving this instance (\(d_{1}\) to \(d_{12}\)). While some of the decisions will add an item to the knapsack, others will discard it. As the HH represents a sequence of five heuristics, the first five decisions will be made in the same order in which the heuristics are presented in \(\mathbf{h}\): Def, MaxP, MaxP, Def, and MinW. After that, there are no more heuristics to choose to make further decisions. Then, the HH is used again, but now backwards: MinW, Def, MaxP, MaxP, and Def. The process repeats by inverting the sequence every time we reach the end of the HH. Although this scheme seems disruptive, we consider it feasible to favor the changes in heuristics throughout the solving process.