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

11 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

@article{f6c987ca23ee44b4a47d2ac02c2b6ef2,
title = "Performance Analysis of Continuous Black-Box Optimization Algorithms via Footprints in Instance Space",
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.",
keywords = "Algorithm selection, Black-box continuous optimization, Exploratory landscape analysis, footprint analysis, Performance prediction",
author = "Munoz, {Mario A.} and Kate Smith-Miles",
year = "2017",
doi = "10.1162/EVCO_a_00194",
language = "English",
volume = "25",
pages = "529--554",
journal = "Evolutionary Computation",
issn = "1063-6560",
publisher = "Massachusetts Institute of Technology Press",
number = "4",

}

Performance Analysis of Continuous Black-Box Optimization Algorithms via Footprints in Instance Space. / Munoz, Mario A.; Smith-Miles, Kate.

In: Evolutionary Computation, Vol. 25, No. 4, 2017, p. 529-554.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

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

AU - Munoz, Mario A.

AU - Smith-Miles, Kate

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Algorithm selection

KW - Black-box continuous optimization

KW - Exploratory landscape analysis

KW - footprint analysis

KW - Performance prediction

U2 - 10.1162/EVCO_a_00194

DO - 10.1162/EVCO_a_00194

M3 - Article

VL - 25

SP - 529

EP - 554

JO - Evolutionary Computation

JF - Evolutionary Computation

SN - 1063-6560

IS - 4

ER -