# A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack Problem
## 3 Proposed Hyper-Heuristic Model
### Mutation Operators  
The evolutionary process dynamically chooses among eight available mutation operators to alter the candidate hyper-heuristic \(\mathbf{h}^{\prime}\). Operators contained within set \(\mathcal{D}\) are described below. To clarify the behavior of such operators, we also provide a brief example of their behavior. Bear in mind that, in all the examples, we always consider the HH depicted in Figure 1 as the HH to mutate, i.e., \(\mathbf{h}^{\prime}=\{\texttt{Def},\texttt{MaxP},\texttt{MaxP},\texttt{Def},\texttt{ MinW}\}\). **Add**: inserts a randomly chosen heuristic at a random position \(i\sim\mathcal{U}\{0,\omega-1\}\) into \(\mathbf{h}^{\prime}\). In doing so, cardinality (\(\omega=\#\mathbf{h}^{\prime}\)) increases by one and existing heuristics at this position onward are shifted to the right. For the example, let us assume that \(i=3\) and that the random selection chooses MaxPW. Thus, the resulting HH has a cardinality of six and is given by \(\mathbf{h}^{\prime}=\{\texttt{Def},\texttt{MaxP},\texttt{MaxP},\texttt{Def}, \texttt{MinW}\}\). **Single-point Flip**: selects a position \(i\sim\mathcal{U}\{0,\omega-1\}\) at random from \(\mathbf{h}^{\prime}\) and changes its heuristic \(h_{i}\in\mathbf{h}\) to a different one (selected at random). Thus, cardinality is preserved. Let us suppose that \(i=0\). As Def is the current heuristic at this position, it cannot be chosen. Therefore, let us assume that the new heuristic is MinW. Then, the resulting HH is \(\mathbf{h}^{\prime}=\{\texttt{MinW},\texttt{MaxP},\texttt{MaxP},\texttt{Def}, \texttt{MinW}\}\). **Two-point Flip**: is a more disruptive version of the previous operator. This time, heuristics at two different positions \((i,j\sim\mathcal{U}\{0,\omega-1\})\) are renewed. Let us suppose that \(i=2\) and \(j=4\). In the first case, the available heuristics are Def, MaxPW, and MinW. In the second one, they are Def, MaxP, and MaxPW. Imagine that MaxPW and Def are selected, respectively. Then, the resulting HH still preserves cardinality and is given by \(\mathbf{h}^{\prime}=\{\texttt{Def},\texttt{MaxP},\texttt{MaxPW},\texttt{Def}, \texttt{Def}\}\). **Neighbor-based Add**: is similar to Add as it also inserts a heuristic at a random position \(k\sim\mathcal{U}\{0,\omega-1\}\) within \(\mathbf{h}^{\prime}\). However, the heuristic to insert is randomly selected among neighboring heuristics (positions \(j=i-1\) and \(k=i+1\)), as long as theyare valid positions. Should \(i\) correspond to an edge, the only neighbor is copied. Let us suppose that \(i=1\). In this case, the heuristic to insert would be either Def (\(j=0\)) or MaxP (\(k=2\)), with the same probability (50%). Imagine that MaxP is selected. Then, and as with the Add operator, cardinality grows to six and the resulting HH is \(\mathbf{h}^{\prime}=\{\texttt{Def},\texttt{MaxP},\texttt{MaxP},\texttt{Def}, \texttt{MinW}\}\). **Neighbor-based Single-point Flip**: is a variant of Single-Point Flip where the heuristic at \(i\sim\mathcal{U}\{0,\alpha-1\}\) changes into one of its neighbors (positions \(j=i-1\) and \(k=i+1\), if they exist). For example, suppose that \(i=2\). In this case, candidate replacements would be either MaxP (\(j=1\)) or Def (\(k=3\)), each one with a 50% probability. Let us suppose that Def is selected. Then, the resulting HH preserves cardinality and becomes \(\mathbf{h}^{\prime}=\{\texttt{Def},\texttt{MaxP},\texttt{Def},\texttt{Def}, \texttt{MinW}\}\). **Neighbor-based Two-point Flip**: likewise, this is a variant of Two-Point Flip in which heuristics are chosen at random from neighboring ones. Let us suppose that \(i=2\) and \(j=4\). In the first case, available heuristics are MaxP and Def; in the second one, it is only Def since the position corresponds to an edge of the HH. Let us suppose that, in the first case, Def is selected. Therefore, the resulting HH is \(\mathbf{h}^{\prime}=\{\texttt{Def},\texttt{MaxP},\texttt{Def},\texttt{Def}, \texttt{Def},\texttt{Def}\}\).