Algorithm selection for black-box continuous optimization problems: A survey on methods and challenges

Mario Andres Munoz Acosta, Yuan Sun, Michael Gerard Kirley, Saman Kumara Halgamuge

Research output: Contribution to journalArticleResearchpeer-review

93 Citations (Scopus)

Abstract

Selecting the most appropriate algorithm to use when attempting to solve a black-box continuous optimization problem is a challenging task. Such problems typically lack algebraic expressions, it is not possible to calculate derivative information, and the problem may exhibit uncertainty or noise. In many cases, the input and output variables are analyzed without considering the internal details of the problem. Algorithm selection requires expert knowledge of search algorithm efficacy and skills in algorithm engineering and statistics. Even with the necessary knowledge and skills, success is not guaranteed. In this paper, we present a survey of methods for algorithm selection in the black-box continuous optimization domain. We start the review by presenting Rice s (1976) selection framework. We describe each of the four component spaces - problem, algorithm, performance and characteristic - in terms of requirements for black-box continuous optimization problems. This is followed by an examination of exploratory landscape analysis methods that can be used to effectively extract the problem characteristics. Subsequently, we propose a classification of the landscape analysis methods based on their order, neighborhood structure and computational complexity. We then discuss applications of the algorithm selection framework and the relationship between it and algorithm portfolios, hybrid meta-heuristics, and hyper-heuristics. The paper concludes with the identification of key challenges and proposes future research directions.
Original languageEnglish
Pages (from-to)224-245
Number of pages22
JournalInformation Sciences
Volume317
DOIs
Publication statusPublished - 2015

Keywords

  • Algorithm selection
  • Black-box continuous optimization
  • Empirical performance models
  • Exploratory landscape analysis
  • Performance prediction
  • Problem hardness measures

Cite this