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. © 1997-2012 IEEE.
Bibliographical noteThis 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.
- Algorithm selection task
- dynamic fitness landscape analysis
- population evolvability
- population-based metaheuristic algorithms