演化优化作为一种通用的优化方法,在众多领域已取得成功的应用。然而,在许多应用场景中,待优化的函数值评估过程往往存在噪声,这使得对优化问题的求解变得更加复杂,从而也更具有挑战性。我们在AAEO第22期(链接)和第70期(链接)已经和大家分享了关于噪声环境下演化优化部分以往工作,本期AAEO我们将继续这一主题,和大家分享一篇近期论文。由于笔者能力有限,如果分享过程中存在疏漏,还请大家不吝赐教与指正。

发表在GECCO 2018,来自Chao Qian,Chao Bian,Yang Yu,Ke Tang,Xin Yao的文章:Analysis of Noisy Evolutionary Optimization When Sampling Fails,从理论视角研究了基于采样的噪声处理策略的有效性,通过构造实例进行分析,探索和回答采样策略何时有效、何时失效、失效时的替代有效策略是什么等基本理论问题,从而为算法的实际应用提供指导。(文章链接

文章首先证明了使用(1+1)-EA结合采样策略优化One-bit噪声下的LeadingOnes问题,随着评估时样本数量的增加,算法总体期望运行时间将从指数变为多项式然后再变为指数,从而在理论上揭示了采样数量对采样策略性能的影响。

AAEO142-1

接着,文章分析了使用(1+1)-EA结合采样策略优化对称噪声下的OneMax问题,证明出在该情形下采样策略将失效,即算法期望运行时间为指数级。然而,同样情形下,若使用基于Parent Populations的策略,文章具体考虑使用了(μ+1)-EA,则算法期望运行时间为多项式级。

AAEO142-2

最后,文章分析了在Segmented噪声下优化OneMax问题,无论是(1+1)-EA结合采样策略,还是(μ+1)-EA,算法的期望运行时间均为指数级。然而,在这种情形下如果使用Adaptive Sampling策略:

AAEO142-3

即带噪评估下两个解的值相差过大或过小时,需要增加采样数量来提高比较结果的置信度。此时,算法期望运行时间为多项式级。

AAEO142-4

钱 鸿

钱 鸿

南京大学计算机科学与技术系-机器学习与数据挖掘研究所 (LAMDA)-博士生

© 2019 ECOLE