Population Evolvability: Dynamic Fitness Landscape Analysis for Population-Based Metaheuristic Algorithms

Mang WANG, Bin LI, Guofu ZHANG, Xin YAO

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

38 Citations (Scopus)

Abstract

Fitness landscape analysis (FLA) is an important approach for studying how hard problems are for metaheuristic algorithms to solve. Static FLA focuses on extracting the properties of a problem and does not consider any information about the optimization algorithms; thus, it is not adequate for indicating whether a particular algorithm is suitable for solving a problem. By contrast, dynamic FLA considers the behavior of algorithms in combination with the properties of an optimization problem to determine the effectiveness of a given algorithm for solving that problem. However, previous dynamic FLA approaches are all individually based and lack statistical significance. In this paper, the concept of population evolvability is presented, as an extension of dynamic FLA, to quantify the effectiveness of population-based metaheuristic algorithms for solving a given problem. Specifically, two measures of population evolvability are defined that describe the probability that a population will obtain improved solutions to a problem and its ability to do so. Then, a combined measure is derived from these two measures to represent the overall population evolvability. Subsequently, the significance and validity of the proposed measures are investigated through analytical and experimental studies. Finally, the utility of the proposed measures is illustrated in an application of algorithm selection for black-box optimization problems. High accuracy in selecting the best algorithm is observed in a statistical analysis, with a low computational cost in terms of fitness evaluations.

Original languageEnglish
Pages (from-to)550-563
Number of pages14
JournalIEEE Transactions on Evolutionary Computation
Volume22
Issue number4
Early online date24 Aug 2017
DOIs
Publication statusPublished - Aug 2018
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 1997-2012 IEEE.

Funding

This work was supported in part by the National Natural Science Foundation of China under Grant 61473271, Grant 61573125, and Grant 61329302, in part by the Ministry of Science and Technology of China under Grant 2017YFC0804003, in part by the Science and Technology Innovation Committee Foundation of Shenzhen under Grant ZDSYS201703031748284, and in part by the EPSRC under Grant EP/K001523/1. The work of X. Yao was supported by the Royal Society Wolfson Research Merit Award.

Keywords

  • Algorithm selection task
  • dynamic fitness landscape analysis
  • population evolvability
  • population-based metaheuristic algorithms

Fingerprint

Dive into the research topics of 'Population Evolvability: Dynamic Fitness Landscape Analysis for Population-Based Metaheuristic Algorithms'. Together they form a unique fingerprint.

Cite this