Speeding Up the NSGA-II via Dynamic Population Sizes

Résumé Technique : Accélération de l'algorithme NSGA-II via des tailles de population dynamiques

Énoncé du Problème
Les algorithmes évolutionnaires multi-objectifs (MOEA), en particulier le Non-dominated Sorting Genetic Algorithm II (NSGA-II), sont largement utilisés pour résoudre des problèmes d'optimisation multi-objectifs. Un défi central de leur application est la gestion de la taille de la population ($N$). Pour représenter efficacement le front de Pareto (l'ensemble des compromis optimaux), la population doit être suffisamment grande. Cependant, une population trop nombreuse ralentit l'algorithme car le NSGA-II évalue $N$ solutions par itération. Cela crée un dilemme de conception : une population trop petite ne parvient pas à couvrir le front de Pareto efficacement, tandis qu'une population trop grande engendre des coûts computationnels inutiles. Des analyses mathématiques récentes ont montré que le NSGA-II statique avec une taille de population fixe optimale a un temps d'exécution de $\Theta(n^2 \log n)$ sur le benchmark OneMinMax (OMM), ce qui est considéré comme sous-optimal par rapport aux bornes inférieures théoriques pour certaines classes d'algorithmes.

Méthodologie
Les auteurs proposent le Dynamic NSGA-II, une variante de l'algorithme classique qui répond au dilemme de la taille de la population en commençant par une petite population initiale et en l'augmentant au fil du temps.

• Structure de l'Algorithme : L'algorithme commence avec une taille de population de $N=4$. Il effectue un nombre fixe d'évaluations de fonctions, noté par un paramètre spécifié par l'utilisateur $\tau$, avant de tenter de doubler la taille de la population. Ce doublement se poursuit jusqu'à ce qu'une taille de population maximale, $N_{max}$, soit atteinte. Crucialement, le doublement est déclenché par le nombre d'évaluations de fonctions plutôt que par les itérations, garantissant que chaque « phase » de l'algorithme reçoit un budget de calcul approximativement égal, quelle que soit la taille actuelle de la population.
• Mécanisme de Sélection : Les auteurs utilisent une variante spécifique du NSGA-II qui emploie la distance de crowding actuelle (current crowding distance) pour la résolution des ex-æquo. Ce mécanisme, précédemment démontré comme améliorant la distribution des solutions, supprime de manière itérative les individus ayant la plus petite distance de crowding et recompute les distances, conduisant à une répartition plus équidistante des solutions.
• Variantes :
  1. Standard Dynamic NSGA-II : Double la population tous les $\tau$ évaluations.
  2. Dynamic NSGA-II avec Phase Initiale Plus Longue : Prolonge la durée de la phase initiale (où $N=4$) pour correspondre au budget de calcul total de toutes les phases suivantes combinées. Cela permet à l'algorithme de passer plus de temps dans l'étape initiale hautement efficace sans augmenter l'ordre de complexité asymptotique.
  3. Stratégie Sans Paramètre (Algorithme 3) : Pour éliminer le besoin de réglage manuel de $\tau$, les auteurs proposent une stratégie d'exécution concurrente. Ce cadre lance plusieurs instances du Dynamic NSGA-II avec différentes valeurs de $\tau$ (puissances de deux) et alloue dynamiquement les ressources à l'instance qui a dépensé le moins d'effort de calcul total jusqu'à présent.

Contributions Clés et Résultats
L'article fournit des analyses rigoureuses du temps d'exécution de ses algorithmes proposés sur deux benchmarks standards : OneMinMax (OMM) et OneJumpZeroJump (OJZJ$_k$).

1. Benchmark OMM :

   • Le Standard Dynamic NSGA-II avec un $\tau$ optimal atteint un temps d'exécution de $O(n \log^2 n)$ évaluations de fonctions avec une haute probabilité. C'est une amélioration significative par rapport au temps de $\Theta(n^2 \log n)$ du NSGA-II statique.
   • La variante avec la Phase Initiale Plus Longue atteint un temps d'exécution de $O(n \log n)$. C'est asymptotiquement optimal pour une large classe d'algorithmes de boîte noire non biaisés, correspondant à la borne inférieure théorique pour trouver la chaîne "all-ones".
   • La stratégie concurrente sans paramètre (Algorithme 3) atteint des temps d'exécution de $O(n \log^3 n)$ (standard) et $O(n \log(N_{max}) \log(n \log N_{max}))$ (phase initiale plus longue), n'infligeant qu'une pénalité logarithmique par rapport aux versions optimisées.

2. Benchmark OJZJ$_k$ (avec taille de gap $k$) :

   • Le Standard Dynamic NSGA-II atteint un temps d'exécution de $O(nk \log^2 n)$, améliorant le temps connu de $\Theta(nk+1)$ du NSGA-II statique.
   • La variante avec la Phase Initiale Plus Longue atteint $O(nk \log n)$.
   • La stratégie concurrente sans paramètre produit des temps d'exécution de $O(kn^k \log^3 n)$ et $O(kn^k \log(N_{max}) \log(nk \log N_{max}))$, respectivement.

3. Robustesse et Indépendance des Paramètres :

   • Les garanties de temps d'exécution des variantes dynamiques sont largement indépendantes de la taille de population maximale $N_{max}$, à condition que $N_{max}$ soit légèrement supérieur à la taille du front de Pareto (par exemple, $N_{max} \ge n+4$).
   • Si $\tau$ est choisi de manière sous-optimale (trop petit), l'algorithme revient aux performances du NSGA-II statique avec une population de $N_{max}$, garantissant qu'un mauvais choix de paramètre n'est pas catastrophique.
   • La stratégie d'exécution concurrente élimine efficacement le besoin pour l'utilisateur de sélectionner $\tau$, créant un algorithme « sans paramètre » concernant la dynamique de la taille de la population.

Signification et Revendications
Les auteurs affirment que ce travail est le premier à analyser mathématiquement un MOEA avec des paramètres dynamiques, démontrant que la nature multi-objectif des problèmes permet des accélérations significatives grâce aux stratégies de croissance de population.

• Avancée Théorique : L'article établit que le dimensionnement dynamique de la population peut briser la barrière $\Theta(n^2 \log n)$ pour le NSGA-II sur OMM, atteignant des temps d'exécution presque optimaux ($O(n \log n)$) lorsque la phase initiale est prolongée.
• Implications Pratiques : En montrant qu'une stratégie simple d'exécution concurrente peut atteindre des performances proches de l'optimal sans réglage manuel de paramètre, les auteurs suggèrent une voie vers des MOEA plus robustes et « sans paramètres ».
• Comparaison avec les Archives : Les auteurs notent que bien que d'autres travaux aient proposé d'utiliser des archives pour stocker des solutions et permettre des populations plus petites, leur approche dynamique est théoriquement préférable dans certains contextes (spécifiquement concernant la mutation bit à bit sans croisement) car elle évite le risque que la population devienne insuffisante pour générer de nouvelles solutions sur le front de Pareto.

L'article conclut que le Dynamic NSGA-II offre une accélération prouvable de $\tilde{\Omega}(n)$ par rapport au NSGA-II statique et que l'extension de la phase initiale améliore davantage les performances pour atteindre les limites théoriques de l'optimisation de boîte noire non biaisée. Des travaux futurs sont suggérés pour examiner si ces avantages s'appliquent à d'autres scénarios populaires, tels que le benchmark LOTZ.