Average Drift Analysis and Population Scalability
Average Drift Analysis and Population Scalability
复制标题
DOI：
10.1109/tevc.2016.2608420
复制
发表时间：
2013-08
影响因子：
14.3
通讯作者：
Jun He;X. Yao
中科院分区：
文献类型：
--
作者：
Jun He;X. Yao
研究了种群规模对进化算法计算时间的影响。进化算法的计算时间可以通过生成的次数（命中时间）或找到最优解的适应度评估的次数（运行时间）来衡量。群体可伸缩性是基准算法和使用较大群体大小的算法之间的预期命中时间的比率。引入平均漂移分析来比较两种算法的期望命中时间，并估计种群可扩展性的上下界。几个直观的信念进行了严格的分析。事实证明：1）使用种群有时会增加而不是减少预期命中时间; 2）使用种群不能缩短任何精英EA在时间适应度景观上的任何单峰函数上的预期运行时间，然而，就基于距离的适应度景观而言，这种说法是不正确的;以及3）使用种群并不总是减少欺骗性函数的期望运行时间，这取决于基准算法是使用精英选择还是随机选择。
This paper aims to study how the population size affects the computation time of evolutionary algorithms (EAs) in a rigorous way. The computation time of EAs can be measured by either the number of generations (hitting time) or the number of fitness evaluations (running time) to find an optimal solution. Population scalability is the ratio of the expected hitting time between a benchmark algorithm and an algorithm using a larger population size. Average drift analysis is introduced to compare the expected hitting time of two algorithms and to estimate lower and upper bounds on the population scalability. Several intuitive beliefs are rigorously analyzed. It is proven that: 1) using a population sometimes increases rather than decreases the expected hitting time; 2) using a population cannot shorten the expected running time of any elitist EA on any unimodal function on the time-fitness landscape, however, this statement is not true in terms of the distance-based fitness landscape; and 3) using a population cannot always reduce the expected running time on deceptive functions, which depends on whether the benchmark algorithm uses elitist selection or random selection.