🏔️ Fitness Landscape Analysis

Fitness landscape metrics quantify different aspects of problem difficulty. Common metrics include:

• Ruggedness: The number and distribution of local optima in the landscape.
• Epistasis: The degree to which the fitness contribution of a variable depends on the values of other variables.
• Autocorrelation: The correlation between fitness values of neighboring solutions, which captures the smoothness of the landscape.
• Neutrality: The proportion of neighboring solutions with equal fitness, forming neutral networks in the landscape.

Epistasis — the dependence of a variable's fitness contribution on the values of other variables — is a key driver of problem difficulty for evolutionary algorithms. Research has examined how epistasis relates to the performance of different algorithms, particularly EDAs, and how landscape analysis can guide the design of problem decompositions that facilitate search.

The NK landscape model, introduced by Stuart Kauffman, provides a tunable benchmark for studying the relationship between problem structure and algorithm performance. The N parameter controls the number of variables, while K controls the degree of epistatic interactions among variables. As K increases from 0 to N-1, the landscape transitions from smooth and unimodal to rugged and multimodal.

My research on NK landscapes has examined how the interaction structure of NK landscapes relates to the models learned by EDAs, how landscape properties change with different interaction topologies, and how neural networks can provide compact representations of NK landscape structures.

Extension of the NK landscape model to the multi-objective setting, including the development of multi-objective NK landscapes with heterogeneous objectives (where different objectives have different epistatic structures). These benchmarks provide a controlled environment for studying the behavior of multi-objective evolutionary algorithms on problems with known landscape properties.

Investigation of the relationship between the epistatic structure of NK landscapes and the Bayesian networks learned by EDAs when solving these problems. Research on whether EDAs can identify the true interaction structure of NK landscapes and how this ability relates to optimization performance.

Local optima networks (LONs) model the structure of the set of local optima in a fitness landscape as a graph, where nodes are local optima and edges represent possible transitions between them. Research on the properties of LONs for combinatorial problems and their relationship to algorithm performance, particularly for EDAs and other population-based search methods.

Analysis of fitness–distance correlation (FDC) as a predictor of problem difficulty. FDC measures the correlation between the fitness of a solution and its distance to the nearest global optimum. Research on the conditions under which FDC accurately predicts the difficulty of problems for different classes of algorithms.

Research on the relationship between landscape properties and the performance of specific algorithms. The goal is to identify which landscape features make a problem easy or hard for a given algorithm, enabling algorithm selection and configuration based on landscape analysis. This connects fitness landscape analysis to the algorithm selection problem in machine learning.

Investigation of the probabilistic models learned by EDAs as probes of the fitness landscape. The model learned in each generation of an EDA encodes information about the dependencies among variables that are important for fitness, effectively capturing aspects of the landscape structure. Research on how to extract and use this information to improve understanding of the problem.

Discovery that neural embeddings of NK landscape solutions exhibit a characteristic boomerang shape when projected onto a two-dimensional space. This geometric structure emerges from the interaction between the epistatic structure of the landscape and the neural network's learned representation. Research on the origins of this structure and its implications for understanding landscape geometry.

Use of neural networks to learn compact representations of fitness landscape structures that can be used for landscape characterization, algorithm selection, and the prediction of algorithm performance. Research on how different network architectures and training objectives capture different aspects of the landscape geometry.

• Santana R, Liefooghe A and Derbel B (2022). Boomerang-shaped neural embeddings for NK landscapes. GECCO 2022.
• Cosson R, Santana R, Derbel B and Liefooghe A (2022). Multi-objective NK landscapes with heterogeneous objectives. GECCO 2022.
• Santana R, Echegoyen C, Mendiburu A and Lozano JA (2012). Evolving NK-complexity for evolutionary solvers. GECCO 2012.
• Santana R, Mendiburu A and Lozano JA (2015). Evolving MNK-landscapes with structural constraints. CEC 2015.
• Santana R, Mendiburu A, Bengoetxea E and Lozano JA (2015). Multi-objective NM-landscapes. GECCO 2015.
• Santana R, Mendiburu A, Bengoetxea E and Lozano JA (2015). Computing factorized approximations of Pareto-fronts using mNM-landscapes and Boltzmann distributions. CEC 2015.
• Martins MS, Yafrani ME, Delgado M, Lüders R, Santana R, Siqueira HV, Akcay HG and Ahiod B (2021). Analysis of Bayesian Network Learning Techniques for a Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm. CODA 2021.