Parameter Control Strategies of Parallel Hybrid Metaheuristics Applied to the Quadratic Assignment Problem Jonathan Duque Gallego Tesis de maestŕıa presentada para al t́ıtulo de Maǵıster en Ingenieŕıa, especialidad Informática Director Danny Alexandro Múnera Ramı́rez, Doctor (PhD) en Informática Universidad de Antioquia Facultad de Ingenieŕıa Maestŕıa en Ingenieŕıa Medelĺın, Antioquia, Colombia 2022 Cita (Duque Gallego, 2022) Referencia Estilo APA 7 (2020) Duque Gallego, J. (2022). Parameter Control Strategies of Paral- lel Hybrid Metaheuristics Applied to the Quadratic Assignment Problem [Tesis de maestŕıa]. Universidad de Antioquia, Medelĺın, Colombia.. Maestŕıa en Ingenieŕıa, Cohorte XIII. Grupo de Investigación Telecomunicaciones Aplicadas (GITA). Biblioteca Carlos Gaviria Dı́az Repositorio Institucional: http://bibliotecadigital.udea.edu.co Universidad de Antioquia - www.udea.edu.co Rector: John Jairo Arboleda Céspedes. Decano/Director Jesús Francisco Vargas Bonilla Jefe departamento: Augusto Enrique Salazar Jiménez. El contenido de esta obra corresponde al derecho de expresión de los autores y no compromete el pensamiento institucional de la Universidad de Antioquia ni desata su responsabilidad frente a terceros. Los autores asumen la responsabilidad por los derechos de autor y conexos. Thesis to obtain the degree of Master’s degree in engineering Specialty: informatics Presented by: Jonathan Duque Gallego Title: Parameter Control Strategies of Parallel Hybrid Metaheuristics Applied to the Quadratic Assignment Problem March 24, 2022 M. Danny Alexandro Múnera Ramı́rez Director 3 To the loving memory of my best friend Danilo To my mother Dora En la memoria de mi mejor amigo Danilo A mi madre Dora 4 Abstract The Quadratic Assignment Problem (QAP) is one of the most challenging combina- torial optimization problems with many real-life applications. Multiple methods have been created to solve QAP, exact and approximate methods, among others. Meta- heuristics are a subset of approximative methods which have shown to be very efficient in solving QAP. Their behavior can be controlled by a set of parameters. Currently, the best solvers are based on hybrid and parallel metaheuristics. However, the design of parallel hybrid methods requires even more the fine tuning of a larger number of parameters. The parameter setting problem (PSP) is the task of finding the correct values of the metaheuristic parameters that results in the best possible performance. It is possible to identify four main ways for solving the PSP, these are: Parameter Tuning Strate- gies, Parameter Control Strategies, Instance-specific Parameter Tuning Strategies and HyperHeuristics. Several methods for solving the PSP have been proposed. However, there is a need for parameter control strategies for single-solution metaheuristics, more notorious in parallel hybrid metaheuristics. To solve this problem, we have proposed PACAS, a framework to configure the PArameter Control Adaptation for Single solu- tion metaheuristics in a parallel hybrid solver for the efficient solution of combinatorial optimization problems. We proposed a Java implementation of framework J-PACAS, which implemented the functionality for solving the QAP. Our implementation uses three popular metaheuristics applied to QAP: the Ro- bust Tabu Search, the Extremal Optimization method and a simple Multi-start Local Search. J-PACAS also supplies three different strategies to perform the adaptation of the parameters. We present the results obtained by executing an experimental evalu- ation on a set of very difficult instances of QAPLIB. We explore different parameter control strategies, with different parallel configurations (independent or cooperative). We compare the best J-PACAS configuration identified in the experimental evalu- ation against a competitive state-of-the-art parameter control method, finding that our implementation presents a similar performance in small instances and a better performance in hard instances of the QAPLIB benchmark. 5 Contents 1 Introduction 10 1.1 Solution Methods for QAP . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Setting Metaheuristic Parameters . . . . . . . . . . . . . . . . . . . . . 12 1.3 Thesis Goals and Contributions . . . . . . . . . . . . . . . . . . . . . . 13 2 Background 15 2.1 Quadratic Assignment Problem . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 Hybrid Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4 Parallel Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5 Setting Metaheuristic Parameters . . . . . . . . . . . . . . . . . . . . . 20 2.5.1 Parameter Tuning Strategies (PTS) . . . . . . . . . . . . . . . . 21 2.5.2 Parameter Control Strategies (PCS) . . . . . . . . . . . . . . . 21 2.5.3 Instance-specific Parameter Tuning Strategies (IPTS) . . . . . . 21 2.5.4 HyperHeuristics (HH) . . . . . . . . . . . . . . . . . . . . . . . 22 3 State of the Art 23 3.1 Parameter Tuning Strategies (PTS) . . . . . . . . . . . . . . . . . . . . 24 3.2 Parameter Control Strategies (PCS) . . . . . . . . . . . . . . . . . . . . 30 3.3 Instance-specific Parameter Tuning Strategies (IPTS) . . . . . . . . . . 34 3.4 HyperHeuristics (HH) . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.5 Taxonomy PSP Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4 Framework 40 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2 General description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2.1 Team structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.2.2 Master node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2.3 Searcher nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.3 Parameter Control Strategies . . . . . . . . . . . . . . . . . . . . . . . 45 4.4 Framework Parameters Summary . . . . . . . . . . . . . . . . . . . . . 46 4.5 Hybridization in the PACAS framework . . . . . . . . . . . . . . . . . . 46 6 5 A Java Implementation of PACAS framework 49 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.2 Implementation details . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.2.1 MetaheuristicSearch Class . . . . . . . . . . . . . . . . . . . . . 51 5.2.2 GenericTeam Class . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.2.3 SolutionPopulation Class . . . . . . . . . . . . . . . . . . . . . . 55 5.2.4 ParameterControl Class . . . . . . . . . . . . . . . . . . . . . . 55 5.2.5 QAPData Class . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.2.6 AlgorithmConfiguration Class . . . . . . . . . . . . . . . . . . . 57 5.2.7 Other important classes . . . . . . . . . . . . . . . . . . . . . . 58 5.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 6 Experimental Evaluation 60 6.1 Independent group evaluation . . . . . . . . . . . . . . . . . . . . . . . 61 6.2 Cooperative group evaluation . . . . . . . . . . . . . . . . . . . . . . . 63 6.3 Evaluation of mixing parameter adaptation strategies . . . . . . . . . . 66 6.4 Distribution analysis of winning metaheuristics . . . . . . . . . . . . . . 67 6.5 Comparison with a state-of-the-art method . . . . . . . . . . . . . . . . 70 6.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7 Conclusion 73 7.1 Research perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Acknowledgement 75 Bibliography 76 7 List of Figures 3.1 Taxonomy for parameter control in EA and SI algorithms, adapted from [Parpinelli et al., 2019] . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 Taxonomy of strategies to solve the parameter setting problem (PSP) . 37 4.1 Representation of the search process using PACAS . . . . . . . . . . . 41 4.2 Structure of a Team . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3 Searcher report . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.1 J-PACAS Class Diagram Notation . . . . . . . . . . . . . . . . . . . . . 50 5.2 J-PACAS Class Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.3 J-PACAS Diversification gain percentages limits. . . . . . . . . . . . . . 54 5.4 Parameters adaptation in EO. . . . . . . . . . . . . . . . . . . . . . . . 56 5.5 Example parameters configuration of two AdaptedParamsTeam teams . 58 8 List of Tables 2.1 Metaheuristic parameter and its influence (note that MH stands for Metaheuristic type). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1 Summary of methods’ features for PTS . . . . . . . . . . . . . . . . . . 29 4.1 Summary PACAS framework parameters. . . . . . . . . . . . . . . . . . 47 5.1 Main methods in the MetaheuristicSearch Class . . . . . . . . . . . . . 51 5.2 Parameter ranges of the implemented metaheuristics. (note that n stands for problem instance’s size). . . . . . . . . . . . . . . . . . . . . 53 5.3 Request and Entry policies in SolutionPopulation Class . . . . . . . . . 55 5.4 Main methods in the ParameterControl Class . . . . . . . . . . . . . . 55 5.5 Parameters in J-PACAS framework. . . . . . . . . . . . . . . . . . . . . 58 6.1 J-PACAS configurations Independent Group . . . . . . . . . . . . . . . 61 6.2 Independent Group Evaluation on 26 hardest instances of QAPLIB. . . 62 6.3 J-PACAS configurations Cooperative Group . . . . . . . . . . . . . . . 64 6.4 Cooperative Group Evaluation on 26 hardest instances of QAPLIB. . . 65 6.5 Comparison performance: Independent vs Cooperative . . . . . . . . . 66 6.6 Mixing parameter adaptation strategies, Evaluation on 26 hardest in- stances of QAPLIB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 6.7 Distribution of winning metaheuristics in cooperative and independent group (analysis). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 6.8 Distribution of winning on CMIXING configuration . . . . . . . . . . . 69 6.9 Comparison results CMIXING vs. MSH-QAP (Timeout 5 mins). . . . . 71 6.10 Comparison results CMIXING vs. MSH-QAP (Timeout greater than 5 min). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 9 Chapter 1 Introduction The Quadratic Assignment Problem (QAP) is defined as the assignment of facilities, or tools, to exactly one location and vice versa. The distance between the locations and the flows between facilities is known, the problem is to find the minimum cost associated to assign a facility in one location; the cost is the sum of all the products between flows and the distance [Kaufman and Broeckx, 1978]. QAP is one of the best known combinatorial optimization problems and one of the most difficult (since it is NP-hard), it was presented by Koopmans and Beckmann in 1957 as a mathematical model for the location of indivisible economic activities [Koopmans and Beckmann, 1957]. Real-life applications can be modeled as QAP [Wu et al., 2012], such as electronic chipset layout and wiring, scheduling, process communications, turbine runner bal- ancing, data center network topology, among many others [Commander, 2005, Bhati and Rasool, 2014]. In general, one can find applications of QAP in multiple areas, such as archeology, statistics, economics, chemistry, logistics and electricity, among others. Even problems like the traveling salesman (TSP) can be formulated as a QAP problem [Loiola et al., 2007a]. Other types of QAP transformable problems can be found in [Burkard, 1984, Burkard et al., 2012]. 1.1 Solution Methods for QAP QAP can be solved using exact and approximative methods. Exact methods con- sider the entire search space: either explicitly by exhaustive search or implicitly, by pruning some portions of the search space that have been detected as irrelevant for the search. However, the QAP presents a “combinatorial explosion” i.e., the size of the search space grows exponentially with relation to the size of the instance (num- ber of variables, location or facilities). For this reason exact methods can not solve QAP instances with size larger than 35 in a reasonable time [Loiola et al., 2007b]. In contrast, approximative methods efficiently explore only some portions of the search space, obtaining a good sub-optimum solution (local optimum) in a reasonable time. 10 Metaheuristics are a subset of approximative methods which have shown to be very efficient in solving QAP. Metaheuristics are algorithms usually inspired by nature or physical principles. These methods usually make decisions to efficiently explore the search space of the problem and use randomness in their behavior [Boussäıd et al., 2013]. Some examples of metaheuristics are genetic algorithms, local search, or simu- lating annealing. Metaheuristics consider two main working principles, intensification and diversi- fication. Intensification refers to the method’s ability to deeply explore a promising region of the search space, while diversification refers to explore different regions of the search space. By design, some metaheuristics methods are better at intensifying the search while others are so at diversifying it. Nonetheless, a set of parameters controls the behavior of most metaheuristics. A fine tuning of these parameters is therefore crucial to achieve an effective trade-off between intensification and diver- sification, and hence good performance in solving a given problem. Unfortunately, selecting the best-performing set of parameters is usually a hard task. This process is even more difficult because the best parameters values are different for different problems and even for different instances of the same problem, as demonstrated by the Non-Free-Lunch theorem [Wolpert and Macready, 1997]. Each metaheuristic has its own strengths and weaknesses, which may vary accord- ing to the problem or even to the instance being solved. The trend is thus to design hybrid metaheuristics, which combine diverse methods in order to benefit from the individual advantages of each one [Blum et al., 2011]. This increases the number of parameters (parameters of individual metaheuristics and new parameters to control the hybridization). The design and implementation of a hybrid metaheuristic is a complex process; setting the resulting parameters to reach the best performance is also very challenging. Despite the good results obtained with the use of hybrid metaheuristics, it is still necessary to reduce the processing times needed for the hardest instances [Saifullah Hussin, 2016]. One of the most plausible options entails parallelism [Crainic and Toulouse, 2010]. In parallel metaheuristics, one can have multiple instances of the same (or different) metaheuristics running in parallel, either independently or cooperatively, through concurrent process communications [Caniou et al., 2014]. Parallelism not only helps to decrease processing time but also is a mean to easily implement hybridization. The creation of parallel hybrid methods requires the fine tuning of a larger number of parameters, since more metaheuristics (of different types) are involved. Moreover, the configuration of the parallel interaction itself (communication between the meth- ods) involves yet another set of parameters which need to be adjusted. Tuning this increasing number of parameters makes it even more difficult to find the appropriate setting for the algorithm to behave optimally. Automating the task of finding good parameters is thus desirable and has attracted significant attention from researchers. 11 1.2 Setting Metaheuristic Parameters It is possible to identify three specific strategies focused on solving the task problem of setting the metaheuristic parameters: parameter tuning, parameter control [Huang et al., 2020] and instance-specific parameter tuning [Calvet et al., 2016]. In parameter tuning (off-line tuning) the set of parameters are defined before applying the algorithm to a specific problem instance(s) (static definition of parameters). Several strategies for parameter tuning of metaheuristics have been proposed [Birattari and Kacprzyk, 2009, Hutter et al., 2009, 2011]. In contrast, parameter control strategies (online- tuning) adapt the values of the controlled parameters during the algorithm execution (dynamic/reactive adaptation of parameters). The idea is to find the best parameters setting during the solving process, using some mechanism to alter the parameter val- ues according to the observed algorithm performance. The instance-specific strategy considers a combination of the two previous methods (parameter tuning and param- eter control) with the aim of having for each specific instance of a problem, one set of static parameters values, few papers can be found with this approach [Ries and Beullens, 2015, Calvet et al., 2016, Dobslaw, 2010a]. Parameter tuning can be seen as a pre-process pass which is executed before the solving procedure in order to determine the adequate values for parameters. This does not affect the implementation of the solver. Unlike parameter control strategies, which has to be implemented in the kernel of the solver, as part of it. Parameter tuning strategies may appear easier, but when the number of parameters becomes large, it is hard to use in practice, e.g., within a parallel hybrid method. Indeed, it usually requires many runs to identify the best parameter settings, making this a time- consuming process. These methods are often limited by the number of parameters and the computational power available. In that case, parameter control strategies emerge as a viable solution to deal with the high complexity of current solvers (hybrid and/or parallel). Regarding the instance-specific parameter tuning strategies, these avoid the need to modify the metaheuristic method and try to minimize all the computational effort that parameter control strategies require adapting parameters. Additionally, these define parameters values for each specific instance since looking for one fixed set of parameter values for an entire set of instances with different characteristics is likely not performing well as parameter tuning does [Ries et al., 2012]. There is another way to setting the parameters (a fourth way), with a more general purpose, Hyper-heuristics. These methods are part of a novel research approach in which a high level strategy selects or generates the best metaheuristics with their respective parameters and solutions acceptance criteria. This approach is used with the aim of having more general methods, not designed for a single problem or for a few instances of a problem [Burke et al., 2019]. As shown in the analysis of the state-of-the-art, despite the strategies available to solve the problem of setting the parameters of a metaheuristic, there is a need for parameter control strategies for single-solution metaheuristics, more evident in 12 parallel hybrid methods. The main contribution of this thesis is to propose a general framework to configure the parameter control strategy for single-solution metaheuristics in a parallel hybrid solver, for solving combinatorial optimization problems. 1.3 Thesis Goals and Contributions In this research, we study the methods that have been proposed for the resolution of the parameter setting problem. By performing this study, we have noticed the gap that exists for parameter control strategies (PCS) methods in single-solution meta- heuristics. This gap is even more notable for parallel hybrid metaheuristic methods. The contributions of our research are the following: • We propose PACAS: a general framework to configure the PArameter Control Adaptation for Single solution metaheuristics in a parallel hybrid solver, for solv- ing combinatorial optimization problems (COP). PACAS aimed at increasing the performance of parallel method based on several parameter control strate- gies through the analysis of the behavior of single-solution metaheuristics. The framework allows to customize the parameter adaptation strategy in order to have a trade-off between intensification and diversification in the search process. The hybrid behavior is granted by the use of different types of metaheuristics and by cooperation mechanism through an intra-team communication. • In order to validate our approach, we present J-PACAS: an implementation of PACAS in the Java programming language. Our implementation provides three different metaheuristics and three kinds of teams to perform different parameter adaptation strategy. We provide the code to support one of the most difficult COPs, the Quadratic Assignment Problem (QAP). J-PACAS implementation is available in open source code through a git repository. It is implemented in Java 11 using the ForkJoinPool and AtomicType classes to handle the parallelism in a shared memory model. J-PACAS can be executed on a multicore parallel platform. • We tackle one of the most difficult problems in combinatorial optimization, the Quadratic Assignment Problem. We consider the set of very hard QAP problems, the QAPLIB benchmark. We make a contribution exploring different parame- ter adaptation strategies, with different parallel configurations (independent or cooperative). Finally, we make a comparison with the most similar work in the state-of-the-art. Partial results of this experimentation were published in the International Conference on Optimization and Learning [Duque et al., 2021] Finally, this document is organized as follows: 13 Chapter 2 explains the concepts, definitions and main related principles of meta- heuristics and their parameter settings to understand this thesis. Chapter 3 is dedicated to analyze the state of the art related to the strategies to solve the parameter setting problem for metaheuristic methods. This chapter contains an analysis of the most relevant characteristics of the strategies, advantages and dis- advantages. According to this analysis, we further present our taxonomy that covers all the strategies reviewed. Chapter 4 introduces the PACAS framework that we propose, detailing the design aspects for each part. Chapter 5 presents an implementation of the PACAS framework made on the Java programming language, J-PACAS. We provide guidelines to extend the framework functionality and to configure all its parameters. Chapter 6 describes the experimental evaluation to validate the functionalities of our proposed framework. We compare the performance of seven J-PACAS configu- rations on the most difficult instances of QAPLIB. We also make an analysis of the winner metaheuristic and its configuration. Finally, a comparison with the most sim- ilar work in the state-of-the-art is done. Chapter 7 concludes this thesis and presents some perspectives about future re- search directions. 14 Chapter 2 Background This chapter includes a formal definition of the Quadratic Assignment Problem (QAP), analysing its complexity. Then, it presents a brief description of metaheuristic methods used to solved QAP, as well as a presentation of the research trends related to this topic. Finally, we present a formulation of the parameter setting problem and the approaches to solve this problem. 2.1 Quadratic Assignment Problem The Quadratic Assignment Problem (QAP) was first proposed by Koopmans and Beckmann in 1957 [Koopmans and Beckmann, 1957] as a model for a facilities location problem. This problem consists in assigning a set of n facilities to a set of n locations, while minimizing the cost associated with the flows of items among facilities and the distance between them. Let F be the flow matrix, where fij is the flow between facilities i and j, let D be the distance matrix, where dkl, is the distance between the locations k and l. The goal is to find an optimum assignment of facilities to locations at minimum total cost, which is defined as the sum of all products between flows and distances [Kaufman and Broeckx, 1978]. Equation 2.1 presents a formulation of QAP, where φ(i) is the location which facility i is assigned to and dφ(i)φ(j) is the distance between locations φ(i) and φ(j). min n∑ i=1 n∑ j=1 fij ∗ dφ(i)φ(j) (2.1) QAP has a computational complexity that classifies it as an NP-hard problem [Sahni and Gonzalez, 1976]. Technology has advanced in a way that the processors speed has increased, however QAP remains computationally difficult to accurately solve it when the number of facilities and locations is greater than 35. It is at this point that methods with metaheuristic approaches produce high quality solutions in reasonable times [Dokeroglu and Cosar, 2016]. 15 2.2 Metaheuristics Metaheuristic methods are a type of approximate methods used to solve difficult opti- mization problems, most of them are inspired by nature (based on some principles of physics, biology or ethology); theses methods use stochastic components (use random- ness in their behavior) and have several parameters that must be adjusted depending on the problem in question [Boussäıd et al., 2013]. Metaheuristics operate on two main working principles: intensification and diver- sification, also call exploitation and exploration respectively. On the one hand the former refers to the method’s ability to explore more deeply a promising region of the search space and does not explore the whole set of solutions, providing at the end of the search the best solution of that region, called optimum, which is not necessary the global optimum of the whole search space; the optimum of this region is called local optimum. On the other hand, diversification refers to the exploration of different regions of the search space. Diversification helps to escape from local optima, guiding the search to other promising regions of the solution space and avoiding stagnation. The hybridization of metaheuristics helps to have a balance between intensification and diversification, by combining the characteristics of different methods. We can classify metaheuristics as single-solution metaheuristics and population metaheuristics. The main difference between these two categories depends on the number of solutions used during the execution of the algorithm. A single-solution metaheuristic starts with an initial solution and at each step of the search the cur- rent solution is replaced by another (often the best) solution found in its neighbor- hood [Alba et al., 2013]. The neighborhood is a set of solutions obtained by making small disturbances or changes to one solution [Yagiura and Ibaraki, 2002]. The single- solution metaheuristics allow to quickly find an optimum solution locally, so these are good at intensifying the search space. Population-based metaheuristics make use of a population of solutions. In this case, the initial population is generated randomly (or created with a greedy algorithm), and then improved through an iterative process. At each generation of the process, all (or part) of the population is replaced by newly generated individuals (often the best ones). These methods are commonly used for exploration, since they work with many solutions, producing a larger search at the solution space, and trying to make the search more diverse [Alba et al., 2013]. Some of the best known metaheuristics are described below: • Local Search (LS): LS is one of the oldest and most frequently used metaheuris- tics. LS starts from an initial solution and repeatedly replaces it with better solutions within its neighborhood, this method finishes when there are no better solutions in the neighborhood of the current solution, ending the search in a local optimum [Yagiura and Ibaraki, 2002]. • Simulated Annealing (SA): In 1983, Kirkpatrick et al. introduced the concept of Simulated Annealing. This algorithm is based on the method of cooling a 16 material, a technique called annealing. In this process, if the material is cooled down too fast, the atoms have no chance to produce a powerful structure and settle randomly, resulting in a brittle metal; but if the temperature decreases slowly, the atoms have more time to build strong crystals increasing the quality of the product [Dokeroglu and Cosar, 2016]. The SA algorithm begins with an initial solution, then this solution is transformed into another by introducing small disturbances or changes. The algorithm replaces the current solution when the resulting solution is better than the current one, ending the search when there are no improvements (local optimum). SA uses a probability function to accept worse solutions, this function simulates the way the temperature decreases in the cooling of the material. This function will allow, with a high probability, worse solutions and, as the execution of the algorithm advances, this probability decreases allowing only improving solutions [Dowsland and Diaz, 2003]. • Tabu Search (TS): The Tabu Search method refers to the use of adaptive mem- ories and special problem-solving strategies, called intelligent strategies, which differentiate TS from a LS. The idea is to memorize within a structure the ele- ments that for the LS will be forbidden to use and thus avoid staying in local optima. TS searches within the neighborhood for the best solution but does not visit the solutions of previous neighbors if they have been visited before or have been marked as prohibited solutions or “tabu” solutions [Dokeroglu and Cosar, 2016]. • Genetic Algorithm (GA): GA is a population algorithm, it has a direct analogy with nature, in this case biological evolution. GA works on a population of individuals, where each one represents a solution. Each individual is assigned a fitness, according to how good is the solution for the problem, i.e, the fitness is the value for the objective function [Beasley et al., 1993]. This population evolves by applying crossing and mutation operators to some individuals. The best set of new individuals replaces the initial population (elitist policy). The algorithm finishes when a given number of iterations have been performed or when the population converges. • Ant Colony Optimization (ACO): ACO is inspired by the behavior of ants to find the shortest path from their nest to a food source. Ants mark their way to the food source by placing pheromones, at the end, the path with the most pheromones persists. The idea of the ACO as an algorithm is to start from an initial population of solutions (representing ants) and, through an iterative process, the ants that find good solutions guide the following ants by using a memory, this memory will be the pheromone information saved by the ants when they find good solutions [Merkle and Middendorf, 2001]. In addition to the metaheuristics that are presented, there are others like, Pi- lot Method [Voss et al., 2005], Variable Neighbourhood Search [Hansen et al., 2003], 17 Table 2.1: Metaheuristic parameter and its influence (note that MH stands for Meta- heuristic type). MH Parameter name Parameter Influence type TS Tabu duration factor integer Small value promotes intensification. Large value promotes diversification. Aspiration factor integer It is used as a solution cost exception to take good solutions. SA Temperature function function It controls the acceptance criteria for new solutions. It avoids the stagnation of the search, making it more diverse. GA Population size integer A small value promotes intensification. A large value promotes diversification. Crossover operator operator It helps to diversify the search, guiding the exploration toward different neighborhoods. Mutation probability decimal Small value promotes intensification. Large value promotes diversification. Greedy Randomized Adaptive Search Procedures (GRASP) [Resende and Gonzáles Velarde, 2003], Scatter Search [Mart́ı and Laguna, 2003], Particle Swarm Optimiza- tion (PSO) [Merkle and Middendorf, 2001], among others. Each metaheuristic type has some intrinsic parameters that guide the search to be- have in one way or another. While there are methods that are better for intensification or diversification, adjusting those parameters offer a trade-off between exploitation or exploration search. Table 2.1 shows some metaheuristic methods with their parame- ters and its influence over the search. In addition to these intrinsic parameters, there are parameters common to most methods. For example, the stopping criterion and the type of neighborhood to explore. It is important to note that even for some parameters it is necessary to define other “internal” parameters. There is no theory to determine the most adequate metaheuristics for a problem or the optima values for its parameters, so usually different strategies have been proposed, such as consulting an expert opinion, extracting values from state-of-the-art works, developing a design of experiments or even invoking to the developer’s intuition. This is an import topic to take into account, given that the quality of the solutions will depend on the choice of the metaheuristics and on the values of its parameters [Turky et al., 2018]. The configuration of the metaheuristic parameters is a fundamental part of the algorithm design. This configuration can also include changing the order in which the components of a metaheuristic are executed, where a component is a specific and unique part that defines the algorithm and each one may have one or more parameters that determine its functionality. Examples of components are a local search operator in a Variable Neighbourhood Search, a tabu list in a TS, a crossover operator or a mutation operator in an GA. The configuration of these components is called the control flow [Sevaux et al., 2015]. 18 Determining the control flow of the algorithm is a task for the algorithm de- signer. There is no a guide for the best order or to choose the best components for a method [Sevaux et al., 2015]. In general, methods usually have a default or- der and available components. The practitioners work with this default mode, since configure it, is long and fastidious task, usually done with trials and errors methods. One question arose, is there an optimum configuration for achieving the best perfor- mance?. While this question is of interest to the target community, it is broader than our research question and is beyond our scope. 2.3 Hybrid Metaheuristics Having a equilibrium between intensification and diversification is a hard task [Beasley et al., 1993], with this aim hybridization have been used. The propose is adding up metaheuristic strengths and balancing their weaknesses. In recent years, the research on hybrid metaheuristics has notably increased [Bhati and Rasool, 2014], positioning hybrid methods as one of the best performing solvers for tackling many hard problems. Particularly for QAP, hybrid methods provide outstanding performances for difficult QAP instances. The basic idea about hybridization of metaheuristics is the design and implemen- tation of algorithms that, through the combination of different metaheuristics retains the best features that each one has to offer. Although the way as metaheuristics are hybridized varies according to the type of problem or the type of method, several research works have been proposed to define criteria that allows the development of a hybrid metaheuristic, for example [Blum et al., 2008]. 2.4 Parallel Metaheuristics The parallelization of metaheuristics is another strategy that has been used simultane- ously with hybridization. At the early days, the parallelization has been done with the traditional idea of accelerating the execution time of the operations of the algorithm, focusing on operations that are more expensive in processing time. Later, it has been used to distribute tasks or sets of tasks on the available processors, tasks that result from the decomposition of the total computational load of the algorithm. Four major strategies can be identified in the parallelization of metaheuristics. The first strategy is the decomposition of the low level computer tasks without modifying the original algorithm but accelerating its execution, for example by parallelizing the execution of the neighborhood assessment in a single-solution metaheuristics or the population assessment in a population-based metaheuristics. The second strategy is the decomposition of the search space into smaller portions and the assignment of one or more processors for exploration using one or more metaheuristics. To make the search space decomposition, special techniques are used for its partitioning and 19 special techniques to assemble solutions from the solutions found in the exploration of each partition. The third strategy is the independent multiple search which consists of executing several self-contained searches, each with a different initial solution and with no exchange of information between them. The searches have a starting point that is usually random and to the final solution no partitioning and composition technique is applied. Finally, the cooperative multiple search is similar to the independent one with the difference that the metaheuristics that are executed simultaneously resort to the exchange of information during their execution [Codognet et al., 2018]. Coopera- tive parallelization not only improves the processing times but also open a bunch of possibilities to create new hybrid algorithms. Parallel hybrid metaheuristics often have many parameters which modify the algo- rithm behaviour. Setting these parameters has a heavy influence on the performance of the method, however, finding the optima values for these parameters is usually a hard task [Hutter et al., 2009]. Using hybridization and parallelism makes this task even more difficult for mainly two reasons: First, hybrid metaheuristics inherit the parameters of each “low level” metaheuristic, so one needs to find the setting of more parameters, since a parameter configuration for one algorithm usually is not suitable for another. Second, cooperative parallel strategies also require parameters to define their behaviour, e.g., for determining how frequently metaheuristics should interact or how each metaheuristic has to use the received information. 2.5 Setting Metaheuristic Parameters The metaheuristic parameters can be of different kinds, as show in table 2.1. There are integers, decimals, functions, operators, and others. These can be classify in two groups, numerical and categorical (or non-numerical) parameters [Huang et al., 2020]: • Numerical: Corresponds to all those parameters that are real or integer numbers, and they are typically in a range of values. • Categorical: Refers to the remaining parameters that control the behavior of a metaheuristic, these are functions, mathematical expressions, operators, or mechanisms. One example is the crossover operator in the GA algorithm. The Parameter Setting Problem (PSP) is the task of finding the parameter values for a metaheuristic that results in the best possible performance across the given problem instance(s). This problem can be briefly described as: given an algorithm method (to be parametrized), one instance or a set of problem instances, and a free set of parameters to choose, the purpose of parameter configuration is to resolve the problem of finding such values that optimizes the objective function of the algorithm over the given problem instance(s). 20 Let M the metaheuristic algorithm to parameterize, P the parameter space values, a set of problem instances I and a performance metrics mp that measures the perfor- mance of M across I for a given configuration p (p ∈ P ). The problem is therefore to find a configuration p∗ ∈ P that optimizes the performance of M on I according to the metrics established mp [Huang et al., 2020]. The PSP is hence itself a combinatorial optimization problem (COP) and, in general, NP-hard [Kern, 2006] and it is often called meta-optimization [Pedersen, 2010]. Three dedicated strategies to solve the PSP can be found, these form a range of strategies categorized into Parameter Tuning Strategies (PTS), Parameter Control Strategies (PCS) [Huang et al., 2020] and Instance-specific Parameter Tuning Strate- gies (IPTS) [Calvet et al., 2016]. There are others strategies not dedicated to solving the PSP, however, as part of its purpose solves it, these are HyperHeuristics methods (HH) [Burke et al., 2019]. In the next subsections we define each category. 2.5.1 Parameter Tuning Strategies (PTS) Eiben et al. define Parameter Tuning Strategies as “The commonly practiced approach that amounts to finding good values for the parameters before the run of the algorithm and then running the algorithm using these values, which remain fixed during the run” [Eiben et al., 1999]. The aim is to find a priori the best set of values for the parameters. With a preliminary analysis, standard values for the parameters can be recommended for future executions. However, such recommendations should not be generalised to all classes of problems. 2.5.2 Parameter Control Strategies (PCS) Parameter Control Strategies (also known as online setting) is an approach that elimi- nates the parameter values analysis step carry out in PTS, therefore the setting occurs during the optimization process (algorithm running) [Parpinelli et al., 2019]. In this methodology is required adequate control strategies for the controlled parameters, these strategies change or adapt relevant parameter values during the run [Huang et al., 2020]. The control strategies usually make use of information gathered during the execution of the algorithm as a feedback, based on this feedback, the parameter are adapted dynamically [Calvet et al., 2016]. 2.5.3 Instance-specific Parameter Tuning Strategies (IPTS) Instance-specific Parameter Tuning Strategies (IPTS) the parameters remain fixed during the run, similar to PTS. Therefore, there is a design phase that precedes the algorithm execution to find the parameter values. In the design phase, a representative set of instances is first investigated. This instance set is used to design an efficient tuning method (or model) that can return instance-specific parameter values for each specific problem instance, rather than aiming to obtain one set of parameter values for 21 all instances. The tuning method is done based on measurable instance characteristics. Further, in the execution phase, an instance is examined by the tuning method in order to return a set of instance-specific parameter values [Ries et al., 2012]. The IPTS approach is a new research area, hence the published works are few and sometimes the differences with PTS are diffused. The differences are not yet clear because in both strategies the parameters remain fixed. One can find in the literature papers categorized as PTS, but those match perfectly under the definition of IPTS, for example [Pavón et al., 2009]. 2.5.4 HyperHeuristics (HH) HyperHeuristics (HH) present another way to face the problem of metaheuristic param- eter setting and they have some similarity to PCS. This is a novel research approach, it appears in 2001, with the purpose of selecting or generating the best metaheuristics with their respective parameter settings and acceptance criteria to face a problem. HH are methods to manage the control flow of an algorithm by applying some strategies to select or generate the best component order, with the aim of having the best pa- rameter settings and configuration for a the method. This approach is used with the idea of having more general methods, not only designed for a single type of problem or for a few instances of a problem. HH usually makes use of learning strategies outside or inside the execution of the algorithm [Burke et al., 2019]. A hyperheuristic is also known as a heuristic to select/generate metaheuristics, heuristic known as a high-level heuristic. The set of available metaheuristics or meta- heuristic components are known as a low-level heuristics. A high-level heuristic works on the set of metaheuristics or metaheuristic components rather than on the search space of solutions of the given problem, it is independent of the type of problem. A HH aims to automate the design and adaptation of metaheuristic methods to address computational search problems, in our case COPs. The motivation is raising the level of generality in which search methodologies can work [Burke et al., 2019]. These methods are learning algorithms, which use feedback during the search pro- cess. According to the way of feedback during this learning, one can distinguish between online and offline learning. In online learning hyperheuristics, learning takes place while the algorithm is solving an instance of a problem (similar to PCS). While in offline learning hyperheuristics, the idea is to gather knowledge in the form of rules or programs, from a set of training problems, which will help to solve instances of unknown problems [Burke et al., 2013]. 22 Chapter 3 State of the Art The problem of setting the best set of parameters is called the Parameter Setting Problem (PSP). The PSP is gaining a lot of interest among researchers and prac- titioners, since setting parameters by hand or by experience is not the best option. Classical methods like using design of experiments to identify a good set of parameters is computational expensive and time consuming for the designer. This is one reason why parameter setting studies have not been extensively developed [Dobslaw, 2010b], but since the mid-1990s it is an issue that is taking great importance [Calvet et al., 2016] and the scientific community started to treat it formally, as shown by Ferro’s work [Ferro et al., 1996b]. From the literature, it is possible to identify four main ways for solving the PSP, these are: Parameter Tuning Strategies (PTS), Parameter Control Strategies (PCS), Instance-specific Parameter Tuning Strategies (IPTS) and HyperHeuristic (HH). These methodologies form a group of strategies, which perform different functionality, from the “limited” ability to change only the parameters, to the “complete” ability to change the whole algorithm. The literature about parameter settings for metaheuristics is diverse, there is no re- view that covers completely the four ways to solve the PSP. The most studied strategy is PTS, and several taxonomies can be found for this approach [Huang et al., 2020, Dobslaw, 2010b]. For PCS, one can also find classifications made only for population algorithms, most of them for evolutionary algorithms [Parpinelli et al., 2019, Zhang et al., 2012, Eiben et al., 2007]. In addition, some publications consider the PSP in a summarized but not detailed or exhaustive way [Sevaux et al., 2015, Stützle and López-Ibáñez, 2019]. For the HH strategy the situation is different. Burke et al. [2019] present a recent classification and taxonomy. It is important to remember that these kinds of works consider the total manipulation of the method (either generation or selection) not only the setting of the parameters. The intention of our review is to bring out the most relevant methodologies that exist for setting the parameters of metaheuristics when solving hard optimization prob- lems and show how researchers have classified them. We present a detailed description of each strategy, pointing out main characteristics, advantages and disadvantages and 23 some of the most relevant papers that have been published. Finally, a complete tax- onomy is presented and discussed. In order to achieve the proposed taxonomy, we consider the aforementioned reviews and many others who make interesting contribu- tions to this field. 3.1 Parameter Tuning Strategies (PTS) As mentioned above, PTS can be defined as the procedure to find good values for the parameters before the execution of the metaheuristic algorithm. PTS methods allow the user to find a good set of parameters for running the algorithm with these values, which will remain fixed throughout the execution. This strategy can be seen as a pre- process phase or as an off-line parameter setting. Dobslaw called this step algorithm configuration [Dobslaw, 2010b], because is the configuration before trying to solve the problem. Meanwhile, A. Fialho, in his Ph.D. thesis, called these strategies as External Parameter Tuning since it is a process done outside the algorithm core [Fialho, 2010]. From the beginnings of metaheuristics, parameter setting was done by hand. When more metaheuristics methods were created showing better results, one common strat- egy was to use parameters’ values reported in the literature as a starting point for finding a good set of parameters in new algorithms. This is indeed one of the most common strategies that has been used by most researchers [Sevaux et al., 2015]. However, there is a problem. On the one hand, the idea of taking parameters from similar works is not suitable in all cases. This is a blind process which not considers the particularities of new algorithms or instances. On the other hand, the task of testing many parameters values via trials and errors methods for finding the best ones can be very time-consuming and tedious. That is why more elaborate tools were created. These tools aimed at finding the best initial parameters of a solver, in order to yield (near-)optimum algorithm performance. One of the pioneering strategies was the use of the classic Design of Experiments (DoE), then followed by a large number of PTS methods, such as EGO, F-Race, REVAC, ParamILS, SPO, SMAC, SKO, among others. We describe below the most known methods. As we found in the analysis of the state-of-the-art for PTS methods, parameter tuning methods are a large part of the works that has been proposed to solve the PSP. Some methods have its origin in the Design of Experiments (DoE). DoE methods have been refined and extended for proposing new ones since the 90s, e.g, EGO, SPO, SKO, among others. Metaheuristic methods are also used to find the right parameters, an example is GGA, Calibra and HORA. Also, racing techniques are a common strategy, which aim to discard the irrelevant parameters during the procedure and keep the ones who are the better, for instance, F-Race, Iterative F-Race, HORA and SMAC. In the following, we present a definition of each identified technique for solving the PSP in PTS methods: • Brute-Force: The most intuitive and easiest method for solving the tuning prob- lem is the brute-force. This method consists in allocating an equal share of 24 computational power to each candidate configuration and to perform the same number of experiments on each part. The configuration with the best estimated performance is considered the optimum parameter setting. To reach good pa- rameter values, high amount of executions are necessary and a large number of parameters must be tested, being this the main weakness of the brute-force method. • DoE: Design of Experiments is a technique for conducting experiments with the objective of identifying the causes of the behavior of a problem and get conclu- sions. These conclusions are drawn on the basis of statistical methods [Fisher, 1936]. Usually, the full factorial design is the most applied for PTS. In this approach, the researcher takes a small number of the problems from the entire problem set (representative instances). Then an experiment is carried out with several values of the parameters, parameters act as factors with various levels, taking into account lower and upper bounds and values in the middle. This process allows the user to select good parameter settings for each problem. An example of DoE using a full factorial design for setting parameters is presented in [Coy et al., 2001]. Other kinds of DoE techniques had been applied, like block design, and response surface optimization. • Revac: Relevance Estimation and Value Calibration of Parameters (REVAC) method was proposed in 2006. This method is used to calibrate the values of parameters of any evolutionary algorithm. The method works on distributions over parameter values and uses the Shannon entropy to estimate the relevance of a parameter [Nannen and Eiben, 2006]. REVAC is an iterative algorithm that consists of estimating the distributions of promising parameter values for each parameter within the configuration space, and then generating parameter con- figurations by drawing values from these distributions [Huang et al., 2020]. One important weakness of REVAC is that this method cannot handle categorical parameters. • ParamILS: This method is one of the best-known methods for algorithm con- figuration. ParamILS is an automatic tuning method proposed by Hutter et al. [Hutter et al., 2009] in 2009. The authors present two versions: BasicILS and FocussedILS. Both versions use iterated local search (ILS) techniques in order to guide the search towards promising areas in the search space of the parameters. BasicILS is the simplest approach that evaluates every parameter configuration by running it on the same training problem instances using the same random number of seeds. FocussedILS is a variant of BasicILS that adaptively makes a variation in the number of training samples considered from one parameter con- figuration to another. ParamILS can use the so-called adaptive capping mecha- nism and is able to tune both numerical and categorical parameter. The software 25 of ParamILS is implemented in the Ruby programming language 1. • EGO: Efficient Global Optimization (EGO) is an algorithm for the creation of a response surface model for black box functions. It combines the predictive model (Kriging or Gaussian process model), i.e., design and analysis of computer experiments (DACE) [Sacks et al., 1989], for diversification and a branch and bound-based phase for intensification. The EGO algorithm fits a DACE model with a set of initial points specified for the experimental design. The hard- ware requirements for this method are low. EGO is restricted to non-stochastic algorithms [Jones et al., 1998]. The SPO and SKO methods extended EGO. • SPO: The Sequential Parameter Optimization (SPO) method is an extension of EGO. This method was presented by Thomas BartzBeielstein, Christian Lasar- czyk, and Mike Preuss in 2005 [Bartz-Beielstein et al., 2005]. The main purpose is to determine improved parameter settings for optimization algorithms to an- alyze and understand their performance. This makes use of Kriging models to perform the optimization, creating a response surface model. With this model, new set of design points (parameter settings) are generated and tested. The most promising points, which have the highest expected improvement, are chosen as new candidate configurations through an iterative process. The corresponding software package will be referred to as SPOT, an acronym which stands for se- quential parameter optimization toolbox. SPOT package for R can be downloaded and used for free. Unfortunately, SPO only supports numerical parameters and only optimizes an algorithm for a single instance 2. • SKO: Another extension of EGO, Sequential Kriging Optimization (SKO) was proposed by Huang et al. [Huang et al., 2006]. The method is based on a kriging metamodel that provides a global prediction of the objective values and a mea- sure of prediction uncertainty at every point. SKO is formulated to extend the EGO scheme to stochastic systems. SKO restricts the user to optimize continu- ous parameters. It is a sequential approach; the model is becoming updated at each iteration until a certain quality or time-bound is reached [Dobslaw, 2010b]. • F-Race: It is a racing algorithm that uses the Friedman test (two-way analysis of variance by ranks), a non-parametric statistical test [Birattari et al., 2002]. In this method, all the configurations take part in a race, some are discarded based on the statistical study and those who pass the test continue the race. In each evaluation round of the candidate configurations, the non-parametric Friedman test is used as a family-wise test to check whether there is evidence that at least one of the candidate configurations is significantly different from others in terms of performance measures. The original version has the drawback 1ParamILS software available at http://www.cs.ubc.ca/labs/beta/Projects/ParamILS/ index.html 2SPOT package available at https://cran.r-project.org/web/packages/SPOT/index.html 26 http://www.cs.ubc.ca/labs/beta/Projects/ParamILS/index.html http://www.cs.ubc.ca/labs/beta/Projects/ParamILS/index.html https://cran.r-project.org/web/packages/SPOT/index.html that only works for a handfull of parameters. The reason is that experimental design is expensive. There is a free available extension in R language called race. • Iterated F-Race: To alleviate the problem of F-Race for the tuning problem when there are a large number of parameters and/or each parameter has a wide range of possible values, Prasanna Balaprakash, Mauro Birattari and Thomas Stützle [Balaprakash et al., 2007] proposed the iterative application of F-Race. Iterated F-Race is an iterative procedure in which each iteration consists in the definition of a probability measure over the parameter space that is available at the moment, using promising configurations obtained from the previous it- erations. Then, the method generates configurations according to the newly defined probability measure and finally applies a standard F-Race on the gener- ated configurations. For the probability measure, it is used a d-variate normal distribution parameterized by mean vector (using surviving configuration from the previous iteration) and covariance matrix. This measure plays a crucial role in biasing the search towards regions containing high-quality configurations. It- erated F-Race has become one of the most competitive PTS [Huang et al., 2020]. It can deal with both numerical and categorical parameters. An R package is available called irace 3. • Calibra: This method employs statistical analysis techniques (for exploration) and a local search (for exploitation). Calibra is a procedure to create a systematic way to find good parameter settings within a specified range of values [Adenso- Diaz and Laguna, 2006]. The idea of the statistical analysis is to provide a way to focus the local search on promising regions of the search space, helping to initialize the search at a non-arbitrary point. Calibra can only handle up to five parameters. The authors recommend to use the Taguchi’s L16 (215) array to determine the five most significant parameters and fix the others to appropriate values, in the case that the algorithm being fine-tuned has more than five pa- rameters. Using the Taguchi’s array, Calibra can handle up to 15 parameters. Calibra works with integer arithmetic; however, parameters with continuous val- ues must be discretized by specifying a level of accuracy (three decimal places). • GGA: Gender based Genetic Algorithm (GGA) is a parallel genetic algorithm (GA) that uses genders for its individuals. The individuals are candidate con- figuration parameter [Ansótegui et al., 2009]. The authors say: mate choice is more likely to have a high impact on result quality than, for instance, nat- ural selection. The GGA uses the concept of competitive and non-competitive genders, dividing all the individuals into two sub-populations with different gen- ders (competitive and non-competitive). Different selection pressure on the two genders are applied. The algorithm allows the user to define the “design of the 3Iterated F-Race package available at https://cran.r-project.org/web/packages/irace/ index.html 27 https://cran.r-project.org/web/packages/irace/index.html https://cran.r-project.org/web/packages/irace/index.html genome”, i.e. relationship between parameters, through a tree. GGA can man- age numerical and categorical parameters. The implementation makes use of parallel computations by taking advantage that a GA is easily parallelizable. • HORA: It is a process proposed by Barbosa and Senne [2017], it is called Heuris- tic Oriented Racing Algorithm (HORA). The name comes from the use of a heuristic method and racing techniques. The idea of the authors is to consider the parameter configurations as a search space and to explore it for finding pa- rameter values near to the promising (or the best) candidate configurations. The process starts with a number of instances selected arbitrarily from the given set of problem instances. The selected instances are treated as a training set. Exper- imental studies are carried out with the Response Surface Methodology (RSM) to define the best (promising) parameters settings for each instance. HORA ex- ecutes a loop procedure, where dynamically creates new candidates parameters in the neighborhood of the promising candidate parameters and evaluates these with a racing method to discard poor ones (following statistical evidences us- ing the Friedman statistic test). Through this procedure, HORA reaches better parameter settings iteration by iteration. • SMAC: In [Hutter et al., 2011], the authors proposed two methods, Random Online Aggressive Racing (ROAR) and Sequential Model-Based Algorithm Con- figuration (SMAC). SMAC can be understood as an extension of ROAR. SMAC selects configurations based on a model rather than uniformly at random. SMAC also is an implementation of Sequential Model-Based Optimization (SMBO). The aim of SMAC is to remove some limitations that several SMBO methods (e.g., SPO) have. Limitations like only managing numerical parameters and tackling only one instance of a problem. To remove these limitations, the authors pro- posed: (1) a new intensification mechanism that employs blocked comparisons between configurations; (2) random forests as alternative class of response sur- face models, to handle categorical parameters and multiple instances; and (3) a new optimization procedure to select the most promising parameter configura- tion in a large mixed categorical/numerical space 4. There is a variety of methods (or procedures or tools) to solve the PTP offline, all these with its specific features. Classifying them is a task that has already been done by other researchers. Dobslaw [2010b] distinguishes between two types of automated parameter tuning methods: model-free and model-based. The main difference between both two is that model-based approaches build a model. This model is created from the observations done by running the target algorithm with several parameter settings and interpreting the relation between the algorithm and its parameters. Model-free approaches do not create any model, it obtains implicit conclusions based on heuristic 4SMAC software available at http://www.cs.ubc.ca/labs/beta/Projects/SMAC/ 28 http://www.cs.ubc.ca/labs/beta/Projects/SMAC/ rules; thus, the selection of interesting parameters is usually guided by randomness or by a simple experimental design [Dobslaw, 2010b]. Meanwhile, Huang et al. [2020] classify the methods into three categories: simple generate-evaluate methods, iterative generate-evaluate methods, and high-level generate- evaluate methods. The first are simple approaches, which consist of a generation phase and an evaluation phase. These are non-iterative methods that directly adopt this prin- ciple by firstly creating a number of parameter settings (candidate configurations), and then evaluating each of them for finding the best configuration. The iterative generate- evaluate methods involve a repeated process of generation and evaluation steps. These methods begin with a small set of initial configurations and create new configurations iteratively during execution. In this iterative execution, methods collect important information to make a smarter process and to choose better configurations. The last category, high-level generate-evaluate methods, has the main feature of quickly generate a set of elite or high-quality parameter configurations with a small need of computational resources; these methods carefully select the best configuration from this set instead of evaluating each candidate configuration thoroughly from the very beginning. In this category, the problem is to keep the diversity of elite candidates. Table 3.1 summarizes the methods reviewed, proposed as PTS. The table shows the category if a method is model-based and its classification according to the generate- evaluate approach. Other important features are included in order to provide more information. For example, the table shows if the method uses some statistical test or some heuristic to guide the search. We also show if the method is implemented in parallel. The publication year and the programming language of the package (if there is one) are included too. The number of papers using each method is a difficult task to perform, so it is included the number of citations that have been made in google scholar until October 30, 2021. Table 3.1: Summary of methods’ features for PTS Method Model Kind Statistical Uses Uses Parameter Year Language Google scholar based generate-evaluate heuristics parallelism Types citations DoE iterative all 19XX R, python 9338 Revac iterative numerical 2006 121 ParamILS iterative all 2009 Ruby 1005 EGO iterative all 1998 6424 SPO iterative numerical 2005 R 367 SKO iterative numerical 2006 692 F-Race simple all 2002 R 704 Iterated F-Race iterative all 2007 R 285 Calibra iterative numerical 2006 497 Brute-force simple all 19XX N/A GGA iterative all 2009 348 HORA iterative all 2017 6 SMAC iterative all 2010 java, python 2029 The table 3.1 shows the characteristics of the Parameter Tuning Strategies. Most of these have been published in the last two decades, which shows the increasing impor- tance of parameters setting in metaheuristics. Many of the methods are able to work 29 with all kinds of parameters (numerical and non-numerical). The main disadvantage of the method in general is that the amount of parameters are limited to a certain number. It is also possible to see that most of them have as a basis of their operation one or several characteristics, such as heuristics, some statistical analysis, iterative approaches or the creation of a model. Generally speaking, these methods are a time- consuming step for the designer. To speed this up, it is good practice to use parallel computing. From the state-of-the-art of PTS, only GGA uses this functionality. 3.2 Parameter Control Strategies (PCS) According to the literature, online parameter setting or Parameter Control Strategies (PCS) is when the configuration of the parameters is accomplished as part of the algorithm execution while trying to solve the problem in question. Other less com- mon terms found in the literature to refer to this approach are Internal Parameter Control [Fialho, 2010] or Adaptive Metaheuristics [Sevaux et al., 2015]. The latter definition also considers the modification of the whole behavior of the metaheuristic, changing the order in which the components are executed and/or the parameter values (i.e., the control flow of the algorithm). For this kind of strategies, it is common to find that the adaptation mechanism is based on a behavior analysis of the metaheuristic during the search. The analysis implies getting some indicators (e.g., solution quality, similarity between solutions, local optima, among others). These indicators help to understand the behavior of the search. The knowledge gathered is used to adapt the parameters for obtaining better results during the process. The main drawback is the high amount of compu- tational resource needed for solving the problem of the parameter and for solving the optimization problem. In addition, it is necessary to understand how the parameters influence the behavior of the method and how to identify which parameters are good for focussing the strategy so that prevail the best parameters [Calvet et al., 2016]. Modifying parameters during an algorithm execution in the context of Evolutionary Algorithms (EA) is not a new thing. The history of EA shows studies with this aim since the 60’s and 70’s [Fogel et al., 1966, De Jong, 1975, Schwefel, 1977], but at this time these strategies were known as evolution strategies. In EA, PCS has had the importance than other methods have hardly taken in the last two decades. Hence, various classifications can be found, and the latest and most complete taxonomy is the one proposed by Parpinelli et al. [2019]; this taxonomy combines the ones performed by Eiben et al. [1999, 2007] and Zhang et al. [2012]. The Parpinelli’s taxonomy is not limited to EA but also focuses on another group of population algorithms, the swarm intelligence methods (SI). SI methods are characterised by algorithms inspired by the collective behaviour of insects such as ants, bees, termites and also animals such as fish and birds [Parpinelli et al., 2019], one example is the Ant Colony Optimization algorithm. Parpinelli’s paper reviewed 158 scientific articles, considering several aspects, such 30 as the control technique used, the domain of application, and the bio-inspired algo- rithm. They provide a broad overview about this topic, with the bonus that they consider both, EA and SI, areas that other reviews had not addressed. In this review, it is possible to note that there are algorithms with 2 parameters to 11. However, this applies not only for population methods. For single-solution methods, the number of parameters may also vary from few to many. Figure 3.1: Taxonomy for parameter control in EA and SI algorithms, adapted from [Parpinelli et al., 2019] Figure 3.1 shows the completed taxonomy for PCS in EA and SI algorithms adapted from Parpinelli’s taxonomy. It is possible to identify three groups, Deterministic, Adaptive and Aggregated methods. The first group uses simple deterministic rules that modify the parameter values using no feedback during the execution. An usual action for a deterministic method is to initialize the parameter value with a big value and gradually decreases it during the optimization process. This action is done by trying to balance between diversification and intensification in the search. To per- form the control, it is common to use the number of generations (iterations) or the number of fitness evaluations [Parpinelli et al., 2019]. Due to the simplicity and low computational effort, a lot of applications use this type of control. A well-known strategy for Deterministic parameter control in EA is the 1/5th rule [Rechenberg, 1973]. This rule establishes that the proportion of success muta- tions for all mutations should be 1/5. Therefore, if the proportion is superior to 1/5, the mutation step size should be increased. If the proportion is inferior to 1/5, the mutation step size should be decreased [Parpinelli et al., 2019]. The second group presented in the taxonomy is Adaptive. This group is divided into five different subcategories: Simple Rules, Fuzzy Control, Learning Automata, Entropy and Other. Zhang et al. [2012] included Aggregated category within Adaptive category. The Adaptive control strategies consider a certain form of feedback from the algorithm. The feedback contains information of the optimization process which will be used to modify the parameters values. For EA and SI, the most commonly information used is the generation number, fitness evaluations number, and some population diversity measurement [Zhang et al., 2012]. The five subcategories are described next. 31 In Simple Rules methods, the control is carried out only using simple rules, based on the observations of the algorithm behaviour or runtime characteristics of the EA [Zhang et al., 2012]. Examples of these controls are the implementation of rules based on log- arithmic, exponential, or linear functions [Fogarty, 1989]. In the Fuzzy Control methods, a controller converts an input (information from the feedback) to an output (actions for changing parameters) based on a set of fuzzy rules. These rules take inspiration on fuzzy logic. In [Herrera and Lozano, 2001] is summarized the fuzzy controller models applied to EA until 2001. A Learning Automata method is used to select the parameter values by means of a learning process. The learning process is carried out according to the feedback obtained while performing the optimization. The aim is to update progressively its adaptation mechanism and the performance algorithm through the learning process. These methods learn from the previous experiences, being in permanent change, trying to refine its process and thus the results [Parpinelli et al., 2019]. It is possible to call a learning automata method as a machine learning technique. The last classification subcategory named is Entropy-based methods. In the con- text of information theory, entropy is used to measure uncertainty of expected infor- mation, with a random variable. In the population-based algorithms, the generation of new population usually involves random and probabilistic operators. Thus, in this context, entropy can be used to analyze that population, getting characteristics and adjust the parameters accordingly. Shannon entropy is the most common control for entropy-based methods [Zhang et al., 2012]. Finally, the methods that not fall into any subcategory below are included in the Other methods, for instance, clustering, covariance matrix and pheromone matrix methods [Parpinelli et al., 2019]. The last category is Aggregated methods, also called self-adaptive methods [Eiben et al., 2007]. The main two features of aggregated methods are: (1) these contain the parameters directly coded with the solution vector, as an extra dimensions and (2) their parameters are adapted into the evolution process, using the same methods as the original algorithm (used for solving the optimization problem) or through specific routines [Zhang et al., 2012]. Zhang et al. consider self-adaptive control methods as a subset of Adaptive, because these methods are included in the adaptive definition. A notable feature of the PCS methods for EA and SI is that they can be at the individual or population level. The individual level is when each individual (or solution) has its own set of parameters and the parameters are adapted specifically for this individual. On the population level, parameters are adapted for the whole population. This adaptation is done through fitness measurements of each individual or population-based indicators. An example of a population-based indicator is the relationship between the average and maximum fitness values of the population used in [Dai et al., 2006]. Population-based indicators are not restricted to population-based algorithms. For instance, it is possible to use them in parallel methods with single- solution metaheuristics (one or many) that have in their design a solution population. In summary, we can conclude that, in the last decade, there have been proposed 32 several parameter setting methods for solving the PTP and PCS in EA and SI algo- rithms. For PCS methods in single-solution metaheuristics, the situation is quite dif- ferent. If a researcher (or practitioner) is thinking of solving an optimization problem using metaheuristics with parameterization within the algorithm, there is no guide for classifying parameterization methods. Of course, there have been publications about this approach, however these have been done in isolation, specialized for a particular metaheuristic or a specific problem, not easily reproducible [Calvet et al., 2016]. The aforementioned problem has been partially solved by the Reactive Search Op- timization (RSO) [Battiti and Brunato, 2010]. Battiti and Brunato define reactive word as follows: “The word reactive hints at a ready response to events during the search through an internal online feedback loop for the self-tuning of critical parame- ters”. This definition fits into the definition of Adaptive control strategies done for EA and SI algorithms, “The Adaptive control strategies consider certain form of feedback of the algorithm, information of the optimisation process to modify the parameter val- ues” [Zhang et al., 2012]. However, the reaction possibilities of RSO consider not only to change the parameter values; these possibilities consider also changing the neighbors definition, the objective function, and the use of some constrains. Therefore, these all possibilities differ from modifying just the parameters as PCS. It is for reason that the RSO approach does not seem to fit completely with Adaptive control strategies. Examples of PCS adjusted to the RSO approach are the Reactive Tabu Search (Reactive-TS) [Battiti and Tecchiolli, 1994] and the Adaptive Simulated Annealing (ASA) [Ingber, 1989]. For Reactive-TS, the tabu tenure, and for ASA, the temper- ature cooling schedule, are adjusted through feedback mechanisms during the search depending of the algorithm progress. In the literature about PCS, it is possible to find other different approaches for parameter control in single-solution methods. These methods contain techniques like support vector machines [Zennaki and Ech-Cherif, 2010], probability matching tech- niques [Prais and Ribeiro, 2000, Neto and Martins, 2018], simple parameters explo- ration through parallelism [Blesa and Xhafa, 2004] and adaptation based on empirical analysis of the algorithm behavior [Ferro et al., 1996a]. However, some of the showed methodologies are not easily reproducible or are highly metaheuristic and problem dependent. These are some of the reasons why, in spite of the amount of parameter control works, many practitioners go on setting by hand or trying to design algo- rithms without parameters (or with a very low number of them), even with the proof that parameterizing an algorithm results in better algorithms leads to better perfor- mance [Calvet et al., 2016]. We can conclude that there is not method or methodology commonly accepted by the scientific community to setting the parameter of a metaheuristic. There is also a lack of methods (or research) for PCS and more for PCS in single-solution meta- heuristics. The PCS for PSP is far from being solved, despite the methods mentioned above. However, it is worth mentioning and being aware that designing a PCS is much more complex than designing a PTS one [Dobslaw, 2010b]. This gap of PCS methods 33 makes this research work relevant in its theoretical and practical study. Additionaly, the importance of PCS as a vital part of the implementation and application of better metaheuristics methods, for the solution of optimization problems. 3.3 Instance-specific Parameter Tuning Strategies (IPTS) The idea of Instance-specific Parameter Tuning Strategies (IPTS) is to find, for each specific instance of a problem, one static parameter values. PTS differs of IPTS, since PTS has the aiming to obtain one specific “robust” set of parameter values but for all instances of a problem. In IPTS each instance set is used to design an efficient tuning method that can return instance-specific parameter values based on measurable instance characteristics [Ries and Beullens, 2015]. In IPTS methods, the relation between the parameter values and the performance of the metaheuristic has to be strongly analyzed. This analysis is done taking into account instance specific features. IPTS avoids the need to modify the metaheuristic algorithm, reducing the possible computational effort required to adapt parameter values during algorithm execution as the PCS approach does. Another reason to implement IPTS is that looking for one fixed set of parameter values for an entire set of instances with different characteristics is not likely to perform well in all instances [Ries et al., 2012]. In simple words, IPTS works like this: a representative set of instances of the prob- lem is selected, this set is investigated and used to design the tuning method. Once designed, the tuning method calculates the characteristics of any given instance, and then applies a method (or model, function) to return a custom parameter values for a specific instance. These values are used to initialize the metaheuristic for solving the specific instance, and these parameter values remain fixed during the execution [Ries and Beullens, 2015]. Ries and Beullens noted that an IPTS design has several chal- lenges, like the selection of relevant characteristics, as well as the identification of the relation between: (1) the instance-specific information, (2) the parameter values of the algorithm, and (3) their impact on running times and quality of solutions obtained. Is possible to think IPTS as a subcategory of PTS, firstly, because the IPTS name suggests it and second by the fact that the parameters for solving the problem instance remain fixed during the execution, even if they are different for all instances. Never- theless, there is in the literature another definition that can make a difference between IPTS and PTS. Some authors define and have used the IPTS as the combination of the advantages of PTS and PCS [Ries and Beullens, 2015, Calvet et al., 2016, Dobslaw, 2010a]. Only few approaches can be currently found in the literature that used IPTS or that may fall within the definition of this approach. As we have said, the differences in their definitions are still a problem to be solved for this area of research. For 34 that reason, some papers have been published as PTS approach, for example [Pavón et al., 2009, Dobslaw, 2010a]. The Dobslaw’s work is interesting, it combines the advantages of Design of Experiments (PTS) and Artificial Neural Networks (PCS) for the recognition of good initial parameter settings for new problem instances. They tested their methodology adjusting the parameters of the Particle Swarm Optimization algorithm. Ries et al. [2012] introduced the concept of IPTS in 2012, even they mention instance-specific parameter control strategies (IPCS), in order to adapt the dynamic parameter control procedures to the specific characteristics of each case. In view of the state-of-the-art of PSP, IPCS is an unused approach. As the IPTS studies has shown, an important part is to carry out a statistical analysis to identify the impact of parameters on the metaheuristic performance and to know the interaction between them. However, the statistical analysis requires someone to interpret the results. The most of IPTS methods have been designed by using this statistical analysis and all the knowledge of the problem gathered [Ries et al., 2012, Ries and Beullens, 2015, Dobslaw, 2010a]. In [Ries et al., 2012], they proposed a fuzzy logic method based on the knowledge obtained from the statistical analysis. The fuzzy logic method is a rule-based approach, where the control objectives and relationships between inputs and actions (or outputs) are captured in the fuzzy logic system, usually through a set of IF–THEN rules. Ries and Beullens [2015] proposed a semi-automated approach for designing fuzzy logic, whereby the classification rules are derived from automatically generated deci- sion trees. With this automation, they has the intention of removing the requirement of having an expert to interpret of the statistical results. According to the authors, the mentioned approach is generally applicable for developing an IPTS for any meta- heuristic and type of problem. They tested it to parameterize a Guided Local Search for solving the Travelling Salesman Problem. In previous work, Pavón et al. [2009] propose the idea of having methods without the utilization of statistical analysis. They designed a hybrid system, using Case-Based Reasoning (CBR) and Bayesian Networks (BN). BNs are used to model qualitative and quantitative relationships between the different algorithm parameters, while the CBR methodology is used to update the models associated with each case and to learn new cases within the domain. The system was done to tune a Genetic Algorithm for solving the root identification problem. This system is an extension of the model done in 2008 [Pavón et al., 2008]. This last also uses a BN to capture the dependencies between the parameters and the performance of the algorithm. It is gaining attention to consider the instance-specific information. Knowing this information, and learning how to interpret it, can be crucial to achieve better methods and better results in less computational time. For the time being, the number of IPTS works are low, since it is relatively new approach. So, proposing a taxonomy does not make sense now, however, this chapter shows the highlights of IPTS. 35 3.4 HyperHeuristics (HH) The term hyperheuristic was first used in a conference paper [Cowling et al., 2001]. A single pre-2001 occurrence can also be found in a technical report where it was used in a different context, to describe an approach that combines a range of artificial intelligence algorithms for automated theorem testing [Denzinger et al., 1996]. However, the basic idea of automating the design and/or selection of metaheuristics with its parameters is much older. It dates back to the early 1960s [Burke et al., 2013], as mentioned also for the Evolutionary Algorithms [Fogel et al., 1966, De Jong, 1975, Schwefel, 1977]. Related to this emerged new concept, several publications have attempted to clas- sify the work that has been done [Burke et al., 2003, Ross, 2005, Chakhlevitch and Cowling, 2008, Burke et al., 2009, 2013, 2019]. Burke et al. [2009] discusses method- ologies for generating new metaheuristics from a set of potential metaheuristic compo- nents, in which genetic programming (GP) plays a prominent role as machine learning technique and as high-level heuristic. Later, Burke et al. [2013, 2019] propose a uni- fied classification and definition that captures all the work being done in the field of hyperheuristics, showing that it is a promising research area. Thus, since the introduction of the hyperheuristic concept, there have been impor- tant advances in solving combinatorial optimization problems. The design of an Evo- lutionary HyperHeuristic with the implementation of evolutionary algorithms [Oltean and Grosan, 2004, Guogis and Misevičius, 2014], such as genetic programming (GP), gene expression programming (GEP), and grammatical evolution (GE), acting as a high-level heuristic has been successfully applied [Su et al., 2011, Dokeroglu and Cosar, 2016, Garrido and Riff, 2010, Marshall et al., 2014, Sabar et al., 2013, 2014, 2015]. Non-evolutionary approaches such as Roulette wheel, Monte Carlo algorithm, and others have also been used as high-level heuristics with satisfactory results [Marshall et al., 2014, Sabar and Kendall, 2014, Sim and Hart, 2014, Turky et al., 2018]. Due to the growing interest in hyperheuristics, in 2011, during the first Cross- Domain Heuristic Search Challenge Competition (CHeSC), HyFlex, a flexible frame- work for the creation of hyperheuristics, was presented [Ochoa et al., 2012]. HyFlex provides six difficult combinatorial optimization problems, is public and is imple- mented in Java. Multiple applications have been done using HyFlex [Marshall et al., 2014, Sabar et al., 2014, Sabar and Kendall, 2014, Sabar et al., 2015, Su et al., 2011]. It can find in the literature that just one hyperheuristic work solves the QAP and uses parallelism in its design. In this study, the authors proposed a high-performance Multistart Hyper-heuristic Algorithm (MSH-QAP). MSH-QAP makes use of some of the metaheuristics that have been reported to be among the best performance algorithms for solving difficult QAP instances, Simulated Annealing, Robust Tabu Search, Fast Ant System, and Breakout Local Search. The high-level heuristic is performed by a genetic algorithm (GA) and is called master agent hiperheuristic. MSH-QAP has two execution phases [Dokeroglu and Cosar, 2016]. This method is a Evolutionary HyperHeuristic, because it has GA as high-level heuristic. 36 In the first phase of MSH-QAP, in the GA each individual in the population rep- resents as a whole a solution, a metaheuristic method and its parameters. In each generation of the execution by parallel computing, each available execution unit pro- cesses a metaheuristic with its parameters and returns its result to the master agent hiperheuristic. The master agent generation by generation performs the adapta- tion of parameters through crossing and mutation operators (similar behavior to Aggregated category in PCS methods). At the end the parameters with their best ad- justment for each method remain. If in this first phase the best known solution is not reached, phase two is activated. In phase two, the best metaheuristic is selected with its parameter settings, it is given to all execution units and executed with multiple starts. It can be seen that the lines that differentiate some Evolutionary HyperHeuristic with the Aggregated methods in PCS are diffuse. That is, there are works that can be classified by its design as Evolutionary HyperHeuristic as Aggregated, for instance the MSH-QAP method. 3.5 Taxonomy PSP Methods Figure 3.2 depicts our complete taxonomy about PSP, it summarizes all the infor- mation reviewed here. As we mentioned earlier, the literature about PSP is highly different and varied. In the last two decades, this problem has been of great interest to researchers and practitioners who study optimization problems and metaheuristic methods. Figure 3.2: Taxonomy of strategies to solve the parameter setting problem (PSP) 37 The task of classifying all methods to solve the PSP had not been done until now. Here, we propose a taxonomy that generalize the taxonomies made individually for each category of PSP (PTS, PCS, IPTS and HH). In this taxonomy, it is possible to identify that there are an overlapping of subcategories, which means there are subcategories that are part of two categories. This suggests two things, the first is the definition of a subcategory is sufficiently broad or ambiguous to fit into two categories or that more studies are needed to show more clearly their differences. We consider the latter to be the main reason, due to the newness of the PSP methods and the research gaps that still exist in many of them (e.g. PCS methods for single solution metaheuristic). To make this taxonomy, we classified PTS methods in the next subcategories: Simple, Iterative, Heuristic, Statistical and Model-based. This classification is done based on the characteristics we analyzed in the summary table 3.1 of the section 3.1. Thus, those methods that use simple strategies to select the parameters are Simple, those who use an iterative process to perform the selection are Iterative, those that use some heuristic to guide the search to select good parameters are Heuristic, those who use some statistical test are Statistical and those who build a model are Model-based. From the figure 3.2, it is possible appreciate that the methods classified as Heuris- tic, Statistical, Fuzzy Control, Learning Automata, Self-Adaptative and Others also belong within two big superior categories, for example Heuristic belongs to PTS and IPTS. In the case of those methods that belong to IPTS category, all belong either to PTS or PCS, a situation that was expected, since as mentioned IPTS methods contemplate the combination of PTS and PCS. Finally, Self-Adaptative methods (or Aggregated in PCS for some authors) belong to both PCS and parameter setting in Evolutionary Hyperheuristics. This is because Self-Adaptative methods manage the parameters together with the solution of the problem within the evolutionary process [Zhang et al., 2012]. We can conclude that knowing which method is best for solving the PSP is a difficult task to assess, in general each one offer different advantages and have many disadvantages. The dynamic adaptation of the parameter values that characterizes PCS usually provides better results. However, the computational effort tends to be higher. On the other hand, the PTS approach is the easiest and fastest to use. Once a set of parameter values is selected, the algorithm code does not have to change to find the set of parameter. Nevertheless, finding an adequate set may be also time- consuming. Finally, the IPTS group of strategies represents a compromise strategy: it takes less computational time than the PCS approach, but requires implementing a learning mechanism to interpret the relation between the relevant metaheuristic characteristics selected [Calvet et al., 2016]. Therefore, there is no approach that stands out from the others. Probably, the most adequate depends on the specific problem to tackle, the instances to solve, the available time and the skills of the researcher. Despite this fact, some general guidelines can 38 be formulated. PTS can be considered as the best option when working with robust algorithms [Calvet et al., 2016] and when the instances to be solved are somehow similar in their characteristics due to the specific area of application in which they occur [Ries et al., 2012]. Regarding IPTS, they are more complex than PTS, but provide better results when the algorithm is not robust and at the same time, when the instances differ in their characteristics. In case of prioritizing the algorithm performance, PCS usually constitute the most recommendable approach [Calvet et al., 2016], these strategies work arguably best when the instances that need solving are not a priori well known but are expected to differ significantly in their characteristics [Ries et al., 2012]. Finally, in order to create a general method for solving various optimization problems, HH is the best choice. 39 Chapter 4 Framework 4.1 Introduction As we pointed out in the state of the art, there is a gap in parameter control strate- gies for single-solution metaheuristics. The research problem is even more notorious in parallel hybrid metaheuristics, since these methods need to fine tune a large num- ber of parameters (more metaheuristic of different types are involved and there are parameters to define their parallel hybrid behaviour). In this chapter, we propose PACAS: a general framework to configure the PArameter Control Adaptation for Single solution metaheuristics in a parallel hybrid solver. The PACAS framework aimed at increasing the performance of parallel method based on several parameter control strategies through the analysis of the behavior of single solution metaheuristics. This framework allows the programmer to define the adap- tation of the parameter using some mechanisms to customize the trade-off between intensification and diversification in the search process. In the remaining of this chapter we describe the general concepts of our PACAS framework (Section 4.2), the subsections within this section contain details of the team structure and the description of the functionality of each team component. In addition, the mechanisms for setting the parameter control strategies are exposed in Section 4.3. Then, we present a summary of the framework parameters (Section 4.4). Finally, we introduce a dedicated section to discuss the sources of hybrid behavior within the framework. 4.2 General description In this section, we describe the design details of our framework, PACAS. Searcher nodes are the basic components of the framework: each searcher node corresponds to a single solution metaheuristic solver instance of any type. The idea is to set each searcher node ideally bound to its own dedicated core, using all available processing hardware. One of the basic uses of the framework is for running several instances of 40 different metaheuristic, in an independent parallel search with static parameters, all of them starting from a different search point, i.e. different initial solution. The framework allows cooperation through a solution population and allows change dynamically the setting parameters of each single metaheuristic every certain time. In PACAS is possible to control when accept or how select a solution from the solution population by means of a request and entrance policy. The adjustment of the request and entrance policy and the mechanisms defined for the adaptation of the parameters contribute to the strategies to balance diversification and intensification. Even the configuration of these policies, and the moments related with the application of them, i.e. the time associated to set how often this task is done, establish the hybrid behavior and the amount of cooperation among the searchers. A master node manages these policies, adaptation mechanisms and times. The master node additionally carries out a performance evaluation of each searcher node using some collected information in order to apply the parameter adaptation mechanisms. Figure 4.1: Representation of the search process using PACAS Searcher nodes can be grouped into teams of fixed size, teams with the same number of metaheuristics of each type. For example, teams configured to have 10 Local Search, 10 Tabu Search and 10 Simulated Annealing. Thus, if we have 2 teams, it means 60 metaheuristic in total, 20 for each type. Each team inside has its own request and entrance policy. For instance, one team could have an elite entrance policy, to control that only the best solutions can enter in the solution population, and a second team implemented a random entrance policy, where a solution comes out randomly to give space for a new solution. Within a team, it would also be possible to design different versions of the mechanisms used to make the adaptation of the parameter (feature will be explained in detail later, Section 4.3). There is no communication between the teams, so it is important to be careful with the policies and mechanisms defined, the definition of these both features work together for having a good trade-off between intensification and diversification. On the head of each team there is a master node. 41 Figure 4.1 depicts the search process using PACAS. Among the master node and the searcher nodes, there is communication (Intra-team communication). The Intra-team communication is performed synchronously by each searcher node every certain time. The communication process is necessary for the master node to obtain the behavior of the metaheuristics, make the performance evaluation and later apply the establish parameter control strategies (PCS). The PCS involve two stages, (1) evaluating the searcher node behavior and (2) adapting the parameters. For each stage some rules and mechanisms must be defined. 4.2.1 Team structure In our framework, a team is integrated by one master node, several searcher nodes and one solution population (SP). All these components work together in an environment controlled by the master (see Figure 4.2). Our framework proposes an intra-team communication as a cooperative mechanism, to ensure inside this environment the balance of intensification and diversification. Each team is a parallel cooperative search. Figure 4.2: Structure of a Team Each searcher node reports periodically its current candidate solution and some contextual information (e.g., solution cost, performance metrics, parameters, etc. See Figure 4.3) to the master node, which stores (or not) intermediate solutions into the SP based on the input policy specified for the team. This mechanism promotes diversity (much or few) for