Populations can be essential in dynamic optimisation

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

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion CynhadleddTrafodion Cynhadledd (Nid-Cyfnodolyn fathau)


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. The ability of evolutionary algorithms to track optimal solutions is investigated by considering a Hamming ball of optimal points that moves randomly through the search space. It is shown that algorithms based on a single individual are likely to be unable to track the optimum while non-elitist population-based evolutionary algorithms can be able to do so with overwhelmingly high probability. It is shown that this holds for a range of the most commonly used selection mechanisms even without diversity enhancing mechanisms. Appropriate parameter settings to achieve this behaviour are derived for these selection mechanisms.
Iaith wreiddiolSaesneg
TeitlProceedings of the Genetic and Evolutionary Computation Conference (GECCO 2015)
Man cyhoeddiNew York
CyhoeddwrAssociation for Computing Machinery
ISBN (Argraffiad)978-1-4503-3472-3
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 2015

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Populations can be essential in dynamic optimisation'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn