期刊
ALGORITHMICA
卷 75, 期 3, 页码 462-489出版社
SPRINGER
DOI: 10.1007/s00453-015-0072-0
关键词
Run time analysis; Stochastic fitness function; Evolutionary algorithm; Populations; Robustness
资金
- European Union [618091]
- Danish Council for Independent Research (DFF) [4002-00542]
We consider stochastic versions of ONEMAX and LEADINGONES and analyze the performance of evolutionary algorithms with and without populations on these problems. It is known that the (1+ 1) EA on ONEMAX performs well in the presence of very small noise, but poorly for higher noise levels. We extend these results to LEADINGONES and to many different noise models, showing howthe application of drift theory can significantly simplify and generalize previous analyses. Most surprisingly, even small populations (of size Theta (log n)) can make evolutionary algorithms perform well for high noise levels, well outside the abilities of the (1 + 1) EA. Larger population sizes are even more beneficial; we consider both parent and offspring populations. In this sense, populations are robust in these stochastic settings.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据