Populations Can Be Essential in Tracking Dynamic Optima

被引：23

作者：

Dang, Duc-Cuong ^{[1
]}

Jansen, Thomas ^{[2
]}

Lehre, Per Kristian ^{[1
]}

机构：

[1] Univ Nottingham, Sch Comp Sci, ASAP Res Grp, Jubilee Campus,Wollaton Rd, Nottingham NG8 1BB, England

[2] Aberystwyth Univ, Dept Comp Sci, Penglais Campus,Llandinam Bldg, Aberystwyth SY23 3DB, Dyfed, Wales

来源：

ALGORITHMICA | 2017年 / 78卷 / 02期

关键词：

Runtime analysis; Population-based algorithm; Dynamic optimisation; LOWER BOUNDS; OPTIMIZATION;

D O I：

10.1007/s00453-016-0187-y

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：660 / 680

页数：21