Self-Adjusting Evolutionary Algorithms for Multimodal Optimization

Abstract

Recent theoretical research has shown that self-adjusting and self-adaptive mechanisms can provably outperform static settings in evolutionary algorithms for binary search spaces. However, the vast majority of these studies focuses on unimodal functions which do not require the algorithm to flip several bits simultaneously to make progress. In fact, existing self-adjusting algorithms are not designed to detect local optima and do not have any obvious benefit to cross large Hamming gaps. We suggest a mechanism called stagnation detection that can be added as a module to existing evolutionary algorithms (both with and without prior self-adjusting algorithms). Added to a simple (1+1) EA, we prove an expected runtime on the well-known Jump benchmark that corresponds to an asymptotically optimal parameter setting and outperforms other mechanisms for multimodal optimization like heavy-tailed mutation. We also investigate the module in the context of a self-adjusting (1+$\lambda$) EA and show that it combines the previous benefits of this algorithm on unimodal problems with more efficient multimodal optimization. To explore the limitations of the approach, we additionally present an example where both self-adjusting mechanisms, including stagnation detection, do not help to find a beneficial setting of the mutation rate. Finally, we investigate our module for stagnation detection experimentally.

26 pages. Full version of a paper appearing at GECCO 2020

References in corpus (6)

• Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices
• The (1+$\lambda$) Evolutionary Algorithm with Self-Adjusting Mutation Rate
• Self-Adjusting Evolutionary Algorithms for Multimodal Optimization
• A Tight Runtime Analysis for the cGA on Jump Functions---EDAs Can Cross Fitness Valleys at No Extra Cost
• Towards a Theory-Guided Benchmarking Suite for Discrete Black-Box Optimization Heuristics: Profiling $(1+\lambda )$ EA Variants on OneMax and LeadingOnes
• Offspring Population Size Matters when Comparing Evolutionary Algorithms with Self-Adjusting Mutation Rates

Cited by in corpus (15)

• Self-Adjusting Evolutionary Algorithms for Multimodal Optimization
• The Runtime of the Compact Genetic Algorithm on Jump Functions
• Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover
• A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization
• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives
• Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
• Stagnation Detection with Randomized Local Search
• A Rigorous Runtime Analysis of the $(1+(\lambda ,\lambda ))$ GA on Jump Functions
• Lower Bounds from Fitness Levels Made Easy
• Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution
• Towards a Stronger Theory for Permutation-based Evolutionary Algorithms
• The $(1+(\lambda ,\lambda ))$ Global SEMO Algorithm
• Drift Analysis with Fitness Levels for Elitist Evolutionary Algorithms
• Evolutionary Algorithms with Self-adjusting Asymmetric Mutation
• An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics