Runtime Analysis of Evolutionary Algorithms for Discrete Optimization

Peter S. OLIVETO, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsBook ChapterResearchpeer-review

33 Citations (Scopus)

Abstract

Theoretical studies of evolutionary algorithms (EAs) have existed since the seventies when EAs started to become popular. These early studies contributed towards the understanding of EAs but did not explain their performance in terms of their dynamical or limit behaviour. Only in the nineties the first convergence and time complexity results appeared for simple algorithms and toy problems. Nowadays, it is possible to analyse the time complexity of more complicated algorithms for combinatorial optimization problems with practical applications. This chapter overviews the most popular mathematical techniques used in the runtime analysis of EAs and gives some simple examples of their application. © 2011 by World Scientific Publishing Co. Pte. Ltd.
Original languageEnglish
Title of host publicationTheory of Randomized Search Heuristics: Foundations and Recent Developments
EditorsAnne AUGER, Benjamin DOERR
PublisherWorld Scientific Publishing Co.
Pages21-52
Number of pages32
Volume1
ISBN (Print)9789814282673
DOIs
Publication statusPublished - Feb 2011
Externally publishedYes

Publication series

NameSeries on Theoretical Computer Science
PublisherWorld Scientific Publishing Co.
ISSN (Print)1793-849X

Fingerprint

Dive into the research topics of 'Runtime Analysis of Evolutionary Algorithms for Discrete Optimization'. Together they form a unique fingerprint.

Cite this