Workshop Theory of Randomized Search Heuristics

(colocated with ICALP 2007)


Plateaus Can Be Harder in Multi-Objective Optimization

by Tobias Friedrich, Nils Hebbinghaus, Frank Neumann

In recent years a lot of progress has been made in understanding the behavior of evolutionary computation methods for single- and multi-objective problems. Our aim is to analyze the diversity mechanisms that are implicitly used in evolutionary algorithms for multi-objective problems by rigorous runtime analyses. We show that, even if the population size is small, the runtime can be exponential where corresponding single-objective problems are optimized within polynomial time. To illustrate this behavior we analyze a simple plateau function in a first step and extend our result to a class of instances of the well-known SetCover problem.

Back to mainpage