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

dynamic optimisationpopulation-based algorithmruntime analysis

Mathematics Subject Classification ID

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

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

• (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
• scientific article; zbMATH DE number 2013506 (Why is no real title available?)
• scientific article; zbMATH DE number 2013543 (Why is no real title available?)
• 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

(8)

• Sorting by swaps with noisy comparisons
• Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem
• A runtime analysis of parallel evolutionary algorithms in dynamic optimization
• A large population size can be unhelpful in evolutionary algorithms
• Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change
• Analysing equilibrium states for population diversity
• On the efficiency of nonelitist evolutionary algorithms in the case of sparsity of the level sets inconsistent with respect to the objective function
• Runtime analysis of evolutionary neural architecture search for binary classification

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)