Fitness Landscape Based Features for Exploiting Black-Box Optimization Problem Structure

TR-2012-163, Authors: Tinus Abell, Yuri Malitsky, and Kevin Tierney

Fitness Landscape Based Features for Exploiting Black-Box Optimization Problem Structure

Tinus Abell
Yuri Malitsky
Kevin Tierney

December 2012

Abstract

We present a robust set of features that analyze the fitness landscape of black-box optimization (BBO) problems. We show that these features are effective for training a portfolio algorithm using Instance Specific Algorithm Configuration (ISAC). BBO problems arise in numerous applications, especially in scientific and engineering contexts. BBO problems are characterized by computationally intensive objective functions, which severely limit the number of evaluations that can be performed. We introduce a collection of problem independent features to categorize BBO problems and show how ISAC can be used to select the best minimization search strategy. We test our methodology on data from the GECCO Workshop on Black-box Optimization Benchmarking 2012, which contains 21 state-of-the-art BBO solvers run on 24 well-established BBO functions, and show that ISAC is able to exploit our general, problem independent features and outperform any single solver.

Technical report TR-2012-163 in IT University Technical Report Series, December 2012.

Available as PDF