Exploratory Landscape Analysis (ELA)

Due to the steadily increasing amount of suggested optimization algorithms the selection of the “best” algorithm for a given optimization problem has become a very complex challenge. A formal discussion of this issue dates back to as early as 1976 and is denoted as the algorithm selection problem (AS). As it is well-known that a global best algorithm for all kind of optimization problems does not exist, one is especially interested in giving algorithm recommendations for certain classes of optimization problems which differ in the kind of exhibited problem characteristics. Currently, the AS problem is still an unsolved issue except from very special cases.

Systematically designed benchmarks form the basis for meaningfully addressing the AS problem. In recent years several benchmark sets comprising test problems with different characteristics, both for single-objective as well as multiobjective continuous optimization tasks were constructed. However, the performance assessment and ranking of the participating algorithms was usually addressed in a rather ad-hoc manner. Thus, the validity of the results might be questionable. In general, the outcome of a benchmark study strongly depends on the kind of analysis and interpretation method used. In Mersmann et al. (2010, see link below) a systematic benchmarking framework was introduced. The test problem set has to be constructed such that it ideally represents the whole problem domain in order to allow for a generalization of the benchmarking results.

However, performance rankings of optimization algorithms alone are not sufficient in order to give algorithm recommendations for unseen problems. One is rather interested in deriving rules for determining how problem properties influence algorithm performance and in grouping test problems into classes for which similar performance of the optimization algorithms can be observed. Exploratory Landscape Analysis (ELA) aims at solving these issues by deriving cheaply computable problem features based on which models relating features to algorithm performance can be constructed based on the benchmark experiments. The final goal is an accurate prediction of the best suited algorithm for an arbitrary optimization problem based on the computed features.

During the last years the respective research groups at (formerly) TU Dortmund and currently University of Münster and LMU Munich successfully made important steps into this direction for single-objective continuous optimization problems. Links to selected papers are provided below.

Additionally, the groups focus on combinatorial optimization problems as well in collaboration with the research groups of Frank Neumann (University of Adelaide, Australia) and Holger Hoos (University of British Columbia, Canada). In particular, a set of meaningful experimental features for characterizing properties of Traveling Salesman problems (TSP) was set up and it was investigated which properties determine the hardness of TSP instances for specific algorithms. Additionally, feature-based per-instance algorithm selection for TSP is a matter of current research.

Selected Research Articles and Material

Benchmarking Concepts

Exploratory Landscape Analysis / Algorithm Selection for Contininuous Optimization Problems

Exploratory Landscape Analysis / Algorithm Selection for Combinatorial Optimization Problems

R-Packages

  • FLACCO (official release on CRAN or developers version on github):
    This package is a collection of exploratory landscape features for Black-Box-Optimization Problems.
  • smoof (official release on CRAN or developers version on github):
    This package contains lots of single- and multi-objective test functions, which are widely used within the literature for benchmarking numerical optimization algorithms.
  • salesperson (developers version on github):
    The salesperson package contains function to compute a large set of features for TSP problem instances. Moreover, it contains an interface to a wide variety of TSP solvers including the exact state-of-the-art solver concorde and the inexact state-of-the-art solvers LKH and EAX.