期刊
THEORETICAL COMPUTER SCIENCE
卷 773, 期 -, 页码 53-70出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2018.07.007
关键词
Evolutionary computation; Diversity mechanisms; Fitness sharing; Multimodal optimisation; Runtime analysis
资金
- European Union [618091]
- EPSRC [EP/M004252/1]
- EPSRC [EP/M004252/1] Funding Source: UKRI
Fitness sharing is a well-known diversity mechanism inspired by the idea that individuals in the population that are close to each other have to share their fitnesses in a similar way to how species in nature occupying the same ecological environment have to share resources. Thus, by derating the fitness of close individuals one hopes to encourage the population to spread out more. Previous runtime analyses of fitness sharing studied a variant where selection was based on populations instead of individuals. We study the conventional fitness sharing mechanism based on individuals and use runtime analysis to highlight its benefits and dangers on the well-known bimodal test problem TwoMAx, where diversity is crucial for finding both optima. In contrast to population-based sharing, a (2+1) evolutionary algorithm (EA) with conventional fitness sharing does not guarantee to find both optima in polynomial time even when problem specific knowledge is used to estimate the distance between individuals; however, a (mu+1) EA with mu >= 3 always succeeds in expected polynomial time. We further show theoretically and empirically that large offspring populations in (mu+lambda) EAs can be detrimental as creating too many offspring in one particular area of the search space can make all individuals in this area go extinct. We conclude the paper with an empirical study indicating that similar conclusions may be drawn when using the genotypic distance that has to be relied upon when no problem specific knowledge is available. (C) 2018 The Author(s). Published by Elsevier B.V.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据