On the Benefits and Risks of Using Fitness Sharing for Multimodal Optimisation

Pietro S. Oliveto, Dirk Sudholt, Christine Zarges

Research output: Contribution to journalArticlepeer-review

28 Citations (SciVal)
141 Downloads (Pure)

Abstract

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 (μ+1) EA with μ≥3 always succeeds in expected polynomial time. We further show theoretically and empirically that large offspring populations in (μ+λ) EA s 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.

Original languageEnglish
Pages (from-to)53-70
Number of pages18
JournalTheoretical Computer Science
Volume773
DOIs
Publication statusPublished - 14 Jun 2019

Keywords

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

Fingerprint

Dive into the research topics of 'On the Benefits and Risks of Using Fitness Sharing for Multimodal Optimisation'. Together they form a unique fingerprint.

Cite this