Stagnation detection with randomized local search

DOI10.1007/978-3-030-72904-2_10MaRDI QIDQ2233520zbMATH OpenOpenAlexFDO

Authors Amirhossein Rajabi, Carsten Witt

Publication date 18 October 2021

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

zbMATH Keywords

local searchruntime analysisrandomized search heuristicsmultimodal functionsself-adjusting algorithms

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms (68W40) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50)

Abstract: Recently a mechanism called stagnation detection was proposed that automatically adjusts the mutation rate of evolutionary algorithms when they encounter local optima. The so-called $SD-(1+1)EA$ introduced by Rajabi and Witt (GECCO 2020) adds stagnation detection to the classical $(1+1)EA$ with standard bit mutation, which flips each bit independently with some mutation rate, and raises the mutation rate when the algorithm is likely to have encountered local optima. In this paper, we investigate stagnation detection in the context of the $k$-bit flip operator of randomized local search that flips $k$ bits chosen uniformly at random and let stagnation detection adjust the parameter $k$. We obtain improved runtime results compared to the $SD-(1+1)EA$ amounting to a speed-up of up to $e=2.71dots$ Moreover, we propose additional schemes that prevent infinite optimization times even if the algorithm misses a working choice of $k$ due to unlucky events. Finally, we present an example where standard bit mutation still outperforms the local $k$-bit flip with stagnation detection.

Recommendations

• Principles of Stochastic Local Search
• A stochastic local search algorithm for constrained continuous global optimization
• Detection and Remediation of Stagnation in the Nelder--Mead Algorithm Using a Sufficient Decrease Condition
• Stopping and restarting strategy for stochastic sequential search in global optimization
• Stagnation detection meets fast mutation
• Stagnation detection meets fast mutation
• Sequential Stopping Rules for Random Optimization Methods with Applications to Multistart Local Search
• Stochastic local search. Foundations and applications.

Cites work

• Optimal static and self-adjusting parameter choices for the (1+( , )) genetic algorithm
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate
• The impact of random initialization on the runtime of randomized search heuristics
• Theory of evolutionary computation. Recent developments in discrete optimization

Cited in

(10)

• A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions
• 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
• Self-adjusting evolutionary algorithms for multimodal optimization
• When move acceptance selection hyper-heuristics outperform metropolis and elitist evolutionary algorithms and when not
• Do additional target points speed up evolutionary algorithms?
• How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys
• Stagnation detection meets fast mutation
• Stagnation detection meets fast mutation

This page was built for publication: Stagnation detection with randomized local search

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