Fast non-elitist evolutionary algorithms with power-law ranking selection
Fast non-elitist evolutionary algorithms with power-law ranking selection
复制标题
具有幂律排序选择的快速非精英进化算法
DOI：
10.1145/3512290.3528873
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Dang D
中科院分区：
文献类型：
--
作者：
Dang D
理论证据表明，非精英进化算法（EA）的非线性选择机制，可以有效地克服广泛的类的局部最优的精英EA失败。然而，该分析假设弱选择压力和突变率仔细选择接近“错误阈值”，超过该阈值，它们就不再有效。在更容易爬山的问题上，人口可能会减慢这些算法，导致与精英（1+1）EA的变体相比更差的运行时间。在这里，我们表明，具有幂律排名选择的非精英EA在简单的基准问题上导致快速运行，同时保持逃避某些局部最优的能力，其中精英EA在期望中花费指数时间。我们推导出一个变体，基于水平的定理，它解释了幂律分布。对于经典的理论基准测试，预期的运行时间用小的前导常数来表示。对于复杂的，多模态的健身景观，我们提供了充分的条件多项式优化，制定在欺骗性区域稀疏性和健身谷密度。我们推导出错误阈值，并表现出极高的突变率的容忍度。在Kauffman模型下生成的NK-Landscape函数上的实验结果表明，该算法优于（1+1）EA和单变量边际分布算法（UMDA）。
Theoretical evidence suggests that non-elitist evolutionary algorithms (EAs) with non-linear selection mechanisms can efficiently overcome broad classes of local optima where elitist EAs fail. However, the analysis assumes a weak selective pressure and mutation rates carefully chosen close to the "error threshold", above which they cease to be efficient. On problems easier for hill-climbing, the populations may slow down these algorithms, leading to worse runtime compared with variants of the elitist (1+1) EA.Here, we show that a non-elitist EA with power-law ranking selection leads to fast runtime on easy benchmark problems, while maintaining the capability of escaping certain local optima where the elitist EAs spend exponential time in the expectation.We derive a variant of the level-based theorem which accounts for power-law distributions. For classical theoretical benchmarks, the expected runtime is stated with small leading constants. For complex, multi-modal fitness landscapes, we provide sufficient conditions for polynomial optimisation, formulated in terms of deceptive regions sparsity and fitness valleys density. We derive the error threshold and show extreme tolerance to high mutation rates. Experiments on NK-Landscape functions, generated according to the Kauffman's model, show that the algorithm outperforms the (1+1) EA and the univariate marginal distribution algorithm (UMDA).
登录
查看更多内容
影响因子：
6.8
作者：
Ochoa, Gabriela
通讯作者：
Ochoa, Gabriela
DOI：
10.1145/3449639.3459312
发表时间：
2021-06
期刊：
Proceedings of the Genetic and Evolutionary Computation Conference
影响因子：
--
作者：
P. Lehre;Xiaoyu Qin
通讯作者：
P. Lehre;Xiaoyu Qin
非精英群体的运行时分析：从经典优化到部分信息
影响因子：
1.1
作者：
D. Dang;P. Lehre
通讯作者：
P. Lehre
单变量边际分布算法的基于级别的分析
影响因子：
1.1
作者：
D. Dang;P. Lehre;P. Nguyen
通讯作者：
P. Nguyen
基于群体的增量学习算法的基于级别的分析
DOI：
--
发表时间：
2018
期刊：
Parallel Problem Solving from Nature
影响因子：
--
作者：
P. Lehre;P. Nguyen
通讯作者：
P. Nguyen