A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms
A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms
复制标题
DOI：
10.1109/tevc.2012.2202241
复制
发表时间：
2011-09
影响因子：
14.3
通讯作者：
Dirk Sudholt
中科院分区：
文献类型：
--
作者：
Dirk Sudholt
本文提出了一种新的证明进化算法期望运行时间下界的方法。它是基于适应度水平分区和一个额外的条件之间的转移概率的适应度水平。该方法是通用的，直观的，优雅的，非常强大的。它为LO、OneMax、长k路径和具有唯一最优值的所有函数产生精确或接近精确的下界。大多数下限是非常一般的;它们适用于所有仅使用位翻转突变作为变异算子的EA，即，所有的选择算子和种群模型。下限与突变率的依赖关系。这些结果具有很强的意义。它们允许我们确定LO和OneMax的最佳基于突变的算法，即，最小化适应度评估的期望数量的算法。这包括最佳突变率的选择。
In this paper a new method for proving lower bounds on the expected running time of evolutionary algorithms (EAs) is presented. It is based on fitness-level partitions and an additional condition on transition probabilities between fitness levels. The method is versatile, intuitive, elegant, and very powerful. It yields exact or near-exact lower bounds for LO, OneMax, long k-paths, and all functions with a unique optimum. Most lower bounds are very general; they hold for all EAs that only use bit-flip mutation as variation operator, i.e., for all selection operators and population models. The lower bounds are stated with their dependence on the mutation rate. These results have very strong implications. They allow us to determine the optimal mutation-based algorithm for LO and OneMax, i.e., the algorithm that minimizes the expected number of fitness evaluations. This includes the choice of the optimal mutation rate.