How to escape local optima in black box optimisation: when non-elitism outperforms elitism

DOI10.1007/s00453-017-0369-2zbMath1390.68605OpenAlexW2753470076WikidataQ59607685 ScholiaQ59607685MaRDI QIDQ1750360

Pietro S. Oliveto, Tiago Paixão, Barbora Trubenová, Jorge Pérez Heredia, Dirk Sudholt

Publication date: 18 May 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://europepmc.org/articles/pmc6438649

zbMATH Keywords

simulated annealingpopulation geneticsevolutionary algorithmsMetropolis algorithmruntime analysisblack-box optimisationstrong selection weak mutation regime

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Derivative-free methods and methods using generalized derivatives (90C56) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Does comma selection help to cope with local optima? ⋮ When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms ⋮ Choosing the right algorithm with hints from complexity theory ⋮ More precise runtime analyses of non-elitist evolutionary algorithms in uncertain environments ⋮ An extended jump functions benchmark for the analysis of randomized search heuristics ⋮ Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem ⋮ On the analysis of trajectory-based search algorithms: when is it beneficial to reject improvements? ⋮ How to escape local optima in black box optimisation: when non-elitism outperforms elitism

Cites Work

• Unnamed Item
• Runtime analysis of non-elitist populations: from classical optimisation to partial information
• Hybridizing evolutionary algorithms with variable-depth search to overcome local optima
• Toward a unifying framework for evolutionary processes
• Improved time complexity analysis of the simple genetic algorithm
• The impact of parametrization in memetic evolutionary algorithms
• Landscapes, operators and heuristic search
• A new adaptive multi-start technique for combinatorial global optimizations
• The Metropolis algorithm for graph bisection
• On the analysis of the \((1+1)\) evolutionary algorithm
• How to escape local optima in black box optimisation: when non-elitism outperforms elitism
• The analysis of evolutionary algorithms -- A proof that crossover really can help
• On the runtime analysis of the simple genetic algorithm
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• Towards a runtime comparison of natural and artificial evolution
• On easiest functions for mutation operators in bio-inspired optimisation
• A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation
• Convergence and finite-time behavior of simulated annealing
• The time complexity of maximum matching by simulated annealing
• Automata, Languages and Programming
• Tail bounds on hitting times of randomized search heuristics using variable drift analysis
• Drift analysis and average time complexity of evolutionary algorithms