Ants Colony optemisation (ACO)
Algorithme d’optimisation par colonies de fourmis (AOCF):
Appelé en anglais Ant Colony Optimisation (ACO)
L’origine de l’algorithme :
L’AOCF est un algorithme méta heuristique d’IE, qui a été introduit par l’italien Marco Dorigo autour des années 1990 durant sa thèse de doctorat sur l’optimisation et les algorithmes naturel. Cet algorithme a été proposé la première fois pour résoudre un problème d’optimisation discrète, et il a été aussi utilisé pour le problème de voyageur de commerce. Plusieurs versions de cet algorithme ont été proposées dans la littérature comme l’algorithme de minimum/maximum proposée par Stützle et Hoos en 1997, et l’algorithme de système des fourmis.
La source d’inspiration :
L’AOCF a été inspiré par le mode de vie des fourmis et leur aptitude à trouver le plus court chemin entre leur nid et la source de nourriture. Ces insectes sont caractérisés par le phénomène du stigmergie introduit en 1959 par grasse qui se réfère à la communication indirecte entre les fourmis grâce aux traces de phéromone.
Les fourmis commencent d’abord par explorer aléatoirement l’environnement autour de leur nid. En se déplaçant, les fourmis laissent une trace de phéromone chimique sur leur chemin. Le mouvement des fourmis est guidé par l’odeur de phéromone. Les fourmis ont tendance à choisir les chemins balisés par la concentration de phéromone les plus forte. Dans le retour, la quantité de phéromone qu’une fourmi laisse sur son chemin dépend de la qualité et la quantité de nourriture porter.
Résumé de l’algorithme :
L’idée principale de l’algorithme est de modéliser le problème à résoudre sous forme d’un problème de recherche d’un chemin optimal dans un graphe pondéré et d’utiliser les fourmis artificielles pour trouver les chemins de qualité parmi tous les chemins disponibles. Les fourmis se déplacent d’un nœud à un autre suivant une règle de transition basée sur une probabilité. Chaque solution construite est évaluée suivant une fonction de fitness afin de détecter le plus court chemin(les nœuds du graphe qui correspond aux composants de la solution).
Passage de la vie artificielle à la vie naturelle :
|
|
Colonie de fourmis natural |
La vie artificielle des fourmis |
|
Entrée |
Plusieurs chemins possibles du nid vers la source de nourriture. |
Plusieurs solutions possibles sous forme d’un graphe pondérer avec fixation du nœud de départ et le nœud d’arriver pour chaque fourmi artificiel. |
|
Traitement |
Exploration aléatoire des fourmis d’une position à un autre. |
Déplacement aléatoire des fourmis d’un nœud à un autre et construction des solutions aléatoire. |
|
Initialement les probabilités de déplacement d’une position à une autre sont similaires |
Initialement les probabilités de déplacement d’un nœud à un autre sont fixes |
|
|
L’évaporation des phéromones. |
Évaporation des phéromones à travers le paramètre P |
|
|
Fourmis naturelles |
Fourmis artificielles |
|
|
la quantité de phéromone qu’une fourmi laisse sur un chemin dépend de la qualité et la quantité de nourriture porter. |
La densité du phéromone de chaque arc dépend du nombre de fourmis qui ont passé par cet arc et la distance globale du chemin parcourus par chaque fourmi (calculer par la formule et d’une ville I à une ville j). |
|
|
Communication en laissant des traces de phéromones
|
Mise à jour des phéromones |
|
|
Probabilité de déplacement d’une position à une autre basé sur la quantité de phéromone déposer sur chaque chemin |
Probabilité de déplacement d’un nœud à un autre dépend de la densité de phéromone et la distance entre les nœuds (calculer par la formule ) |
|
|
Le mouvement des fourmis est guidé par l’odeur des phéromones puisqu’elles ont tendance à choisir les chemins balisés par la concentration de phéromone les plus forte. |
Le mouvement des fourmis artificielles est guidé par la quantité de phéromone et le cout dans chaque arc. |
|
|
Sortie |
Trouver le chemin le plus court entre la source de nourriture et le nid parmi l’ensemble des chemins possibles. |
Trouver la solution optimale pour un problème parmi l’ensemble des solutions possible
|
Processus général :
L’architecture générale regroupant les différentes étapes de l’AOEF est présentée dans la figure suivante:
