A Guided Mutation Operator for Dynamic Diversity Enhancement in Evolutionary Strategies

Introduction

Meta-heuristic approaches (Talbi, 2009) have to deal, according to their optimization method nature, with two complimentary processes: exploration and exploitation. Different approaches show different strengths regarding these two complementary requirements. Population-based approaches, and particularly evolutionary computation (Bäck, Fogel, &Michalewicz, 1997), excel at their exploration capabilities (also named diversification), while other approaches, such as local search techniques (Hoos & Stützle, 2005), provide a better exploitation (also named intensification) of the obtained information.

Evolutionary computation arose as a powerful technique to deal with optimization and search problems, particularly evolution strategies, focused on real value representations, which have been successfully tested on a wide variety of problems, both theoretical and practical in nature. The increase in the computational resources of computers and the increasing number of parallel implementations and multi-objective approaches have lead this growth, making them more appealing for practitioners focused on solving particular problems, rather than theoretical research of the algorithms themselves. An example of these applications may be providing a better adjustment between simulation models and reality for the car industry (Bäck, Keßler, & Heinle, 2011). There are, however, a number of issues for these applications.

Early convergence and local optima constitute a drawback for evolutionary algorithms, since they do not provide, as most metaheuristics (Talbi, 2009), a measurement of the proximity of the solutions found to global optima, performing a best-effort approach. This early convergence arises as a concern regarding this topic, being closely related to the diversity preservation in the population as the algorithm progresses, which can be linked to features such as selection pressure and gene flow between population members (Ursem, 2002). Many approaches have been proposed to deal with this issue, from the restriction of certain operator applications (such as the incest prevention proposed in (Eshelman & Schaffer, 1991)) to multi-objective approaches where the diversity of the population is treated as an additional objective function (Toffolo & Benini, 2003).

Diversity preservation and management can also be looked at from a stopping criterion perspective. In single-objective optimization, dynamic stopping criteria have been formulated establishing thresholds over different measures of population diversity, such as the standard deviation of the distance among the different individuals in the population (Zaharie & Petcu, 2005) or the difference between the best and worst individual in the population (Babu & Angira, 2003). These differences can be considered in either the variable or the objective space.

In multi-objective approaches, diversity is usually focused on the objective space (a comparison of the importance of diversity in objective and variable space for multi-objective initialization processes has been carried out in (Guerrero, Berlanga, & Molina, 2012)). This diversity can be measured through the use of quality indicators such as the hypervolume indicator (Zitzler, Brockhoff, & Thiele, 2007), which measures closeness and spread of the Pareto front. General stopping criteria are, thus, a concern for practitioners using evolutionary techniques, which is in fact shared by many different iterative processes, but the stochastic nature of evolutionary computation makes it probably more important and, at the same time, harder to solve.