Skip to content
Retour aux résultats

Optimisation par Essaim de Loups Gris — GWO

Introduite par
Seyedali Mirjalili, Seyed Mohammad Mirjalili, Andrew Lewis
Année
2014
Type
Swarm-intelligence metaheuristic

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

Taille de police

À quoi sert-elle ?

L'Optimisation par Essaim de Loups Gris (GWO) est une métaheuristique d'intelligence en essaim introduite par Mirjalili, Mirjalili et Lewis en 2014, qui modélise la hiérarchie sociale et le comportement de chasse coopératif des loups gris.

Une population de solutions candidates est divisée en quatre rangs de leadership — alpha, bêta, delta et oméga — et les trois meilleures solutions à chaque itération guident l'ensemble de l'essaim vers des régions de plus en plus favorables de l'espace de recherche.

L’intuition derrière la méthode

Imaginez une meute de loups gris traquant une proie sur un terrain dense. Le loup alpha prend la décision finale, les loups bêta et delta conseillent, et le reste de la meute se repositionne en réponse aux trois leaders. Le GWO reproduit cela exactement : les trois solutions les plus adaptées trouvées jusqu'à présent agissent comme des balises de navigation, et chaque autre candidat ajuste sa position comme un mélange pondéré des directions indiquées par ces trois balises. Un paramètre unique, a, est progressivement réduit de 2 à 0 au fur et à mesure des itérations, de sorte que la meute commence par s'étendre pour explorer, puis resserre son cercle pour exploiter la meilleure région trouvée.

Histoire

Le GWO a été proposé par Seyedali Mirjalili, Seyed Mohammad Mirjalili et Andrew Lewis en 2014 dans la revue Advances in Engineering Software. L'algorithme s'est inspiré des observations écologiques de la structure de la meute de loups gris : une hiérarchie sociale stricte (alpha, bêta, delta, oméga) et la stratégie de chasse en trois phases consistant à encercler, harceler et attaquer la proie. Mirjalili et al. ont comparé le GWO à l'Optimisation par Essaim Particulaire (PSO), à l'Algorithme de Recherche Gravitationnelle et à l'Évolution Différentielle sur 29 fonctions de test et plusieurs problèmes de conception technique, rapportant des résultats compétitifs ou supérieurs. Depuis 2014, l'algorithme a généré une littérature de suivi substantielle : Faris et al. (2018) ont examiné plus d'une décennie de variantes — extensions binaires, multi-objectifs, chaotiques et hybrides — et ont documenté des applications dans la sélection de caractéristiques, les systèmes d'alimentation, la segmentation d'images et la planification.

Quand l’utiliser

Le GWO convient aux problèmes d'optimisation continue où la fonction objectif est coûteuse à évaluer analytiquement ou est une boîte noire. Il ne nécessite aucune information de gradient ni aucune hypothèse distributionnelle sur les données. La méthode est adaptée à la conception technique, au réglage de paramètres et aux tâches de sélection de caractéristiques. Étant donné qu'elle est basée sur la population, une taille de population minimale d'environ 10 à 30 agents est conseillée ; de très petites populations réduisent la diversité et augmentent le risque de convergence prématurée. Le GWO n'est pas approprié pour les problèmes discrets ou combinatoires sans modification, ni pour les problèmes où une solution mathématique exacte existe.

Limites et points d’attention

  • La convergence vers l'optimum global n'est pas garantie ; la qualité dépend de la diversité de la population et du nombre d'itérations.
  • Non nativement adapté aux espaces de recherche discrets, binaires ou combinatoires sans encodage personnalisé.
  • Comme la plupart des méthodes d'essaim, il peut stagner si les trois leaders se regroupent prématurément dans une région sous-optimale.
  • Échelle mal aux espaces de recherche de très haute dimension par rapport aux solveurs basés sur le gradient lorsque l'objectif est lisse.

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

Points forts

  • Sans gradient : fonctionne sur toute fonction objectif qui renvoie un scalaire, y compris les simulations et les modèles de boîte noire.
  • Paramétrisation minimale : seule la taille de la population et le nombre d'itérations doivent être définis ; a diminue automatiquement.
  • Équilibre l'exploration et l'exploitation grâce à un seul paramètre à décroissance linéaire, rendant le mécanisme d'équilibre transparent.
  • Performances compétitives sur les bancs d'essai de conception technique avec une faible complexité d'implémentation (niveau de difficulté 2 sur 5).

Applications

  • Optimisation de la conception technique : minimisation du poids structurel, conception d'antennes, estimation des paramètres de systèmes d'alimentation.
  • Réglage des hyperparamètres et sélection de caractéristiques pour les tâches de classification en apprentissage automatique.
  • Systèmes énergétiques : répartition optimale dans les réseaux électriques et placement des unités d'énergie renouvelable.
  • Segmentation d'images et analyse d'images médicales par optimisation de seuillage.
  • Problèmes d'ordonnancement et d'allocation de ressources avec une relaxation continue.

Comment ça marche

Comment ça marche

1

Une population de solutions candidates est générée uniformément et aléatoirement dans les bornes inférieures et supérieures définies de l'espace de recherche. La taille de la population et le nombre maximal d'itérations sont les deux seuls paramètres qui doivent être définis avant le début de l'exécution.

2

Chaque solution candidate est évaluée par la fonction objectif. Comme le GWO est sans gradient, la fonction peut être une boîte noire — elle n'a besoin que de renvoyer une valeur de fitness scalaire pour chaque position candidate.

3

Les candidats sont triés par fitness. La meilleure solution est désignée alpha (α), la deuxième meilleure bêta (β), et la troisième meilleure delta (δ). Tous les candidats restants sont des loups oméga (ω). Ces rôles sont réaffectés à chaque itération afin que les étiquettes suivent toujours les trois meilleures positions actuelles.

4

Chaque loup oméga met à jour sa position en calculant trois vecteurs de distance — un vers chacun de α, β et δ — et en se déplaçant vers le centroïde des trois positions cibles résultantes. Le paramètre de contrôle a diminue linéairement de 2 à 0 au cours de l'exécution : les grandes valeurs de a favorisent l'exploration (les candidats peuvent dépasser et chercher loin des leaders), les petites valeurs favorisent l'exploitation (les candidats convergent étroitement autour des leaders).

5

L'étape de chasse est répétée jusqu'à ce que le nombre maximal d'itérations soit atteint ou qu'un critère d'arrêt soit rempli. La position du loup alpha à la fin de l'exécution est renvoyée comme la meilleure solution trouvée.

Pièges courants

  • Définir une taille de population trop petite (moins d'environ 10) réduit la diversité prématurément ; les trois leaders convergent trop tôt et l'exécution n'explore qu'une petite région.
  • Exécuter trop peu d'itérations donne un cycle de chasse insuffisant ; une exécution qui se termine alors que a est encore grand n'est pas entrée dans la phase d'exploitation.
  • L'application du GWO à des problèmes avec des variables entières ou catégorielles sans schéma de discrétisation produit des mises à jour de position dénuées de sens.
  • Ignorer l'échelle des bornes de recherche — des bornes très larges combinées à une petite population laissent la majeure partie de l'espace non échantillonnée lors des premières itérations.

Questions fréquentes

Comment choisir la taille de la population et le nombre d'itérations ?

Un point de départ courant est de 30 agents et 200 à 500 itérations pour les problèmes de dimension modérée (jusqu'à environ 30 variables). Augmentez la taille de la population et le nombre d'itérations à mesure que la dimensionnalité du problème augmente. Comme le GWO est stochastique, exécutez-le au moins 20 à 30 fois avec différentes graines aléatoires et rapportez la moyenne et l'écart type de la meilleure fitness.

Le GWO peut-il gérer des variables discrètes ou binaires ?

Pas nativement. Les équations standard de mise à jour de position sont définies pour des espaces continus à valeurs réelles. Des variantes binaires ou discrètes existent dans la littérature — utilisant généralement une fonction de transfert pour mapper les positions continues à des décisions binaires — mais ce sont des extensions plutôt que l'algorithme original.

Comment le GWO se compare-t-il à l'Optimisation par Essaim Particulaire ?

Les deux sont des méthodes d'intelligence en essaim avec un coût de calcul similaire. Le GWO utilise trois leaders (alpha, bêta, delta) plutôt qu'un seul meilleur global et le meilleur personnel de chaque particule, ce qui tend à préserver la diversité plus longtemps. Mirjalili et al. (2014) ont trouvé le GWO compétitif ou supérieur au PSO sur leur ensemble de bancs d'essai, mais la performance dépend du problème ; aucune méthode ne domine universellement.

Que contrôle le paramètre a, et dois-je le régler ?

Le paramètre a diminue linéairement de 2 à 0 au cours de l'exécution et contrôle si les loups explorent (a élevé) ou exploitent (a faible). Ce calendrier est fixé par l'algorithme — vous ne réglez pas a directement. Les seuls leviers que vous contrôlez sont la taille de la population et le nombre total d'itérations, qui déterminent ensemble la vitesse à laquelle a diminue.

Méthodes associées

Sources

  1. Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey Wolf Optimizer. Advances in Engineering Software, 69, 46-61.

    Ouvrir la référence DOI
    Copié.
  2. Faris, H., Aljarah, I., Al-Betar, M. A., & Mirjalili, S. (2018). Grey Wolf Optimizer: A Review of Recent Variants and Applications. Neural Computing and Applications, 30(2), 413-435.

    Ouvrir la référence DOI
    Copié.