Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results

Pietro S. OLIVETO, Jun HE, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

182 Citations (Scopus)


Computational time complexity analyzes of evolutionary algorithms (EAs) have been performed since the mid-nineties. The first results were related to very simple algorithms, such as the (1+1)-EA, on toy problems. These efforts produced a deeper understanding of how EAs perform on different kinds of fitness landscapes and general mathematical tools that may be extended to the analysis of more complicated EAs on more realistic problems. In fact, in recent years, it has been possible to analyze the (1+1)-EA on combinatorial optimization problems with practical applications and more realistic population-based EAs on structured toy problems. This paper presents a survey of the results obtained in the last decade along these two research lines. The most common mathematical techniques are introduced, the basic ideas behind them are discussed and their elective applications are highlighted. Solred problems that were still open are enumerated as are those still awaiting for a solution. New questions and problems arisen in the meantime are also considered. © 2007 Institute of Automation, Chinese Academy of Sciences.
Original languageEnglish
Pages (from-to)281-293
Number of pages13
JournalInternational Journal of Automation and Computing
Issue number3
Publication statusPublished - Jul 2007
Externally publishedYes

Bibliographical note

This work was supported by an EPSRC grant (No. EP/C520696/1).


  • Combinatorial optimization
  • Computational complexity
  • Evolutionary algorithms
  • Evolutionary computation theory


Dive into the research topics of 'Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results'. Together they form a unique fingerprint.

Cite this