1 Search Results for "Giel, Oliver"


Document
Runtime Analysis of a Simple Multi-Objective Evolutionary Algorithm

Authors: Oliver Giel

Published in: Dagstuhl Seminar Proceedings, Volume 4461, Practical Approaches to Multi-Objective Optimization (2005)


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.

Cite as

Oliver Giel. Runtime Analysis of a Simple Multi-Objective Evolutionary Algorithm. In Practical Approaches to Multi-Objective Optimization. Dagstuhl Seminar Proceedings, Volume 4461, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{giel:DagSemProc.04461.19,
  author =	{Giel, Oliver},
  title =	{{Runtime Analysis of a Simple Multi-Objective Evolutionary Algorithm}},
  booktitle =	{Practical Approaches to Multi-Objective Optimization},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4461},
  editor =	{J\"{u}rgen Branke and Kalyanmoy Deb and Kaisa Miettinen and Ralph E. Steuer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04461.19},
  URN =		{urn:nbn:de:0030-drops-2711},
  doi =		{10.4230/DagSemProc.04461.19},
  annote =	{Keywords: Runtime analysis, multi-objecive evolutionary algorithms}
}
  • Refine by Author
  • 1 Giel, Oliver

  • Refine by Classification

  • Refine by Keyword
  • 1 Runtime analysis
  • 1 multi-objecive evolutionary algorithms

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2005

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail