Self-adaptation of mutation rates in non-elitist populations

Lehre, Per Kristian; Dang, Duc-Cuong

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 level-based 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.

Citation

Lehre, P. K., & Dang, D.-C. (2016, September). Self-adaptation of mutation rates in non-elitist populations. Presented at 14th International Conference on Parallel Problem Solving from Nature, Edinburgh, UK

• Presentation Conference Type: Edited Proceedings
• Conference Name: 14th International Conference on Parallel Problem Solving from Nature
• Start Date: Sep 17, 2016
• End Date: Sep 21, 2016
• Acceptance Date: May 27, 2016
• Online Publication Date: Aug 31, 2016
• Publication Date: Aug 31, 2016
• Deposit Date: Jun 24, 2016
• Publicly Available Date: Aug 31, 2016
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Pages: 803–813
• Series Title: Lecture notes in computer science
• Series Number: 9921
• Series ISSN: 1611-3349
• Book Title: Parallel problem solving from nature – PPSN XIV
• ISBN: 978-3-319-45822-9
• DOI: https://doi.org/10.1007/978-3-319-45823-6_75
• Public URL: https://nottingham-repository.worktribe.com/output/788353
• Publisher URL: https://link.springer.com/chapter/10.1007/978-3-319-45823-6_75
• Contract Date: Jun 24, 2016