Non-uniform Mutation Rates for Problems with Unknown Solution Lengths

Stephan Cathabard, Per Kristian Lehre, Xin Yao

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


    Many practical optimisation problems allow candidate solu- tions of varying lengths, and where the length of the opti- mal 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 oper- ator 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 func- tions. Furthermore, the behaviour of the new mutation op- erator is investigated empirically on a real world software engineering problem that has variable, and unknown solu- tion 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 engi- neering problem that is conjectured to have short solutions on average.
    Original languageEnglish
    Title of host publicationFOGA '11 - Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms
    Publication date2011
    ISBN (Print)978-1-4503-0633-1
    Publication statusPublished - 2011
    Event11th Foundations of Genetic Algorithms workshop Schwarzenberg - Schwarzenberg, Austria
    Duration: 5 Jan 20119 Jan 2011
    Conference number: 11


    Workshop11th Foundations of Genetic Algorithms workshop Schwarzenberg
    Internet address

    Cite this