Further Enquiries

School of Computer and Mathematical Sciences
Ingkarni Wardli Building
The University of Adelaide
SA 5005
AUSTRALIA
Email

Telephone: +61 8 8313 5586
Facsimile: +61 8 8313 4366

Research Projects

Approximation Guided Evolution - A Multi-Objective Optimization Algorithm

Most 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.

Software

The 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.

Publications

  • A Fast Approximation-Guided Evolutionary Multi-Objective Algorithm
    Markus Wagner and Frank Neumann
    Proceedings, Genetic and Evolutionary Computation Conference (GECCO 2013)
    PDF
  • Efficient Parent Selection for Approximation-Guided Evolutionary Multi-Objective Optimization
    Markus Wagner and Tobias Friedrich
    Proceedings, IEEE Conference on Evolutionary Computation (CEC 2013)
    PDF
  • 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)
    PDF

Additional Resources