# Sampling Effects on Algorithm Selection for Continuous Black-Box Optimization
## 4 Selector Implementation
As a result, we have five samples for each dimension. The samples have sizes \(n\) equal to \(\{100,178,316,562,1000\}\times D\) points, where each one is roughly \(80\%\) larger than the previous. We generate the input samples, \(\mathbf{X}\), using MATLAB's Latin Hypercube Sampling function lhsdesign with default parameters. We generate the output sample, \(\mathbf{Y}_{f,i}\), by evaluating \(\mathbf{X}\) in one of the first 15 instances of the 24 functions from COCO, guaranteeing that the differences observed on the ELA features only depend on the function value and sample size, as illustrated in Figure 4. As \(D\) increases, the size of \(\mathbf{X}\) becomes relatively smaller because the input space has increased \begin{table}
\begin{tabular}{l l r} \hline \hline
**Algorithm** & **Description** & **Reference** \\ \hline \((1+2)_{n}^{m}\)CMA-ES & A simple CMA-ES variant, with one parent and two offspring, sequential selection, mirroring and random restarts. & [42] \\  & All other parameters are set to the defaults. & \\ \hline BFGS & The MATLAB implementation (fminunc) of this quasi-Newton method, which is randomly restarted whenever a numerical error occurs. The Hessian matrix is iteratively approximated using forward finite differences, with a step size equal to the square root of the machine precision. Other than the default parameters, the function and step tolerances were set to \(10^{-11}\) and \(0\), respectively. & [43] \\ \hline BIPOP-CMA-ES & A multistart CMA-ES variant with equal budgets for two interlaced restart strategies. After completing a first run with a population of size \(\lambda_{\text{def}}=4+\lfloor 3+\ln D\rfloor\), the first strategy doubles the population size; while the second one keeps a small population given by \(\lambda_{\text{s}}=\left\lfloor\lambda_{\text{def}}\Big{(}\frac{1}{2}\frac{ \lambda_{\text{s}}}{\lambda_{\text{def}}}\Big{)}^{\ell(0,1)^{2}}\right\rfloor\), where \(\lambda_{\ell}\) is the latest population size from the first strategy, \(\lambda\), and \(\mathcal{U}[0,1]\) is an independent uniformly distributed random number. Therefore, \(\lambda_{\text{s}}\in[\lambda_{\text{def}},\lambda/2]\). All other parameters are at default values. & \\ \hline LSfminbnd & The MATLAB implementation (fminbnd) of this axis parallel line search method, which is based on the golden section search and parabolic interpolation. It can identify the optimum of quadratic functions in a few steps. On the other hand, it is a local search technique; it can miss the global optimum (of the 1D function). & [45] \\ \hline LSstep & An axis parallel line search method effective only on separable functions. To find a new solution, it optimizes over each variable independently, keeping every other variable fixed. The STEP version of this method uses interval division, i.e., it starts from an interval corresponding to the upper and lower bounds of a variable, which is divided by half at each iteration. The next sampled interval is based on its “difficulty”, i.e., by its belief of how hard it would be to improve the best-so-far solution by sampling from the respective interval. The measure of difficulty is the coefficient \(a\) from a quadratic function \(f(x)=ax^{2}+bx+c\), which must go through the both interval boundary points. & [46] \\ \hline Nelder–Mead & A version of the Nelder–Mead algorithm that uses random restarts, resizing and half-runs. In a resizing step, the current simplex is replaced by a “fat” simplex, which maintains the best vertex, but relocates the remaining ones such that they have the same average distance to the center of the simplex. Such steps are performed every 1000 algorithm iterations. In a half-run, the algorithm is stopped after \(30\times D\) interations, with only the most promising half-runs being allowed to continue. & \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Summary of the algorithms employed in this paper, which were selected using ICARUS [41] and the publicly available results from the BBOB sessions at the 2009 and 2010 GECCO Conferences.