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

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

Standard

Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation. / Witt, Carsten.

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). ed. / Christoph Dürr; Thomas Wilke. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2012. p. 420-431 (Leibniz International Proceedings in Informatics, Vol. 14).

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

Harvard

Witt, C 2012, 'Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation'. in C Dürr & T Wilke (eds), 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, pp. 420-431. Leibniz International Proceedings in Informatics, vol. 14, , 10.4230/LIPIcs.STACS.2012.420

APA

Witt, C. (2012). Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation. In C. Dürr, & T. Wilke (Eds.), 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). (pp. 420-431). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. (Leibniz International Proceedings in Informatics, Vol. 14). 10.4230/LIPIcs.STACS.2012.420

CBE

Witt C. 2012. Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation. Dürr C, Wilke T, editors. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. pp. 420-431. (Leibniz International Proceedings in Informatics, Vol. 14). Available from: 10.4230/LIPIcs.STACS.2012.420

MLA

Witt, Carsten "Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation". and Dürr, Christoph Wilke, Thomas (ed.). 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. 2012. 420-431. (Leibniz International Proceedings in Informatics, Volume 14). Available: 10.4230/LIPIcs.STACS.2012.420

Vancouver

Witt C. Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation. In Dürr C, Wilke T, editors, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. 2012. p. 420-431. (Leibniz International Proceedings in Informatics, Vol. 14). Available from: 10.4230/LIPIcs.STACS.2012.420

Author

Witt, Carsten / Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation.

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). ed. / Christoph Dürr; Thomas Wilke. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2012. p. 420-431 (Leibniz International Proceedings in Informatics, Vol. 14).

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

Bibtex

@inbook{b506dcb9d70745bfa0313376f954d2d8,
title = "Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation",
keywords = "Randomized Search Heuristics, Evolutionary Algorithms, Linear Functions, Running Time Analysis",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany",
author = "Carsten Witt",
year = "2012",
doi = "10.4230/LIPIcs.STACS.2012.420",
editor = "Christoph Dürr and Thomas Wilke",
isbn = "978-3-939897-35-4",
series = "Leibniz International Proceedings in Informatics",
pages = "420-431",
booktitle = "29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)",

}

RIS

TY - GEN

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

A1 - Witt,Carsten

AU - Witt,Carsten

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Randomized Search Heuristics

KW - Evolutionary Algorithms

KW - Linear Functions

KW - Running Time Analysis

U2 - 10.4230/LIPIcs.STACS.2012.420

DO - 10.4230/LIPIcs.STACS.2012.420

SN - 978-3-939897-35-4

BT - 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

T2 - 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

A2 - Wilke,Thomas

ED - Wilke,Thomas

T3 - Leibniz International Proceedings in Informatics

T3 - en_GB

SP - 420

EP - 431

ER -