MB University of M'sila
Faculty of MI
Department of Computer Science
Module / Optimization methods
Home work
Whale Optimization Algorithm – WOA
By: Master 2 IDO
Tharafi sliman
1. Introduction
L'algorithme d'optimisation des baleines (WOA) est l'un des algorithmes méta-héroïques les
plus récents et les plus performants, inspiré par la nature. Il a été développé par la
scientifique Seyedali Mirjalili en 2016. Cet algorithme imite le comportement social et la
stratégie de chasse unique des baleines à bosse.
2. Inspiration biologique
L'algorithme s'inspire d'une technique de chasse appelée « pêche au filet de bulles ». Les
baleines à bosse ne chassent pas au hasard ; elles suivent les étapes suivantes :
Nager autour de la proie en décrivant un cercle étroit.
Libérer des bulles d'air par le dessous pour pousser la proie vers la surface et la
piéger au centre du cercle.
Attaquer la proie au centre.
3. Le modèle mathématique
L'algorithme repose sur trois étapes mathématiques fondamentales :
a. Encerclement de la proie
Les baleines repèrent et encerclent leur proie. Ceci est exprimé par l'équation
suivante :
D=¿C · X∗(t)− X (t)∨¿
X (t+1)=X∗(t)− A · D
Étant donné que X* est la meilleure solution obtenue jusqu'à present.
B. La stratégie d'attaque (bulles d'air) est mise en œuvre par deux mécanismes
simultanés :
1. Mécanisme de constriction circulaire : diminution progressive de la valeur du
coefficient A pour se rapprocher de la proie.
2. Mise à jour de la position hélicoïdale : simulation du mouvement en spirale de la
baleine autour de la proie à l’aide d’une équation hélicoïdale.
X(t+1) = D' * e^(bl) * cos(2 \pi l) + X*(t)
c. Recherche de proies (Phase d'exploration)
Dans cette phase, la baleine recherche aléatoirement de nouvelles proies au lieu de suivre la
baleine qui offre la meilleure proie du moment, ce qui garantit que l'algorithme ne tombe
pas dans un « optimum local ».
4. Avantages de l'algorithme
Simplicité : Facile à programmer et à appliquer à divers types de problèmes.
Équilibre : Maintient une grande précision entre l'exploration et l'exploitation.
Flexibilité : Nécessite moins de paramètres d'ajustement que les algorithmes génétiques.
5. Applications
L'algorithme WOA est utilisé avec succès dans les domaines suivants :
Conception de circuits électriques et de systèmes mécaniques.
Entraînement de réseaux de neurones artificiels (apprentissage profond).
Résolution de problèmes d'ordonnancement d'atelier.
Amélioration de la distribution d'énergie dans les réseaux électriques.
Code python :
En appliquant l'algorithme Whale dans la planification (WOA pour Job Shop Scheduling),
l'objectif est d'organiser un ensemble de tâches (Jobs) sur un ensemble de machines
(Machines) afin de réduire le temps d'exécution total (Makespan).
1. Modélisation du problème
L'algorithme de la Baleine opérant dans un espace continu (nombres décimaux), tandis que
les problèmes d'ordonnancement sont discrets (ordonnancement des tâches 1, 2, 3…), nous
utilisons une technique appelée ROV (Ranked Order Value) :
La position de la Baleine est représentée par des nombres aléatoires.
Ces nombres sont ensuite triés, et leur rang détermine l'ordre des tâches.
2. Les étapes de l'algorithme d'ordonnancement :
Exploration : Les baleines recherchent de nouvelles séquences de tâches à tester,
évitant ainsi de rester bloquées sur un ordonnancement ancien et inefficace.
Optimisation : Une fois un ordonnancement performant (temps d'exécution court)
trouvé, les autres baleines ajustent l'ordre de leurs tâches pour s'en rapprocher.
Attaque en spirale : Les positions des tâches dans l'ordonnancement sont modifiées
en spirale, c'est-à-dire par de légers ajustements, afin d'explorer des solutions très
proches et potentiellement meilleures.
Pourquoi l'algorithme WOA est-il excellent pour la planification ?
1. Rapidité de réponse : Dans les usines où les commandes évoluent rapidement, WOA
offre une solution bien plus rapide que les méthodes traditionnelles.
2. Temps d'arrêt réduit : Il répartit efficacement les tâches afin qu'aucune machine ne
soit inactive pendant qu'une autre est en activité.
3. Flexibilité : D'autres contraintes peuvent être facilement ajoutées, telles que les
dates de livraison, les coûts énergétiques ou la maintenance des machines.
Exemple pratique (diagramme de Gantt) : Lorsqu'il est appliqué à un problème de
planification, l'algorithme Whale génère un diagramme de Gantt indiquant le début et la fin
de chaque tâche sur chaque machine, garantissant ainsi un minimum d'interruptions entre
les tâches.
Exemple pratique
Imaginons trois tâches à effectuer sur trois machines. Chaque tâche doit passer par les machines
dans un ordre précis. L'objectif est de trouver l'ordre qui permet de terminer le travail le plus
rapidement possible.
1. Représentation des baleines : Dans l’algorithme des baleines, chaque baleine représente une
« chronologie proposée ». Supposons que la position de la baleine soit un ensemble de
nombres décimaux :
Baleine (A) : [1.2, 0.5, 2.8]
Baleine (B) : [0.1, 3.4, 1.1]
2. Le décodage des nombres à l'aide de la règle du plus petit au plus grand (ROV) implique de
trier les tâches :
Baleine (A) : Le plus petit nombre est 0,50 $ (Tâche 2), puis 1,20 $ (Tâche 1), puis
2,80 $ (Tâche 3).
o L'ordre obtenu est : (Tâche 2 → Tâche 1 → Tâche 3).
Baleine (B) : Le plus petit nombre est 0,10 (Tâche 1), puis 1,10 (Tâche 3), puis 3,40
(Tâche 2).
o L'ordre obtenu est : (Tâche 1 → Tâche 3 → Tâche 2).
3. Évaluation de la fonction d'évaluation de la baleine
Nous calculons le temps total (Makespan) pour chaque tâche. Supposons que :
La tâche (A) est terminée en 15 heures.
La tâche (B) est terminée en 12 heures.
Par conséquent : la baleine (B) est actuellement la « Meilleure Baleine/Proie » car
elle est la plus rapide.
4. Mise à jour des positions (selon la logique des baleines)
La baleine A constate que la baleine B a obtenu un meilleur résultat et commence donc à s'en
rapprocher :
Phase d'encerclement : La baleine A ajuste ses valeurs décimales pour se rapprocher
de celles de la baleine B, dans l'espoir de trouver une configuration similaire et plus
performante.
Phase de mise à jour en spirale : La baleine A modifie l'ordre de deux tâches
seulement (par exemple, en inversant les tâches 1 et 3) en spirale afin d'explorer la
possibilité d'améliorer le temps, par exemple à 11 heures.
Phase d'exploration : Si la baleine A s'éloigne du leader, elle peut découvrir une
configuration inédite (par exemple, tâche 3 → tâche 2 → tâche 1), qui pourrait
constituer la solution idéale.
Résultat final de l'exemple
Après plusieurs itérations :
1. Les distances entre les baleines (l'ordonnancement proposé) diminuent.
2. Toutes les baleines sont concentrées autour de la configuration qui minimise les temps
d'arrêt des machines.
3. On obtient un diagramme de Gantt idéal illustrant la répartition des tâches.
6. Conclusion
WOA est un ajout puissant à la famille des algorithmes méta-hérétiques, et il surpasse
souvent les algorithmes populaires tels que PSO et les algorithmes génétiques en termes de
rapidité et de précision dans l'obtention de la solution finale.