Parameter setting in sequential and parallel evolutionary algorithmsan approach based on hyper-heuristics and parameter control strategies

Resumen

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. 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 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, which are applied herein to adapt different 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.