Skip to main content

Research Repository

Advanced Search

Populations can be essential in tracking dynamic optima

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

Authors

Duc-Cuong Dang duc-cuong.dang@nottingham.ac.uk

Thomas Jansen t.jansen@aber.ac.uk

Per Kristian Lehre PerKristian.Lehre@nottingham.ac.uk



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.

Journal Article Type Article
Journal Algorithmica
Print ISSN 0178-4617
Electronic ISSN 1432-0541
Publisher Springer Verlag
Peer Reviewed Peer Reviewed
APA6 Citation Dang, D., Jansen, T., & Lehre, P. K. (in press). Populations can be essential in tracking dynamic optima. Algorithmica, https://doi.org/10.1007/s00453-016-0187-y
DOI https://doi.org/10.1007/s00453-016-0187-y
Keywords Runtime Analysis, Population-based Algorithm, Dynamic Optimisation
Publisher URL http://link.springer.com/article/10.1007/s00453-016-0187-y
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf

Files

34913 optima.pdf (568 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations

;