论文标题
动态纤维函数上（MU+1）-EA的运行时分析
Runtime analysis of the (mu+1)-EA on the Dynamic BinVal function
论文作者
论文摘要
我们在动态环境中研究进化算法，其中选择了不同的适应性函数，并且针对当前的适应性函数进行选择。具体而言，我们考虑了动态纤维，其中每一代的适应性函数由线性函数binval给出，但是在每一代中，位的位顺序是随机置换的。对于（1+1）-EA，众所周知，突变参数有效率阈值$ C_0 $，在该参数中，运行时从Quasilinear切换到指数。以前的经验证据表明，对于较大的人口大小$μ$，阈值可能会增加。我们证明，至少在$ \ varepsilon $ - 最佳范围内是这种情况：如果选择$μ$足够大，则（μ+1）-ea的阈值任意大。 但是，最令人惊讶的结果是通过$μ= 2 $的二阶分析获得的最令人惊讶的结果：阈值随着与最佳距离的距离的增加而增加。特别是，最难优化的区域不在最佳范围内。
We study evolutionary algorithms in a dynamic setting, where for each generation a different fitness function is chosen, and selection is performed with respect to the current fitness function. Specifically, we consider Dynamic BinVal, in which the fitness functions for each generation is given by the linear function BinVal, but in each generation the order of bits is randomly permuted. For the (1+1)-EA it was known that there is an efficiency threshold $c_0$ for the mutation parameter, at which the runtime switches from quasilinear to exponential. A previous empirical evidence suggested that for larger population size $μ$, the threshold may increase. We prove that this is at least the case in an $\varepsilon$-neighborhood around the optimum: the threshold of the (μ+1)-EA becomes arbitrarily large if the $μ$ is chosen large enough. However, the most surprising result is obtained by a second order analysis for $μ=2$: the threshold INcreases with increasing proximity to the optimum. In particular, the hardest region for optimization is NOT around the optimum.
