论文标题
在广义多数功能上进行随机本地搜索的运行时间分析
Run Time Analysis for Random Local Search on Generalized Majority Functions
论文作者
论文摘要
进化算法的运行时间分析最近在将算法性能与算法参数联系起来方面取得了重大进展。但是，研究问题参数的影响的设置很少见。最近提出的W模型为此类分析提供了一个良好的框架，从而生成了具有可调属性的伪树状优化问题。 我们通过研究其一种特性（中立性）如何影响随机局部搜索的运行时间来启动W-Model的理论研究。中立性通过首先对解决方案候选者的子集进行多数投票，然后通过低级健身函数评估较小维的字符串，从而在搜索空间中创建高原。 我们证明，对于此大多数问题的整个参数频谱，随机局部搜索的预期运行时间是上限。为此，我们提供了适用于许多优化算法的定理，该定理将多数的运行时间与其对称版本HasmaJority联系起来，其中需要足够多数来优化子集。我们还介绍了经典漂移定理的广义版本以及Wald方程的广义版本，我们认为这两个都具有独立的兴趣。
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.
