Performance Analysis of Continuous Black-Box Optimization Algorithms via Footprints in Instance Space.
Evol Comput
; 25(4): 529-554, 2017.
Article
em En
| MEDLINE
| ID: mdl-27689468
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.
Palavras-chave
Texto completo:
1
Coleções:
01-internacional
Base de dados:
MEDLINE
Assunto principal:
Algoritmos
/
Simulação por Computador
Tipo de estudo:
Prognostic_studies
Idioma:
En
Revista:
Evol Comput
Assunto da revista:
BIOLOGIA
Ano de publicação:
2017
Tipo de documento:
Article