Infeasibility and structural bias in Differential Evolution

Fabio Caraffini, Anna V. Kononova, David Corne

Research output: Contribution to journalArticle

10 Citations (Scopus)
4 Downloads (Pure)

Abstract

Structural bias is a recently identified property of optimisation algorithms, causing them to favour certain regions of the search space over others, independently of the objective function. Since structural bias can adversely affect the progress of optimisation, a better understanding of it is needed in order to inform the theory and practice of algorithm design. For example, it is generally accepted that larger populations are favoured when solution quality is paramount and time constraints are permissive. However, common variants of both Genetic Algorithms and Particle Swarm Optimisation have been found to exhibit structural bias that increases with population size. Herein we investigate structural bias in popular variants of Differential Evolution (DE), and attempt to identify which algorithm features trigger its emergence. In particular, we focus on the (often overlooked)constraint handling mechanism. Our results suggest that DE is generally robust to structural bias. Only one of the variants studied – DE/current-to-best/1/bin – shows clear signs of bias, however this is mitigated by a judicious choice of constraint handling technique. These findings contribute towards explaining the widespread success of DE in algorithm comparison studies; its robustness to structural bias represents the absence of a factor that may confound other algorithms.

Original languageEnglish
Pages (from-to)161-179
Number of pages19
JournalInformation Sciences
Volume496
Early online date11 May 2019
DOIs
Publication statusPublished - Sep 2019

Keywords

  • Algorithmic design
  • Differential evolution
  • Optimisation
  • Population-based algorithms
  • Structural bias

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Infeasibility and structural bias in Differential Evolution'. Together they form a unique fingerprint.

Cite this