Fitness Landscapes and Problem Difficulty in Evolutionary Algorithms: From Theory to Applications

Guanzhou LU, Jinlong LI, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsBook ChapterResearchpeer-review


Above many successes of evolutionary algorithms in solving computationally hard optimisations problems, a major challenge in practice remains how to select/construct the best suited algorithm when solving a problem. The well-known no free lunch theorem rules out the possibility of developing one best algorithmgenerally suitable for solving all problems. Within the realm of algorithm selection in general, the problem becomes how can we characterise problem hardness with reference to evolutionary algorithms (EAs). For the first time, this chapter rigorously derives a problem hardness measure from a theoretical difficulty measure widely used in complexity theory of EAs. Furthermore, the proposed measure is applied to construct an offline optimisation algorithm and an online optimisation algorithm. On one hand, the measure is incorporated with a machine learning algorithm for parameter tuning and achieves powerful performance. On the other hand, an adaptive algorithm framework is proposed and shows promising results. We argue that the proposed measure is general, yet powerful as an indicator of EA-hardness, and contribute to the goal of constructing better suited algorithms for solving problems.
Original languageEnglish
Title of host publicationRecent Advances in the Theory and Application of Fitness Landscapes
EditorsHendrik RICHTER, Andries ENGELBRECHT
PublisherSpringer Berlin Heidelberg
Number of pages20
ISBN (Electronic)9783642418884
ISBN (Print)9783642418877
Publication statusPublished - 2014
Externally publishedYes

Publication series

NameEmergence, Complexity and Computation
ISSN (Print)2194-7287
ISSN (Electronic)2194-7295


  • Support Vector Machine
  • Evolutionary Algorithm
  • Problem Instance
  • Problem Hardness
  • Fitness Landscape


Dive into the research topics of 'Fitness Landscapes and Problem Difficulty in Evolutionary Algorithms: From Theory to Applications'. Together they form a unique fingerprint.

Cite this