Runtime Analysis of Non-elitist Populations: From Classical Optimisation to Partial Information
Runtime Analysis of Non-elitist Populations: From Classical Optimisation to Partial Information
复制标题
非精英群体的运行时分析：从经典优化到部分信息
DOI：
10.1007/s00453-015-0103-x
复制
发表时间：
2016
期刊：
影响因子：
1.1
通讯作者：
P. Lehre
中科院分区：
文献类型：
--
作者：
D. Dang;P. Lehre
尽管在优化中得到了广泛的应用，但关于群体在随机搜索过程中的作用和行为的严格证明相对较少。本文提出了一种新的方法来证明基于群体的随机搜索启发式算法的期望优化时间的上界，该算法使用非精英选择机制和一元变异算子。我们的结果源于对这些启发式算法中种群动态的详细漂移分析。这一分析表明，优化时间取决于选择压力的强度与变分算子引入的变异程度之间的关系。给定有限的变化，一个令人惊讶的微弱的选择压力足以在预期的多项式时间内优化许多函数。我们使用各种选择机制，包括适应度比例选择，得到了非精英进化算法(EA)的期望优化时间的上界。我们证明，在给定足够低的变异率的情况下，使用适应度比例选择的进化算法可以在预期的多项式时间内优化标准基准函数。作为第二个贡献，我们考虑了部分信息的优化场景，其中解的适应值只有部分可用。我们证明了在一组特定条件下的非精英进化算法可以在预期的多项式时间内优化基准函数，即使在关于个体解或种群的适应值的信息非常少的情况下也是如此。据我们所知，这是首次对部分信息下的随机搜索启发式算法进行运行时分析。
Although widely applied in optimisation, relatively little has been proven rigorously about the role and behaviour of populations in randomised search processes. This paper presents a new method to prove upper bounds on the expected optimisation time of population-based randomised search heuristics that use non-elitist selection mechanisms and unary variation operators. Our results follow from a detailed drift analysis of the population dynamics in these heuristics. This analysis shows that the optimisation time depends on the relationship between the strength of the selective pressure and the degree of variation introduced by the variation operator. Given limited variation, a surprisingly weak selective pressure suffices to optimise many functions in expected polynomial time. We derive upper bounds on the expected optimisation time of non-elitist evolutionary algorithms (EA) using various selection mechanisms, including fitness proportionate selection. We show that EAs using fitness proportionate selection can optimise standard benchmark functions in expected polynomial time given a sufficiently low mutation rate. As a second contribution, we consider an optimisation scenario with partial information, where fitness values of solutions are only partially available. We prove that non-elitist EAs under a set of specific conditions can optimise benchmark functions in expected polynomial time, even when vanishingly little information about the fitness values of individual solutions or populations is available. To our knowledge, this is the first runtime analysis of randomised search heuristics under partial information.