On the Runtime Analysis of the Clearing Diversity-Preserving Mechanism
通过严格运行时分析，证明基于突变的进化算法在足够大种群和表型距离下，能在多项式时间内优化所有单峰函数，而基因型距离需要指数时间；同时清除机制能在多项式期望时间内找到双峰函数的最优解。
Clearing is a niching method inspired by the principle of assigning the available resources among a niche to a single individual. The clearing procedure supplies these resources only to the best individual of each niche: the winner. So far, its analysis has been focused on experimental approaches that have shown that clearing is a powerful diversity-preserving mechanism. Using rigorous runtime analysis to explain how and why it is a powerful method, we prove that a mutation-based evolutionary algorithm with a large enough population size, and a phenotypic distance function always succeeds in optimising all functions of unitation for small niches in polynomial time, while a genotypic distance function requires exponential time. Finally, we prove that with phenotypic and genotypic distances, clearing is able to find both optima for [Formula: see text] and several general classes of bimodal functions in polynomial expected time. We use empirical analysis to highlight some of the characteristics that makes it a useful mechanism and to support the theoretical results.