License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.420
URN: urn:nbn:de:0030-drops-33920
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3392/
Go to the corresponding LIPIcs Volume Portal

Witt, Carsten

Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation

pdf-format:
8.pdf (0.6 MB)

Abstract

The analysis of randomized search heuristics on classes of functions
is fundamental for the understanding of the underlying stochastic
process and the development of suitable proof techniques. Recently,
remarkable progress has been made in bounding the expected
optimization time of the simple (1+1) EA on the class of linear
functions. We improve the best known bound in this setting from
(1.39+o(1))(en ln n) to (en ln n)+O(n) in expectation and with high
probability, which is tight up to lower-order terms. Moreover, upper
and lower bounds for arbitrary mutations probabilities p are derived,
which imply expected polynomial optimization time as long as
p=O((ln n)/n) and which are tight if p=c/n for a constant c. As a
consequence, the standard mutation probability p=1/n is optimal for
all linear functions, and the (1+1) EA is found to be an optimal
mutation-based algorithm. Furthermore, the algorithm turns out to be
surprisingly robust since large neighborhood explored by the mutation
operator does not disrupt the search.

BibTeX - Entry

@InProceedings{witt:LIPIcs:2012:3392,
  author =	{Carsten Witt},
  title =	{{Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{420--431},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3392},
  URN =		{urn:nbn:de:0030-drops-33920},
  doi =		{10.4230/LIPIcs.STACS.2012.420},
  annote =	{Keywords: Randomized Search Heuristics, Evolutionary Algorithms, Linear Functions, Running Time Analysis}
}

Keywords: Randomized Search Heuristics, Evolutionary Algorithms, Linear Functions, Running Time Analysis
Collection: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue Date: 2012
Date of publication: 24.02.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI