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

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2012

Documents

DOI

View graph of relations

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.
Original languageEnglish
Title of host publication29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
EditorsChristoph Dürr, Thomas Wilke
Number of pages12
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Publication date2012
Pages420-431
ISBN (print)978-3-939897-35-4
DOIs
StatePublished

Conference

Conference29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
CountryFrance
CityParis
Period29/02/1203/03/12
Internet addresshttp://stacs2012.lip6.fr/
NameLeibniz International Proceedings in Informatics
Volume14
ISSN (Print)1868-8969

Bibliographical note

Licensed under Creative Commons License NC-ND.

CitationsWeb of Science® Times Cited: No match on DOI

Keywords

  • Randomized Search Heuristics, Evolutionary Algorithms, Linear Functions, Running Time Analysis
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 12674148