# Sampling Effects on Algorithm Selection for Continuous Black-Box Optimization
## 2 Background and Related Work  
### Black-Box Optimization and Fitness Landscapes  
Before describing the methods employed, let us define our notation. Without losing generality over maximization, we assume minimization throughout this paper. The goal in a bound-constrained, single-objective, continuous black-box optimization problem is to minimize a cost function \(f:\mathcal{X}\rightarrow\mathcal{Y}\) where \(\mathcal{X}\subset\mathbb{R}^{D}\) is the _input space_, \(\mathcal{Y}\subset\mathbb{R}\) is the _output space_, and \(D\in\mathbb{N}^{*}\) is the dimensionality of the problem. A _candidate solution_\(\mathbf{x}\in\mathcal{X}\) is a \(D\)-dimensional vector, and the scalar \(y\in\mathcal{Y}\) is the candidate's _cost_. A continuous BBO problem is the one such that \(f\) is unknown; the gradient information is unavailable or uninformative; and there is a lack of specific goals or solution paths. Only the inputsand the outputs of the function are reliable information, and they are analyzed without considering the internal workings of the function. Therefore, a _target solution_, \(\mathbf{x}_{t}\in\mathcal{X}\), is found by sampling the input space. To find a target solution we may use a search algorithm, which is a systematic procedure that takes previous candidates and their cost as inputs, and generates new and hopefully less costly candidates as outputs. For this purpose, the algorithm maintains a simplified model of the relationship between solutions and costs. The model assumes that the problem has an exploitable structure. Hence, the algorithm can infer details about the structure of the problem by collecting information during the run. We call this structure _fitness landscape_[21], which is defined as the tuple \(\mathcal{L}=(\mathcal{X},f,d)\), where \(d\) denotes a _distance_ metric that quantifies the similarity between candidates in the input space. Similar candidates are those where the distance between each one of them is less than a radius \(r\to 0\)[22], forming a _neighborhood_, \(\mathcal{N}_{r}(\mathbf{x})\subset\mathcal{X}\), which defines associations between the candidates in the input space. A _local optimum_ is a candidate \(\mathbf{x}_{t}\in\mathcal{X}\) such that \(y>y_{l}\) for all \(\mathbf{x}\in\mathcal{N}_{r}(\mathbf{x}_{t})\). We denote the set of local optima as \(\mathcal{X}_{l}\subset\mathcal{X}\). The _global optimum_ for a landscape \(\mathcal{L}\) is a candidate \(\mathbf{x}_{o}\in\mathcal{X}\) such that \(y_{l}\geq y_{o}\) for all \(\mathbf{x}_{l}\in\mathcal{X}_{l}\). We denote the set of global optima as \(\mathcal{X}_{o}\subseteq\mathcal{X}_{l}\). A fitness landscape can be described using the cardinality of \(\mathcal{X}_{l}\) and \(\mathcal{X}_{o}\). An _unimodal_ landscape is the one such that \(|\mathcal{X}_{o}|=|\mathcal{X}_{l}|=1\). A _multimodal_ landscape is the one such that \(|\mathcal{X}_{l}|>1\). A closely related concept is _smoothness_, which refers to the magnitude of the change in cost between neighbors. A landscape can be informally classified as rugged, smooth, or neutral. A _rugged_ landscape has large cost fluctuations between neighbors. It presents several local optima and steep ascents and descents. A _neutral_ landscape has large flat areas or plateaus, where changes in the input fail to generate significant changes in the output. At these extremes, both gradient and correlation values are uninformative [23]. The set of local optima \(\mathcal{X}_{l}\) can constitute a pattern known as the _global structure_, which can be used to guide the search for \(\mathbf{x}_{t}\). If the global structure is smooth, it may provide exploitable information. If the global structure is rugged or nonexistent, finding an optimum can be challenging, even impossible [24]. It is also possible to find problems that exhibit _deceptiveness_, i.e., the global structure and gradient information leads the algorithm away from an optimum, resulting in a performance similar to a random search [23].