The one-fifth success rule is one of the best-known and most widely accepted techniques to control the parameters of evolutionary algorithms. While it is often applied in the literal sense, a common interpretation sees the one-fifth success rule as a family of success-based updated rules that are determined by an update strength $F$ and a success rate. We analyze in this work how the performance of the (1+1) Evolutionary Algorithm on LeadingOnes depends on these two hyper-parameters. Our main result shows that the best performance is obtained for small update strengths $F=1+o(1)$ and success rate $1/e$. We also prove that the running time obtained by this parameter setting is, apart from lower order terms, the same that is achieved with the best fitness-dependent mutation rate. We show similar results for the resampling variant of the (1+1) Evolutionary Algorithm, which enforces to flip at least one bit per iteration.
翻译:五分之一的成功规则是控制进化算法参数的最著名和最广泛接受的技术之一。 虽然它通常在字面意义上应用, 一种共同的解释认为, 五分之一的成功规则是一套基于成功的最新规则, 由更新的强度 $F$和成功率决定。 我们在这项工作中分析了“ 领导一号” 上的1+1进化算法的性能如何取决于这两个超强参数。 我们的主要结果显示, 微小更新强力 $F=1+o(1)$和成功率 $/ e$ 获得最佳的性能。 我们还证明, 除了更低的顺序条件之外, 这一参数设置所获得的运行时间与最依赖健身的突变率相同。 我们为“ 进化法” ( 1+1) 的复选变法显示类似的结果, 该变法要求至少翻一比特。