Première implémentation de CIAC

Un nouvel algorithme de colonie de fourmis exploitant la communication directe entre individus ; application à l’optimisation en variables continues 

Le premier algorithme inspiré des colonies de fourmis (le "Ant System" [1]), a été appliqué à divers problèmes d’optimisation combinatoire avec succès. Par la suite, un petit nombre de travaux ont été consacrés à l’adaptation au cas continu de cette nouvelle métaheuristique. Le premier algorithme conçu pour l’optimisation de fonctions continues est l’algorithme CACO ("Continuous Ant Colony Algorithm" [2]) qui confie les recherches locales à une colonie de fourmis, tandis que la recherche globale est accomplie par un algo- rithme génétique. Tous ces algorithmes retiennent un trait particulier du comportement des fourmis réelles : le dépôt de piste de phéromone. En effet, la colonie de fourmis est souvent décrite comme un système distribué capable de résoudre des problèmes complexes de par la mise en jeu de processus "stigmergiques", définis comme une forme de communi- cation indirecte, par le biais de modifications de l’environnement. Mais le dépôt de piste est aussi rencontré dans certains processus de "recrutement". Le recrutement est défini par les biologistes comme un mode de communication conduisant quelques individus à se réunir à un endroit où un travail est nécessaire. Une séquence typique de recrutement par piste est schématisé en figure 1. Une autre méthode d’optimisation s’inspirant de cette définition a été développée dans le cas continu : l’algorithme API, qui est quant à lui inspiré par le comportement de recrutement d’une fourmi primitive [3]. Cet algorithme exploite en effet le "tandem running", qui implique deux fourmis et tend à réunir les individus sur un même site de chasse. Les auteurs préconisent ce recrutement particulier pour faire progresser la population vers l’optimum, en choisissant le meilleur point parmi ceux évalués par les fourmis. Mais l’algorithme API utilise peu les structures mémorielles qui caractérisent généralement les systèmes de colonies de fourmis [4], à savoir la présence d’une mémoire externe, partagée par les agents.

Notre point de vue est que la métaphore des colonies de fourmis peut être définie comme un modèle mettant en jeu non seulement des phénomènes stigmergiques, mais aussi, plus largement, des processus de recrutement. Selon cette idée, le dépôt de piste ne serait pas la seule façon d’exploiter la métaphore des colonies de fourmis pour des problèmes d’optimisation. Nos recherches récentes en modélisation du comportement de la fourmi [5] ont montré qu’il est possible de mettre en oeuvre une partie de la séquence de recrutement, sans prendre de pistes de phéromone en considération. Dans ce modèle, les processus stigmergiques ont été délibérément ignorés et nous nous sommes concentrés sur les rapports entre individus. L’objectif de ce travail était de reproduire le flux de fourmis quittant le nid après l’entrée d’une "éclaireuse", qui aurait découvert une nouvelle source d’alimentation. Pour différencier ce processus du recrutement par piste, nous l’avons appelé "mobilisation". En effet, comme le suggère la figure 2, ce phénomène prend place au moment où l’éclaireuse rentre au nid, provoquant la sortie simultanée de plusieurs individus. Nous avons montré que, par une modélisation simple des "trophallaxies" (un échange d’aliment liquide entre deux individus), on peut expliquer certains comportements collectifs, comme l’adaptation de l’amplitude et de la vitesse du flux sortant à "l’état" de l’éclaireuse. Les principaux mécanismes impliqués dans la réponse sont la distribution des états des fourmis et la propagation de l’information de mobilisation. Un tel modèle suggère l’importance de la communication interindividuelle : nous pensons que la prise en compte de tels processus dans un algorithme de colonie de fourmis peut en améliorer le fonctionnement, en accélérant la diffusion de l’information à travers la population des agents.

Nous développons actuellement une méthode d’optimisation continue, inspirée des colonies de fourmis, qui exploite le concept de communication interindividuelle. Cette méthode, dénommée CIAC ("Continuous Interacting Ant Colony"), s’applique à la fois à la recherche globale et à la recherche locale d’un optimum. Ce nouvel algorithme sera testé sur un large ensemble de fonctions analytiques comprenant un grand nombre de variables (jusqu’à 100), et comparé avec les meilleures méthodes publiées (autres algorithmes fondés sur les colonies de fourmis, algorithmes génétiques, recherche tabou et recuit simulé).

[1] A. Colorni, M. Dorigo, V. Maniezzo. "Distributed Optimization by Ant Colonies". Proceedings of ECAL91 - European Conference on Artificial Life, 134-142. Elsevier Pub- lishing, 1991.

[2] G. Bilchev, I.C. Parmee, "The Ant Colony Metaphor for Searching Continuous Design Spaces", Lecture Notes in Computer Science, 993, 25-39, 1995.

[3] N. Monmarché, G. Venturini, M. Slimane, "On how Pachycondyla apicalis ants suggest a new search algorithm", Future Generation Computer Systems , 16, 937-946, 2000.

[4] E.D. Taillard, L. Gambardella, M. Gendreau, J-Y. Potvin, "Adaptive Memory Pro- gramming : A Unified View of Metaheuristics", EURO XVI Conference Tutorial and Re- search Reviews booklet, Brussels, July 1998.

[5] J. Dréo, "Modélisation de la mobilisation chez les fourmis", Mémoire de DEA, Uni- versité Paris7 & Université Libre de Bruxelles, 2001.

Commentaires