Self-adaptation of Mutation Rates in Non-elitist Populations

2016/06/17 by Dang, Duc-Cuong, Lehre, Per Kristian · 1 citation
#FOS: Biological sciences #FOS: Computer and information sciences #Neural and Evolutionary Computing (cs.NE) #Populations and Evolution (q-bio.PE)

paper · doi:10.48550/arxiv.1606.05551

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.

Cited by

• Tuning without Peeking: Provable Generalization Bounds and Robust LLM Post-Training

Related

• Self-adaptation in non-Elitist Evolutionary Algorithms on Discrete\n Problems with Unknown Structure
• Runtime Analysis for Self-adaptive Mutation Rates
• The Impact of Mutation Rate on the Computation Time of Evolutionary Dynamic Optimization
• Self-Adjusting Population Sizes for Non-Elitist Evolutionary Algorithms: Why Success Rates Matter
• On the Impact of Mutation-Selection Balance on the Runtime of Evolutionary Algorithms