Performance Analysis of Continuous Black-Box Optimization Algorithms via Footprints in Instance Space - PubMed Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2017 Winter;25(4):529-554.
doi: 10.1162/EVCO_a_00194. Epub 2016 Sep 30.

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

Mario A Muñoz  1 , Kate A Smith-Miles  2
Affiliations

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

Mario A Muñoz et al. Evol Comput. 2017 Winter.

Abstract

This article presents a method for the objective assessment of an algorithm's strengths and weaknesses. Instead of examining the performance of only 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, that is, 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, that is, 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.

PubMed Disclaimer

Similar articles

See all similar articles

LinkOut - more resources