论文标题
在跳跃功能上的重尾$（1+（λ，λ））$遗传算法的运行时分析
Runtime Analysis of a Heavy-Tailed $(1+(λ,λ))$ Genetic Algorithm on Jump Functions
论文作者
论文摘要
最近观察到，$（1+（λ，λ））$遗传算法可以轻易地轻松逃脱跳跃函数基准的局部最佳。因此，该算法可以在预期的运行时使用$ n^{（k + 1）/2} k^{ - k/2} e^{o（k）$ fitness评估（antipov，doerr，doerr，doerr，karavaev（gecco 2020））的预期运行时优化跳跃功能$ k $。但是，为了获得此性能，使用了非标准的参数设置，具体取决于跳跃尺寸$ k $。 为了克服这一难度，我们建议选择$（1+（λ，λ））$遗传算法的两个参数从幂律分布中随机。通过数学运行时分析，我们表明，在所有跳跃函数上具有自然实例独立于分布参数的自然选择的算法，最多$ n/4 $的跳跃大小的性能接近了先前获得的最佳实例特定参数。实例独立的价格可以使其小至$ o（n \ log（n））$ factor。考虑到跳跃问题的困难以及使用轻度次优的固定参数（在这项工作中也讨论的）中造成的运行时损失，这似乎是一个公平的价格。
It was recently observed that the $(1+(λ,λ))$ genetic algorithm can comparably easily escape the local optimum of the jump functions benchmark. Consequently, this algorithm can optimize the jump function with jump size $k$ in an expected runtime of only $n^{(k + 1)/2}k^{-k/2}e^{O(k)}$ fitness evaluations (Antipov, Doerr, Karavaev (GECCO 2020)). To obtain this performance, however, a non-standard parameter setting depending on the jump size $k$ was used. To overcome this difficulty, we propose to choose two parameters of the $(1+(λ,λ))$ genetic algorithm randomly from a power-law distribution. Via a mathematical runtime analysis, we show that this algorithm with natural instance-independent choices of the distribution parameters on all jump functions with jump size at most $n/4$ has a performance close to what the best instance-specific parameters in the previous work obtained. This price for instance-independence can be made as small as an $O(n\log(n))$ factor. Given the difficulty of the jump problem and the runtime losses from using mildly suboptimal fixed parameters (also discussed in this work), this appears to be a fair price.
