On the impact of the mutation-selection balance on the runtime of evolutionary algorithms

Per Kristian LEHRE, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

12 Citations (Scopus)


The interplay between the mutation operator and the selection mechanism plays a fundamental role in the behaviour of evolutionary algorithms. However, this interplay is still not completely understood. This paper presents a rigorous runtime analysis of a non-elitistic population based evolutionary algorithm that uses the linear ranking selection mechanism. The analysis focuses on how the balance between parameter η controlling the selection pressure in linear ranking selection, and parameter Χ controlling the bit-wise mutation rate impacts the expected runtime. The results point out situations where a correct balance between selection pressure and mutation rate is essential for finding the optimal solution in polynomial time. In particular, it is shown that there exist fitness functions which under a certain assumption can be solved in polynomial time if the ratio between parameters η and Χ is appropriately tuned to the problem instance class, but where a small change in this ratio can increase the runtime exponentially. Furthermore, it is shown that the appropriate parameter choice depends on the characteristics of the fitness function. Hence there does in general not exists a problem-independent optimal balance between mutation rate and selection pressure. The results are obtained using new techniques based on branching processes. Copyright 2009 ACM.
Original languageEnglish
Title of host publicationProceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09
Number of pages12
Publication statusPublished - 9 Jan 2009
Externally publishedYes


  • Branching processes
  • Evolutionary algorithms
  • Runtime analysis


Dive into the research topics of 'On the impact of the mutation-selection balance on the runtime of evolutionary algorithms'. Together they form a unique fingerprint.

Cite this