论文标题
双峰优化的限制比赛选择的运行时分析
Runtime Analysis of Restricted Tournament Selection for Bimodal Optimisation
论文作者
论文摘要
已经开发出了狭窄的方法来维持人口多样性，以并行研究许多峰并减少遗传漂移的影响。我们介绍了嵌入（$μ$+1）EA中的第一个严格的限制比赛选择（RTS）的运行时分析，并分析了其在找到Bimodal函数的最佳功能$ {\ rm T {\ small wo} m {\ small wo} m {\ small ax}} $方面的有效性。在RTS中，在$ W $（窗口大小）人口成员（随机选择替换）中，在$ W $（窗口大小）中，一个后代与最接近的人竞争，以鼓励在同一利基市场中竞争。我们证明，RTS在$ {\ rm t {\ small wo} m {\ small ax}}} $上有效地找到了两种优点，如果窗口尺寸$ w $足够大，则可以有效地找到optima。但是，如果$ w $太小，即使在指数时间内，RTS也无法找到两者，并且概率很高。我们进一步考虑了RTS的变体，为比赛选择个人\ Emph {无}替代。它产生了更多样化的锦标赛，并且更有效地防止一个利基市场接管另一个。但是，这是以牺牲速度降低到Optima为代价的，而当利基市场崩溃到一个人时。我们的理论结果伴随着实验研究，这些研究阐明了理论结果未涵盖的参数，并支持猜想的较低的运行时结合。
Niching methods have been developed to maintain the population diversity, to investigate many peaks in parallel and to reduce the effect of genetic drift. We present the first rigorous runtime analyses of restricted tournament selection (RTS), embedded in a ($μ$+1) EA, and analyse its effectiveness at finding both optima of the bimodal function ${\rm T{\small WO}M{\small AX}}$. In RTS, an offspring competes against the closest individual, with respect to some distance measure, amongst $w$ (window size) population members (chosen uniformly at random with replacement), to encourage competition within the same niche. We prove that RTS finds both optima on ${\rm T{\small WO}M{\small AX}}$ efficiently if the window size $w$ is large enough. However, if $w$ is too small, RTS fails to find both optima even in exponential time, with high probability. We further consider a variant of RTS selecting individuals for the tournament \emph{without} replacement. It yields a more diverse tournament and is more effective at preventing one niche from taking over the other. However, this comes at the expense of a slower progress towards optima when a niche collapses to a single individual. Our theoretical results are accompanied by experimental studies that shed light on parameters not covered by the theoretical results and support a conjectured lower runtime bound.
