💻 computer science

MO-ELA: Rigorously Expanding Exploratory Landscape Features for Automated Algorithm Selection in Continuous Multi-Objective Optimisation

Cet article introduit MO-ELA, un nouvel ensemble de caractéristiques de paysage exploratoires dérivées à la fois des espaces de décision et d'objectifs à travers cinq catégories distinctes, qui améliore significativement la sélection automatisée d'algorithmes pour l'optimisation multi-objectif continue en capturant efficacement la difficulté du problème et en distinguant la performance des algorithmes.

Auteurs originaux : Oliver Preuß, Jeroen Rook, Jakob Bossek, Heike Trautmann

Publié 2026-02-03

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Oliver Preuß, Jeroen Rook, Jakob Bossek, Heike Trautmann

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes un chef essayant de décider quelle recette cuisiner pour un dîner. Vous avez un livre de cuisine massif contenant des milliers de recettes (algorithmes), mais vous savez qu'aucune recette ne fonctionne parfaitement pour tous les types d'ingrédients (problème d'optimisation). Certains plats demandent une manipulation délicate, tandis que d'autres demandent une main lourde. Si vous vous trompez, le repas est gâché.

C'est le problème de la Sélection Automatisée d'Algorithmes (AAS). C'est comme si vous aviez un sous-chef intelligent qui regarde vos ingrédients et vous dit instantanément : « Pour ce mélange spécifique d'ingrédients, utilisez la Recette A, pas la Recette B. »

Pendant longtemps, ce « sous-chef » a très bien fonctionné pour la cuisine simple à objectif unique (Optimisation Mono-Objectif). Mais quand l'objectif devient complexe — comme essayer de préparer un plat qui soit à la fois le plus sain et le plus savoureux en même temps (Optimisation Multi-Objectif) — les anciens outils ont échoué. Ils ne pouvaient pas voir la relation complexe entre les deux objectifs.

Ce document présente un nouvel ensemble d'outils surpuissants appelé MO-ELA (Analyse de Paysage Exploratoire Multi-Objectif) pour aider le sous-chef à voir clairement le paysage de ces problèmes complexes.

Le Problème : Naviguer dans une chaîne de montagnes embrumée

Imaginez un problème multi-objectif comme une chaîne de montagnes dans le brouillard où vous essayez de trouver le sommet le plus haut (la meilleure solution). Cependant, vous avez deux objectifs contradictoires : vous voulez être aussi haut que possible (maximiser un objectif) mais aussi aussi proche que possible d'une vallée spécifique (minimiser un autre).

Dans ce brouillard, certains sentiers sont lisses et faciles à grimper, tandis que d'autres sont des falaises escarpées avec de nombreux impasses. Les « anciens » outils ne pouvaient regarder qu'un seul côté de la montagne à la fois, manquant le fait que le terrain change radicalement lorsqu'on regarde l'image globale.

La Solution : Une nouvelle paire de jumelles

Les auteurs ont créé une nouvelle paire de « jumelles » (caractéristiques) pour prendre un instantané rapide de la chaîne de montagne avant de commencer l'ascension. Au lieu de simplement regarder la hauteur du sol, ils regardent comment les points sont liés entre eux dans deux mondes différents :

L'Espace de Décision : Là où les randonneurs se tiennent (les entrées).
L'Espace des Objectifs : À quelle hauteur et à quelle distance de la vallée se trouvent ces randonneurs (les résultats).

Ils ont construit cinq types de lentilles différents pour analyser cet instantané :

La Lentille « Gâteau à Couches » (Tri Non-Dominé) : Imaginez trier les randonneurs en couches. La couche supérieure contient les « super-randonneurs » qui sont meilleurs que tous les autres d'au moins une manière. Cette lentille compte combien il y a de couches et comment les « super-randonneurs » sont répartis. Si les couches sont plates et régulières, la montagne est facile. Si elles sont dentelées et irrégulières, la montagne est difficile.
La Lentille « Instantané Statistique » : Elle effectue simplement une vérification mathématique rapide sur la couche supérieure de randonneurs. Sont-ils dispersés ? Bougent-ils de concert ? C'est comme vérifier si le groupe est une équipe soudée ou une foule éparpillée.
La Lentille « Changeuse de Forme » (PCA) : Cette lentille écrase la montagne en 3D pour la transformer en une carte 2D afin de voir la forme principale. Elle demande : « Est-ce que la montagne est une longue crête, un dôme arrondi ou une plaine plate ? »
La Lentille « Art du Fil » (Structures de Graphes) : C'est la partie la plus créative. Imaginez connecter les randonneurs avec des fils pour former une toile.
- Ils dessinent des fils basés sur la proximité des randonneurs dans l'Espace de Décision (où ils se tiennent).
- Ensuite, ils étirent ces mêmes fils vers l'Espace des Objectifs (où ils arrivent).
- La Magie : Si les fils restent tendus et droits, la montagne est lisse. Si les fils se tordent, s'emmêlent ou s'étirent, cela signifie que le terrain est trompeur et difficile à naviguer. C'est comme voir si une carte correspond à la réalité du terrain.
La Lentille de « Pente » (Gradient) : Elle mesure la raideur des collines. Les pentes sont-elles douces ou y a-t-il des falaises soudaines ?

L'Expérience : Le Grand Test de Goût

Pour tester ces nouvelles jumelles, les auteurs ont mené une expérience massive. Ils ont pris 1 165 « chaînes de montagnes » différentes (problèmes de référence) et ont laissé trois équipes de grimpeurs (algorithmes : NSGA-II, SMS-EMOA et MOEA/D) tenter de conquérir ces montagnes.

Ils ont demandé : « Nos nouvelles jumelles peuvent-elles prédire quelle équipe gagnera sur quelle montagne ? »

Les Résultats :

L'Ancienne Méthode : Sans les nouveaux outils, la prédiction était correcte, mais souvent erronée.
La Nouvelle Méthode : Avec les caractéristiques MO-ELA, le « sous-chef » est devenu incroyablement précis. Pour les problèmes à deux objectifs, le système était presque parfait, choisissant l'équipe gagnante presque à chaque fois. Pour les problèmes à trois objectifs, c'était également une amélioration majeure.
Le Meilleur Aspect : Le système n'avait pas besoin de toutes les jumelles. Il n'avait besoin que d'un petit sous-ensemble spécifique (environ 32 caractéristiques sur plus de 200) pour fonctionner parfaitement. Cela prouve que les nouveaux outils sont efficaces et ne sont pas simplement du « bruit ».

Pourquoi cela importe

Ce document montre qu'en regardant la relation entre l'endroit où vous commencez et l'endroit où vous arrivez — en utilisant ces astuces de « l'art du fil » et du « gâteau à couches » — vous pouvez comprendre la difficulté d'un problème très rapidement.

Les auteurs ont constaté que ces outils sont stables (ils donnent la même réponse même si vous prenez un instantané légèrement différent de la montagne) et expressifs (ils disent exactement ce qui rend un problème difficile).

En bref, ce document nous donne une meilleure carte pour naviguer dans les problèmes complexes à objectifs multiples, garantissant que nous choisissons le bon solveur avant même de commencer l'ascension.

Résumé Technique : MO-ELA

Énoncé du Problème

La sélection automatisée d'algorithmes (AAS - Automated Algorithm Selection) est un domaine mature pour l'optimisation mono-objectif (SO), où des modèles d'apprentissage automatique prédisent le meilleur algorithme performant pour une instance de problème spécifique en se basant sur des caractéristiques d'analyse du paysage exploratoire (ELA - Exploratory Landscape Analysis). Cependant, dans le domaine de l'optimisation multi-objectif (MO) continue, le paysage des caractéristiques disponibles est parc于. Les approches existantes reposent souvent soit sur le calcul de caractéristiques SO pour chaque objectif individuellement, ce qui ne parvient pas à capturer les interactions complexes entre les objectifs, soit sur des caractéristiques MO contraintes qui ne sont pas directement applicables aux problèmes continus non contraints (à contraintes de boîte), ce qui échoue à caractériser la structure globale. Il existe un besoin pour un ensemble rigoureux et complémentaire de caractéristiques spécifiquement conçues pour caractériser le paysage des problèmes d'optimisation multi-objectif continue à contraintes de boîte (MOPs) afin d'améliorer les performances de l'AAS.

Méthodologie

Les auteurs proposent MO-ELA, un nouvel ensemble de 226 caractéristiques pour les problèmes bi-objectifs et de 233 caractéristiques pour les problèmes tri-objectifs. Ces caractéristiques sont dérivées d'un échantillon aléatoire de points dans les espaces de décision et d'objectif, en utilisant les relations de dominance et diverses analyses structurelles. Les caractéristiques sont classées en cinq groupes distincts :

Caractéristiques basées sur le tri non-dominé (NDS - Non-Dominated Sorting) :
- Utilise la procédure de tri non-dominé (inspirée de NSGA-II) pour partitionner l'échantillon en couches ( $L_1, L_2, \dots$ ).
- Calcule des métriques telles que le nombre de points non-dominés, le nombre de couches et le nombre moyen de points par couche.
- Calcule l'Hypervolume (HV) et les mesures de Solow-Polasky (SP) pour les cinq premières couches.
- Ajuste des régressions polynomiales (degré 1 à 4) sur les valeurs d'HV à travers les couches pour capturer la non-linéarité de la distribution du front de Pareto, en utilisant le $R^2$ comme caractéristique.
Statistiques descriptives des points non-dominés :
- Applique des mesures statistiques (min, max, moyenne, écart-type) aux vecteurs d'objectifs de la première couche non-dominée ( $L_1$ ).
- Inclut les corrélations de Spearman par paires entre les objectifs et la différence absolue des écarts-types pour les cas bi-objectifs.
Caractéristiques basées sur l'ACP (PCA) :
- Effectue une Analyse en Composantes Principales (ACP) sur trois ensembles : les points de l'espace de décision ( $X$ ), les points de l'espace d'objectif ( $Y$ ) et l'ensemble concaténé ($XY$) de la couche non-dominée.
- Extrait la variance expliquée minimale, maximale et moyenne des composantes principales de ces ensembles.
Caractéristiques basées sur les graphes :
- Construit des graphes basés sur la couche non-dominée $L_1$ dans les espaces de décision et d'objectif.
- Graphes MST et kNN : Construit des arbres couvrant de poids minimal (MST) et des graphes k-plus proches voisins (kNN) ( $k=1$ ) dans l'espace de décision ( $G_D$ ) et l'espace d'objectif ( $G_O$ ).
- Transfert d'arêtes : Transfère la structure d'arêtes d'un graphe à l'autre (par exemple, les arêtes MST de l'espace de décision appliquées aux points d'objectif, noté $G_{D \to O}$ ).
- Métriques : Calcule les poids des arêtes (distances), la centralité de proximité des nœuds, les angles entre les nœuds connectés, ainsi que les propriétés des composantes connexes (nombre de composantes, nœuds par composante, plus long chemin).
- Inclut des ratios de caractéristiques entre les graphes des espaces de décision et d'objectif pour capturer la distorsion entre les espaces.
Caractéristiques basées sur le gradient :
- Calcule les pentes absolues par variable entre les nœuds connectés dans l'arbre couvrant de poids minimal de l'espace d'objectif ( $G^O_{ST}$ ).
- Aggrège ces pentes à travers tous les objectifs et toutes les arêtes pour former un vecteur de gradient multi-objectif, à partir duquel les valeurs min, max, écart-type et moyenne sont extraites.

Configuration expérimentale :

Benchmarks : Un ensemble complet de 1 165 instances de problèmes dérivées de BiObjBBOB, ZDT, DTLZ et MPM2, couvrant 2 et 3 objectifs et des dimensions $d \in \{2, 5, 10, 20\}$ .
Algorithmes : Trois solveurs (NSGA-II, SMS-EMOA, MOEA/D) ont été exécutés 20 fois par instance.
Cadre AAS : Des modèles d'apprentissage automatique (SVM, XGBoost, Forêt Aléatoire) ont été entraînés pour prédire le meilleur solveur. La sélection de caractéristiques a été effectuée via une recherche exhaustive avant-arrière pour identifier le sous-ensemble le plus influent.
Métriques : La performance a été évaluée à l'aide de l'Hypervolume Normalisé (HVN) et de l'Amélioration Relative (RI) dans la réduction de l'écart entre le Meilleur Solveur Unique (SBS - Single Best Solver) et le Meilleur Solveur Virtuel (VBS - Virtual Best Solver).

Résultats Clés

Performance de la sélection d'algorithmes : Les caractéristiques proposées ont considérablement amélioré les performances de l'AAS. Pour les problèmes bi-objectifs, le meilleur sélecteur (XGBoost avec sélection de caractéristiques) a atteint un RI de 0,963, comblant efficacement l'écart avec le VBS. Pour les problèmes tri-objectifs, un RI de 0,272 a été obtenu.
Contribution des caractéristiques : Après la sélection, les nouvelles caractéristiques MO-ELA proposées figuraient fréquemment parmi les principaux contributeurs.
- Pour les problèmes bi-objectifs, 14 des 3 2 sélectionnées étaient de nouvelles caractéristiques (dominées par les caractéristiques NDS).
- Pour les problèmes tri-objectifs, 17 des 36 sélectionnées étaient nouvelles (dominées par les caractéristiques de graphe kNN).
Stabilité des caractéristiques : Les caractéristiques ont démontré une grande stabilité à travers différents échantillons aléatoires et tailles d'échantillons, avec des corrélations par paires moyennes de ~0,8 pour toutes les caractéristiques et de près de 1,0 pour le sous-ensemble sélectionné.
Expressivité des caractéristiques : Les caractéristiques sélectionnées présentaient une faible corrélation mutuelle (moyenne de ~0,30 pour le bi-objectif, ~0,23 pour le tri-objectif), indiquant qu'elles capturent des aspects distincts du paysage du problème.
Sensibilité à la taille de l'échantillon : Une taille d'échantillon de 500 a donné les meilleurs résultats pour les dimensions 5, 10 et 20. Pour la dimension 2, une taille d'échantillon de 200 était optimale. Notamment, des tailles d'échantillon plus grandes ont amélioré la performance même lorsque le budget restant pour les exécutions de solveurs était réduit, suggérant que l'expressivité des caractéristiques est critique.

Signification et Revendications

L'article affirme que MO-EDA fournit une expansion rigoureuse des caractéristiques de paysage exploratoire pour l'optimisation multi-objectif continue. Sa principale importance réside dans :

Combler le fossé : Il répond à la rareté des caractéristiques pour les problèmes MO en introduisant un ensemble complet qui capture les interactions entre les objectifs et la géométrie des espaces de décision et d'objectif.
Utilité prouvée : Les caractéristiques ne sont pas seulement théoriques ; elles permettent empiriquement aux modèles d'apprentissage automatique de distinguer les instances de problèmes et de sélectionner des algorithmes avec une précision quasi optimale (approchant le VBS pour les cas bi-objectifs).
Complémentarité : Les nouvelles caractéristiques complètent les caractéristiques MO-ELA existantes (de Liefooghe et al., 2021), la sélection de caractéristiques conservant systématiquement un mélange des deux, ce qui suggère que les différents groupes de caractéristiques capturent différentes propriétés nécessaires du paysage.
Praticité : Les caractéristiques sont stables et efficaces même avec des tailles d'échantillon relativement faibles (par exemple, 200–500 points), ce qui les rend réalisables pour une application pratique où les budgets de calcul sont limités.

Les auteurs concluent que, bien que la recherche soit à ses débuts, ces caractéristiques fournissent des informations significatives sur la structure des problèmes et améliorent considérablement l'état de l'art de la sélection automatisée d'algorithmes pour l'optimisation multi-objectif continue.