Performance Analysis of Continuous Black-Box Optimization Algorithms via Footprints in Instance Space

Mario A. Munoz, Kate Smith-Miles

Research output: Contribution to journalArticleResearchpeer-review

19 Citations (Scopus)

Abstract

This paper presents a method for the objective assessment of an algorithm's strengths and weaknesses. Instead of examining only the performance of one or more algorithms on a benchmark set, or generating custom problems that maximize the performance difference between two algorithms, our method quantifies both the nature of the test instances and the algorithm performance. Our aim is to gather information about possible phase transitions in performance, i.e., the points in which a small change in problem structure produces algorithm failure. The method is based on the accurate estimation and characterization of the algorithm footprints, i.e., the regions of instance space in which good or exceptional performance is expected from an algorithm. A footprint can be estimated for each algorithm and for the overall portfolio. Therefore, we select a set of features to generate a common instance space, which we validate by constructing a sufficiently accurate prediction model. We characterize the footprints by their area and density. Our method identifies complementary performance between algorithms, quantifies the common features of hard problems, and locates regions where a phase transition may lie.
Original languageEnglish
Pages (from-to)529-554
Number of pages26
JournalEvolutionary Computation
Volume25
Issue number4
DOIs
Publication statusPublished - 2017

Keywords

  • Algorithm selection
  • Black-box continuous optimization
  • Exploratory landscape analysis
  • footprint analysis
  • Performance prediction

Cite this