Runtime Analysis of a Simple Multi-Objective Evolutionary Algorithm

Abstract

Practical knowledge on the design and 
application of multi-objective evolutionary
algorithms (MOEAs) is available but well-founded
theoretical analyses of the runtime are rare.
Laumanns, Thiele, Zitzler, Welzel and Deb (2002)
have started such an analysis for two simple
mutation-based 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 
(Leading-Ones-Trailing Zeroes), the runtime 
does not increase substantially if we use the 
global search operator. Finally, we consider
the problem MOCO (Multi-Objective-Counting-Ones). 
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.