Approximation Guided Evolution - A Multi-Objective Optimization AlgorithmMost real-world optimization problems are characterized by multiple objectives. As these objectives are often in conflict with each other, the goal of solving a multi-objective optimization (MOO) problem is to find a (not too large) set of compromise solutions. The Pareto front of a MOO problem consists of the function values representing the different trade-offs with respect to the given objective functions. Multi-objective optimization is assumed to be more (or at least as) difficult as single-objective optimization due to the task of computing several solutions. From a computational complexity point of view even simple single-objective problems on weighted graphs like shortest paths or minimum spanning trees become NP-hard when they encounter at least two weight functions. In addition, the size of the Pareto front is often exponential for discrete problems and even infinite for continuous ones.
Evolutionary algorithms are frequently used to solve multi-objective optimization problems. Often, it is very hard to formally define the optimization that current state-of-the-art approaches work with. We have developed a new evolutionary multi-objective algorithm (called AGE) that works with a formal notion of approximation. The framework of our algorithm allows to work with various formal notions of approximations. Our experimental results show that given a fixed time budget it outperforms current state-of-the-art approaches in terms of the desired additive approximation on standard benchmark functions. Additionally, it also performs better regarding the covered hypervolume. This holds, in particular, for problems with many objectives, which most other algorithms have difficulties dealing with.
SoftwareThe runtime of our algorithm AGE (IJCAI 2011 + GECCO 2013, see below) increases only linearly with the number of objectives. It was implemented for two widely-used libraries of (evolutionary) algorithms, and is available for download.
GECCO 2013 version: Source Code: jMetal implementation (Note, Author: Markus Wagner). The C implementation will come in a few weeks, stay tuned.
Note: the IJCAI 2011 code is available as well. However, it is recommended that you use the GECCO 2013 version due to the significant improvements. IJCAI 2011 version: jMetal implementation (Note, Author: Markus Wagner), Shark implementation.
A Fast Approximation-Guided Evolutionary Multi-Objective Algorithm
Markus Wagner and Frank Neumann
Proceedings, Genetic and Evolutionary Computation Conference (GECCO 2013)
Efficient Parent Selection for Approximation-Guided Evolutionary Multi-Objective Optimization
Markus Wagner and Tobias Friedrich
Proceedings, IEEE Conference on Evolutionary Computation (CEC 2013)
An Adaptive Data Structure for Evolutionary Multi-Objective Algorithms with Unbounded Archives
Joseph Yuen, Sophia Gao, Markus Wagner, and Frank Neumann
Proceedings, IEEE World Congress on Computational Intelligence: Congress on Evolutionary Computation (WCCI/CEC 2012)
PDF | Bibtex | Abstract
Approximation-Guided Evolutionary Multi-Objective Optimization [the original AGE paper]
Karl Bringmann, Tobias Friedrich, Frank Neumann, and Markus Wagner
Proceedings, 21nd International Joint Conference on Artificial Intelligence (IJCAI 2011)
PDF | BibTeX | Abstract | Errata
Benefits and drawbacks for the use of epsilon-dominance in evolutionary multi-objective optimization
Christian Horoba and Frank Neumann
Proceedings, Genetic and Evolutionary Computation Conference (GECCO 2008)