Self-adaptation in non-Elitist Evolutionary Algorithms on Discrete Problems with Unknown Structure

A key challenge to make effective use of evolutionary algorithms is to choose\nappropriate settings for their parameters. However, the appropriate parameter\nsetting generally depends on the structure of the optimisation problem, which\nis often unknown to the user. Non-deterministic parameter control mechanisms\nadjust parameters using information obtained from the evolutionary process.\nSelf-adaptation -- where parameter settings are encoded in the chromosomes of\nindividuals and evolve through mutation and crossover -- is a popular parameter\ncontrol mechanism in evolutionary strategies. However, there is little\ntheoretical evidence that self-adaptation is effective, and self-adaptation has\nlargely been ignored by the discrete evolutionary computation community.\n Here we show through a theoretical runtime analysis that a non-elitist,\ndiscrete evolutionary algorithm which self-adapts its mutation rate not only\noutperforms EAs which use static mutation rates on \\leadingones, but also\nimproves asymptotically on an EA using a state-of-the-art control mechanism.\nThe structure of this problem depends on a parameter $k$, which is \\emph{a\npriori} unknown to the algorithm, and which is needed to appropriately set a\nfixed mutation rate. The self-adaptive EA achieves the same asymptotic runtime\nas if this parameter was known to the algorithm beforehand, which is an\nasymptotic speedup for this problem compared to all other EAs previously\nstudied. An experimental study of how the mutation-rates evolve show that they\nrespond adequately to a diverse range of problem structures.\n These results suggest that self-adaptation should be adopted more broadly as\na parameter control mechanism in discrete, non-elitist evolutionary algorithms.\n