More Precise Runtime Analyses of Non-elitist Evolutionary Algorithms in Uncertain Environments
More Precise Runtime Analyses of Non-elitist Evolutionary Algorithms in Uncertain Environments
复制标题
DOI：
10.1007/s00453-022-01044-5
复制
发表时间：
2022-10
期刊：
影响因子：
1.1
通讯作者：
P. Lehre;Xiaoyu Qin
中科院分区：
文献类型：
--
作者：
P. Lehre;Xiaoyu Qin
现实世界的应用通常涉及“不确定”的目标，即，其中优化算法将目标值观测为具有正方差的随机变量。在过去的十年中，一些严格的分析结果表明，进化算法（EA）的离散问题可以科普低层次的不确定性，即当不确定的目标值的方差很小，有时甚至受益于不确定性。以前的工作表明，一个大的人口与非精英选择机制相结合是一个很有前途的方法来处理高水平的不确定性。然而，人口规模和突变率可以显着影响非精英EA的性能，这些参数的最佳选择取决于目标函数的不确定性水平。在一些常见的客观不确定性的情况下，非精英EA的性能和所需的参数设置仍然是未知的。我们分析了两个经典的基准问题OneMaxandLeadingOnesin的一位，逐位，高斯和对称噪声模型，和动态二进制值问题（DynBV）的非精英EA的运行时间。我们的分析比以前的分析更广泛和精确的非精英EA。在几个设置中，我们证明了非精英EA优于目前的国家的最先进的结果。此外，我们提供了更精确的指导，如何选择的突变率，选择压力，和人口规模的不确定性水平的函数。
Real-world applications often involve “uncertain” objectives, i.e., where optimisation algorithms observe objective values as a random variables with positive variance. In the past decade, several rigorous analysis results for evolutionary algorithms (EAs) on discrete problems show that EAs can cope with low-level uncertainties, i.e. when the variance of the uncertain objective value is small, and sometimes even benefit from uncertainty. Previous work showed that a large population combined with a non-elitist selection mechanism is a promising approach to handle high levels of uncertainty. However, the population size and the mutation rate can dramatically impact the performance of non-elitist EAs, and the optimal choices of these parameters depend on the level of uncertainty in the objective function. The performance and the required parameter settings for non-elitist EAs in some common objective-uncertainty scenarios are still unknown. We analyse the runtime of non-elitist EAs on two classical benchmark problemsOneMaxandLeadingOnesin in the one-bit, the bitwise, the Gaussian, and the symmetric 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 outperform the current state-of-the-art results. Furthermore, we provide more precise guidance on how to choose the mutation rate, the selective pressure, and the population size as a function of the level of uncertainty.