Non-uniform mutation rates for problems with unknown solution lengths

Stephan CATHABARD, Per Kristian LEHRE, Xin YAO

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

21 Citations (Scopus)

Abstract

Many practical optimisation problems allow candidate solutions of varying lengths, and where the length of the optimal solution is thereby a priori unknown. We suggest that non-uniform mutation rates can be beneficial when solving such problems. In particular, we consider a mutation operator that flips each bit with a probability that is inversely proportional to the bit position, rather than the bitstring length. The runtime of the (1+1) EA using this mutation operator is analysed rigorously on standard example functions. Furthermore, the behaviour of the new mutation operator is investigated empirically on a real world software engineering problem that has variable, and unknown solution lengths. The results show how the speedup that can be achieved with the new operator depends on the distribution of the solution lengths in the solution space. We consider a truncated geometric distribution, and show that the new operator can yield exponentially faster runtimes for some parameters of this distribution. The experimental results show that the new mutation operator leads to dramatically shorter runtimes on a class of instances of the software engineering problem that is conjectured to have short solutions on average. © 2011 ACM.
Original languageEnglish
Title of host publicationFOGA'11 - Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI
Pages173-180
Number of pages8
DOIs
Publication statusPublished - 5 Jan 2011
Externally publishedYes

Fingerprint

Dive into the research topics of 'Non-uniform mutation rates for problems with unknown solution lengths'. Together they form a unique fingerprint.

Cite this