Self-adjusting evolutionary algorithms for multimodal optimization

DOI10.1007/S00453-022-00933-ZzbMATH Open1490.68307arXiv2004.03266OpenAlexW4220673243MaRDI QIDQ2144276FDOQ2144276

Authors: Amirhossein Rajabi, Carsten Witt 

Publication date: 1 June 2022

Published in: Algorithmica (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2004.03266

Recommendations

• The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate
• Stagnation detection with randomized local search
• Runtime analysis for self-adaptive mutation rates
• Evolutionary self-adaptation: a survey of operators and strategy parameters
• scientific article; zbMATH DE number 1975085

zbMATH Keywords

runtime analysisrandomized search heuristicsmultimodal functionsself-adjusting algorithms

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50)

Cites Work

• Title not available (Why is that?)
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Tight bounds on the optimization time of a randomized search heuristic on linear functions
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Analyzing evolutionary algorithms. The computer science perspective.
• Adaptive population models for offspring populations and parallel evolutionary algorithms
• On the analysis of the \((1+1)\) evolutionary algorithm
• Population size versus runtime of a simple evolutionary algorithm
• The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate
• Optimal static and self-adjusting parameter choices for the \((1+(\lambda ,\lambda ))\) genetic algorithm
• Runtime analysis for self-adaptive mutation rates
• Static and self-adjusting mutation strengths for multi-valued decision variables
• A tight runtime analysis for the \((1+(\lambda,\lambda))\) GA on LeadingOnes
• Stagnation detection with randomized local search
• Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
• The benefits and limitations of voting mechanisms in evolutionary optimisation
• Theory of evolutionary computation. Recent developments in discrete optimization

Cited In (11)

• Title not available (Why is that?)
• Choosing the right algorithm with hints from complexity theory
• Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution
• Lower bounds from fitness levels made easy
• An extended jump functions benchmark for the analysis of randomized search heuristics
• Runtime analysis for permutation-based evolutionary algorithms
• Stagnation detection in highly multimodal fitness landscapes
• Auto-tuning strategy for evolutionary algorithms: Balancing between exploration and exploitation
• Self-adjusting offspring population sizes outperform fixed parameters on the Cliff function
• Stagnation detection meets fast mutation
• Decomposition-based multiobjective optimization for nonlinear equation systems with many and infinitely many roots

This page was built for publication: Self-adjusting evolutionary algorithms for multimodal optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2144276)