PaperlayerView exact revision on arXiv

Source-linked AI summary

Comprehensive Feature-Based Landscape Analysis of Continuous and Constrained Optimization Problems Using the R-Package flacco

Pascal Kerschke

arXiv:1708.05258v1stat.ML

TL;DR

Selecting an optimizer is difficult when black-box functions are unknown and evaluations are expensive, while computing multiple landscape features has been fragmented across platforms and packages. This paper presents flacco, an R package that unifies a broad collection of ELA features with visualization and a GUI. It is positioned as a toolbox for landscape analysis and work toward algorithm selection, rather than a solver for optimization or algorithm selection itself.

  • Problem

    Computing multiple ELA features has been complicated because their code was spread across platforms and packages, despite ELA’s relevance to selecting optimizers for unknown problems with expensive evaluations.

    Source: §1 · pp. 2, 4

  • Method

    The paper presents flacco, an R package that unifies landscape feature sets and provides visualizations and a GUI for feature-based landscape analysis.

    Source: §1 · p. 4, §2 · p. 4, §4 · p. 19

  • Results

    flacco bundles numerous landscape features and visualization strategies in one package, simplifying access without requiring experiments across multiple platforms.

    Source: §6 · p. 26

  • Takeaways & Limitations

    flacco is a toolbox for exploratory landscape analysis and work toward algorithm-selection models for single-objective continuous optimization.

    Source: §6 · p. 26

    Three included feature sets lack detailed descriptions and, to the authors’ knowledge, had not been used in published experiments.

    Source: §2 · p. 12

Abstract

from arXiv · show

Choosing the best-performing optimizer(s) out of a portfolio of optimization algorithms is usually a difficult and complex task. It gets even worse, if the underlying functions are unknown, i.e., so-called Black-Box problems, and function evaluations are considered to be expensive. In the case of continuous single-objective optimization problems, Exploratory Landscape Analysis (ELA) - a sophisticated and effective approach for characterizing the landscapes of such problems by means of numerical values before actually performing the optimization task itself - is advantageous. Unfortunately, until now it has been quite complicated to compute multiple ELA features simultaneously, as the corresponding code has been - if at all - spread across multiple platforms or at least across several packages within these platforms. This article presents a broad summary of existing ELA approaches and introduces flacco, an R-package for feature-based landscape analysis of continuous and constrained optimization problems. Although its functions neither solve the optimization problem itself nor the related "Algorithm Selection Problem (ASP)", it offers easy access to an essential ingredient of the ASP by providing a wide collection of ELA features on a single platform - even within a single package. In addition, flacco provides multiple visualization techniques, which enhance the understanding of some of these numerical features, and thereby make certain landscape properties more comprehensible. On top of that, we will introduce the package's build-in, as well as web-hosted and hence platform-independent, graphical user interface (GUI), which facilitates the usage of the package - especially for people who are not familiar with R - making it a very convenient toolbox when working towards algorithm selection of continuous single-objective optimization problems.

1. Introduction

Optimizer performance depends on the structure of the problem, motivating landscape features as numerical, sample-based information for algorithm selection. The introduction presents flacco as a unified package responding to fragmented feature implementations and combining earlier package and GUI work with a detailed feature description.

1. Introduction

  • Landscape features provide numerical, sample-based information about problem properties to help select a well-performing optimizer when performance depends on landscape structure.High-level properties such as multimodality, separability, and variable scaling require expert knowledge and knowledge of the full problem; low-level properties are computed from sampled observations.Source: §1 · p. 2
  • The paper situates this work within a broader field that also includes feature-based landscape analysis for discrete optimization and discretized continuous problems.The introduction mentions cell mapping and barrier-tree approaches for discretized landscapes.Source: §1 · p. 3
  • Earlier studies developed diverse landscape features, but their implementations across platforms meant only a few feature sets were usually combined in one study.The introduction cites approaches based on fitness-distance correlation, dispersion, ruggedness, hill climbing, and information content, among others.Source: §1 · pp. 3–4
  • flacco addresses this fragmentation by bringing the general package idea and its GUI together for the first time, while adding a detailed description of implemented landscape features.The package and GUI had previously been published individually.Source: §1 · p. 4

2. Integrated ELA features

This section describes how flacco organizes and computes landscape features through a shared feature object, including PCA- and coefficient-based features and configurable feature sets. It also covers support for unconstrained and box-constrained problems, package access and contributions, and guidance to keep initial samples modest when evaluations are costly.

Integrated feature collection

  • More than 300 numerical landscape features across 17 feature sets are available by default, with function evaluations and runtime tracked for each set.The package is intended to be extended with feature sets not yet integrated.Source: §2 · p. 4

Feature object

  • A feature object stores sampled inputs and objective values, with optional function definitions, block counts, and bounds; it underpins feature computation and visualization.Bounds default to the initial design's per-variable minima and maxima when omitted.Source: §2 · pp. 4–6

Sampling guidance

  • For restricted evaluation budgets, initial designs of 50·d observations may suffice for some high-level properties; designs above 10,000 observations or 40 features are discouraged without ample resources.The passage also cautions that running every optimizer on every instance may be feasible depending on the problems, algorithms, and resources.Source: §2 · p. 5

Classical ELA features

  • The 83 classical ELA features across six sets include convexity and linearity estimates, derivative-based curvature summaries, and objective-value density measures.Convexity comparisons and derivative estimates require additional function evaluations.Source: §2 · p. 6
  • Other classical sets characterize level sets through classifier errors, local optima and basin structure through local searches, and fitted linear or quadratic models.Level-set errors use configurable thresholds and classifiers, with 10-fold cross-validation by default; local searches use L-BFGS-B by default.Source: §2 · pp. 6–7

Cell mapping and generalized cell mapping

  • Cell mapping features summarize within-cell point locations, normalized neighbor gradients, and estimated convexity; generalized cell mapping treats cells as an absorbing Markov chain and categorizes their attraction behavior.Generalized cell mapping derives features from attractor, transient, periodic, and uncertain cells and their basin probabilities.Source: §2 · pp. 7–8

Barrier tree, nearest better clustering, and dispersion

  • Barrier-tree features encode local optima as leaves and connecting ridges as branches, while nearest-better and dispersion features compare observation distances and distance distributions.Nearest-better features also include distance correlations and an indegree measure; dispersion compares subsets selected by objective-value thresholds with the full design.Source: §2 · pp. 9, 11

Information content and miscellaneous features

  • Information-content features characterize landscape smoothness, ruggedness, or neutrality from a random-walk symbol sequence; three further sets include basic and cellwise linear-model features.The three miscellaneous sets comprise 40 features and lack detailed published-experiment descriptions in the author's account.Source: §2 · pp. 11–12

Integrated ELA features

  • Coefficient-based features include cell-wise means and standard deviations of coefficient-vector lengths and ratios of largest to smallest non-intercept coefficients.The passage also specifies that the coefficients are a priori normalized per cell.Source: §2 · p. 13
  • Four PCA combinations yield ten features measuring components needed to explain 90% of variance and variation explained by the first component.The combinations use initial-design data with or without objective values and covariance or correlation matrices.Source: §2 · p. 13
  • Most feature-set parameters can be changed through control arguments, with defaults generally following the original publications.Parameters include classifiers for level-set features and the partial-information-sensitivity ratio for information-content features.Source: §2 · p. 13
  • For box constraints, 14 of 17 feature sets require no additional evaluations, while convexity, local search, and curvature features are designed to remain feasible.Convexity evaluates midpoints of feasible points; default L-BFGS-B respects bounds, and curvature estimation is adapted to evaluate within bounds, including at borders.Source: §2 · p. 13

3. Exemplary feature computation

The section demonstrates flacco’s feature-computation workflow on Gallagher’s Gaussian 101-me Peaks, from preparing a feature object to calculating and configuring feature sets. It also compares feature-set runtimes and notes practical costs and requirements.

3. Exemplary feature computation

  • The example uses Gallagher’s Gaussian 101-me Peaks, BBOB’s 21st problem, with an 800-point sample over the [−5, 5] bounds and a feature object configured with 8 and 5 blocks.The function is supplied to the feature object because some feature sets require additional evaluations; block counts support cell-based features.Source: §3 · pp. 14, 15, 17
  • From the feature object, users can calculate individual feature sets or compute more than 300 features simultaneously.The example shows angle, dispersion, and nearest better clustering sets; the all-features calculation is also available.Source: §3 · pp. 15–16
  • Feature outputs are mostly numeric and use feature-set abbreviations as prefixes to distinguish similarly named features.The authors caution against interpreting most values individually; they are intended to distinguish problems, usually through automated methods such as machine learning.Source: §3 · p. 16
  • Most feature sets ran in under half a second, but curvature, level set, and local search usually took one to two seconds.Basic features took under a millisecond; repeated computation across many instances can make the slower sets costly, and stochastic sets should be run multiple times to capture variance.Source: §3 · pp. 16–17, Figure 11 · p. 17
  • Some feature sets require information beyond the initial sample, and cell-based features depend on block settings; barrier trees need at least two cells and cell-mapping convexity needs three blocks per dimension.The feature object can store the function definition for additional evaluations and the block counts used to form a grid.Source: §3 · p. 17
  • A shared control argument can change settings across feature sets, including using Manhattan distance for dispersion and selecting the “min” and “near” GCM approaches.The same shared control mechanism also works when calculating all feature sets together.Source: §3 · pp. 17–18

4. Visualisation techniques

flacco’s plots make several landscape-feature representations visually interpretable, from cell mappings and barrier trees to information-content curves. It also offers a feature-importance plot for reviewing selection across cross-validation folds.

Cell mapping

  • Cell-mapping plots show representative cell fitness, attractors, uncertain and certain cells, and arrows toward attractors, with arrow length proportional to transition probability.Representative fitness can be the minimum or mean of sampled values in each cell.Source: §4 · pp. 18–19

Barrier trees

  • Barrier trees can be overlaid on cell mappings in 2D or on discretized-space plots in 3D, with roots, saddle points, leaves, and branches distinguished visually.Branches at the same level share a color; roots are red triangles, saddle points unfilled diamonds, and leaves filled circles.Source: §4 · p. 19

Information content

  • Information-content plots relate log information sensitivity ε to partial information content, with marked values corresponding to features such as Hmax and εs.The solid red curve is H(ε), the dashed blue curve is M(ε), and markers identify M0, Hmax, ε0.5, and εs.Source: §4 · p. 19

Feature importance

  • The Feature Importance Plot summarizes feature selection across 10 cross-validation folds, marking features selected in at least 80% of iterations as important.The plot can be generated from a list containing one vector of selected feature names per fold.Source: §4 · pp. 20–21, Figure 12 · p. 20

5. Graphical user interface

The GUI brings flacco’s feature computation and visualizations to researchers unfamiliar with R through an in-package interface or a platform-independent web application. It supports single-problem analysis and batch computation across benchmark instances.

Access

  • The GUI provides access to flacco for users unfamiliar with R and can run within R or as a platform-independent web application.It was implemented using the R package shiny.Source: §5 · p. 21

Single Function Analysis

  • Single Function Analysis accepts a user-defined function, a smoof or BBOB problem, or imported observations and objective values as the basis for a feature object.The interface collects dimension, boundaries, sample settings, and cells per dimension, then presents feature calculation or visualization output.Source: §5 · p. 22

Visualizations

  • The GUI can display cell mappings, barrier trees, information-content plots, and function plots, with information-content plots currently the only option for problems above two dimensions.Function plots are interactive; the available function views include 1D plots and 2D contours or 3D surfaces.Source: Figure 14 · p. 23, §5 · p. 24

Visualization settings

  • For cell-mapping and barrier-tree plots, users can choose the cell’s minimum, mean, or nearest-to-center sample objective value as its representative value.For information-content plots, users can configure the range of logarithmic information-sensitivity values on the x-axis.Source: §5 · p. 24

Batch computation

  • The authors recommend computing feature sets across a benchmark rather than interpreting single features on single problems, to distinguish instances and predict optimizers or adapt their parameters.The GUI supports batch computation of a feature set or all feature sets over multiple instances.Source: §5 · p. 24
  • The GUI supports batch feature computation across BBOB or smoof problems, with outputs downloadable as CSV files.For BBOB, the input CSV specifies function ID, instance ID, and dimension; for smoof, it specifies dimension. The authors recommend at least 5–10 replications because many features are stochastic.Source: §5 · pp. 24–25

6. Summary

flacco bundles landscape features and visualizations in one package, providing a toolbox for exploratory landscape analysis and work toward algorithm-selection models. Its GUI also extends access to people unfamiliar with R.

Summary

  • flacco computes numerous numerical features of continuous single-objective landscapes from relatively small decision-space samples, bundling feature sets in one package.The package’s visualizations support analysis and illustration of feature sets to improve their comprehensibility.Source: §6 · p. 26
  • The package can be combined with mlr or smoof in work toward algorithm-selection models for single-objective continuous optimization.The paper presents flacco as a foundation for further research into algorithm-selection scenarios and optimization algorithms.Source: §6 · p. 26
  • A GUI available within R or as a standalone web application lets people unfamiliar with R use flacco’s functionality without interfacing with or reimplementing features.Source: §6 · p. 26
Loading 1708.05258v1…