Self-adaptation of Mutation Rates in Non-elitist Populations
This addresses the challenge of costly manual parameter tuning for researchers and practitioners in optimization, though it is incremental as it builds on prior work in continuous optimization.
The paper tackled the problem of automated parameter tuning in evolutionary algorithms for discrete optimization by analyzing self-adaptation of mutation rates, showing that it leads to exponential speedups over fixed-rate methods.
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.