On the Runtime Analysis of Fitness Sharing Mechanisms^*

Pietro S. Oliveto¹, Dirk Sudholt¹, and Christine Zarges²

¹University of Sheffield, Sheffield, UK

²University of Birmingham, Birmingham, UK

Abstract. Fitness sharing is a popular diversity mechanism implementing the idea that similar individuals in the population have to share resources and thus, share their fitnesses. Previous runtime analyses of fitness sharing studied a variant where selection was based on populations instead of individuals. We use runtime analysis to highlight the benefits and dangers of the original fitness sharing mechanism on the well-known test problem TwoMax, where diversity is crucial for finding both optima. In contrast to population-based sharing, a (2+1) EA in the original setting does not guarantee finding both optima in polynomial time; however, a (+1) EA with   3 always succeeds in expected polynomial time. We further show theoretically and empirically that large offspring populations in ( + ) EAs can be detrimental as overpopulation can make clusters of search points go extinct.

Keywords: Evolutionary computation, diversity mechanisms, fitness sharing, runtime analysis

^*The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement no 618091 (SAGE).

LNCS 8672, p. 932 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer International Publishing Switzerland 2014