Algorithme de colonies de fourmis - Définition
La liste des auteurs de cet article est disponible ici.
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’image.
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 Optimization » (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 l'algorithme suivant :
Initialisation des pistes de phéromone ; Boucler tant que critère d'arrêt non atteint: construire les solutions composants par composants, utilisation (facultative) d'une heuristique, mise à jour des pistes de phéromone ; Fin de la boucle. Une variante efficace du Ant System est le Max-Min Ant System (MMAS), 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), 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é 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.
D’après certains auteurs, ce qui différencierait les algorithmes de colonies de fourmis d’autres métaheuristiques proches (telles que les algorithmes à estimation de distribution ou l’optimisation par essaim particulaire) serait justement son aspect constructif. En effet, dans les problèmes combinatoires, il est possible que la meilleure solution finisse par être trouvée, alors même qu’aucune fourmi ne l’aura éprouvée effectivement. Ainsi, dans l’exemple du problème du voyageur de commerce, il n’est pas nécessaire qu’une fourmi parcoure effectivement le chemin le plus court : celui-ci peut être construit à partir des segments les plus renforcés des meilleures solutions. Cependant, cette définition peut poser problème dans le cas des problèmes à variables réelles, où aucune structure du voisinage n’existe.
Le comportement collectif des insectes sociaux reste une source d’inspiration pour les chercheurs. La grande diversité d’algorithmes (pour l’optimisation ou non) se réclamant de l’auto-organisation dans les systèmes biologiques a donné lieu au concept d’« intelligence en essaim », qui est un cadre très général, dans lequel s’inscrivent les algorithmes de colonies de fourmis.
Algorithmes stigmergiques
On observe en pratique qu’un grand nombre d’algorithmes se réclament d’une inspiration « colonies fourmis », sans toujours partager le cadre général de l’optimisation par colonies de fourmis canonique (ACO). En pratique, l’utilisation d’un échange d’informations entre fourmis via l’environnement (principe dénommé « stigmergie ») suffit à rentrer dans la catégorie des algorithmes de colonies de fourmis. Ce principe a mené certains auteurs à créer le terme d’« optimisation stigmergique ».
On trouve ainsi des méthodes s’inspirant de comportements de recherche de nourriture, de tri de larves, de division du travail ou de transport coopératif.
