Contacts tuteurs : Antoine Saillenfest (antoine.saillenfest AT telecom-paristech.fr)
L’idée originale vient de l’observation des fourmis qui sont capables de trouver le chemin le plus court entre une source de nourriture et leur nid.
Un modèle expliquant ce comportement est le suivant :
- une fourmi parcourt plus au hasard l’environnement autour de la colonie ;
- si celle-ci découvre une source de nourriture, elle rentre plus ou moins directement au nid, en laissant sur son chemin des phéromones ;
- ces phéromones permettent à d’autres fourmis de suivre plus ou moins bien la piste entre la fourmilière et la nourriture ;
- en revenant au nid, ces fourmis vont renforcer la piste (ie. Redéposer des phéromones);
- si deux pistes sont possibles pour atteindre la même source de nourriture, celle étant la plus courte sera, dans le même temps, parcourue par plus de fourmis que la plus longue. La piste courte sera donc de plus en plus renforcée ;
- la longue piste finira par disparaître, les phéromones étant volatiles ;
- à terme, il restera essentiellement la piste la plus courte.
Ceci est un bon exemple de système auto-organisé.
Cet algorithme trouve des applications dans un grand nombre de domaines, en particulier il est très adapté à la recherche de plus courts chemins dans un graphe ou la planification dans le déplacement d’un robot. L’algorithme de base est adaptable à un grand nombre de problèmes (recherche multi-objectifs…). L’algorithme de colonies de fourmis doit être utilisé avec discernement et ne doit pas remplacer des méthodes plus adaptées ou plus efficaces.
Dans le cadre de PACT, cette méthode peut être utilisées :
- pour trouver la solution optimale d’un problème donné (distance minimale)
- comme source d’inspiration pour la modélisation d’un phénomène naturel