# A Survey of Advances in Landscape Analysis for Optimisation
## 3 Advances in Landscape Analysis
### Techniques for Landscape Analysis
\begin{table}
\begin{tabular}{l l} \hline \hline Technique 23: & **Local optima networks (LONs)** by [PERSON] et al. [23] with extensions [24; 25; 26; 27; 28; 29; 30; 31]. \\ Years: & 2008 \\ Focus: & Global landscape structure \\  & Requires a complete enumeration of a discrete search space. Later extensions are based on samples to produce approximate LONs [32; 33] and are adapted for continuous spaces [34]. \\  & A LON is a graph-based abstraction of the search space representing the global structure, where each node of the LON is a local optimum and edges between nodes represent adjacency of the basins of optima (the possibility of search transitioning from one local optimum to another). The LON model is also extended to multiobjective problems to form pareto local optimal solutions networks (PLOS-nets) [30; 31]. More detail and resources on LONs can be found on the website: [[http://lomaps.com](http://lomaps.com)]([http://lomaps.com](http://lomaps.com)). \\ Result: & A graph visualisation showing the connectivity between local optima. Metrics can also be extracted from LONs such as number of optima, size of basins of attraction, shortest path to the global optimum [35], as well as funnel metrics [36; 37], and PageRank centrality [38]. \\ \hline Technique 24: & **Exploratory landscape analysis (ELA)** by [PERSON] et al. [39] with extensions [40]. \\ Year: & 2011 \\ Focus: & Low-level features based on small samples \\ Assumptions: & Assumes a continuous search space. \\  & Based on a small sample of random solutions (using Latin Hypercube sampling), six classes of low level features are defined: (1) convexity, (2) \\  & \(y\)-distribution, (3) levelset, (4) meta-model, (5) local search, and (6) curvature. Features are estimations of attributes such as the probability of the objective function being linear, the skewness of the distribution of the function values, the accuracy of fitted meta models, the number of local optima identified by local search, estimated numerical gradient and so on. The standard ELA feature set was later extended to include features based on general cell mapping (GCM) [40], but these are currently limited to low-dimensional spaces. ELA is supported by an online package in R, called face [41; 42] ([[https://github.com/lexestre/flasco/](https://github.com/lexestre/flasco/)]([https://github.com/lexestre/flasco/](https://github.com/lexestre/flasco/))). \\ Result: & 50 numerical values for the standard ELA feature set and a further 44 values for GCM features. \\ \hline Technique 25: & **Length scale distribution** by [PERSON] and [PERSON] [43] with extensions [44]. \\ Year: & 2012 \\ Focus: & Variation in gradient estimations across the search space \\ Assumptions: & Assumes a distance metric in solution space. \\  & Based on a sample of solutions from a random. [PERSON] walk through the search space, the length scale (the absolute difference in fitness over the distance in space) is calculated for each pair of solutions in the sample. The length scale distribution is defined as the probability density function of length scales and is estimated using kernel density estimation on the sample of length scales. \\ Result: & Plot of length scale distribution and a single value for the estimated entropy of the length scale distribution. \\ \hline Technique 26: & **Codynamic landscape measures** by [PERSON] [10]. \\ Year: & 2014 \\ Focus: & Similarity between the objective and subjective landscapes in coevolution \\ Assumptions: & Assumes a model of coevolution for fast evaluation of subjective and objective fitness values. \\  & Given a sample of points in the search space and two coupled and codynamic landscapes: the objective landscape (the fitness landscape of the problem) and the subjective landscape (how the coevolution perceives the problem) landscape measures are defined to quantify differences between the landscapes. \\ Result: & Three numeric values at each generation, quantifying different aspects of similarity. \\ \hline Technique 27: & **Degree of separability** by [PERSON] et al. [45]. \\ Year: & 2014 \\ Focus: & Nonseparability \\ Assumptions: & Assumes a continuous search space and the use of the covariance matrix adaptation evolution strategy (CMA-ES) search algorithm. \\  & A portion of the budget of the CMA-ES algorithm is executed on the problem. After a limited number of generations, the matrix CE evolves to estimate the covariance matrix describing the correlation between pairs of variables. The degree of separability is defined as the average of the absolute values of the Pearson correlation matrix of **C** (ignoring symmetrical and diagonal elements) after discretisation of the coefficients into classes in \(0.2,0.4,0.6,0.8\). \\ Result: & An index in the range \([0,1]\) where 0 indicates full separability and 1 indicates full nonseparability. \\ \hline Technique 28: & **Constrained landscape metrics** by [PERSON] et al. [5]. \\ Year: & 2015 \\ Focus: & Constraint violation in relation to fitness \\ Assumptions: & Assumes that the extent to which constraints are violated can be quantified for all solutions. \\  & Given a sequence of solutions based on a progressive random walk [46], with associated fitness and level of constraint violation for each solution, the following are estimated: (1) the proportion of feasible solutions in the search space (F=8R), (2) the level of disjointedness between feasible areas, \\ Description: & quantified as the ratio of feasible boundary crossings (RFB\({}_{n}\)), (3) the correlation between the fitness and violation (FVC), and (4) the proportion of solutions that are both high in fitness and low in constraint violation, in the form of two metrics: proportion of solutions in the top 50\% percentile and 20\% percentile for both fitness and violation. \\ Result: & A vector of five numerical values. \\ \hline Technique 29: & **Bag of local landscape features** by [PERSON] and [PERSON] [47]. \\ Year: & 2016 \\ Focus: & Relative fitness patterns in local neighbourhood \\ Assumptions: & Assumes a distance metric in solution space. \\  & Given a sample of solutions for size \(\lambda\), the local neighbourhood of a solution is defined as the \(M\) nearest solutions in the sample, based on a distance metric in solution space. \\  & The \(LLP\) (local landscape pattern) of a solution is a pattern number corresponding to the binary sequence characterising \\ Description: & the relative fitness of \(M\) nearest neighbours to the current solution. The \(LLP\) of \(x_{i}\) is of (string of \(M\) /s) if all \(M\) neighbours are filter than \(x_{i}\), and \\  & \(2^{M}-1\) (string of \(M\) /s) if \(x_{i}\) is filter than all \(M\) neighbours. The \(Evo\) (revolvability) of \(x_{i}\) is defined as the number of better neighbours (out of \(M\)). \\  & Histograms are constructed to characterise the distribution of \(LLP\) and \(Evo\) values of all solutions in the sample. \\ Result: & Two vectors: BoLLP (of length \(2^{M}\)) and BoEvo of length \(M+1\), representing the normalised histograms of \(LLP\) and \(Evo\), respectively. Principle component analysis is used to reduce the dimensions of the vectors for analysis. \\ \hline Technique 30: & **Maximum entropic epistasis (MEE)** by [PERSON] et al. [48]. \\ Year: & 2017 \\ \hline Assumptions: & Variable interactions (direct and indirect) \\ Assumptions: & Assumes a continuous search space. \\  & For each pair of decision variables \(x_{i},x_{j}\), the interaction matrix for direct interactions (\((IM_{d})\) is identified by calculating the maximal information coefficient (largest mutual information at different scales) between \(x_{i}\) and the estimated partial derivative of the objective with respect to \(x_{i}\). The \(IM_{d}\) is then used to construct an interaction graph to map the strongly connected components to identify the indirect interactions. \\ Result: & Three measures: (1) the degree of direct variable interaction (DUVI), (2) the degree of indirect variable interactions (DIVI), and (3) the degree of variable interactions (DVI). \\ \hline \hline \end{tabular}
\end{table}