On the runtime analysis of fitness sharing mechanisms

Pietro S. Oliveto, Dirk Sudholt, Christine Zarges

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XIII
Subtitle of host publication13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings
EditorsThomas Bartz-Beielstein, Jürgen Branke, Bogdan Filipič, JIm Smith
Number of pages10
ISBN (Electronic)9783319107622
ISBN (Print)9783319107615
Publication statusPublished - 2014
Event13th International Conference on Parallel Problem Solving from Nature – PPSN XIII - Ljubljana, Slovenia
Duration: 13 Sept 201417 Sept 2014

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference13th International Conference on Parallel Problem Solving from Nature – PPSN XIII
City Ljubljana


  • Diversity mechanisms
  • Evolutionary computation
  • Fitness sharing
  • Runtime analysis

ASJC Scopus subject areas

  • General Computer Science
  • Theoretical Computer Science


Dive into the research topics of 'On the runtime analysis of fitness sharing mechanisms'. Together they form a unique fingerprint.

Cite this