We propose a new method based on discrete Fourier analysis to analyze the time evolutionary algorithms spend on plateaus. This immediately gives a concise proof of the classic estimate of the expected runtime of the $(1+1)$ evolutionary algorithm on the Needle problem due to Garnier, Kallel, and Schoenauer (1999). We also use this method to analyze the runtime of the $(1+1)$ evolutionary algorithm on a new benchmark consisting of $n/\ell$ plateaus of effective size $2^\ell-1$ which have to be optimized sequentially in a LeadingOnes fashion. Using our new method, we determine the precise expected runtime both for static and fitness-dependent mutation rates. We also determine the asymptotically optimal static and fitness-dependent mutation rates. For $\ell = o(n)$, the optimal static mutation rate is approximately $1.59/n$. The optimal fitness dependent mutation rate, when the first $k$ fitness-relevant bits have been found, is asymptotically $1/(k+1)$. These results, so far only proven for the single-instance problem LeadingOnes, are thus true in a much broader respect. We expect similar extensions to be true for other important results on LeadingOnes. We are also optimistic that our Fourier analysis approach can be applied to other plateau problems as well.
翻译:我们提出基于离散的Fleier分析的新方法,以分析在高原上花费的时间进化算法。 这立即简要地证明了对由于Garnier、Kallel和Schoenauer(1999年)造成的针线问题的(1+1)美元进化算法的预期运行时间的典型估计。 我们还使用这种方法分析美元(1+1)美元进化算法在新基准上的运行时间,该新基准由有效大小为$/美元2 ⁇ ell-1美元的高原组成,这些高原必须在“领导一号”时按顺序优化。我们使用新的方法,确定静态和健身型突变率的精确运行时间。我们还确定非同步最佳静态和健身型突变率。对于$=o(n)美元,最佳静态变算法的运行时间约为1.5/n美元。当发现第一批美元与健康相关的高原位时,最佳的健身率是1美元/(k+1美元)。这些结果对静态和健身型突变速率的精确的预期时间,也是我们对一次领导结果的真正乐观性分析的证明。