Optimal Mutation Rates for the (1+ λ) EA on OneMax Through Asymptotically Tight Drift Analysis

Christian Gießen*, Carsten Witt

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

45 Downloads (Pure)

Abstract

We study the (1+λ) EA, a classical population-based evolutionary algorithm, with mutation probability c / n, where c> 0 and λ are constant, on the benchmark function OneMax, which counts the number of 1-bits in a bitstring. We improve a well-established result that allows to determine the first hitting time from the expected progress (drift) of a stochastic process, known as the variable drift theorem. Using our improved result, we show that upper and lower bounds on the expected runtime of the (1+λ) EA obtained from variable drift theorems are at most apart by a small lower order term if the exact drift is known. This reduces the analysis of expected optimization time to finding an exact expression for the drift. We then give an exact closed-form expression for the drift and develop a method to approximate it very efficiently, enabling us to determine approximate optimal mutation rates for the (1+λ) EA for various parameter settings of c and λ and also for moderate sizes of n. This makes the need for potentially lengthy and costly experiments in order to optimize c for fixed n and λ for the optimization of OneMax unnecessary. Interestingly, even for moderate n and not too small λ it turns out that mutation rates up to 10% larger than the asymptotically optimal rate 1 / n minimize the expected runtime. However, in absolute terms the expected runtime does not change by much when replacing 1 / n with the optimal mutation rate.
Original languageEnglish
JournalAlgorithmica
Volume80
Issue number5
Pages (from-to)1710-1731
ISSN0178-4617
DOIs
Publication statusPublished - 2018

Keywords

  • Runtime analysis
  • Populations
  • Mutation

Cite this