More precise runtime analyses of non-elitist EAs in uncertain environments
More precise runtime analyses of non-elitist EAs in uncertain environments
复制标题
DOI：
10.1145/3449639.3459312
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
P. Lehre;Xiaoyu Qin
中科院分区：
文献类型：
--
作者：
P. Lehre;Xiaoyu Qin
现实世界的优化问题往往涉及不确定性。在过去的十年中，一些严格的分析结果表明，进化算法（EA）的离散问题可以科普低层次的不确定性，有时受益于不确定性。使用非精英EA与大人口规模是一个很有前途的方法来处理更高层次的不确定性。然而，在一些常见的健身不确定性的情况下，非精英EA的性能仍然是未知的。我们分析了OneMax和LeadingOnes上的非精英EA在先验和后验噪声模型下的运行时间，以及动态二进制值问题（DynBV）。我们的分析比以前的分析更广泛和精确的非精英EA。在几种情况下，我们证明了非精英EA击败了当前最先进的结果。以前的工作表明，人口规模和突变率可以显着影响非精英EA的性能。这些参数的最佳选择取决于适应度函数中的不确定性水平。我们提供了更精确的指导，如何选择突变率和人口规模的不确定性水平的函数。
Real-world optimisation problems often involve uncertainties. In the past decade, several rigorous analysis results for evolutionary algorithms (EAs) on discrete problems show that EAs can cope with low-level uncertainties, and sometimes benefit from uncertainties. Using non-elitist EAs with large population size is a promising approach to handle higher levels of uncertainties. However, the performance of non-elitist EAs in some common fitness-uncertainty scenarios is still unknown. We analyse the runtime of non-elitist EAs on OneMax and LeadingOnes under prior and posterior noise models, and the dynamic binary value problem (DynBV). Our analyses are more extensive and precise than previous analyses of non-elitist EAs. In several settings, we prove that the non-elitist EAs beat the current state of the art results. Previous work shows that the population size and mutation rate can dramatically impact the performance of non-elitist EAs. The optimal choices of these parameters depend on the level of uncertainties in the fitness functions. We provide more precise guidance on how to choose mutation rate and population size as a function of the level of uncertainties.