Optimal Mutation Rates for the (1+λ) EA on OneMax

Maxim Buzdalov, Carola Doerr

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

11 Citations (Scopus)
39 Downloads (Pure)

Abstract

The OneMax problem, alternatively known as the Hamming distance problem, is often referred to as the “drosophila of evolutionary computation (EC)”, because of its high relevance in theoretical and empirical analyses of EC approaches. It is therefore surprising that even for the simplest of all mutation-based algorithms, Randomized Local Search and the (1 + 1) EA, the optimal mutation rates were determined only very recently, in a GECCO 2019 poster.

In this work, we extend the analysis of optimal mutation rates to two variants of the (1+λ) EA and to the (1+λ) RLS. To do this, we use dynamic programming and, for the (1+λ) EA, numeric optimization, both requiring Θ(n3) time for problem dimension n. With this in hand, we compute for all population sizes λ∈{2i∣0≤i≤18} and for problem dimension n∈{1000,2000,5000} which mutation rates minimize the expected running time and which ones maximize the expected progress. Our results do not only provide a lower bound against which we can measure common evolutionary approaches, but we also obtain insight into the structure of these optimal parameter choices. For example, we show that, for large population sizes, the best number of bits to flip is not monotone in the distance to the optimum. We also observe that the expected remaining running times are not necessarily unimodal for the (1+λ) EA0→1 with shifted mutation.
Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XVI
EditorsThomas Bäck, Mike Preuss, André Deutz, Michael Emmerich, Hao Wang, Carola Doerr, Heike Trautmann
PublisherSpringer Nature
Pages574-587
Number of pages14
ISBN (Electronic)978-3-030-58115-2
ISBN (Print)978-3-030-58114-5
DOIs
Publication statusPublished - 02 Sept 2020

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Nature
Volume12270
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Parameter Control
  • Optimal Mutation Rates
  • Population-based Algorithms
  • OneMax

Fingerprint

Dive into the research topics of 'Optimal Mutation Rates for the (1+λ) EA on OneMax'. Together they form a unique fingerprint.

Cite this