Parameter Setting in Sequential and Parallel Evolutionary Algorithms


Abstract

In recent decades a wide range of algorithmic approaches have been designed to solve both single-objective and multi-objective optimisation problems. The application of exact methods allows the optimal solutions of these optimisation problems to be obtained. However, exact methods are generally not affordable for many complex applications; as a result, a wide variety of approximate algorithms have been developed with the aim of obtaining high-quality solutions in a reasonable amount of time that might be quite close to the optimal solutions. Among the groups of approximate algorithms, the family of heuristics and meta-heuristics is worth mentioning. Meta-heuristics are a set of approximate techniques that have become popular for solving optimisation problems. They are high-level problem-independent strategies that guide a set of heuristics in the search of an optimum. A large variety of meta-heuristics have been proposed in the literature. Among them, Evolutionary Algorithms (EAs) are one of the most popular strategies. They are population-based meta-heuristics inspired by biological evolution. EAs have shown great promise for calculating solutions to large and difficult single-objective and multi-objective optimisation problems. Nevertheless, even with the application of meta-heuristics like EAs, the resolution of some complex optimisation problems could involve using a vast amount of computational resources and time. As a result, the parallelisation of EAs has been proposed in order to speed up the process of obtaining high-quality solutions, and consequently deal with such complex problems. Among the different parallel EAs proposed in the literature, the island-based model is one of the most frequently used schemes, because it is suitable for parallel architectures and it can be combined with both single-objective and multi-objective methods. One of the main drawbacks of EAs is that, for some problems, they exhibit a tendency to converge towards local optima due to diversity loss in populations with a finite sizeā€”also called genetic drift. Genetic drift is the main reason for the appearance of premature convergence in EAs. One of the proposals that has gained some popularity in recent years to address the problem of premature convergence relies on applying multi-objective schemes to single-objective optimisation problems. Several ways of applying the multi-objective concepts have been devised, with diversity-based Multi-Objective Evolutionary Algorithms (MOEAs) being one of the most promising schemes. In these algorithms, a metric of the diversity introduced by each individual is used as an auxiliary objective, whereas the original objective function of the optimisation problem being solved is kept. Besides the problem of premature convergence, finding the appropriate setting for an EA remains one of the persistent challenges for Evolutionary Computation (EC). In order to completely define a configuration of an EA several symbolic parameters, such as the variation or parent selection operators, and different numeric parameters, such as the mutation and crossover rates, must be set. In general, the performance of an EA and, consequently, the quality of the resulting solutions, is highly dependent on these parameters. As a result, it is essential that the parameters of an EA be suitably determined. Parameter setting strategies are commonly divided into two categories: parameter tuning and parameter control. In parameter tuning the objective is to identify the best set of values for the parameters of a given EA, which is then executed using these values, which remain constant for the duration of the run. In contrast, the aim of parameter control is to design control strategies that select the most suitable values for the parameters at each stage of the search process while the algorithm is being executed. In recent years, parameter tuning approaches have exhibited some disadvantages with respect to parameter control methods, so recent research developments have focused on control strategies, since it has been theoretically and empirically demonstrated that the most appropriate parameter values change depending on the stage of the optimisation procedure. Thus, in this dissertation the main aim is twofold. Firstly, to design and study diversity-based MOEAs as methods for dealing with premature convergence in EAs. In this regard, several diversity metrics with parameters are proposed as novel auxiliary objectives, as well as a novel diversity-based survivor selection mechanism which preserves diversity in a population of individuals. Secondly, to design several parameter control strategies with the final aim of being able to simultaneously adapt numeric and symbolic parameters of an EA. These parameter control schemes are based on the usage of Fuzzy Logic Controllers and Hyper-heuristics, and they are applied, respectively, to adapt numeric and symbolic parameters belonging to the proposed diversity-based MOEAs. Additionally, in order to more quickly obtain high-quality solutions and to enable the usage of some of these techniques in parallel environments, they are integrated with an island-based model. Finally, the validation of the different proposals is carried out by measuring their performance over a set of well-known benchmark problems and real-world complex applications.