# Hyper-Heuristic Based on ACO and Local Search for Dynamic Optimization Problems +
## 1 Introduction  
Hyper-heuristics comprise a set of approaches with the common goal of automating design and tuning heuristic methods to solve hard computational search problems. Their main goal is to produce applicable search methodologies more broadly. Hyper-heuristics' distinguishing feature is that they operate on a search space of heuristics (or heuristic components) rather than directly on the search space of solutions to the underlying problem, as happens with most meta-heuristic approaches [1]. For an updated survey about hyper-heuristics for Dynamic Optimization Problems (DOPs), see [2]. Ant colony optimization (ACO) algorithms have proved that they are capable to find the optimal (or near optimal) solution for difficult combinatorial optimization problems (e.g., the static travelling salesman problem (STSP) [3]). In this research, we utilize the travelling salesman problem (TSP) as the base problem to generate both symmetric and asymmetric dynamic test cases. The STSP has been studied extensively for the last few decades [4] and it is one of the most challenging \(\mathcal{NP}\)-complete combinatorial optimization problems. As a whole, literature publications have dealt only with static problems, without dynamic changes, i.e., the instances do not change during the problem solving. However, several real-world applications experience changes during the optimization process (e.g., traffic restrictions), making the problem even more difficult. DOPs are defibecause they need to quickly search for the best solution to the problem while dealing with changes in the search space [5]. A dynamic change may involve many factors, such as the objective function, input variables, problem instance, search space, and constraints. The traveling salesman problem with varying parameters are referred to as dynamic traveling salesman problem (DTSP). Many real-life applications can be modelled like a DTSP, e.g., transportation managers need to handle stochasticity and dynamicity in designing and managing a route plan. DTSP appears in some studies, and approaches are proposed to solve it efficiently. The authors of [6] say that DTSPs are more difficult than STSP and also point out that traditional methods to solve STSPs may not be able to find answers for DTSPs. Therefore, the study of metaheuristic optimization algorithms such as swarm and evolutionary algorithms has taken place to solve DTSPs. The studies on this subject matter concentrate primarily on improving metaheuristics -- formerly developed to solve conventional static optimization problems. Some examples of these algorithms include but are not limited to Artificial Immune Systems (AISs) [7], ant colony optimization algorithms [8; 9; 10; 11; 12; 13], Genetic Algorithms (GAs) [14; 15; 16], and Particle Swarm Optimization algorithms (PSOs) [17; 18]. Since ACOs can adapt to dynamic changes by transferring knowledge from past environments, ACOs naturally combine with other techniques. Moreover, several ACOs features such as adaptability, instance ease of use, and efficiency make ACO-based approaches popular among researchers to solve DTSPs [11]. The authors of [19] propose a rank-based ACO algorithm to solve DTSP. The authors of [9] propose a memetic algorithm for symmetric DTSPs that was extended to solve asymmetric DTSPs [10]. The authors of [20] propose some pheromone modification strategies and investigate their performance in solving DTSPs. The authors of [21] propose an ACO algorithm for DTSPs with a technique, named Shaking, to smoothen the pheromone trails after a dynamic change. The authors of [22] propose two multi-colony ACO algorithms to solve a DTSP. The authors of [23] propose a memory-based ACO algorithm, namely, P-ACO, with the disadvantage that the algorithm may generate the same ants multiple times, worsening the computational performance.