Skip to content
Retour aux résultats

NSGA-II — Algorithme génétique à tri non dominé II

Année
2002
Type
Evolutionary multi-objective optimisation algorithm

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

NSGA-II (Non-dominated Sorting Genetic Algorithm II) est l'algorithme de référence standard pour l'optimisation évolutionniste multi-objectif, introduit par Deb, Pratap, Agarwal et Meyarivan en 2002.

Plutôt que de réduire plusieurs objectifs conflictuels à un score unique, il fait évoluer une population de solutions candidates au fil des générations et retourne un ensemble de solutions d'arbitrage Pareto-optimales — le front de Pareto — en utilisant un tri rapide non dominé et une métrique de distance de densité pour préserver la diversité.

L’intuition derrière la méthode

Imaginez que vous souhaitiez concevoir un produit qui soit simultanément aussi bon marché et aussi durable que possible. Moins cher signifie généralement moins durable, il n'y a donc pas de réponse parfaite unique — il existe une famille de compromis raisonnables. NSGA-II fonctionne comme une population de conceptions concurrentes : chaque génération, les conceptions les plus faibles qui sont dominées par d'autres sur tous les objectifs sont éliminées, et les survivants sont répartis de manière à couvrir toute la gamme des compromis plutôt que de se regrouper dans un coin. Après suffisamment de générations, il vous reste un riche éventail d'options — le front de Pareto — parmi lesquelles vous choisissez l'équilibre qui correspond à vos priorités.

Histoire

NSGA-II a été publié par Kalyanmoy Deb et ses collègues de l'Indian Institute of Technology Kanpur en 2002 en tant que successeur corrigé et substantiellement amélioré du NSGA original (Srinivas & Deb, 1994). Les innovations clés étaient une procédure de tri rapide non dominé de complexité O(MN²), un opérateur explicite de distance de densité pour maintenir la diversité des solutions sans paramètre de partage, et un mécanisme de sélection élitiste. L'article de 2002 dans IEEE Transactions on Evolutionary Computation est devenu l'une des publications les plus citées en calcul évolutionniste et a établi NSGA-II comme la référence de facto pour les algorithmes évolutionnistes multi-objectifs. Des variantes ultérieures — NSGA-III (2014) et autres — étendent le cadre aux problèmes à nombreux objectifs.

Quand l’utiliser

NSGA-II s'applique chaque fois qu'un problème a deux ou plusieurs fonctions objectifs conflictuelles qui ne peuvent pas être fusionnées en un seul critère sans perte d'information. Les variables de décision peuvent être continues, binaires ou catégorielles, et aucune hypothèse distributionnelle sur le paysage objectif n'est requise. L'algorithme convient à la conception d'ingénierie, à l'allocation de ressources, à la planification et aux problèmes de portefeuille où un spectre de solutions d'arbitrage est plus utile qu'un optimum unique. Un nombre suffisant de générations (typiquement plusieurs centaines ou plus) est nécessaire pour obtenir une bonne couverture du front ; exécuter trop peu de générations est le principal mode d'échec.

Limites et points d’attention

  • Les performances se dégradent lorsque le nombre d'objectifs dépasse trois ou quatre — la distance de densité devient une mesure de diversité médiocre dans les hautes dimensions.
  • Nécessite un réglage minutieux de la taille de la population et du nombre de générations ; trop peu de générations empêchent une couverture adéquate du front.
  • L'évaluation des fonctions objectifs impliquant des simulations coûteuses rend l'algorithme coûteux en calcul.
  • Les résultats sont stochastiques : différentes graines aléatoires peuvent produire différents fronts de Pareto, donc plusieurs exécutions et comparaisons statistiques (par exemple, hypervolume) sont recommandées.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Produit un ensemble diversifié de solutions d'arbitrage Pareto-optimales en une seule exécution, évitant ainsi la nécessité de répéter l'optimisation avec des poids différents.
  • Le tri rapide non dominé s'exécute en temps O(MN²) (M objectifs, N taille de population), le rendant traitable pour des tailles de problèmes modérées.
  • La sélection élitiste garantit que les bonnes solutions trouvées tôt ne sont jamais écartées.
  • Applicable aux variables de décision continues, binaires et catégorielles sans hypothèses distributionnelles.
  • Largement validé dans les domaines de l'ingénierie, de la recherche opérationnelle et des sciences computationnelles.

Applications

  • Conception d'ingénierie : minimisation simultanée du poids et maximisation de la résistance structurelle dans les composants mécaniques.
  • Systèmes environnementaux et énergétiques : équilibrage du coût, des émissions et de la fiabilité dans la planification des réseaux électriques ou des énergies renouvelables.
  • Santé et recherche opérationnelle : planification optimisant simultanément le temps d'attente des patients, l'utilisation des ressources et le coût.
  • Optimisation de portefeuille en finance et sélection de projets en entreprise : arbitrage entre le rendement, le risque et la liquidité.
  • Réglage des hyperparamètres en apprentissage automatique : optimisation de la précision par rapport à la complexité du modèle ou au temps d'inférence.

Comment ça marche

Comment ça marche

1

Une population de solutions candidates est créée en échantillonnant aléatoirement (ou par conception) les variables de décision dans leurs bornes. La taille de la population est définie suffisamment grande pour assurer dès le départ la diversité dans l'espace des objectifs.

2

Chaque solution candidate est décodée en valeurs de variables de décision et chaque fonction objectif est évaluée. Le résultat est un vecteur de scores d'objectifs par individu. Cette étape est souvent le goulot d'étranglement computationnel lorsque les objectifs impliquent des simulations ou des modèles coûteux.

3

Les solutions sont classées par tri non dominé : le premier front contient toutes les solutions qu'aucune autre solution ne domine sur tous les objectifs ; le deuxième front contient les solutions dominées uniquement par celles du premier front ; et ainsi de suite. Au sein de chaque front, un score de distance de densité est calculé pour mesurer à quel point une solution est isolée de ses voisines — une distance de densité plus élevée signifie que la solution occupe une région moins dense du front.

4

Une stratégie de sélection élitiste fusionne la population actuelle avec la descendance et conserve les N meilleurs individus, remplissant les fronts dans l'ordre et utilisant la distance de densité pour départager les égalités au sein du dernier front admissible. Cela garantit que les bonnes solutions trouvées lors des générations précédentes ne sont jamais perdues.

5

Les individus sélectionnés se reproduisent par opérateurs génétiques — sélection par tournoi binaire, croisement binaire simulé (SBX) et mutation polynomiale — produisant une nouvelle population de descendance. Ces opérateurs préservent une variation significative tout en explorant le voisinage des solutions prometteuses.

6

Les étapes s'évaluent à travers l'évolution, se répètent pour un nombre spécifié de générations. La convergence est jugée par inspection visuelle du front de Pareto ou par suivi de l'indicateur d'hypervolume. Le résultat final est l'ensemble des solutions non dominées approximant le front de Pareto réel.

Pièges courants

  • L'exécution de moins de plusieurs centaines de générations produit généralement un front de Pareto incomplet ; si le budget de calcul est limité, envisagez plutôt une optimisation mono-objectif pondérée.
  • Traiter un problème avec un seul objectif comme multi-objectif est inutile — utilisez un optimiseur mono-objectif.
  • Négliger de définir des bornes de variables raisonnables conduit à des populations qui n'atteignent jamais des régions réalisables ou significatives de l'espace de recherche.
  • Rapporter une seule solution du front de Pareto sans divulguer le front complet masque la structure d'arbitrage que NSGA-II est conçu pour révéler.

Questions fréquentes

Combien de générations NSGA-II nécessite-t-il ?

Il n'y a pas de règle universelle, mais exécuter moins de quelques centaines de générations produit généralement un front de Pareto incomplet. Une approche pratique consiste à tracer l'indicateur d'hypervolume au fil des générations et à s'arrêter lorsqu'il se stabilise. Si le budget de calcul l'empêche, un optimiseur mono-objectif pondéré est une alternative plus sûre.

Qu'est-ce que le front de Pareto ?

Le front de Pareto est l'ensemble des solutions où aucune amélioration sur un objectif n'est possible sans en dégrader au moins un autre. NSGA-II approxime ce front, vous donnant l'éventail complet des compromis équilibrés plutôt qu'une réponse unique.

NSGA-II peut-il gérer plus de deux objectifs ?

Oui, mais la distance de densité — le mécanisme de diversité — devient moins efficace lorsque le nombre d'objectifs dépasse trois ou quatre (le régime des 'nombreux objectifs'). Pour les problèmes avec cinq objectifs ou plus, NSGA-III ou des algorithmes basés sur la décomposition tels que MOEA/D sont généralement préférés.

NSGA-II est-il déterministe ?

Non. Les opérateurs génétiques et la population initiale impliquent du hasard, donc différentes exécutions avec différentes graines aléatoires peuvent produire différentes approximations du front de Pareto. La meilleure pratique consiste à exécuter l'algorithme plusieurs fois et à comparer la qualité du front à l'aide de l'indicateur d'hypervolume.

Méthodes associées

Sources

  1. Deb, K., Pratap, A., Agarwal, S. & Meyarivan, T. (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.

    Ouvrir la référence DOI
    Copié.
  2. Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.

    Ouvrir la référence DOI
    Copié.