Self-adaptation of mutation rates in non-elitist populations

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

External organisations

  • University of Nottingham

Abstract

The runtime of evolutionary algorithms (EAs) depends critically on their parameter settings, which are often problem-specific. Automated schemes for parameter tuning have been developed to alleviate the high costs of manual parameter tuning. Experimental results indicate that self-adaptation, where parameter settings are encoded in the genomes of individuals, can be effective in continuous optimisation. However, results in discrete optimisation have been less conclusive. Furthermore, a rigorous runtime analysis that explains how self-adaptation can lead to asymptotic speedups has been missing. This paper provides the first such analysis for discrete, population-based EAs. We apply levelbased analysis to show how a self-adaptive EA is capable of fine-tuning its mutation rate, leading to exponential speedups over EAs using fixed mutation rates.

Details

Original languageEnglish
Title of host publicationPPSN 2016
Subtitle of host publicationParallel Problem Solving from Nature – PPSN XIV
EditorsJulia Handl, Emma Hart, Peter R. Lewis, Manuel López-Ibáñez, Gabriela Ochoa, Ben Paechter
Publication statusPublished - 31 Aug 2016
Event14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 - Edinburgh, United Kingdom
Duration: 17 Sep 201621 Sep 2016

Publication series

NameLecture Notes in Computer Science (LNCS)
Volume9921
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameTheoretical Computer Science and General Issues (LNTCS)
Volume9921

Conference

Conference14th International Conference on Parallel Problem Solving from Nature, PPSN 2016
CountryUnited Kingdom
CityEdinburgh
Period17/09/1621/09/16