Run time analysis of evolutionary algorithms recently makes significant progress in linking algorithm performance to algorithm parameters. However, settings that study the impact of problem parameters are rare. The recently proposed W-model provides a good framework for such analyses, generating pseudo-Boolean optimization problems with tunable properties. We initiate theoretical research of the W-model by studying how one of its properties -- neutrality -- influences the run time of random local search. Neutrality creates plateaus in the search space by first performing a majority vote for subsets of the solution candidate and then evaluating the smaller-dimensional string via a low-level fitness function. We prove upper bounds for the expected run time of random local search on this MAJORITY problem for its entire parameter spectrum. To this end, we provide a theorem, applicable to many optimization algorithms, that links the run time of MAJORITY with its symmetric version HASMAJORITY, where a sufficient majority is needed to optimize the subset. We also introduce a generalized version of classic drift theorems as well as a generalized version of Wald's equation, both of which we believe to be of independent interest.
翻译:对进化算法的运行时间分析最近在将算法性能与算法参数挂钩方面取得重大进展。 但是,研究问题参数影响的设置很少。 最近提议的W型模型为此类分析提供了一个良好的框架,在可加金枪鱼特性方面产生了假的boolean优化问题。 我们通过研究W型模型的特性之一 -- -- 中性 -- -- 如何影响随机本地搜索的运行时间,开始对W型模型进行理论研究。 中性在搜索空间中创造了高原,先对解决方案候选子集进行多数票表决,然后通过低水平的健身功能对小维字符串进行评估。 我们证明,在预期的随机本地搜索这一MAJORITY问题整个参数谱的运行时间里,我们提供了一种适用于许多优化算法的理论,将MAJORITY的运行时间与其对称版本HASMAORITY联系起来, 在那里需要足够多数来优化子集。 我们还引入了典型流体流体的通用版本, 以及通用的瓦尔德方程式, 我们认为两者都具有独立的兴趣。