vignette|Certains comportements des fourmis sont à l'origine d'algorithmes d’optimisation (ici, des fourmis légionnaires du genre Dorylus).
Les algorithmes de colonies de fourmis (, ou ACO) sont des algorithmes inspirés du comportement des fourmis, ou d'autres espèces formant un superorganisme, et qui constituent une famille de métaheuristiques d’optimisation.
Initialement proposé par Marco Dorigo dans les années 1990A. Colorni, M. Dorigo et V. Maniezzo, Distributed Optimization by Ant Colonies, actes de la première conférence européenne sur la vie artificielle, Paris, France, Elsevier Publishing, 134-142, 1991.M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992., pour la recherche de chemins optimaux dans un graphe, le premier algorithme s’inspire du comportement des fourmis recherchant un chemin entre leur colonie et une source de nourriture. L’idée originale s'est depuis diversifiée pour résoudre une classe plus large de problèmes et plusieurs algorithmes ont vu le jour, s’inspirant de divers aspects du comportement des fourmis.
En anglais, le terme consacré à la principale classe d’algorithme est (ACO). Les spécialistes réservent ce terme à un type particulier d'algorithme. Il existe cependant plusieurs familles de méthodes s'inspirant du comportement des fourmis. En français, ces différentes approches sont regroupées sous les termes : , , ou diverses combinaisons de ces variantes.
Origine L’idée originale provient de l’observation de l’exploitation des ressources alimentaires chez les fourmis. En effet, celles-ci, bien qu’ayant individuellement des capacités cognitives limitées, sont capables collectivement de trouver le chemin le plus court entre une source de nourriture et leur nid.
Des biologistes ont ainsi observé, dans une série d’expériences menées à partir de 1989S. Goss, S. Aron, J.-L. Deneubourg et J.-M. Pasteels, The self-organized exploratory pattern of the Argentine ant, Naturwissenschaften, volume 76, pages 579-581, 1989.J.-L. Deneubourg, S. Aron, S. Goss et J.-M. Pasteels, The self-organizing exploratory pattern of the Argentine ant, Journal of Insect Behavior, volume 3, page 159, 1990., qu’une colonie de fourmis ayant le choix entre deux chemins d’inégale longueur menant à une source de nourriture avait tendance à utiliser le chemin le plus court.
Un modèle expliquant ce comportement est le suivant : une fourmi (appelée « éclaireuse ») parcourt plus ou moins 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 une piste de phéromones ; ces phéromones étant attractives, les fourmis passant à proximité vont avoir tendance à suivre, de façon plus ou moins directe, cette piste ; en revenant au nid, ces mêmes fourmis vont renforcer la piste ; 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 longue piste ; la piste courte sera donc de plus en plus renforcée, et donc de plus en plus attractive ; la longue piste, elle, finira par disparaître, les phéromones étant volatiles ; à terme, l’ensemble des fourmis a donc déterminé et « choisi » la piste la plus courte.
Les fourmis utilisent leur environnement comme support de communication : elles échangent indirectement de l’information en déposant des phéromones, le tout décrivant l’état de leur « travail ». L’information échangée a une portée locale, seule une fourmi située à l’endroit où les phéromones ont été déposées y a accès. Ce système porte le nom de « stigmergie », et se retrouve chez plusieurs animaux sociaux (il a notamment été étudié dans le cas de la construction de piliers dans les nids de termites).
Le mécanisme permettant de résoudre un problème trop complexe pour être abordé par des fourmis seules est un bon exemple de système auto-organisé. Ce système repose sur des rétroactions positives (le dépôt de phéromone attire d’autres fourmis qui vont la renforcer à leur tour) et négatives (la dissipation de la piste par évaporation empêche le système de s'emballer). Théoriquement, si la quantité de phéromone restait identique au cours du temps sur toutes les branches, aucune piste ne serait choisie. Or, du fait des rétroactions, une faible variation sur une branche va être amplifiée et permettre alors le choix d’une branche. L'algorithme va permettre de passer d'un état instable où aucune branche n'est plus marquée qu'une autre, vers un état stable où l'itinéraire est formé des « meilleures » branches.
Exemple : le « système fourmi » Description générale Le premier algorithme de colonies de fourmis proposé est appelé le Ant systemM. Dorigo, V. Maniezzo, et A. Colorni, Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics--Part B, volume 26, numéro 1, pages 29-41, 1996. (système fourmi). Il vise notamment à résoudre le problème du voyageur de commerce, où le but est de trouver le plus court chemin permettant de relier un ensemble de villes.
L’algorithme général est relativement simple, et repose sur un ensemble de fourmis, chacune parcourant un trajet parmi ceux possibles. À chaque étape, la fourmi choisit de passer d’une ville à une autre en fonction de quelques règles : elle ne peut visiter qu’une fois chaque ville ; plus une ville est loin, moins elle a de chance d’être choisie (c’est la « visibilité ») ; plus l'intensité de la piste de phéromone disposée sur l’arête entre deux villes est grande, plus le trajet aura de chance d’être choisi ; une fois son trajet terminé, la fourmi dépose, sur l’ensemble des arêtes parcourues, plus de phéromones si le trajet est court ; les pistes de phéromones s’évaporent à chaque itération.
Description formelle La règle de déplacement, appelée « règle aléatoire de transition proportionnelle », est écrite mathématiquement sous la forme suivante : ,
où est la liste des déplacements possibles pour une fourmi lorsqu’elle se trouve sur une ville , la visibilité, qui est égale à (l’inverse de la distance de deux villes et ) et l’intensité de la piste à une itération donnée . Les deux principaux paramètres contrôlant l’algorithme sont et , qui contrôlent l’importance relative de l’intensité et de la visibilité d’une arête.
En pratique, pour que les fourmis explorent des pistes non découvertes, on attribue une probabilité non nulle d'exploration de ces villes « inconnues », contrôlée par le paramètre . De cette façon, la probabilité de déplacement s'écrit : .
Une fois la tournée des villes effectuée, une fourmi dépose une quantité de phéromone sur chaque arête de son parcours : ,
où est la tournée faite par la fourmi à l’itération , la longueur du trajet et un paramètre de réglage.
À la fin de chaque itération de l’algorithme, les phéromones déposées aux itérations précédentes par les fourmis s’évaporent de .
Et à la fin de l'itération, on a la somme des phéromones qui ne se sont pas évaporées et de celles qui viennent d'être déposées : ,
où est le nombre de fourmis utilisées pour l’itération et un paramètre de réglage.
Principales variantes L’algorithme de colonies de fourmis a été à l’origine surtout utilisé pour produire des solutions quasi optimales au problème du voyageur de commerce, puis, plus généralement, aux problèmes d’optimisation combinatoire. On observe que depuis ses débuts son emploi s'est étendu à plusieurs domaines, depuis l’optimisation continue jusqu’à la classification ou encore le traitement d’images.
Le cadre « ACO » Une partie des algorithmes (notamment ceux conçus par M. Dorigo et ses collègues) sont maintenant regroupés sous le terme de « Ant Colony Optimisation » (ACO). Ce cadre se limite cependant aux algorithmes construisant des solutions sous la forme de paramètres associés aux composants d'un graphe, à l'aide d'un modèle statistique biaisé.
Une méthode de type ACO suit le schéma algorithmique suivant, paramétré par : un critère d'arrêt de l’algorithme un temps de calcul ou un nombre d'itérations alloué dépassé, un seuil d'amélioration des solutions qui n’est plus satisfaisant, ou une combinaison de critères des heuristiques (éventuellement) une construction des solutions et des pistes de phéromones dépendant du problème à résoudre et de sa structure
Initialisation des pistes de phéromone ;
Boucler tant que critère d'arrêt non atteint :
construire les solutions composant par composant,
utilisation (facultative) d'une heuristique,
mise à jour des pistes de phéromone ;
Fin de la boucle.
Une variante efficace du système formique est le Max-Min Ant System (MMAS)T. Stützle et H.H. Hoos, MAX MIN Ant System, Future Generation Computer Systems, volume 16, pages 889-914, 2000., où seules les meilleures fourmis tracent des pistes et où le dépôt de phéromones est limité par une borne supérieure (empêchant une piste d’être trop renforcée) et une borne inférieure (laissant la possibilité d’être explorée à n’importe quelle solution). Cet algorithme atteint de meilleurs résultats que l’original, et évite notamment une convergence prématurée.
L’autre variante la plus connue est le Ant Colony System (ACS)M. Dorigo et L.M. Gambardella, Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, volume 1, numéro 1, pages 53-66, 1997., où à une nouvelle règle de déplacement (appelée « règle pseudo-aléatoire proportionnelle ») s’ajoute un processus de mise à jour « locale » des éléments des pistes de phéromones, l’objectif de ce mécanisme étant d’augmenter la diversification de la recherche.
Il est possible, pour certaines versions, de prouver que l’algorithme est convergent (c’est-à-dire qu’il est capable de trouver l’optimum global en un temps fini). La première preuve de convergence d'un algorithme de colonies de fourmis fut apportée en 2000, pour l’algorithme graph-base ant system, puis pour les algorithmes ACS et MMAS. Comme pour la plupart des métaheuristiques, il est très difficile d’estimer théoriquement la vitesse de convergence.
En 2004, Zlochin et ses collègues ont montréM. Zlochin, M. Birattari, N. Meuleau, et M. Dorigo, Model-based search for combinatorial optimization: A critical survey, Annals of Operations Research, vol. 131, , 2004. que les algorithmes de type ACO pouvaient être assimilés aux méthodes de descente stochastique de gradient, d'entropie croisée et des algorithmes à estimation de distribution. Ils ont proposé de regrouper ces métaheuristiques sous le terme de « recherche à base de modèle ».
Une définition difficile
Il n’est pas facile de donner une définition précise de ce qu’est ou ce que n’est pas un algorithme de colonies de fourmis, car la définition peut varier selon les auteurs et les usages.
D’une façon très générale, les algorithmes de colonies de fourmis sont considérés comme des métaheuristiques à population, où chaque solution est représentée par une fourmi se déplaçant sur l’espace de recherche. Les fourmis marquent les meilleures solutions, et tiennent compte des marquages précédents pour optimiser leur recherche.
On peut les considérer comme des algorithmes multi-agents probabilistes, utilisant une distribution de probabilité implicite pour effectuer la transition entre chaque itération. Dans leurs versions adaptées à des problèmes combinatoires, ils utilisent une construction itérative des solutions.