Many-Objective Evolutionary Optimisation

Many-Objective Evolutionary Optimisation

Francesco di Pierro (University of Exeter, UK), Soon-Thiam Khu (University of Exeter, UK) and Dragan A. Savic (University of Exeter, UK)
Copyright: © 2009 |Pages: 7
DOI: 10.4018/978-1-59904-849-9.ch154
OnDemand PDF Download:
$37.50

Abstract

Many-objective evolutionary optimisation is a recent research area that is concerned with the optimisation of problems consisting of a large number of performance criteria using evolutionary algorithms. Despite the tremendous development that multi-objective evolutionary algorithms (MOEAs) have undergone over the last decade, studies addressing problems consisting of a large number of objectives are still rare. The main reason is that these problems cause additional challenges with respect to low-dimensional ones. This chapter gives a detailed analysis of these challenges, provides a critical review of the traditional remedies and methods for the evolutionary optimisation of many-objective problems and presents the latest advances in this field.
Chapter Preview
Top

Background

There has been considerable recent interest in the optimisation of problems consisting of more than three performance criteria, realm that was coined many-objective optimisation by Farina and Amato (Farina, & Amato, 2002). To date, the vast majority of the literature has focused on two and three-dimensional problems (Deb, 2001). However, in recent years, the incorporation of multiple indicators into the problem formulation has clearly emerged as a prerequisite for a sound approach in many engineering applications (Coello Coello, Van Veldhuizen, & Lamont, 2002). Despite the tremendous development that MOEAs have undergone over the last decade, and their ample success in disparate applications, studies addressing high-dimensional real-life problems are still rare (Coello Coello, & Aguirre, 2002). The main reason is that many-objective problems cause additional challenges with respect to low-dimensional ones:

If the dimensionality of the objective space increases, then in general, the dimensionality of the Pareto-optimal front also increases.

The number of points required to characterise the Pareto-optimal front increases exponentially with the number of objectives considered.

It is clear that these two features represent a hindrance for most of the population-based methods, including MOEAs. In fact, in order to provide a good approximation of a high-dimensional optimal Pareto front, this class of algorithms must evolve populations of solutions of considerable size. This has a profound impact on their performance, since evaluating each individual solution may be a time-consuming task. Using smaller populations would not be a viable option, at least for Pareto-based algorithms, given the progressive loss of selective pressure they experience as the number of objectives increases, with a consequent deterioration of performances, as it is theoretically shown in (Farina, & Amato, 2004) and empirically evidenced in (Deb, 2001, pages 404-405). In contrast to Pareto-based methods, traditional multi-objective optimisation approaches, which work by reducing the multi-objective problem into a series of parameterised single-objective ones that are solved in succession, are not affected by the curse of dimensionality. However, such strategies cause each optimisation to be executed independent to each other, thereby losing the implicit parallelism of population-based multi-objective algorithms.

The remainder of this chapter provides a detailed review of the methods proposed to address the first two issues affecting many-objective evolutionary optimisation and discusses the latest advances in the field.

Top

Remedial Measures: State-Of-The-Art

The possible remedies that have been proposed to address the issues arising in evolutionary many-objective optimisation can be broadly classified as follows:

  • aggregation, goals and priorities

  • conditions of optimality

  • dimensionality reduction

In the next sub-sections we give an overview of each of these methods and review the approaches that have been so far proposed.

Key Terms in this Chapter

Many-Objective Problem: Problem consisting of more than 3-4 objectives to be concurrently maximised/minimised.

Selective Pressure: The ratio between the number of expected selections of the best solution and the mean performing one.

Ranking Scheme: Scheme that assigns to each solution of a population a score that is a measure of its fitness relative to the other members of the same population.

Evolutionary Algorithms: Solution methods inspired by the natural evolution process that evolve a population of solutions to an optimisation problem through iterative application of randomised processes of recombination and selection, until a termination criteria is met

Pareto Set: Set of Pareto Optimal solutions.

Pareto Optimal Solution: Solution that is not dominated by any other feasible solution.

Pareto Front: Image of the Pareto Set onto the performance (objective) space.

Complete Chapter List

Search this Book:
Reset