Giel, Oliver
Runtime Analysis of a Simple MultiObjective Evolutionary Algorithm
Abstract
Practical knowledge on the design and
application of multiobjective evolutionary
algorithms (MOEAs) is available but wellfounded
theoretical analyses of the runtime are rare.
Laumanns, Thiele, Zitzler, Welzel and Deb (2002)
have started such an analysis for two simple
mutationbased algorithms including SEMO.
These algorithms search locally in the
neighborhood of their current population by
selecting an individual and flipping one
randomly chosen bit. Due to its local search
operator, SEMO cannot escape from local optima,
and, therefore, has no finite expected runtime
in general.
In this talk, we investigate the runtime of
a variant of SEMO whose mutation operator
flips each bit independently. It is proven
that its expected runtime is O(n^n) for all
objective functions f: {0,1}^n > R^m, and
that there are bicriteria problems among the
hardest problem for this algorithm. Moreover,
for each d between 2 and n, a bicriteria
problem with expected runtime Theta(n^d) is
presented. This shows that bicriteria problems
cover the full range of potential runtimes of
this variant of SEMO. For the problem LOTZ
(LeadingOnesTrailing Zeroes), the runtime
does not increase substantially if we use the
global search operator. Finally, we consider
the problem MOCO (MultiObjectiveCountingOnes).
We show that the conjectured bound O((n^2)log n)
on the expected runtime is wrong for both
variants of SEMO. In fact, MOCO is almost a
worst case example for SEMO if we consider
the expected runtime; however, the runtime is
O((n^2)log n) with high probability. Some
ideas from the proof will be presented.
BibTeX  Entry
@InProceedings{giel:DSP:2005:271,
author = {Oliver Giel},
title = {Runtime Analysis of a Simple MultiObjective Evolutionary Algorithm},
booktitle = {Practical Approaches to MultiObjective Optimization},
year = {2005},
editor = {J{\"u}rgen Branke and Kalyanmoy Deb and Kaisa Miettinen and Ralph E. Steuer},
number = {04461},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2005/271},
annote = {Keywords: Runtime analysis, multiobjecive evolutionary algorithms}
}
2005
Keywords: 

Runtime analysis, multiobjecive evolutionary algorithms 
Seminar: 

04461  Practical Approaches to MultiObjective Optimization

Issue date: 

2005 
Date of publication: 

2005 