Analyzing Randomized Search Heuristics: Tools from Probability Theory

Benjamin Doerr

doi:10.1142/9789814282673-1

Analyzing Randomized Search Heuristics: Tools from Probability Theory

Benjamin Doerr

Max-Planck-Institut fur Informatik

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Chapitre › Revue par des pairs

70 Citations (Scopus)

Résumé

In this chapter, we collect a few probabilistic tools that are useful for analyzing randomized search heuristics. This includes elementary mate¬rial like Markov, Chebyshev and Chernoff bounds, but also lesser known topics like dealing with sums of random variables that are only close to being independent or a strong lower bound for the time needed by the coupon collector process. Such results, while also of general inter¬est, seem to be particularly useful in the analysis of randomized search heuristics.

langue originale	Anglais
titre	Theory of Randomized Search Heuristics
Sous-titre	Foundations and Recent Developments
Editeur	World Scientific Publishing Co.
Pages	1-20
Nombre de pages	20
ISBN (Electronique)	9789814282673
ISBN (imprimé)	9814282669, 9789814282666
Les DOIs	https://doi.org/10.1142/9789814282673-1
état	Publié - 1 janv. 2011
Modification externe	Oui

Accès au document

10.1142/9789814282673-1

Contient cette citation

@inbook{8959c4d46794471bb646e4d38a77d2b9,

title = "Analyzing Randomized Search Heuristics: Tools from Probability Theory",

abstract = "In this chapter, we collect a few probabilistic tools that are useful for analyzing randomized search heuristics. This includes elementary mate¬rial like Markov, Chebyshev and Chernoff bounds, but also lesser known topics like dealing with sums of random variables that are only close to being independent or a strong lower bound for the time needed by the coupon collector process. Such results, while also of general inter¬est, seem to be particularly useful in the analysis of randomized search heuristics.",

author = "Benjamin Doerr",

note = "Publisher Copyright: {\textcopyright} 2011 by World Scientific Publishing Co. Pte. Ltd.",

year = "2011",

month = jan,

day = "1",

doi = "10.1142/9789814282673-1",

language = "English",

isbn = "9814282669",

pages = "1--20",

booktitle = "Theory of Randomized Search Heuristics",

publisher = "World Scientific Publishing Co.",

}

TY - CHAP

T1 - Analyzing Randomized Search Heuristics

T2 - Tools from Probability Theory

AU - Doerr, Benjamin

PY - 2011/1/1

Y1 - 2011/1/1

N2 - In this chapter, we collect a few probabilistic tools that are useful for analyzing randomized search heuristics. This includes elementary mate¬rial like Markov, Chebyshev and Chernoff bounds, but also lesser known topics like dealing with sums of random variables that are only close to being independent or a strong lower bound for the time needed by the coupon collector process. Such results, while also of general inter¬est, seem to be particularly useful in the analysis of randomized search heuristics.

AB - In this chapter, we collect a few probabilistic tools that are useful for analyzing randomized search heuristics. This includes elementary mate¬rial like Markov, Chebyshev and Chernoff bounds, but also lesser known topics like dealing with sums of random variables that are only close to being independent or a strong lower bound for the time needed by the coupon collector process. Such results, while also of general inter¬est, seem to be particularly useful in the analysis of randomized search heuristics.

U2 - 10.1142/9789814282673-1

DO - 10.1142/9789814282673-1

M3 - Chapter

AN - SCOPUS:85129052535

SN - 9814282669

SN - 9789814282666

SP - 1

EP - 20

BT - Theory of Randomized Search Heuristics

PB - World Scientific Publishing Co.

ER -

Analyzing Randomized Search Heuristics: Tools from Probability Theory

Résumé

Accès au document

Empreinte digitale

Contient cette citation