A Guided Mutation Operator for Dynamic Diversity Enhancement in Evolutionary Strategies

A Guided Mutation Operator for Dynamic Diversity Enhancement in Evolutionary Strategies

José L. Guerrero (Computer Science Department, Applied Artificial Intelligence Research Group, University Carlos III of Madrid, Colmenarejo, Spain), Antonio Berlanga (Computer Science Department, Applied Artificial Intelligence Research Group, University Carlos III of Madrid, Colmenarejo, Spain) and José M. Molina (Computer Science Department, Applied Artificial Intelligence Research Group, University Carlos III of Madrid, Colmenarejo, Spain)
Copyright: © 2014 |Pages: 20
DOI: 10.4018/ijncr.2014040102
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Diversity in evolutionary algorithms is a critical issue related to the performance obtained during the search process and strongly linked to convergence issues. The lack of the required diversity has been traditionally linked to problematic situations such as early stopping in the presence of local optima (usually faced when the number of individuals in the population is insufficient to deal with the search space). Current proposal introduces a guided mutation operator to cope with these diversity issues, introducing tracking mechanisms of the search space in order to feed the required information to this mutation operator. The objective of the proposed mutation operator is to guarantee a certain degree of coverage over the search space before the algorithm is stopped, attempting to prevent early convergence, which may be introduced by the lack of population diversity. A dynamic mechanism is included in order to determine, in execution time, the degree of application of the technique, adapting the number of cycles when the technique is applied. The results have been tested over a dataset of ten standard single objective functions with different characteristics regarding dimensionality, presence of multiple local optima, search space range and three different dimensionality values, 30D, 300D and 1000D. Thirty different runs have been performed in order to cover the effect of the introduced operator and the statistical relevance of the measured results
Article Preview

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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 6: 2 Issues (2017): 1 Released, 1 Forthcoming
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing