Black-box optimization problems are of practical importance throughout science and engineering. Hundreds of algorithms and heuristics have been developed to solve them. However, none of them outperforms any other on all problems. The success of a particular heuristic is always relative to a class of problems. So far, these problem classes are elusive and it is not known what algorithm to use on a given problem. Here we describe the use of Formal Concept Analysis (FCA) to extract implications about problem classes and algorithm performance from databases of empirical benchmarks. We explain the idea in a small example and show that FCA produces meaningful implications. We further outline the use of attribute exploration to identify problem features that predict algorithm performance.
Optimization problems are ubiquitous in science and engineering, including
optimizing the parameters of a model [
Owing to their practical importance, hundreds of algorithms and heuristics
have been developed to (approximately) solve black-box optimization problems.
The \No Free Lunch Theorem" [
We aim at developing a recommender system for proposing e cient
algorithms for a given black-box optimization problem. Formal Concept Analysis
(FCA) [
We consider real-valued scalar black-box problems, modeled as an oracle function f : Rd ! R mapping a d-tuple x of real numbers (problem parameters) to a scalar real number f (x) (objective function value). The function f is not assumed to be explicitly known. A black-box optimization problem entails nding extremal points of f using only point-wise function evaluations. The iterative sequence of evaluations used to progress toward an extremum is called the search strategy.
The Black-Box Optimization Benchmark (BBOB) test suit is a standard
collection of test functions used to empirically benchmark di erent optimization
heuristics [
(a) Sphere (b) Rastrigin sep.
(c) Weierstrass (d) Katsuura
A problem instance is a triple (f; d; ), where f is an instance of a black-box function, d > 0 is the parameter space dimension, and 2 R 0 a tolerance. Solving a problem instance (f; d; ) means nding a d-tuple x 2 Rd such that jfmin f (x)j < , where fmin is the global minimum of f . Note that the groundtruth global minimum fmin is known for the benchmark functions, but not in a practical problem instance. 3
We propose a system for recommending suitable algorithms for a given
blackbox optimization problem based on FCA. Similar recommender systems, albeit
not based on FCA, have been suggested [
A run of an algorithm solving a problem instance is called successful. The
performance of an algorithm a on a problem instance p is measured by the expected
running time (ERT) [
ERT(a; p) = N +(a; p) + 1
+(a; p) +(a; p)
N (a; p); where N +(a; p) and N (a; p) are the average numbers of function evaluations for successful and unsuccessful runs of a on p, respectively, and +(a; p) is the ratio of the number of successful runs over the number of all runs of a on p.
The problem instances (fj ; d; ), where j 2 f1; :::; 24g, d 2 f2; 3; 5; 10; 20; 40g, and 2 E = f103, 101, 10 1, 10 3, 10 5, 10 8g, have been used to test over 112 algorithms; the dataset is available online.1 Note that the algorithms treat the benchmark functions as black boxes, i.e., they only evaluate the functions, whereas the actual function remains hidden to the algorithm. The known global minimum is only used to evaluate the performance of the algorithms.
Often, algorithms cannot solve problem instances for any tolerance value within a certain number of function evaluations; see Table 1. To obtain a performance measure also in these cases, we introduce a penalty of 106 for every tolerance level that the algorithm could not solve. This penalized ERT (pERT) of an algorithm a on an instance f of a benchmark function in d dimensions for a set E of tolerances is here de ned as:
ERT(a; (f; d; best)) pERT(a; f; d; E) =
d where best is the smallest value in E such that ERT(a; (f; d; )) 6= 1. + 106jf 2 E j ERT(a; (f; d; )) = 1gj;
Table 1 shows the performance values of four algorithms on the benchmark
functions Sphere and Rastrigin separable in 10 dimensions. The algorithm
(1+1)CMA-ES implements an evolutionary strategy with covariance matrix
adaptation [
74
3 450
10 3
standard PSO [
Functions can be characterized by features. Several high-level features have
been hypothesized to predict black-box optimization algorithm performance,
such as multi-modality, global structure, and separability [
multi-modality global structure separability modality refers to the number of local minima of a function.
Global structure refers to the structure that emerges when only considering minima (in a minimization problem ), i.e., the point set left after deleting all nonoptimal points. Separability speci es whether a function is a Cartesian product of one-dimensional functions. For instance, the Sphere function (Fig. 1(a)) is unimodal and, therefore, has no global structure (only one point remains when restricting to minima) and is highly separable. The separable Rastrigin function (cf. Fig. 1(b)) is separable, highly multimodal, and has a strong global structure (the set of local minima forms a convex funnel). 3.3
Di erent numerical measures have been suggested to estimate the features of a
black-box function from sample evaluations. These include tness distance
correlations [
Step 1: estimate features of input function Step 2: imply features of algorithms that do well on functions with such features Step 3: pick an algorithm that has these features (Step 2) is done using implications that form the background knowledge of the recommender system. The premise of an implication contains algorithm features together with features of benchmark functions, whereas the conclusion consists of attributes corresponding to the performances of the algorithms when solving the functions. The implications are obtained from the BBOB database by FCA. More precisely, we build a formal context K = (G; M; I), where G is the set of objects consisting of all pairs of benchmark functions and algorithms, M is the set of attributes consisting of the features of algorithms and benchmark functions together with the attributes assigned to performance values, and I is the incidence matrix between the objects in G and the attributes in M . We obtain the implications from the context K by computing the canonical base (or another implicational base) of K.
We illustrate our approach in Table 3. The objects are pairs of benchmark functions and algorithms, as introduced in Sec. 3.2. The attributes are features of algorithms, performance attributes Pi, for i 2 f 0; 5; 6; 7 g;2 and the function features (Table 2). As algorithm features we use the respective names of the algorithms together with the features deterministic and hybrid (stating that the algorithm is a combination of di erent search strategy). We consider Table 3 as a formal context and compute its canonical base to obtain the implications: 2 To obtain a binary table, we partition the range of pERT-values into 10 intervals and introduce attribute names Pi for the intervals.
f (1+1)-CMA-ES; multimod high g ! f P6 g
f PSO; sep high g ! f P0 g
f PSO; sep none; multimod high g ! f P6 g
f PSO-BFGS; sep high; globstruct strong; multimod high g ! f P6 g
f sep high; globstruct none g ! f P0 g
f sep none; multimod high; globstruct none; Alg hybrid g ! f P5 g
f globstruct med g ! f P6 g
Based on this background knowledge, the recommender system would, e.g.,
suggest to use the algorithm PSO for functions with high separability. If additionally
the function does not exhibit a global structure (e.g., the function is unimodal),
then any algorithm would do well. For functions with high multi-modality, no
separability, and no global structure, the system would recommend a hybrid
algorithm over (1+1)-CMA-ES, con rming previous observations [
We note that the quality of the recommendations made by the system depends on the \quality" of the implications constituting the background knowledge. To obtain better recommendations (Step 3), suitable features of the input function need to be e ciently computable (Step 1) and the implications need to form a basis of a su cient benchmark set (Step 2). 4
It is not clear that the function features currently used in the optimization
community de ne meaningful problem classes with respect to expected algorithm
performance. It is an open and non-trivial problem to discover new features for
this purpose. We sketch a method that could assist an expert in nding new
features using attribute exploration from FCA [
In attribute exploration, we start from an initial formal context K and a set S of valid implications of K. Then, we compute new implications A ! B such that A ! B is valid in K, but does not follow from S, where A and B are sets of attributes. In case such an implication can be found, a (human) expert has to con rm or reject A ! B. In the former case, A ! B is added to S. If the expert rejects A ! B, s/he has to provide a counterexample that is then added to K. If no new implications can be computed any more, the search terminates.
Consider the context Kfeatures = (G; M; I), where G is the set of benchmark functions, M the set of function features, and the incidence relation I represents the fact that a function has a certain feature. Applying attribute exploration directly to Kfeatures would not work, as we are seeking new attributes (features), and not new objects (benchmark functions). Since objects and attributes behave symmetrically in every formal context, however, we can apply attribute 1 exploration to the dual context Kfeatures = (M; G; I 1).
1
Implications from Kfeatures are of the form f fi1 ; : : : ; fij g ! f fij+1 g, fik 2 G. Presenting such implications to an expert means asking whether all features that Testfunction
Algorithm fi1 ; : : : ; fij have in common are also features of function fij+1 . A counterexample would then correspond to a new feature that fi1 ; : : : ; fij have in common, but that is not shared by fij+1 . These are the features we are looking for.
To illustrate the method, suppose that the context Kfeatures contains the same functions as in Table 3, but the feature multi-modality as the only attribute. Then, using our approach, the expert would need to judge the implication f Rastrigin g ! f Weierstrass g; and s/he could reject the implication by providing a \new" feature global structure strong, which the separable Rastrigin function has, but the Weierstrass function has not (counterexample). 5
We have outlined the use of FCA in building a recommender system for blackbox optimization. The implications resulting from the small, illustrative example presented here are meaningful in that they both con rm known facts and suggest new ones. Attribute exploration could moreover be a powerful tool for discovering new features that are more predictive of the expected performance.
The ideas presented here are work in progress. Ongoing and future work will address the computability/decidability of features on black-box functions, and evaluate the proposed FCA-based recommender system using the BBOB database. We will investigate novel function and algorithm features, and compare the results obtained by FCA with results from clustering and regression analysis.