Populations can be essential in tracking dynamic optima

DOI10.1007/S00453-016-0187-YMaRDI QIDQ2362363zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Duc-Cuong Dang, Per Kristian Lehre, Thomas Jansen

Publication date 7 July 2017

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

runtime analysisdynamic optimisationpopulation-based algorithm

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)

Abstract: Real-world optimisation problems are often dynamic. Previously good solutions must be updated or replaced due to changes in objectives and constraints. It is often claimed that evolutionary algorithms are particularly suitable for dynamic optimisation because a large population can contain different solutions that may be useful in the future. However, rigorous theoretical demonstrations for how populations in dynamic optimisation can be essential are sparse and restricted to special cases. This paper provides theoretical explanations of how populations can be essential in evolutionary dynamic optimisation in a general and natural setting. We describe a natural class of dynamic optimisation problems where a sufficiently large population is necessary to keep track of moving optima reliably. We establish a relationship between the population-size and the probability that the algorithm loses track of the optimum.

Recommendations

• Survey on dynamic optimization algorithms
• Multi-population based univariate marginal distribution algorithm for dynamic optimization problems
• Evolutionary algorithms in dynamic environments
• An overview of multi-population methods for dynamic environments
• Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change

Cites work

• scientific article; zbMATH DE number 2013506 (Why is no real title available?)
• scientific article; zbMATH DE number 2013543 (Why is no real title available?)
• (1+1) EA on Generalized Dynamic OneMax
• Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change
• Evolutionary computation for dynamic optimization problems
• MMAS versus population-based EA on a family of dynamic fitness functions
• On the analysis of the \((1+1)\) evolutionary algorithm
• Probability and Computing
• Runtime analysis of ant colony optimization on dynamic shortest path problems
• Runtime analysis of non-elitist populations: from classical optimisation to partial information
• Simplified drift analysis for proving lower bounds in evolutionary computation
• Upper and lower bounds for randomized search heuristics in black-box optimization

Cited in

(6)

• A runtime analysis of parallel evolutionary algorithms in dynamic optimization
• Analysing equilibrium states for population diversity
• Sorting by swaps with noisy comparisons
• Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem
• A large population size can be unhelpful in evolutionary algorithms
• Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change

This page was built for publication: Populations can be essential in tracking dynamic optima

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