🏔️ Analyse des paysages de fitness

Les métriques des paysages de fitness quantifient différents aspects de la difficulté d'un problème. Les métriques courantes incluent :

• Rugosité : Le nombre et la distribution des optima locaux dans le paysage.
• Épistasie : Le degré auquel la contribution d'une variable à la fitness dépend des valeurs des autres variables.
• Autocorrélation : La corrélation entre les valeurs de fitness de solutions voisines, qui capture la régularité du paysage.
• Neutralité : La proportion de solutions voisines ayant une fitness égale, formant des réseaux neutres dans le paysage.

L'épistasie — la dépendance de la contribution d'une variable à la fitness vis-à-vis des valeurs d'autres variables — est un moteur clé de la difficulté des problèmes pour les algorithmes évolutionnaires. La recherche a examiné comment l'épistasie est liée à la performance de différents algorithmes, particulièrement les EDA, et comment l'analyse du paysage peut guider la conception de décompositions de problèmes qui facilitent la recherche.

Le modèle de paysage NK, introduit par Stuart Kauffman, fournit un benchmark ajustable pour étudier la relation entre la structure du problème et la performance de l'algorithme. Le paramètre N contrôle le nombre de variables, tandis que K contrôle le degré d'interactions épistatiques entre les variables. À mesure que K augmente de 0 à N-1, le paysage passe d'un état lisse et unimodal à un état rugueux et multimodal.

Mes recherches sur les paysages NK ont examiné comment la structure d'interaction des paysages NK est liée aux modèles appris par les EDA, comment les propriétés du paysage changent avec différentes topologies d'interaction, et comment les réseaux de neurones peuvent fournir des représentations compactes des structures de paysage NK.

Extension du modèle de paysage NK au cadre multi-objectif, incluant le développement de paysages NK multi-objectifs avec des objectifs hétérogènes (où différents objectifs ont différentes structures épistatiques). Ces benchmarks fournissent un environnement contrôlé pour étudier le comportement des algorithmes évolutionnaires multi-objectifs sur des problèmes aux propriétés de paysage connues.

Étude de la relation entre la structure épistatique des paysages NK et les réseaux bayésiens appris par les EDA lors de la résolution de ces problèmes. Recherche sur la capacité des EDA à identifier la véritable structure d'interaction des paysages NK et comment cette capacité est liée à la performance d'optimisation.

Les réseaux d'optima locaux (LON) modélisent la structure de l'ensemble des optima locaux dans un paysage de fitness sous forme de graphe, où les nœuds sont les optima locaux et les arêtes représentent les transitions possibles entre eux. Recherche sur les propriétés des LON pour les problèmes combinatoires et leur relation avec la performance des algorithmes, particulièrement pour les EDA et d'autres méthodes de recherche basées sur des populations.

Analyse de la corrélation fitness-distance (FDC) comme prédicteur de la difficulté d'un problème. La FDC mesure la corrélation entre la fitness d'une solution et sa distance à l'optimum global le plus proche. Recherche sur les conditions dans lesquelles la FDC prédit avec précision la difficulté des problèmes pour différentes classes d'algorithmes.

Recherche sur la relation entre les propriétés du paysage et la performance d'algorithmes spécifiques. L'objectif est d'identifier quelles caractéristiques du paysage rendent un problème facile ou difficile pour un algorithme donné, permettant la sélection et la configuration d'algorithmes basées sur l'analyse du paysage. Cela relie l'analyse des paysages de fitness au problème de la sélection d'algorithmes en apprentissage automatique.

Étude des modèles probabilistes appris par les EDA comme sondes du paysage de fitness. Le modèle appris à chaque génération d'un EDA encode des informations sur les dépendances entre les variables qui sont importantes pour la fitness, capturant ainsi des aspects de la structure du paysage. Recherche sur la manière d'extraire et d'utiliser ces informations pour améliorer la compréhension du problème.

Découverte que les plongements neuronaux des solutions de paysages NK présentent une forme de boomerang caractéristique lorsqu'ils sont projetés dans un espace bidimensionnel. Cette structure géométrique émerge de l'interaction entre la structure épistatique du paysage et la représentation apprise par le réseau de neurones. Recherche sur les origines de cette structure et ses implications pour la compréhension de la géométrie du paysage.

Utilisation de réseaux de neurones pour apprendre des représentations compactes des structures de paysages de fitness qui peuvent être utilisées pour la caractérisation des paysages, la sélection d'algorithmes et la prédiction de la performance des algorithmes. Recherche sur la manière dont différentes architectures de réseaux et objectifs d'apprentissage capturent différents aspects de la géométrie du paysage.

• 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.