Authors: K. Bringmann, T. Friedrich, F. Neumann, M. Wagner

Summary: Multi-objective optimization problems arise frequently in applications but can often only be solved approximately by heuristic approaches. Evolutionary algorithms have been widely used to tackle multi-objective problems. These algorithms use different measures to ensure diversity in the objective space but are not guided by a formal notion of approximation. This leaves the optimization goal of these algorithms unclear and  makes it hard to rigorously compare the different approaches with respect to the results obtained. We have presented a framework for evolutionary multi-objective optimization that allows to work with a formal notion of approximation. This approximation-guided evolutionary algorithm (AGE) has a worst-case runtime linear in the number of objectives. We showed in [Ref. 1] that only hypervolume-based algorithms achieve comparable approximation ratios of the Pareto front, but at the cost of runtimes exponential in the number of objectives. In [Ref. 2] we compare AGE with two additional algorithms which use fast hypervolume-approximations to guide their search. This significantly speeds up the runtime of the hypervolume-based algorithms, which now allows a comparison of the underlying selection schemes. Our experimental results show that the approximation-guided algorithm outperforms the hypervolume-based algorithms regarding the achieved approximation and is competitive regarding the achieved total hypervolume.

Bibliography:

1. 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 1198-1203, 2011. (download here)
2. full version under submission.

Errata: The conference version [Ref. 1] contains two errors:

1. The word "maximal" in line 20 of algorithm 4 should be replaced by "minimal".
2. The dominance conditions in lines 3 and 4 of algorithm 2 have to be turned around: a<p becomes p>a, and a≥p becomes a≤p. The version available here is the corrected version.

Resources:

1. Open-source implementation of AGE in Java within the JMetal framework
2. Open-source implementation of AGE in C++ within the Shark library
3. More information on AGE at the University of Adelaide