Selection methods and diversity preservation in many-objective evolutionary algorithms
| Published date | 04 September 2018 |
| DOI | https://doi.org/10.1108/DTA-01-2018-0009 |
| Pages | 502-519 |
| Date | 04 September 2018 |
| Author | Luis Martí,Eduardo Segredo,Nayat Sánchez-Pi,Emma Hart |
| Subject Matter | Library & information science,Librarianship/library management,Library technology,Information behaviour & retrieval,Metadata,Information & knowledge management,Information & communications technology,Internet |
Selection methods and diversity
preservation in many-objective
evolutionary algorithms
Luis Martí
Institute of Computing, Universidade Federal Fluminense, Niterói, Brazil
Eduardo Segredo
School of Computing, Edinburgh Napier University, Edinburgh, UK and
Departamento de Ingeniería Informática y de Sistemas,
Universidad de La Laguna, San Cristóbal de La Laguna, Spain
Nayat Sánchez-Pi
Universidade do Estado do Rio de Janeiro, Rio de Janeiro, Brazil, and
Emma Hart
School of Computing, Edinburgh Napier University, Edinburgh, UK
Abstract
Purpose –One of the main components of multi-objective, and therefore, many-objective evolutionary
algorithms, is the selection mechanism. It is responsible for performing two main tasks simultaneously. First,
it has to promote convergence by selecting solutions which are as close as possible to the Pareto optimal set.
And second, it has to promote diversity in the solution set provided. In the current work, an exhaustive study
that involves the comparison of several selection mechanisms with different features is performed.
Particularly, Pareto-based and indicator-based selection schemes, which belong to well-known multi-objective
optimisers, are considered. The paper aims to discuss these issues.
Design/methodology/approach –Each of those mechanisms is incorporated into a common multi-
objective evolutionary algorithm framework. The main goal of the study is to measure the diversity preserved
by each of those selection methods when addressing many-objective optimisation problems. The Walking
Fish Group test suite, a set of optimisation problems with a scalable number of objective functions, is taken
into account to perform the experimental evaluation.
Findings –The computational results highlight that the the reference-point-based selection scheme of the
Non-dominated Sorting Genetic Algorithm III and a modified version of the Non-dominated Sorting Genetic
Algorithm II, where the crowding distance is replaced by the Euclidean distance, are able to provide the best
performance, not only in terms of diversity preservation, but also in terms of convergence.
Originality/value –The performance provided by the use of the Euclidean distance as part of the selection
scheme indicates this is a promising line of research and, to the best of the knowledge, it has not been
investigated yet.
Keywords Convergence, Diversity preservation, Many-objective optimisation,
Multi-objective evolutionary algorithm, Selection mechanism, Walking Fish Group (WFG) test suite
Paper type Research paper
1. Introduction
Multi-objective optimisation is aimed to deal with optimisation problems defined by a set of
objective functions, which must be optimised in a simultaneous way. Those objective
functionsare conflicting one to each other.In the related literature,these types of problems are
referred to as multi-objective optimisation problems (MOPs). MOPs can be found on a
significant number of real-world applications in different fields, such as aircraft engineering
(Reynoso Meza et al.,2 017), engine design (Patel et al., 2017), renewable energies (Tanwarand
Khatod, 2017) and controller design (Freire et al., 2017), among many others. many-objective
optimisation problems (MaOPs) are those MOPs where more than three objective functions
have to be optimised(Ishibuchi et al., 2008). The Paretooptimal front or Pareto optimal set are
Data Technologies and
Applications
Vol. 52 No. 4, 2018
pp. 502-519
© Emerald PublishingLimited
2514-9288
DOI 10.1108/DTA-01-2018-0009
Received 23 January 2018
Revised 25 May 2018
Accepted 21 June 2018
The current issue and full text archive of this journal is available on Emerald Insight at:
www.emeraldinsight.com/2514-9288.htm
502
DTA
52,4
the terms used to refer to the solution of a MOP, and therefore, a MaOP. The Pareto optimal
front consists of a set of trade-off points in the space of the objective functions.
At this point, we should note that the Pareto optimal set can be obtained by means of
mathematical programming approaches, in case the MOP we are dealing with satisfies
several requirements, for instance, convexity of the feasible set, and linearity or convexity of
the objective functions (Branke et al., 2008). Nevertheless, in general, providing the solution
of a MOP is an NP-complete problem (Bäck, 1996). Bearing the above in mind, exact
algorithmic approaches are not applicable, and consequently, a wide range of heuristic and
meta-heuristic techniques has been proposed in the related literature to deal with MOPs.
Multi-objective evolutionary algorithms (MOEAs) (Coello Coello et al., 2007) are one of the
most popular algorithmic schemes to address MOPs in a successful way. A large number of
MOEAs has been designed to tackle MOPs (Coello Coello et al., 2007), such as the Non-
dominated Sorting Genetic Algorithm II (NSGA-II) (Deb et al., 2002), the Strength Pareto
Evolutionary Algorithm 2 (SPEA2) (Zitzler et al., 2001), the Multi-objective Evolutionary
Algorithm based on Decomposition (MOEA/D) (Zhang and Li, 2007), the Grid-based
Evolutionary Algorithm (Yang et al., 2013) and the Indicator-based Evolutionary Algorithm
(Zitzler and Künzli, 2004), among others.
The approach used to select the individuals that will survive for the next generation of a
MOEA is referred to as theselection scheme, and is one of the most important components in
these types of algorithms. Particularly, the selection scheme is responsible for balancing the
convergence and the diversity of the solution set provided. One of the most frequently used
selection mechanisms is based on Pareto optimality concepts. Pareto-based selection usually
takes into account two independent selection criteria (Liu et al., 2017). First of all, individuals
are ranked by applying Pareto optimality such that the non-dominated individuals are
assigned to a better rank. Afterwards, in order to differentiate individuals that have been
assigned to the same rank, a diversity-based criterion is used. Pareto-based selection has
proven to be one of the most successful selection methods to deal with a large number of
MOPs. When addressing MaOPs, however, the application of Pareto-based MOEAs is not
appropriate. In the caseof dealing with MaOPs, the larger the number of objective functions,
the higher the number of non-dominated solutions. In this scenario, the Pareto-based
selection approach becomes inaccurate when ranking individuals, and consequently,
the selectionpressure of the whole MOEA decreases.This lack of convergence causesthat the
solution set provided is not close enough to the Pareto optimal set.
With the aim of improving the performance of Pareto-based MOEAs when dealing with
MaOPs, three options have been explored mainly (Liu et al., 2017). The first option is based
on providing new dominance definitions that are able to increase the selection pressure of
the MOEA. Examples would be the dominance area control (Sato et al., 2011) and the
L-optimality (Zou et al., 2008). The improvement or replacement of the diversity-based
selection criterion is the second option. An example of the above is the novel diversity
preserving strategy based on dynamic crowding distance proposed by Yang et al. (2017).
The third option consists of providing MOEAs that do not make use of Pareto-based
selection (Liu et al., 2017): decomposition-based MOEAs, grid-based MOEAs and
indicator-based MOEAs. Finally, the order in which the convergence and diversity-based
criteria are considered to select individuals has also been analysed. For instance,
Jiang and Yang (2016) proposed a novel MOEA called Diversity-first Based Evolutionary
Algorithm (DBEA) that considers diversity, rather than convergence, as the first criterion in
the selection mechanism. DBEA demonstrated to attain a better performance for a
significant number of the functions tested in comparison to the well-known Non-dominated
Sorting Genetic Algorithm III (NSGA-III).
A very important research question to be answered and that has arisen as a very
active research field is how to measure the performance of MOEAs properly (Li et al., 2014).
503
Selection
methods and
diversity
preservation
To continue reading
Request your trial