期刊
THEORETICAL COMPUTER SCIENCE
卷 545, 期 -, 页码 20-38出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2013.09.036
关键词
Evolutionary algorithms; Comma strategies; Offspring populations; Runtime analysis; Drift analysis; Theory
资金
- EPSRC [EP/D052785/1]
- Engineering and Physical Sciences Research Council [EP/D052785/1] Funding Source: researchfish
- EPSRC [EP/D052785/1] Funding Source: UKRI
We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1, lambda) EA. We establish a sharp threshold at lambda = log(e/e-1) n approximate to 5log(10) n between exponential and polynomial running times on ONEMAX. For any smaller value, the (1, lambda) EA needs exponential time on every function that has only one global optimum. We also consider arbitrary unimodal functions and show that the threshold can shift towards larger offspring population sizes. In particular, for the function LEADINGONES there is a sharp threshold at lambda = 2 log(e/e-1) n approximate to 10log(10) n. Finally, we investigate the relationship between the offspring population size and arbitrary mutation rates on ONEMAX. We get sharp thresholds for lambda that decrease with the mutation rate. This illustrates the balance between selection and mutation. (C) 2013 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据