Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift

Per Kristian Lehre, Carsten Witt

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Drift analysis is one of the state-of-the-art techniques for the runtime analysis of randomized search heuristics (RSHs) such as evolutionary algorithms (EAs), simulated annealing etc. The vast majority of existing drift theorems yield bounds on the expected value of the hitting time for a target state, e. g., the set of optimal solutions, without making additional statements on the distribution of this time. We address this lack by providing a general drift theorem that includes bounds on the upper and lower tail of the hitting time distribution. The new tail bounds are applied to prove very precise sharp-concentration results on the running time of a simple EA on standard benchmark problems, including the class of general linear functions. The usefulness of the theorem outside the theory of RSHs is demonstrated by deriving tail bounds on the number of cycles in random permutations. All these results handle a position-dependent (variable) drift that was not covered by previous drift theorems with tail bounds. Moreover, our theorem can be specialized into virtually all existing drift theorems with drift towards the target from the literature. Finally, user-friendly specializations of the general drift theorem are given.
Original languageEnglish
Title of host publicationProceedings of the 25th International Symposium on Algorithms and Computation, ISAAC 2014
EditorsHee-Kap Ahn, Chan-Su Shin
PublisherSpringer
Publication date2014
Pages686-697
ISBN (Print)978-3-319-13074-3
ISBN (Electronic)978-3-319-13075-0
DOIs
Publication statusPublished - 2014
Event25th International Symposium on Algorithms and Computation - Jeonju, Korea, Democratic People's Republic of
Duration: 15 Dec 201417 Dec 2014
Conference number: 25
http://tcs.postech.ac.kr/isaac2014/

Conference

Conference25th International Symposium on Algorithms and Computation
Number25
CountryKorea, Democratic People's Republic of
CityJeonju
Period15/12/201417/12/2014
Internet address
SeriesLecture Notes in Computer Science
Number8889
ISSN0302-9743

Fingerprint Dive into the research topics of 'Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift'. Together they form a unique fingerprint.

Cite this