# Hyper-Heuristic Based on ACO and Local Search for Dynamic Optimization Problems +
## 1 Introduction
In order to avoid redundancy in the ant population list, different extensions of P-ACO have been proposed, including Fitness Sharing P-ACO (FS-PACO) [24], Simple Crowding P-ACO (SC-PACO) [25], immigrant schemes with ACO [26], and Memetic ACO (M-PACO) [12] algorithms. The authors of [27] propose adaptive large neighborhood search (ALNS)-based immigrant schemes for DTSPs. Something that stands out is that in the previous articles, DTSPs instances were generated based on a very small number of TSP instances. From our point of view, this can hide important aspects in the results. For this reason, we have used a wider range of TSP base instances to generate our DSTPs. We have also observed that the ACO used as the base for our hyper-heuristic presents one of the best performances in the literature, allowing us to compare between their variants without loss of generality. This paper extends the existing literature by developing an enhanced ACO-based metaheuristic to solve a DTSP. Our efforts lie in developing a hyper-heuristic based on ACO and local search, aiming to solve the DTSP efficiently. The integration of local search operators with metaheuristics showed significant improvements in the solution quality for static optimization problems [28; 29; 30; 31] and, more recently, for DOPs [8; 10]. The Unstringing and Stringing (US) [32] and Lin-Kernighan (LK) [33; 34] local search operators have demonstrated promising performance in ACO-based memetic algorithms for DOPs [8; 9; 10]. This happens because the local search operators take advantage of the global search capabilities of ACO to guide them in neighbourhoods that contain high-quality solutions, while ACO takes advantage of the local search operators to better explore the neighbourhood locally. However, the local search operators' performance often depends on the problem instance and in many cases on the dynamic changes of the DOPs [8]. In this research, a hyper-heuristic [1] is used to enable the selection of the local search operator (either LK or US) that can better contribute to the solution quality of the DTSP. This paper is an extended version of our paper [8] that presents only a local search operator (LSO), improving the best solution found by an Ant Colony Optimisation framework, and compares the use of two of these local search operators (named Lin-Kernighan and Unstring and Stringing) independently. The hyper-heuristic proposed here (called HULK -- Hyper-heuristic with Us and LK as local search operators) is very different from the congress paper due to the intelligence applied in the choice of LSOs and the order in which they are applied that make use of a self-adaptive function. There is another huge difference in the instances and in the frequency of dynamic changes, i.e., the instances used here allow arc blocking, and the frequency of dynamic changes has dropped from \(10^{4}\) to \(100\), making HULK faster without losing quality. This new HULK is able to outperform the methods presented in the congress paper, and a whole set of new results are presented here. The HULK improves its ability to cope with the best features of LK and US, producing much better solutions, mainly in the asymmetric dynamic change environment. For the purpose of keeping a self-sufficient article, the explanations of the LSOs are the same as in the congress paper, and we also present some results to allow for a better understanding of the computational experiments. The paper highlights can be listed as follows:  
* We integrate one of the best ACO variations with advanced and effective local search operators, i.e., the Lin-Kernighan and the Unstringing and Stringing heuristics, resulting in a powerful hyper-heuristic (HULK). * The proposed HULK combines the adaptation capabilities of ACO for DOPs and the superior performance of the local search operators. This is done with a smart and self-adaptive way to choose the LSO that is applied using a weighted roulette wheel, based on the objective function value of the previous solutions.