  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.
