Chapitre 3

OPTIMISATION PAR ESSAIM

L’intelligence en essaim (Swarm Intelligence en anglais), est une discipline de l’intelligence
artificielle (AI), qui est devenue de plus en plus populaire au cours de ces dernières décennies.
Elle est caractérisée par un mode de fonctionnement décentralisé qui imite le comportement
des essaims d'insectes sociaux comme les fourmis, les termites ou les abeilles. Elle s’étend
également à tout groupe d'agents naturels ou artificiels comme les bancs d'oiseaux ou de
poissons, obéissant à des règles simples, ne disposant que d'informations locales et devant
coordonner leurs actions pour réaliser une tâche globale complexe [THE94; BON99].
Les colonies d'insectes sociaux ont fasciné les chercheurs depuis de nombreuses années, et les
mécanismes qui régissent leur comportement sont restés inconnus pendant longtemps. Même
si les membres de ces colonies ne sont pas des individus sophistiqués, ils sont en mesure de
réaliser des tâches complexes en matière de coopération. Ce comportement coordonné qui
ressort des actions relativement simples et des interactions entre les membres de la colonie est
appelé auto organisation. « L’auto-organisation caractérise un processus au cours duquel une
structure émerge au niveau global uniquement d’un grand nombre d’interactions entre les
composants de niveau local du système. De plus, les règles spécifiant les interactions entre
composants du système sont suivies en utilisant uniquement des informations locales, sans
référence à la structure globale» [THE94]. Cette propriété a fait le succès de l'intelligence en
essaim et a permis de concevoir des algorithmes de plus en plus efficaces face à des
problèmes complexes.
En outre, la recherche dans le domaine de l’intelligence en essaim comprend de nombreux
systèmes décentralisée et distribués exploitant le comportement collectif qui émerge de
l'interaction des agents individuels avec leur environnement. Ce dernier point de vue
offre un lien naturel entre l’intelligence en essaim et les systèmes immunitaires. En effet, de
nombreux algorithmes immunitaires fonctionnent de manière analogue avec les populations
« d'agents immunitaires » présentant un comportement collectif de haut niveau.
En outre, il a été suggéré par plusieurs auteurs que le système immunitaire naturel
lui-même doit être considéré comme un essaim [TIM00a; CAS02a]. Dans ce chapitre, nous
présentons trois modèles de l'intelligence en essaim: L’optimisation par colonie de fourmis,
l’optimisation par colonie d’abeilles et les systèmes immunitaires.

1. Optimisation par Colonie de fourmis

Les insectes sociaux sont fascinants car ils semblent compenser leurs faiblesses individuelles
par une coordination globale qui donne à la colonie une forme d’intelligence bien supérieure
à celles de ses membres. Le plus étonnant est que cette coordination n’existe pas
matériellement, au sens où la colonie ne possède aucun chef. En effet, par des mécanismes
élémentaires, les actions individuelles se combinent pour contribuer à la réalisation du but
global, sans plan apparent.
Individuellement une fourmi n’est pas un animal très évolué. Son cerveau est minuscule et
n’est pas capable de s’adapter à des situations nouvelles. Pourtant, le groupe réalise des tâches
relativement complexes, comme la construction d’une fourmilière, l’entretien des larves ou la
collecte de la nourriture. En effet, les fourmis communiquent indirectement via des
modifications dynamiques de leur environnement (les pistes de phéromones) construisant
ainsi une solution à un problème en s’appuyant sur leur expérience collective.
La haute structuration de la société dans une colonie de fourmis ainsi que la simplicité de ses
individus ont attiré l’attention des scientifiques. Les biologistes ont étudié le comportement
collectif des fourmis face à des problèmes complexes, notamment les problèmes de choix lors
de l’exploitation des sources de nourriture [DEN89; DEN90].
 Figure 1 : Les fourmis à la recherche de nourriture.
En partant de leur fourmilière vers une source de nourriture et vice versa, les fourmis aveugles
déposent au sol une substance chimique attractive et volatile et forment ainsi des pistes
odorantes qui sont exploitées par leurs congénères (fig.33).
Une colonie est ainsi capable de choisir le plus court chemin séparant leur nid et la source de
nourriture [GOS89; GOS90], sans que les individus aient une vision globale de la trajectoire.
Deneubourg et Goss [DEN89] ont mis en place une expérience, nommée expérience du pont à
doubles branches, illustrant ce phénomène. Deux voies, l'une est plus courte que l'autre, sont
offertes à des fourmis pour aller du nid à une source de nourriture. Au début de l’expérience,
les fourmis choisissent aléatoirement les deux ponts: il n'y a pas de préférence. Et au bout d'un
moment, les fourmis prennent toutes le même chemin « le plus court » (fig. 34).

Début de l’expérience Fin de l’expérience

Figure 2 : Expérience du pont à double branche.

Ce phénomène est expliqué par le fait que les fourmis empruntant le plus court chemin font le
trajet aller retour plus rapidement et donc plus souvent que les autres. Par conséquent, avec le
temps, la quantité de phéromone déposée sur la plus courte branche est plus importante.
Sachant qu’une piste présentant une plus grande concentration en phéromone est plus attirante
pour les fourmis. Ainsi, la plus courte branche sera choisie par la majorité des fourmis. C'est
un phénomène émergent car pour arriver au plus court chemin, chaque fourmi n'utilise que
deux règles: elle laisse de la phéromone derrière elle, et quand elle a le choix entre deux
chemins, elle choisit le chemin qui dégage la plus forte odeur, donc celui qui a une plus forte
concentration en phéromone. Cet exemple montre que la colonie de fourmis converge vers
une solution optimale alors que chaque fourmi n’a accès qu’à une information locale et
qu’elle est incapable de résoudre seule le problème dans un délai raisonnable. Cette forme de
communication par le biais de modifications de l’environnement se nomme la stigmergie
[BON99; DRE06].
En s’inspirant de ce principe, Marco Dorigo [DOR92] a exposé pour la première fois, dans sa
thèse de doctorat, l’optimisation par colonie de fourmis (ACO pour Ant Colony Optimisation
en anglais).
D’autres études ont été menées sur d’autres comportements des colonies de fourmis comme
la construction du nid, l’allocation des tâches entre les individus, et le transport coopératif, où
plusieurs fourmis coordonnent leurs mouvements pour transporter une proie trop grande pour
un seul individu. Ce comportement a inspiré un algorithme de contrôle permettant à des
robots élémentaires de transporter un objet sans communiquer [BON01].

1.1. Les fourmis artificielles

Le but en informatique ne consiste pas à imiter parfaitement le modèle des fourmis réelles
mais de s’en inspirer utilement pour élaborer des méthodes de résolution de problèmes
complexes. Les algorithmes de colonie de fourmis utilisent des agents appelés fourmis
artificielles, concurrentes et asynchrones, coopérant globalement pour converger vers la
solution optimale. Elles reproduisent certaines caractéristiques des fourmis réelles mais
peuvent cependant présenter quelques différences les rendant plus efficaces. Dans ce qui suit
nous donnons quelques points de similitude et de différence entre les fourmis réelles et les
fourmis artificielles [DOR92 ; COL92a ; COL92b]:
- Comme dans les colonies de fourmis réelles, les algorithmes de fourmis sont composés
d'une population (colonie), d’entités concurrentes et asynchrones qui coopèrent
globalement pour la résolution d’un problème,
- les fourmis artificielles modifient quelques aspects de leur environnement comme le
font les fourmis réelles. Les fourmis réelles disposent de la phéromone, les fourmis
artificielles, quant à elles, changent des informations numériques sauvegardées
localement dans une table de routage,
- la recherche du plus court chemin chez les fourmis réelles correspond à la recherche
d’une solution à un problème qui converge vers la solution optimale, chez les fourmis
artificielles,
- pour se déplacer d’un état vers un autre (adjacent), les fourmis artificielles appliquent
une règle de décision probabiliste. Cette règle n’utilise que les informations localement
disponibles (comme pour les fourmis réelles), et des informations spécifiques au
problème,
- Le mécanisme d’évaporation de l’information phéromone permet aux fourmis
artificielles de diriger la recherche vers de nouvelles directions pour explorer l’espace
de recherche.
Cependant, les fourmis artificielles ont certaines caractéristiques qui ne se trouvent pas chez
les fourmis réelles. Citons quelques unes :
- Les fourmis artificielles évoluent dans un milieu discret. Elles effectuent des
déplacements entre des états discrets reliés par des transitions,
- elles ont une mémoire pour stocker les solutions partielles (les actions passées),
- elles déposent une quantité de phéromone qui est une fonction de la qualité de la
 solution trouvée,
- le dépôt de la phéromone, au fil des générations, dépend du problème à résoudre. En
général, les fourmis artificielles mettent à jour la phéromone après la génération des
solutions,
- les fourmis artificielles peuvent être enrichies par des capacités supplémentaires
(hybridation) à savoir la prévision, la recherche locale et le retour arrière.

1.2. L’approche métaheuristique ACO

Le principe de la métaheuristique ACO est basé sur la manière dont les fourmis recherchent la
nourriture et retrouvent leur chemin pour retourner dans la fourmilière. Pour transposer ce
comportement à une méthode générale d’optimisation combinatoire, une analogie doit être
faite entre l’aire dans laquelle les fourmis cherchent la nourriture et l’espace de recherche du
problème (ensemble des solutions admissibles), entre la quantité (ou la qualité) de la
nourriture et la fonction objectif à optimiser, et enfin entre les traces de phéromone et une
mémoire adaptative [DOR99a].

1.2.1. Formalisme de l’approche ACO

ACO est appliqué aux problèmes de l’optimisation discrète moyennant une modélisation
caractérisée par [DOR96 ; DOR97]:
 Un ensemble fini de composants C= {c1, c 2,…, c n}.
 Un ensemble fini L = {Lcicj/ (ci, cj)  CC} de connexions ou transitions.
 Jcicj le coût associé à la connexion entre Lcicj.
 {C, L, t} un ensemble de contraintes, définies sur les éléments de C et L à
l’instant t.
 L’état du problème est défini par la séquence s=<ci, cj,…, ck,…> des éléments de C.
 Si S est l’ensemble de toutes les séquences possibles, on pose S’ le sous-ensemble de S
qui contient toutes les séquences réalisables.
   S’ est une solution si elle satisfait toutes les contraintes de .
 J, le coût de la solution .
 Une solution S2 est voisine de la solution S1 si et seulement si :
 S1, S2  S,
 L’état S2 peut être atteint par l’état S1 par une seule étape logique ; si c1
est le dernier composant de la séquence déterminant l’état S1,  c2 C
tel que Lc1c2L et S2{S1,c2}.
Notons que la notion de voisinage telle qu’elle a été définie ci dessus n’est pas forcément
commutative (S2 est voisine de S1, par contre S1 n’est pas voisine de S2).
La solution de ce problème peut être exprimée par les chemins réalisables d’un graphe
G=(C,L) associé à un problème d’optimisation discret. Le but de l’algorithme ACO est de
trouver un chemin de coût minimal en respectant les contraintes .
En codant les informations collectées, durant le processus de recherche sur le graphe, sous
forme de phéromone artificielle, les fourmis de la colonie arrivent à résoudre d’une manière
collective le problème. Les arrêtes ou les sommets peuvent avoir des valeurs heuristiques ij,
indiquant des informations sur le problème.
1.2.2. Les caractéristiques de l’approche ACO

Un algorithme ACO possède certaines caractéristiques qui sont présentées ci-dessous:

a. Les pistes de phéromone
En appliquant un algorithme ACO, on doit répondre aux deux questions suivantes: quelle est
la signification qu’on doit donner aux pistes de phéromone, et comment déposer la
phéromone ? La réponse à ces deux questions est cruciale. La performance de l’algorithme en
dépend. La définition des pistes des phéromones dépend bien sur du problème considéré.
Heureusement, le choix intuitif est souvent très bon pour beaucoup de problèmes.
Pour le PCG par exemple, la signification de la piste de phéromone peut être la désirabilité
qu’un sommet j fasse partie d’une même (ou différente) classe de couleur que i. Quelques
interprétations de la piste de phéromone associées à des problèmes d’optimisation connus sont
données dans le tableau 1:

Problème Signification (désirabilité que :)

- Sac à Dos. - Un nœud fasse partie de la solution.

- TSP. - Un nœud i suive un autre sommet j dans la solution.
- Max clique. - Des paires de sommets soient dans la solution.
- Ordonnancement. - Un sommet i ait une position j dans la solution.
- Affectation quadratique. - Une ressource C soit affectée à l’objet O.
Tableau 1 : Exemples d’interprétation de pistes de phéromone.

Concernant le dépôt de phéromone, une fourmi peut déposer de la phéromone pendant qu’elle
construit une solution, on parle alors de mise à jour « online step by step », ou après avoir fini
sa construction. Dans ce dernier cas, elle effectue un retour en arrière vers l’état initial pour
mettre à jour la phéromone, on parle alors d’une mise à jour « online delayed ». Selon la
conception, on utilise l’une ou l’autre de ces formes de mises à jour ou les deux à la fois
[DOR99b].
b. Le nombre de fourmis
Bien qu'une fourmi seule soit capable de produire une solution, il est plus intéressant d’en
utiliser plusieurs. Dans le cas de problèmes d'optimisation combinatoire, l'usage de m fourmis,
(m>1), qui construisent r solutions chacune, pourrait être équivalent à l'usage d'une seule
fourmi qui produit m*r solutions. Dans ce cas, les solutions obtenues sont souvent de moindre
qualité. Les résultats théoriques, sur la convergence des algorithmes ACO, suggèrent que ces
derniers sont performants en utilisant plus d’une fourmi [DOR99a]. Cependant, l’utilisation
d’un très grand nombre de fourmis pourrait ralentir considérablement l’algorithme, et remettre
ainsi en cause l’utilisation même d’une méthode approchée. D’autant plus qu’il a été
remarqué que même si le nombre de fourmis est très grand, la qualité de la solution n’est pas
améliorée. En général, la meilleure valeur de m est fonction de l’approche ACO utilisée et le
problème considéré [DOR03].
c. La liste candidate
L’application de voisinages de grandes tailles dans une approche ACO engendre un large
choix de déplacements possibles pour les fourmis. Ce qui pénalise les performances de
l’algorithme pour les raisons suivantes:
- La construction d’une solution est considérablement ralentie.
 - La probabilité que beaucoup de fourmis visitent le même état est très faible.
Pour remédier à ce problème, les concepteurs de la métaheuristique ACO proposent
l'utilisation d'une liste candidate [DOR03]. Cette dernière contient un ensemble réduit de
voisins d'un état donné. Les voisins sont créés en utilisant des informations relatives au
problème à résoudre si elles sont disponibles. L’usage de cette liste permet aux algorithmes
ACO de se concentrer sur les composants les plus intéressants, en réduisant la dimension de
l'espace de recherche. Pour le problème du voyageur de commerce par exemple, quand le
nombre de villes à visiter est très grand, la liste candidate peut contenir, pour chaque fourmi,
une petite partie des villes voisines les plus proches. Si toutes les villes de la liste candidates
ont déjà été visitées, la fourmi choisit alors une ville parmi les villes voisines restantes. Il a été
prouvé que cette méthode permet dans certains cas de trouver des solutions optimales
[DOR03].

d. Information heuristique
Appelée aussi information publique, elle comprend à la fois des informations heuristiques
spécifiques au problème et des informations codées sous forme de pistes de phéromone.
Celles-ci reflètent l’expérience acquise par toutes les fourmis depuis le début du processus de
recherche. L’information publique constitue donc une mémoire partagée dont le contenu
influence les décisions des fourmis et les guide dans leur recherche.
e. La table de routage
La valeur fonctionnelle de la phéromone localement disponible ainsi que d’autres valeurs
heuristiques définissent une table de décision (ou de routage) pour les fourmis. Il s’agit d’une
table de probabilités que les fourmis utilisent pour orienter leurs recherches vers les régions
les plus intéressantes de l’espace de recherche.

1.2.3. Les effets de l’approche ACO

En plus des caractéristiques présentées ci-dessus, un algorithme ACO possède deux effets :
a. L’évaporation de phéromone
Pour favoriser l'exploration des chemins les moins visités, l’intensité de phéromone est
décrémentée dans le temps. Ainsi, les fourmis ont tendance à ne pas emprunter le même
chemin, et donc ne pas converger vers la même solution. Ce fait, qui a été observé
expérimentalement [DOR99a], est une propriété désirable. En effet, si les fourmis explorent
des chemins différents, alors il y a une plus haute probabilité qu'une fourmi trouve une
amélioration de la solution. Par contre, si elles convergent toutes vers le même chemin, alors,
les solutions ne seront pas diversifiées, ce qui augmente les chances d’être piégé dans un
optimum local. Notons aussi que dans ce dernier cas, l'utilisation de m fourmis est inutile.
b. Les actions du démon
Les actions du démon sont des actions centralisées, qui ne peuvent pas être effectuées par les
fourmis individuelles [DOR99b]. Contrairement à une fourmi, le démon a une vue globale du
processus de recherche. Il peut observer le chemin trouvé par chaque fourmi de la colonie, et
rajouter de l’extra phéromone sur les composants utilisés par la fourmi qui a construit le
meilleur chemin (solution), tout en en respectant la phéromone online déjà déposée. Cette
mise à jour de phéromone effectuée par le démon, est dite la mise à jour « offline » de
phéromone.
Dans la plupart des problèmes NP-difficiles, les algorithmes ACO sont plus performants
quand on leurs associe des algorithmes de recherche locale. Qui est un type particulier
d'actions du démon. Dans ce cas, l'algorithme de recherche locale améliore la meilleure
solution trouvée par les fourmis. Celle-ci est utilisée dans la mise à jour offline.
En outre, l'usage des algorithmes de recherche locale est parfois crucial pour améliorer les
performances de plusieurs applications ACO. Il est à noter aussi que les algorithmes ACO
donnent de bons résultats, là où les algorithmes de la recherche locale ne peuvent pas être
appliqués facilement [DOR99b].

1.2.4. Principe général de l’ACO

Partant d’un état initial, chaque fourmi artificielle construit une solution ou une partie d’une
solution, éventuellement de qualité médiocre. Les solutions de bonne qualité résulteront de la
coopération globale entre toutes les fourmis. Chaque fourmi construit sa propre solution en se
déplaçant à travers une séquence finie d’états voisins. Les déplacements sont choisis par
application d’une politique de recherche locale stochastique qui repose sur :
- Les informations internes de la fourmi (état interne, mémoire privée)
- La phéromone rencontrée et autres informations locales spécifiques au problème.
Une fois qu’une fourmi ait accompli sa tâche (construction d’une solution et mise à jour de la
phéromone), la fourmi meurt et est supprimée du système.
La procédure principale de la métaheuristique ACO se compose des trois activités
élémentaires. La génération de fourmis et leur activité, l’évaporation de phéromone et l’action
du démon (fig.35).
Ces trois activités sont synchronisées par un scheduleur des activités. Ce dernier n’impose pas
la manière dont les trois composantes principales de l’algorithme doivent être synchronisées.
Ce choix est laissé au concepteur du programme qui adaptera sa solution en fonction du
problème et des conditions de résolution. Les procédures « création d’une nouvelle fourmi »
et « cycle de vie d’une fourmis » sont données respectivement dans la figure 35.
Procédure ACO_Metaheuristique
Début
Tant Que (critère d’arrêt non satisfait) Faire
Ordonnancer les activités
Génération_et_activité_des_fourmis ;
Evaporation de la phéromone ;
Actions du démon ; {facultatives}
Fin ordonnancer les activités
Fin Tant Que
Fin.
Procédure Génération_et_activité_des_fourmis
Début
Tant Que (ressources disponibles) Faire
Création_nouvelle_fourmi() ;
Nouvelle_fourmi_active() ;
Fin Tant Que
Fin.
Procédure cycle de vie d’une fourmi
Début
Initialiser la fourmi ;
M = Mise à jour de la mémoire de la fourmi ;
Tant Que (état courant  but) Faire {but signifie une solution complète construite par la fourmi}
A = Lire la table de routage locale de la fourmi ;
P = Calculer la probabilité de transition (A, M, ) ;
Appliquer la règle de décision ( P, ) ;
Se déplacer vers le nouvel état (état suivant) ;
Si (Mise à jour online step by step de la phéromone) Alors
Déposer de la phéromone sur les arcs visités ;
Mettre à jour la table de routage ;
Fin Si
M = Mettre à jour l’état interne de la fourmi ;
Fin Tant Que
Si (Mise à jour online delayed de la phéromone) Alors
Evaluer la solution ;
Déposer de la phéromone sur tous les arcs visités ;
Mettre à jour la table de routage ;
Fin Si
Tuer la fourmi ;
Fin.
Figure 3: Pseudo code de la métaheuristique ACO.

1.2.5. Compromis entre l’intensification et la diversification

L’intensification dans un algorithme ACO signifie l’exploitation des connaissances acquises

par les fourmis depuis le début de la recherche. La diversification quant à elle, signifie
l’exploration des zones de l’espace de recherche relativement inexplorées. Pour tirer profit de
ces deux aspects, un équilibre doit être établi entre eux. Pour parvenir à cet équilibre, il faut
trouver des valeurs appropriées à l’influence des pistes de phéromone α et celle des
informations heuristiques relatives au problème β. En effet, plus les informations phéromone
et heuristiques sont influentes, plus l’exploitation est favorisée, et inversement, plus
l’influence de ces deux paramètres diminue, plus l’exploration est favorisée. De plus, dans
certaines approches, les paramètres α et β changent de valeur dynamiquement en cours
d’exécution, ce qui constitue un moyen simple et efficace d’équilibrer entre l’intensification et
la diversification [DOR99a].
Un autre moyen d’équilibrer entre l’intensification et la diversification consiste en une gestion
appropriée des pistes de phéromone. En effet, les pistes de phéromone induisent une
distribution de probabilité sur l’espace de recherche et déterminent quelles parties de l’espace
de recherche sont les plus visitées, en d’autres termes, les zones de l’espace de recherche où
sont concentrées les solutions construites. Selon la distribution des pistes de phéromone, la
distribution de la recherche peut varier d’une distribution uniforme à une distribution qui
donne une probabilité 1 à une solution et une probabilité nulle à toutes les autres. Cette
dernière situation correspond à une situation de stagnation qui découle d’une focalisation
excessive de la recherche sur une zone à priori bonne. Il est évident qu’en cas de stagnation de
la recherche, la diversification est quasiment nulle. Pour éviter cette situation, et garantir ainsi
une diversification, plusieurs techniques ont été proposées. On peut par exemple définir une
limite maximale aux valeurs de phéromone afin de maintenir un minimum d’exploration. Une
autre façon de diversifier la recherche consiste à réinitialiser les pistes de phéromone.
Combinée à une technique appropriée de mise à jour de phéromone, la méthode de
réinitialisation des pistes de phéromone permet une diversification appréciable de l’espace de
recherche [DOR99a].
Le moyen le plus simple d’exploiter l’expérience de recherche des fourmis est de rendre les
mises à jour de phéromone fonction de la qualité de la solution construite par chaque fourmi.
Cependant, pour obtenir de bonnes performances, utiliser ce moyen seul est souvent
insuffisant. Pour cette raison, dans beaucoup d’algorithmes ACO, comme dans ACS une
stratégie élitiste a été introduite. Le principe de cette stratégie est que la meilleure fourmi
(celle qui a trouvé le meilleur chemin) dépose une quantité de phéromone plus conséquente
afin d’augmenter la probabilité que les autres fourmis explorent la solution la plus
prometteuse.

1.2.6. Importance de l’information heuristique

L’importance de l’utilisation de l’information heuristique dans ACO réside dans l’exploitation

des connaissances spécifiques au problème traité. Ces connaissances peuvent être connues à
l’avance (heuristiques statiques) ou peuvent varier au cours de l’exécution (heuristiques
dynamiques). Les heuristiques statiques sont calculées une seule fois lors de l’initialisation et
demeurent constantes tout au long de l’exécution. Elles présentent l’avantage d’être faciles à
calculer, ce qui permet, à chaque itération, le calcul rapide de la table de routage en utilisant
les valeurs de phéromone courantes. Les heuristiques dynamiques dépendent de la solution en
cours et, de ce fait, doivent être calculées à chaque déplacement d’une fourmi d’un état à un
autre. Ceci engendre une plus grande consommation de temps lors du traitement, lequel peut
être compensé par la précision et l’efficacité de l’information calculée [DOR99a].
Il est à noter que même si l’utilisation des informations heuristiques est importante pour un
algorithme ACO, cette importance est fortement réduite si l’algorithme ACO est hybridé avec
une recherche locale.
La raison en est que la recherche locale prend en considération le coût pour améliorer les
solutions. En effet, même dans le cas de problèmes pour lesquels il est difficile de distinguer
des informations heuristiques significatives, les algorithmes ACO présentent de très bonnes
performances pour peu qu’ils soient hybridés à des algorithmes de recherche locale.
1.3. Système de fourmis

Le système de fourmi (AS pour Ant System en anglais) est l'ancêtre de tous les algorithmes de
fourmis. Il a été appliqué pour la première fois au Problème de Voyageur de Commerce
(PVC) [DOR96; DOR97]. L’application de cet algorithme s’est ensuite étendue pour la
résolution de plusieurs problèmes d’optimisation combinatoire: satisfaction des contraintes
[PIM00], Ordonnancement de production [BEN10], le problème d’affectation quadratique
[STÜ99], coloration des graphes [COS97], Affectation des fréquences [MAN99], etc.
Pour des raisons historiques, la description de l’algorithme de base (original) de l’AS est
étroitement liée au PVC. Ce dernier consiste à trouver le trajet de coût minimal reliant N
villes données en ne visitant chaque ville qu’une seule fois. Le problème est plus
généralement défini dans un graphe fortement connexe G= (V, E), où les villes sont les nœuds
de V et les trajets entre ces villes, les arêtes de E.
Dans ce qui suit, nous présentons le principe d’AS, ses variantes ainsi que les différentes
stratégies de résolution.
A chaque itération de l’algorithme AS, chaque fourmi parcourt le graphe en passant par tous
les noeuds du graphe. Lors d’un déplacement d’un nœud vers un autre nœud non encore
visité, une fourmi choisit sa destination en privilégiant les destinations les plus proches ayant
une plus grande quantité de phéromone en se basant sur une règle aléatoire de transition. Une
fois que toutes les fourmis aient effectués un trajet complet, une mise à jour globale de
phéromone est réalisée. Cette mise à jour comprend le dépôt de phéromone par les fourmis et
l’évaporation de phéromone sur toutes les arrête. Chaque fourmi dépose donc de la
phéromone sur les arrêtes du trajet qu’elle a emprunté. La quantité de phéromone déposée
dépend de la qualité de ce trajet (plus un chemin est court, plus la quantité de phéromone est
importante). Ainsi, les arcs appartenant à plusieurs trajets de bonne qualité recevront plus de
phéromone.
La règle de déplacement ou la règle de transition qu’utilise une fourmi k pour se déplacer
d’une ville i vers une ville j à l’itération t est donnée par la probabilité suivante [DRE03]:

(τij(t))α(ηij ) β
si j  J ik
Pk i, j (t) =
 lJ ik
[τ il(t) ] α [ηil ] β …..…(i)

0 si j  J ik
Où ,
ij  1/ dij est l’heuristique du déplacement du sommet i au sommet j appelée visibilité,
dij désigne la distance entre les villes i et j,
τij est la quantité de phéromone présente sur l’arête (i, j) à l’instant t,

J ik est l’ensemble des voisins du sommet i non encore visité par la fourmi k.
 et  sont deux paramètres contrôlant l'importance relative de l'intensité de la piste, ij(t), et
de la visibilité, ij . Si α= 0, seule la visibilité de la ville est prise en compte ; la ville la plus
proche est donc choisie à chaque étape.
Si au contraire β = 0, seules les pistes de phéromone sont prises en considération. Pour éviter
une sélection trop rapide d'un trajet, un compromis entre ces deux paramètres, jouant sur
l'importance relative de la diversification et de l'intensification, est nécessaire. La Règle de
mises à jour des pistes de phéromone est donnée par la formule suivante :
 m
 ij (i  1)  (1   )   ij (t )    ijk (t ) où
k 1

1
k Si (i, j)  Tk (t)
L (t )
 ijk (t ) =
0 Sinon

m : nombre de fourmis à chaque itération, maintenu constant.

ρ : (0  ρ ≤ 1) taux d’évaporation de la phéromone
Lk (t) : longueur du trajet construit par la kième fourmi à l’instant t.
Tk (t) : le trajet effectué par la kième fourmi à l'itération t.

Ce processus est réitéré Nmax fois (nombre d’itérations fixé à l’avance).

La figure suivante présente le pseudo code de l’algorithme AS appliqué au PVC [DOR97].
Début
Pour chaque fourmi faire
Choisir une ville au hasard
Pour chaque ville non visitée
Choisir une ville destination en se référant à la règle aléatoire de transition proportionnelle
Fin Pour
Déposer de la phéromone sur le trajet emprunté en fonction de la qualité de ce dernier
Fin Pour
Evaporer les pistes de phéromone
Fin.
Figure 4: pseudo code de l’AS pour le PVC.

1.3.1. L’AS pour le problème de coloration des graphes

Nous décrivons dans ce qui suit l’algorithme AS appliqué au PCG [COS97]. Chaque fourmi
colore le graphe en se basant sur une méthode constructive et sur les pistes de la phéromone
qui sont périodiquement mises à jour. A la fin de chaque génération de l’algorithme, on
dépose de la phéromone entre les sommets de même couleur dans chacune des colorations
obtenues. La valeur de phéromone déposée doit être inversement proportionnelle au nombre
de couleurs nc que contient la solution, donc proportionnelle à la qualité de cette solution.
L’importance de la quantité de phéromone τij est alors proportionnelle au nombre de fois où
les sommets i et j ont reçu la même couleur, ainsi qu’à la qualité des colorations produites
sous cette condition. L’information heuristique ηv d’un sommet v mesure les avantages
immédiats liés au choix de v comme le prochain sommet à colorer dans une coloration
partielle. (1-ρ) est le coefficient d’évaporation. Le schéma général de l’algorithme AS
appliqué à la coloration des graphes est donné dans la figure suivante :
Algorithme AS pour le PCG
Initialisation
Tant que (critère d’arrêt non satisfait) faire
Initialiser les pistes de
phéromone
Pour (chaque fourmi) faire
Colorer le graphe à l’aide d’une méthode constructive
Mise à jour de la meilleure solution
Mise à jour online retardée de la phéromone
Fin Pour
Evaporation de la phéromone
Fin tant que
Fin
Figure 5: Algorithme AS pour le PCG.

1.3.2. Autres variantes de l’AS

Malgré les résultats assez compétitifs obtenus par l’AS dans la résolution du PVC de petite
taille (nombre de villes petit), cet algorithme ne rivalise pas avec les autres méthodes de
résolution déjà existantes, particulièrement quand le nombre de villes devient important
[DOR99a ; DRE03]. Plusieurs variantes ont été proposées pour permettre une amélioration
des résultats trouvés par AS. Nous présentons dans ce qui suit, quelques-unes de ces variantes
en se focalisant sur les systèmes des colonies de fourmis.

1.3.2.1. AS et élitisme

Cette variante de l’AS, proposée par Dorigo [DOR99a], constitue la première amélioration
apportée à l’AS. Elle utilise des fourmis « élitistes » en ce sens qu’à chaque itération de
l’algorithme, la fourmi ayant trouvé le plus court chemin dépose une plus grande quantité de
phéromone, afin que les fourmis suivantes aient plus de chances d’explorer les voies les plus
prometteuses.

1.3.2.2. Max-Min Ant System (MMAS)

Cette variante proposée par Stûtzle et Hoos [STÜ97] apporte plusieurs améliorations à
l’algorithme AS. Ces améliorations portent principalement sur la gestion des pistes de
phéromone favorisant ainsi l’exploration de l’espace de recherche. MMAS se distingue de
l’AS par les points suivants :
- Seule la fourmi ayant trouvé la meilleure solution met à jour les pistes de phéromone,
- on impose une valeur minimale et une valeur maximale aux pistes de phéromone,
- les pistes de phéromone sont initialisées à leur valeur maximale,
- la mise à jour des pistes de phéromone se fait de manière proportionnelle de telle sorte que
les pistes de valeurs élevées soient moins renforcées que les pistes de petites valeurs,
- les valeurs de toutes les pistes de phéromone peuvent être réinitialisées.

1.3.2.3. Ant Colony System (ACS)

La performance des deux premières variantes reste limitée par la taille de l’instance du
problème à traiter. Le système de colonie de fourmi (ACS pour Ant Colony System en
Anglais) a été conçu pour améliorer les résultats de ces prédécesseurs notamment pour les
problèmes de grande taille. Les principales modifications apportées par rapport à AS sont
[DOR99a] :
- Introduction d’une gestion de l’équilibre entre l’exploration et l’exploitation,
- Utilisation de listes candidates. A chaque transition, une fourmi choisit sa destination
parmi les éléments de la liste candidate. Dans le cas où tous les éléments de cette liste ont
été visités, la fourmi choisit une autre destination.
- Deux modes de mises à jour séparés des pistes de phéromones : les fourmis mettent à jour
les pistes de phéromones sur leur passage (mise à jour locale) et les arêtes appartenant à la
meilleure solution trouvée lors de l’itération courante voient leur valeur de phéromone
augmentées (mise à jour globale).
Donc la phase d’évaporation de phéromone est remplacée par une mise à jours locale de
phéromone appliquée durant la phase de construction d’une solution, la quantité de
phéromone se modifie à chaque fois qu’une fourmi passe d’un état à un autre suivant la
formule suivante :  i , j (t )  p i , j (t  1)  (1  p) 0 ……………….. (1)
 0 : est la valeur initiale de phéromone. La règle utilisée par une fourmi k pour le choix de
l’état suivant devient :

 
 ArgMax  i , j   i , j

S 
 si q q 0
…………….. (2)

selon la regle III. A.1 Sinon

S : le nœud suivant.
q : une variable aléatoire uniformément distribuée sur]0,1[.
q0 : paramètre de détermination de l’importance relative entre l’exploitation et l’exploration.
ArgMax : c’est la fonction réciproque de max.
ACS peut se présenter sous forme de deux stratégies: La première (stratégie par construction)
consiste à démarrer d’une solution initialement vide, et de l’étendre progressivement jusqu’à
arriver à une solution complète. La deuxième (stratégie par amélioration) consiste à faire
démarrer chaque fourmi d’une solution initiale complète générée aléatoirement ou par une
méthode constructive, et lui appliquer le principe d’une méthode de voisinage en la déplaçant
d’une solution à une autre solution voisine afin d’améliorer sa fonction du coût. Les détails de
ces deux stratégies sont présentés ci-dessous:
- Stratégie par construction
Chaque fourmi est positionnée sur un nœud du graphe choisi aléatoirement. Initialement, on
dispose d’une solution vide. Une fourmi se déplace d’un sommet ver un autre en choisissent
successivement les sommets à rajouter à la solution en cours de construction, jusqu’à arriver à
une solution complète (fig. 38).
Algorithme ACS, stratégie de construction
Début
Initialisation
Tant que critère d’arrêt non atteint, faire
Positionner chaque fourmi sur un nœud
Répéter
Pour chaque fourmi faire
Choisir un nœud adjacent en appliquant la règle de transition d’état
Mettre à jour les pistes de phéromone (step by step)
Fin pour
Jusqu’à construction des solutions
Mettre à jour la meilleure solution construite
Mettre à jour les pistes de phéromone (offline)
Fin tant que
Fin.
Figure 6 : Algorithme ACS, stratégie de construction.
Le choix d’un sommet prochain se fait selon une règle probabiliste, dite règle de transition
d’état, appelée aussi, règle pseudo-aléatoire [DOR99a].
Cette dernière est influencée par les valeurs de phéromone. Plus précisément, une arête ayant
le plus de phéromone a une plus grande probabilité d’être sélectionné.
- Stratégie par amélioration
Dans cette stratégie, les sommets du graphe de construction représentent les différentes
solutions possibles, et une arête relie deux solutions si elles sont voisines [DOR99a]. Chaque
fourmi dispose au début d’une solution initiale complète, puis à chaque itération, chaque
fourmi se déplace vers une autre solution voisine tout en essayant d’améliorer sa solution
courante. Le pseudo code de l’algorithme ACS par amélioration est présenté dans la figure 39.
Début
Initialisation
Répéter
Pour chaque fourmi faire
Générer une solution initiale S0 aléatoirement
Construire une séquence se solutions S en modifiant S 0
Mettre à jour les pistes de phéromone (step by step)
Fin pour
Déterminer la meilleure solution trouvée dans cette itération
Mettre à jour les pistes de phéromone (offline)
Jusqu’à nombre d’itérations atteint
Fin.
Figure 7 : Algorithme ACS, stratégie d’amélioration.

Comme toute autre métaheuristique, pour améliorer la performance d’une approche ACO,
des stratégies d’intensification et de diversification sont utilisées dans le processus de
recherche.

1.4. ACO et Recherche Locale

Appliqués à des problèmes NP-difficiles d’optimisation combinatoire, les algorithmes ACO

donnent de meilleurs résultats quand ils sont hybridés avec des algorithmes de recherche
locale [DOR03]. Ceux-ci ont pour rôle d’améliorer les solutions trouvées par les fourmis. Ce
sont ces solutions localement améliorées qui sont utilisées pour la mise à jour de phéromone.
Notons que les algorithmes de recherche locale constituent dans ce cas, une forme particulière
d’actions du démon. Combiner la recherche locale à l’ACO peut être très intéressant dans la
mesure où les deux approches sont complémentaires. En effet, l’algorithme ACO effectue une
recherche plutôt globale et les solutions qu’il produit peuvent être localement optimisées par
un algorithme de recherche locale adéquat. Cette hybridation est donc en mesure d’améliorer
sensiblement les solutions générées par les fourmis. Cependant, appliquer la recherche locale
aux solutions initiales générées aléatoirement n’est pas toujours efficace.
Enfin, notons que même si l’apport des algorithmes de recherche locale à l’ACO est crucial
pour atteindre les meilleurs résultats, les algorithmes ACO restent très efficaces, même quand
la recherche locale n’est pas appliquée [DOR99a].

1.5. Parallélisation des algorithmes de colonie de fourmis

Dans les algorithmes de fourmis, chaque fourmi constitue une entité à part entière qui peut
construire une solution sans l’aide directe de ses congénères. Par leur nature même, ces
algorithmes comportent donc un parallélisme intrinsèque. Le fait qu’il y ait peu de
dépendance entre les fourmis rend la parallélisation de l’ACO fort souhaitable et assez aisée.
Il existe trois niveaux de parallélisations possibles pour les algorithmes ACO [STÜ98;
BUL97]. Nous présentons dans ce qui suit les différentes manières de paralléliser les
algorithmes de fourmis:
(i) Le parallélisme au niveau des fourmis : c’est la forme de parallélisme la plus naturelle
ou la plus intuitive pour les algorithmes de colonie de fourmis. De ce fait, elle est la plus
utilisée aussi. Dans cette stratégie, la colonie est subdivisée en sous colonies. Chacune
d’elles est affectée à un processeur et est chargée de construire une solution. Selon le
nombre de fourmis que contient chaque sous colonie affectée à chaque processeur, on
parle d’un parallélisme à grains fins (fine-grained) si ce nombre est petit et d’un
parallélisme à gros grains (coarse-grained) si ce nombre est important. On peut aussi
classer ces algorithmes selon les formes de synchronisation et d’échanges d’informations
entre les sous colonies.
(ii) Le parallélisme au niveau des données : ici, on dispose également de plusieurs sous
colonies et le problème à résoudre est subdivisé en plusieurs sous problèmes. Chaque
sous colonie est chargée de résoudre un sous problème.
(iii) Le parallélisme fonctionnel : dans ce cas, on exploite le parallélisme en faisant
exécuter en concurrence les trois procédures du programme principal de ACO : la
génération des fourmis et leur activité, l’évaporation de phéromone et les actions démon.
2. L’Optimisation par colonies d’abeilles

L’Optimisation par Colonie d’Abeilles (BSO pour Bees Swarm Optimization en anglais) est
une approche de résolution évolutionnaire s’inspirant du comportement réel des abeilles. Elle
présente un grand nombre de particularités notamment dans son fonctionnement et sa
souplesse. En effet, cette nouvelle méthode tente d’allier les avantages des méta-heuristiques
(méthodes générales, adaptables à beaucoup de problèmes) et des heuristiques spécialisées
(taillées sur mesure à un problème particulier, donc potentiellement plus efficaces). Dans
notre travail, nous nous intéressons particulièrement à deux métaheuristiques principales de la
BSO : l’optimisation par mariage d’abeilles (MBO pour Marriage in Honey Bees
Optimization en anglais) et l’optimisation par la danse d’abeilles (DBO pour Dance in Bees
Optimization en anglais).

2.1. Optimisation par Mariage d’Abeilles

L’Optimisation par Mariage d’Abeilles (MBO) est une récente méta-heuristique évolutive
inspirée du processus biologique de reproduction des abeilles et fait intervenir dans son
processus de recherche des méthodes de voisinage. Elle est apparu en 2001 [ABB01], et a été
appliquée la première fois au problème 3-Sat [ABB02], puis à d’autres problèmes tels que le
problème de partitionnement [KOU07], le Data Mining [BEN05], le PCG [BES11] et la
programmation dynamique stochastique [CHA06]. Pour bien comprendre le principe de
MBO certaines notions et généralités sur le mode de vie des abeilles sont indispensables.

2.1.1. Structure d’une ruche d’Abeilles

Les abeilles sont des insectes sociaux qui vivent en colonies très organisées. Chaque colonie
d’abeilles se compose d'une ou plusieurs reines, des faux-bourdons, des ouvrières et des
couvées. La reine est la seule femelle fertile de la communauté. Elle est donc la mère de tous
les individus qui la composent : les faux bourdons, les ouvrières et les futures reines. Sa
capacité à pondre est très importante [PHA06b]. Les ouvrières sont toujours beaucoup plus
nombreuses que les mâles. Elles sont incapables de s’accoupler et donc de se reproduire.

Elles sécrètent la cire, construisent les alvéoles, récoltent le nectar, le pollen et l’eau,
transforment le nectar en miel, nettoient la ruche et, si nécessaire, la défendent contre les
prédateurs. Le faux-bourdon est le mâle de la colonie. Sa seule fonction est de s’accoupler
avec les nouvelles reines. La reine s’accouple généralement avec cinq ou six faux-bourdons.
Après l’accouplement, qui a lieu en vol, le mâle meurt rapidement.

2.1.2. Vol nuptial (Mating-Flight)

Lorsque la reine s’accouple avec un faux bourdon, le sperme du faux-bourdon est ajouté à la
spermathèque de la reine (réservoir de spermatozoïdes). La reine se servira toute sa vie de
cette réserve pour féconder les œufs. Un ovule fécondé donnera naissance à une abeille
femelle, soit reine ou ouvrière, et un ovule non fécondé à un faux-bourdon.
Le processus de reproduction des abeilles réels qui est simulé dans MBO, peut être résumé
comme suit: au cours d'un vol nuptial, chaque reine s'accouple avec sept à vingt faux-
bourdans. A chaque accouplement, le sperme est ajouté à la spermathèque de la reine et s'y
accumule pour former le pool génétique de la colonie. Chaque fois qu'une reine pond des
œufs (couvées), elle récupère un mélange de sperme dans sa spermathèque pour féconder un
ovule.

2.1.3. Des Abeilles réelles vers des Abeilles artificielles

L’intérêt d’étudier le comportement des abeilles réelles est de s’en inspirer efficacement dans
le but d’élaborer un modèle artificiel pour l’optimisation. Pour cela, nous abordons dans ce
paragraphe le modèle artificiel tout en donnant les points de ressemblance avec le modèle des
abeilles réelles :
 Une reine artificielle possède essentiellement un génotype, une spermathèque, une vitesse
et une énergie. Le génotype de la reine peut être considéré comme une solution du
problème traité. Les nouvelles solutions sont les œufs de la reine. Le processus de
reproduction tend à améliorer le génotype de la reine au fil des générations et donc
d’améliorer la solution initiale.
 Les ouvrières artificielles sont des heuristiques parfois spécifiques au problème traité
dont le rôle est d’améliorer les génotypes des couvées (futures reines), et donc, permettre
d’obtenir de meilleures solutions.
 Les faux-bourdons réels ne possèdent que la moitié d’un génotype. On dit qu’ils sont
haploïdes. Pour cela, un faux-bourdon dans MBO est constitué d’un génotype complet et
d’un masque servant à dissimuler la moitié des gènes choisis aléatoirement. La moitié non
masquée du génotype constitue le sperme du faux-bourdon.

2.1.4. Le principe de croisement des génotypes

Lors de la fécondation, les gènes du faux-bourdon (éléments de son génotype) sont croisés
avec le génotype de la reine pour former un nouveau génotype qui constitue une solution
complète du problème. Pour illustrer le principe de croisement entre le sperme d’un faux-
bourdon et le génotype d’une reine lors d’un accouplement pour former un nouveau génotype,
nous donnons un exemple dans la figure 40 où U indique le gène non masqué et M indique
le gène masqué. Le génotype de l’enfant résultant du croisement est obtenu en complétant les
gènes manquants dans le sperme du faux-bourdon par les gènes correspondants de la reine.
.
Génotype de la reine 0 1 0 0 0 0 1 0

Masque U M M U U U M M

Sperme du faux-bourdon 1   0 0 1  

Génotype de l’enfant résultant 1 1 0 0 0 1 1 0

du croisement

 Veut dire que le faux-bourdon ne possède pas le gène.

Figure 8: Principe du croisement de MBO

2.1.5. Le vol nuptial artificiel

Le vol nuptial peut être visualisé comme une série de transitions dans un ensemble d’états où
un état représente un faux-bourdon. La reine se déplace entre les différents états dans l'espace
avec une certaine vitesse et s’accouple avec le faux-bourdon pour produire une autre solution.
La probabilité qu’une reine Q s’accouple avec un faux-bourdon D est donnée par la formule
suivante :

prob (Q, D) = e (- différence/ Vitesse (t)) (1)

Où Vitesse (t) est la vitesse de la Reine Q à l’instant t, initialisée au maximum au début du
vol, et Différence est la différence absolue entre les coûts des solutions de D et Q.
Cette formule représente la probabilité d'ajouter le sperme d’un faux-bourdon D à la
spérmathèque de la Reine Q (accouplement réussi). La probabilité d’un accouplement réussi
est très élevée quand les formes physiques du faux-bourdon et de la reine sont bonnes (au
début du vol nuptial). Autrement dit, si la différence absolue entre les coûts des solutions du
faux-bourdon et de la reine est très petite, ou quand la vitesse de la reine est grande.
L’énergie de la reine diminue durant le vol et retourne vers son nid quand son énergie atteint
un seuil critique ou quand sa spérmathèque est pleine. La vitesse et l’énergie de chaque reine
diminuent après chaque transition, suivant les formules suivantes :
Vitesse (t + 1) = α* vitesse (t). tel que : α 0,1 .
Energie (t + 1) = Energie(t) – step.
Où step représente la quantité d’énergie dépensée à chaque étape par une reine.
0.5 * EnerInitia le
Elle est donnée par: Step =
Tsper
Tel que EnerInitiale est l’énergie initiale de la reine et Tsper est la taille de sa spermathèque.
Il est clair que Step diminue à chaque fois qu’un accouplement se produit.
2.1.6. Principe général de l’algorithme MBO

Au début de l'algorithme (fig. 41) , six paramètres sont fixés: (1) le nombre de reines, (2) le
nombre d'ouvrières, (3) le nombre de couvées, (4) le nombre de vols nuptiaux, (5) la taille de
la spermathèque de la reine, et (6) le nombre d'améliorations de la couvée. Dans le processus
de recherche, les reines représentent des solutions, tandis que les ouvrières représentent
l'heuristique employée pour la recherche locale (amélioration). La taille de la spermathèque
représente le maximum possible de vols par reine ou encore le nombre d'accouplements par
reine.
Algorithme MBO ;
M : Taille de la spermathèque ;
E (t) et V (t) : Energie et vitesse des reines respectivement ;
Initialiser les génotypes des reines aléatoirement
Utiliser les ouvrières pour améliorer les génotypes de chaque reine;
Pour un nombre prédéfini de vols nuptiaux faire
Tant Que (les critères d’arrêt ne sont pas satisfaits) Faire
t=0 ; Initialiser E (t) et V (t) à des valeurs aléatoires entre [0.5, 1] ;
step= (0.5 * E (t))/M ; { facteur de réduction de l’énergie}
Générer un faux-bourdon aléatoirement ;
Tant Que (E (t)>0) faire
Générer un nouveau Faux-bourdon en changeant chaque bit du génotype en utilisant la vitesse
comme probabilité ;
Evaluer la fitness de nouveau Faux-bourdon ;
Si (le nouveau Faux-bourdon est meilleur que l’ancien) Alors
Si (le faux-bourdon passe la règle de probabilité) Alors
Si (la spermathèque de la reine n’est pas pleine) Alors
Ajouter le sperme du faux-bourdon à la spermathèque de la reine ;
Fin Si
Fin Si
t ++ ; E (t)= E (t)- step ; V (t)= 0.9* V (t) ;
fliper chaque bit de Génotype de Faux-bourdon avec la probabilité de la vitesse ;
Fin Si
Fin Tant Que
Pour i=1 jusqu’a nombre total de couvées Faire
Sélectionner un sperme aléatoirement dans la spermathèque ;
Générer une couvées en utilisant le croisement et la mutation avec le sperme sélectionné ;
Amélioration des œufs par les ouvrières ;
Mettre à jour le fitness des ouvrières ;
Fin Pour
Si (le meilleur œuf est meilleur que la plus mauvaise reine) Alors
Remplacer la plus mauvaise reine par le meilleur œuf ;
Fin Si
Tuer tous les faux-bourdon ;
Fin Tant Que
Fin Pour {tous les vols sont effectués}
Fin.
Figure 9 : Algorithme général MBO.
L’ouvrière est initialisée avec une heuristique. Un ensemble de reines est généré aléatoirement
puis leur génotype est amélioré en utilisant l’heuristique (ouvrière) pour conserver seulement
les meilleures reines. Un ensemble de vols nuptiaux est alors entrepris sachant que la vitesse
et l’énergie de chaque reine est initialisée aléatoirement à une valeur dans l’intervalle [0.5, 1]
pour s'assurer qu'elle volera pendant un certain nombre de fois. Les transitions effectuées par
chaque reine sont en fonction de sa vitesse et son énergie. La vitesse de la reine représente la
probabilité de flipper chaque bit (inverser un bit) du génome du faux-bourdon. À chaque vol,
la reine s’accouple avec un faux-bourdon rencontré durant sa trajectoire selon la règle de
probabilité (I). Si l’accouplement est réussi, le sperme du faux-bourdon (génotype) est ajouté
à la spermathèque de la reine. Quand toutes les reines ont terminé leurs vols, le procédé de
création de couvée commence. Pour créer une nouvelle couvée, un sperme est choisi
aléatoirement à partir de la spérmathèque de la reine, ensuite, il est croisé avec le génotype de
la reine. La mutation est alors appliquée à la nouvelle couvée pour l’améliorer, en utilisant
l’ouvrière. Les nouvelles couvées améliorées sont alors triées selon leur forme physique
(fitness) et elles remplacent les reines de mauvaises qualités jusqu'à ce qu'il n'y ait aucune
couvée meilleure que n’importe quelle reine. Les couvées restantes sont alors détruites et un
nouveau vol nuptial est entrepris.
Ce processus est répété jusqu'à ce que tous les vols nuptiaux soient générés ou un critère
d’arrêt soit vérifié.

2.2. Optimisation par la danse d’abeilles (DBO)

L’optimisation par danse d’abeilles (DBO pour Dance Bees Optimization en Anglais) est une
récente métaheuristique évolutive pour l’optimisation combinatoire, basée sur le
comportement des abeilles lors de la recherche de nourriture. En effet, une abeille qui a
découvert une source de nourriture revient à la ruche et communique non seulement la
direction de la source, mais également la distance entre la ruche et cette source.
L'abeille transmet ces informations à ses congénères par le moyen d’une danse.
Cette approche a été appliquée à plusieurs problèmes NP-Difficiles tels que le Max-W-Sat
[DRI05 ; SAD07], le problème de classification non supervisée [PHA07a], l’ordonnancement
[PHA07b], et l’optimisation des réseaux de neurones [PHA06b].

2.2.1. La recherche de nourriture chez les abeilles

Une abeille à la recherche de nourriture peut trouver une source de nourriture mais éloignée
de sa ruche (jusqu’à dix kilomètres). Elle doit donc retourner à la ruche pour informer les
autres ouvrières de sa découverte et leur transmettre des informations sur la direction de la
source même si celle-ci est très loin et difficile à retrouver. Pour cela, elle doit communiquer
aux autres ouvrières la direction et la distance de la source de nourriture par rapport à la
ruche, ainsi que certaines indications sur sa qualité. En effet, elle doit attirer l’attention des
autres ouvrières, qui peuvent déjà être occupées à faire autre chose ou avoir reçu des
messages d’autres abeilles. La question qui se pose est alors: « Comment les abeilles
communiquent entre elles ? ».

2.2.2. La communication entre les abeilles : la danse des abeilles

David McFarland et al. [MCF01] ont construit une ruche avec une paroi en verre pour
observer le comportement des abeilles. Ils remarquèrent qu’en revenant après avoir cherché à
manger, les abeilles exécutaient des danses qui attiraient l’attention des autres.
L'abeille qui a découvert une source de nourriture revient à la ruche et communique non
seulement la direction de la nourriture mais également la distance entre la ruche et la source.
Ces informations, l'abeille les transmet via une danse. Il s'agit d'une véritable communication,
d'un véritable langage codé. En effet, les abeilles ainsi informées peuvent localiser la source
de nourriture.
Dès son retour à la ruche, l’abeille appelée éclaireuse commence par dégorger une goutte de
nectar. Ses compagnes prennent non seulement connaissance de la découverte, mais peuvent
en savoir la nature exacte. Le parfum du nectar rapporté est celui d’une fleur bien déterminée
facile à reconnaître. C’est alors que commence la danse. Le type de danse est différent selon
que la nourriture se trouve à moins de 100 m, ou à une distance supérieure. Lorsque la
nourriture est à moins de 100 m, une danse en rond signale simplement la proximité du
repas, sans indication de direction. Faisant vibrer ses ailes pour attirer l’attention de ses
compagnes, l’abeille décrit un cercle, d’abord dans le sens des aiguilles d’une montre puis en
sens inverse. Elle entraîne dans sa danse un certain nombre de ses compagnes. Persuadée de
l’effet produit par sa publicité tapageuse, elle se déplace vers un autre coin de la ruche pour
convaincre un grand nombre d’abeilles appelées butineuses. La nouvelle de la découverte est
vite répandue, et c’est ainsi qu’une partie de la ruche est renseignée sur la nature du butin et
sur la distance à laquelle il se trouve. Les abeilles partent alors pour la récolte.
Elles trouvent d’ailleurs confirmation de leur bonne interprétation du message quand elles
repèrent sur le lieu de rendez-vous l’odeur d’une goutte de sécrétion intentionnellement
laissée par leur indicatrice.
Si la source de nourriture est éloignée (plus de 100m), ce qui arrive fréquemment, les
renseignements à fournir par l’éclaireuse doivent être plus précis: la distance et la direction à
prendre seront indiquées par une danse frétillante, non plus en cercle, mais selon une figure
qui prend la forme d’un huit « 8 ». La distance est donnée par la vitesse de la danse : plus la
danse est rapide, plus la source de nourriture est proche. La direction est indiquée par rapport
au soleil (fig. 42): l’inclinaison verticale de la danse est égale à l’angle horizontal entre la
nourriture et le soleil.

Figure 10 : La direction de la danse des abeilles par rapport au soleil.

Si la danse est dirigée vers le bas, le pollen se trouve dans la direction opposée à celle du
soleil. Si par contre, elle est verticale, le pollen se trouve dans la direction du soleil. Enfin, si
la ligne ascendante ou descendante forme un angle avec la verticale correspondante; celui-ci
représente l'angle entre la direction du soleil et celle dans laquelle se trouve le pollen.

2.2.3. L’algorithme général de DBO

La métaheuristique DBO (fig.43) est constituée principalement de deux phases : la phase

d’initialisation et la phase de recherche [PHA06a, PHA06b].
Algorithme DBO
Début
Sref :=sommet représentant le nid ;
//concrètement Sref représente une solution aléatoire ou un point de départ abondant en nourriture
Tant que non critère d’arrêt faire
Insérer Sref dans la liste Tabou s’il y est pas encore ;
//pou éviter de le choisir une autre fois
Déterminer la région de l’exploration SearchArea à partir de S ref ;
// plusieurs sommets sont créés à partir de Sref
Pour i allant de 1 à BeesNumber faire
Affecter à l’abeille n° i un sommet de SearchArea ;
//chaque abeille cherche à partir d’un sommet de SearchArea
Rechercher depuis le sommet Si qui lui associé ;
// la procédure abeille
Stocker le résultat dans la ieme entrée de la table danse ;
 // chaque abeille stocke ici le résultat de sa recherche
Fin Pour
Choisir le nouveau sommet de référence Sref ;
// choix d’un nouveau point de référence en fonction de la table ‘danse ‘ et
de l’amélioration constatée
Fin Tant que
Fin
Figure 11 : Algorithme général de DBO.
- Phase d’initialisation
Cette phase a pour but de construire une solution initiale qui consiste à trouver un point de
départ qu’on appellera Sref . Plusieurs méthodes peuvent être utilisées pour choisir ce point de
départ.
On peut choisir Sref aléatoirement, ou encore démarrer d’une zone riche en nourriture (une
abondance de nourriture y a été constatée) ; Enfin, pour choisir ce point de départ, on peut
également utiliser une recherche locale ou une méthode constructive, si les propriétés du
problème à traiter sont connues. Une liste tabou qui contient les points de références courant
les plus récents est également créée.
- Phase de recherche
Cette phase consiste en une boucle itérative jusqu’à atteindre un critère d’arrêt prédéfini. Il
peut s’agir d’un nombre d’itération à effectuer, d’un certain nombre d’itération sans
amélioration ou d’autres conditions plus au moins complexes étant étroitement liées au
problème à résoudre.
La phase de recherche est constituée de plusieurs étapes que nous décrivons ci-dessous :
Etape1 : Insertion dans la liste tabou
Dans cette étape, on insère Sref dans une liste Tabou s’il ne s’y trouve pas déjà. La liste
Tabou peut être statique ou dynamique. Si on utilise une liste statique, des cycles peuvent
apparaître. En effet, si un élément est mis dans cette liste et qu’il prend la place d’un
ancien élément, ce dernier peut réapparaître et être considéré une seconde fois comme un
point de référence. En revanche, l’utilisation d’une liste dynamique permet
éventuellement d’éviter les cycles. Son seul inconvénient est la dégradation des
performances de l’algorithme à cause du nombre de comparaisons faites dans la liste qui
augmente avec le nombre d’itération effectuée.
Etape2 : Génération de l’espace de recherche
L’espace de recherche appelé SearchArea est construit à partir du point de référence au
début de chaque itération. Cette zone est constituée d’un ensemble de sommets égal au
nombre d’abeilles. L’obtention de cette région d’exploration se fait en s’éloignant du
point de référence d’une certaine distance. Chacun de ces points est le point de départ
d’une procédure abeille.
Etape3 : Affectation des zones de recherches aux abeilles
Chaque abeille se voit assignée un point de la zone de recherche (SearchArea), dans
lequelle elle démarre une recherche. Cette dernière se fait en se déplaçant d’un sommet
vers un sommet voisin jugé meilleur.
Etape4 : Recherche d’une abeille et rangement du résultat dans la table Danse
Chaque abeille commence donc sa recherche à partir du point de SearchArea qu’on lui a
affecté. Cette recherche est généralement locale mais peut être étendue. Chaque abeille
cherche la meilleure solution dans son voisinage direct. Puis, elle répète cette opération
jusqu’à ce qu’une condition d’arrêt soit vérifiée. A la fin de chaque recherche effectuée,
chaque abeille mémorise le meilleur sommet qu’elle a visité dans une table appelée
Danse. Cette dernière est l’unique moyen de communication entre les abeilles.
Etape5 : Choix d’un nouveau point de référence
La prochaine étape consiste à choisir le nouveau point de référence parmi les résultats des
recherches des abeilles. En effet, une des solutions présentes dans la table « danse »
devient le point de référence courant de la prochaine itération de la boucle principale de
l’algorithme. Une nouvelle zone de recherche est donc explorée. Cependant, dans le cas
où la qualité de la solution obtenue ne s’améliore plus pendant un certain nombre
d’itérations, un critère de diversification est introduit. La diversification permet de
s’echapper de la région d’exploration courante en choisissant un nouveau point de
référence éloigné des régions déjà exploitées .