A note on problem difficulty measures in black-box optimization: Classification, realizations and predictability

Jun HE, Colin REEVES, Carsten WIT, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

52 Citations (Scopus)

Abstract

Various methods have been defined to measure the hardness of a fitness function for evolutionary algorithms and other black-box heuristics. Examples include fitness landscape analysis, epistasis, fitness-distance correlations etc., all of which are relatively easy to describe. However, they do not always correctly specify the hardness of the function. Some measures are easy to implement, others are more intuitive and hard to formalize. This paper rigorously defines difficulty measures in black-box optimization and proposes a classification. Different types of realizations of such measures are studied, namely exact and approximate ones. For both types of realizations, it is proven that predictive versions that run in polynomial time in general do not exist unless certain complexity-theoretical assumptions are wrong. © 2007 by the Massachusetts Institute of Technology.
Original languageEnglish
Pages (from-to)435-443
Number of pages9
JournalEvolutionary Computation
Volume15
Issue number4
Early online date19 Nov 2007
DOIs
Publication statusPublished - Dec 2007
Externally publishedYes

Keywords

  • Black-box optimization
  • Evolutionary algorithm
  • Problem difficulty measure
  • Running time
  • Satisfiability problem

Fingerprint

Dive into the research topics of 'A note on problem difficulty measures in black-box optimization: Classification, realizations and predictability'. Together they form a unique fingerprint.

Cite this