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)

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.

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
PublisherSpringer
Pages932-941
Number of pages10
Volume8672
ISBN (Electronic)9783319107622
ISBN (Print)9783319107615
DOIs
Publication statusPublished - 2014
Event13th International Conference on Parallel Problem Solving from Nature – PPSN XIII - Ljubljana, Slovenia
Duration: 13 Sep 201417 Sep 2014

Publication series

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

Conference

Conference13th International Conference on Parallel Problem Solving from Nature – PPSN XIII
Country/TerritorySlovenia
City Ljubljana
Period13/09/1417/09/14

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Fingerprint

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

Cite this