# Hyper-Heuristic Based on ACO and Local Search for Dynamic Optimization Problems +
## 3 HULK: Hyper-Heuristic Based on ACO and Local Search Operators
### Choosing and Applying Local Search Operator  
[PERSON] and [PERSON] [41] applied local search operators to the iteration-best ant of \(\mathcal{MM}\)AS after every iteration, while in [29], they further applied local search operators to all ants. However, local search operators are computationally expensive methods; thus, this massive usage may not be very efficient for DTSP because of the natural increase of computation effort. As previously discussed, for DTSPs, algorithms must produce high-quality solutions quickly (essentially before the next dynamic change occurs) [37]. In [8; 10], the local search operator is applied to the best-so-far ant of \(\mathcal{MM}\)AS only when a new best solution is found. This is because local search operators are typically executed until no further improvement is possible. However, in this research, as there may be the exchange of LSO there are cases where it is interesting to apply LSO even when there is no improvement in the best solution so far. These exchanges between LSO can change the pheromone trail guiding the search to promising places not yet explored. We investigate two powerful local search heuristics designed for the TSP, LK, and US heuristics that were adapted to cope with both symmetric and asymmetric cases; we describe them in Sections 3.2.1 and 3.2.2, respectively. The proposed hyper-heuristic is designed to select how and when to apply the local search operator. As previously discussed, each time the ACO finds an improved solution, a local search heuristic is applied to that solution for further improvement, but the hyper-heuristic can also apply LSOs to avoid solution stagnation and to perform a sort of diversification in the search space; the whole hyper-heuristic framework is presented in Algorithm 2. To decide which local search will be applied, we use a weighted roulette wheel with choice probabilities of initially equal to 0.5 for both and updated as shown in Equation (11) if US was chosen, and in Equation (12) if LK was chosen. This idea is similar to Genetic Algorithms, where the chromosomes with better fitness value (LSO with better performance) have greater chances to picked. _averUS_ and _averLK_ will be the average improvement of up to three last-solution values produced by US and LK, respectively. We need to make sure that this adjustment was only made if both operators had already been selected at least once and the average of the solutions found by the algorithm chosen was less than the other (minimization problem), i.e., _averUS_\(<\)_averLK_ if US is chosen, and _averLK_\(<\)_averUS_ if LK was chosen. This update attempts to prevent the choice of only one of the operators available prematurely; also, \(\gamma\), and \(\delta\) are limited in the range \([0.1,0.9]\). Observe that HULK starts with the same chance of selecting both LSO, but during the search, the percentages are self-adjusted in favor of the LSO with better performance, and this procedure is easily adapted if there are more than two LSOs or if we consider other DOPs. To choose the LSO, we first generate a random number uniformly distributed in the interval \([0.0,1.0]\), and if this number is less than \(\gamma\), US is chosen. Otherwise, we choose LK. The integration of the LSO into the hyper-heuristic is made through the procedure ApplyLSO(\(\pi^{lb}\), \(A\), \(DistanceMatrix\)), where \(\pi\) is the current solution and \(A\) is the LSO. This procedure is detailed in Algorithm 1. \[\gamma=\gamma+\left(1-\frac{\textit{averUS}}{\textit{averLK}}\right)\,\delta \,\,\text{and}\,\,\delta=\delta-\left(1-\frac{\textit{averLK}}{\textit{averLK }}\right)\,\delta\,,\,\text{if US was chosen} \tag{11}\]  
\[\delta=\delta+\left(1-\frac{\textit{averLK}}{\textit{averLK}}\right)\gamma\, \,\text{and}\,\,\gamma=\gamma-\left(1-\frac{\textit{averLK}}{\textit{averLK }}\right)\,\gamma\,,\,\text{if LK was chosen} \tag{12}\]  
```
1:ApplyLSO(\(\pi^{lb}\), \(A\), \(DistanceMatrix\))
2:if(\(A=\textit{US}\))then
3: ApplyLocalSearchUS(\(\pi^{lb}\))
4:if(Solution was improved?)