The (1+$\lambda$) Evolutionary Algorithm with Self-Adjusting Mutation Rate

Abstract

We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring. We analyze how the $(1+\lambda )$ evolutionary algorithm with this self-adjusting mutation rate optimizes the OneMax test function. We prove that this dynamic version of the $(1+\lambda )$ EA finds the optimum in an expected optimization time (number of fitness evaluations) of $O(n\lambda /\log \lambda +n\log n)$. This time is asymptotically smaller than the optimization time of the classic $(1+\lambda )$ EA. Previous work shows that this performance is best-possible among all $\lambda$-parallel mutation-based unbiased black-box algorithms. This result shows that the new way of adjusting the mutation rate can find optimal dynamic parameter values on the fly. Since our adjustment mechanism is simpler than the ones previously used for adjusting the mutation rate and does not have parameters itself, we are optimistic that it will find other applications.

An extended abstract of this report appeared in the proceedings of the 2017 Genetic and Evolutionary Computation Conference (GECCO 2017), https://doi.org/10.1145/3071178.3071279. Version 2: several extensions, most notably regarding experimental results; Version 3: revised presentation and added more experiments

References in corpus (5)

• Runtime Analysis of the $(1+(\lambda ,\lambda ))$ Genetic Algorithm on Random Satisfiable 3-CNF Formulas
• The (1+$\lambda$) Evolutionary Algorithm with Self-Adjusting Mutation Rate
• An Elementary Analysis of the Probability That a Binomial Random Variable Exceeds Its Expectation
• Optimal Parameter Choices Through Self-Adjustment: Applying the 1/5-th Rule in Discrete Settings
• The Right Mutation Strength for Multi-Valued Decision Variables

Cited by in corpus (17)

• Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
• Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices
• Better Runtime Guarantees Via Stochastic Domination
• Benchmarking Discrete Optimization Heuristics with IOHprofiler
• The (1+$\lambda$) Evolutionary Algorithm with Self-Adjusting Mutation Rate
• Self-Adjusting Evolutionary Algorithms for Multimodal Optimization
• A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization
• An Elementary Analysis of the Probability That a Binomial Random Variable Exceeds Its Expectation
• Stagnation Detection with Randomized Local Search
• Towards a Theory-Guided Benchmarking Suite for Discrete Black-Box Optimization Heuristics: Profiling $(1+\lambda )$ EA Variants on OneMax and LeadingOnes
• An information-theoretic evolutionary algorithm
• Interpolating Local and Global Search by Controlling the Variance of Standard Bit Mutation
• Leveraging Benchmarking Data for Informed One-Shot Dynamic Algorithm Selection
• A Tight Runtime Analysis for the $(\mu +\lambda )$ EA
• Blending Dynamic Programming with Monte Carlo Simulation for Bounding the Running Time of Evolutionary Algorithms
• Sharp Bounds on the Runtime of the (1+1) EA via Drift Analysis and Analytic Combinatorial Tools
• Runtime Analysis for Self-adaptive Mutation Rates