Premiers résultats de CIAC

Un nouvel algorithme de colonie de fourmis exploitant le concept d’hétérarchie pour l’optimisation en variables continues 

Résumé

Les algorithmes de colonies de fourmis sont une classe de métaheuristiques inspirées du comportement des fourmis réelles. L’idée originale consistait à simuler la communication par des processus stigmergiques, ce qui a amené à assimiler ces algorithmes à une forme de programmation à mémoire adaptative. Un nouveau formalisme est proposé pour la conception d’algorithmes de colonies de fourmis, introduisant les notions d’hétérarchie dense et de canaux de communication. Un algorithme hétérarchique, appelé CIAC ("Continuous Interacting Ant Colony"), est proposé pour l’optimisation de fonctions continues. CIAC utilise deux canaux de communication ayant les propriétés des communications stigmergiques et directes, observables dans la nature. Nous illustrons sur un exemple les performances de ce nouvel algorithme.

Introduction

Le premier algorithme inspiré des colonies de fourmis (le "Ant System", [Colorni91]), 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", [Bilchev95]) qui confie les recherches locales à une colonie de fourmis, tandis que la recherche globale est accomplie par un algorithme 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 communication indirecte, par le biais de modifications de l’environnement. 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 inspiré par le comportement de recrutement d’une fourmi primitive [Monmarché00]. Mais cet algorithme utilise peu les structures mémorielles qui caractérisent généralement les systèmes de colonies de fourmis [Taillard01], à savoir la présence d’une mémoire externe, partagée par les agents. Nous nous sommes intéressés à ces différentes approches et il nous a semblé qu’il serait intéressant de les rassembler dans un formalisme unique. En effet, il existe une façon différente d’approcher le comportement des insectes sociaux : la notion d’hétérarchie dense. A l’origine, cette idée est utilisée pour décrire la communication au sein des colonies de fourmis, mais nous proposons un formalisme simple pour utiliser cette notion dans la conception d’algorithmes d’optimisation. Un algorithme hétérarchique tire avantage du flot d’information passant dans une population d’agents. Ces informations sont échangées à travers des canaux de communication et permettent qu’une certaine description de la fonction objectif émerge du système. Le nouvel algorithme hétérarchique que nous avons implémenté est appelé CIAC, pour "Continuous Interacting Ant Colony".

Hétérarchie dense

La notion d’hétérarchie dense a été introduite par Wilson en 1988 [Wilson88] pour décrire les mécanismes de communication dans une colonie de fourmis. Dans cette idée, deux canaux de communication sont présents : le canal stigmergique et la communication directe entre individus. Un résultat important est que l’information circule à travers la colonie, chaque fourmi pouvant communiquer avec n’importe quelle autre (cf. Fig. [Heterarchy_channels]a). Un tel système présente des propriétés émergentes remarquables : en effet, si chaque agent opère avec des règles élémentaires et une précision limitée, la population entière, organisée en hétérarchie avec une communication massive, peut présenter des modes de comportement particuliers, qui ont été soulignés dans l’étude de l’auto-organisation.

Les notions d’hétérarchie et de canal de communication

Nous proposons un formalisme simple pour appliquer cette notion d’hétérarchie dense à des problèmes d’optimisation. Le principal concept d’un algorithme hétérarchique est celui de canaux de communication. Un canal de communication, pour prendre l’exemple des pistes dans la métaphore des colonies de fourmis, transmet une information (la localisation d’une source d’information) et présente des propriétés spécifiques (stigmergie, mémoire) (cf. Fig. [Heterarchy_channels]b). Quelques propriétés de base d’un canal de communication sont les suivantes : portée (l’information passe d’un groupe d’agents à un autre), mémoire (l’information est stockée dans le système) et intégrité (l’information évolue, est modifiée). Ces propriétés peuvent se combiner de façon à ce qu’un grand nombre de canaux différents puissent être construits.

Algorithme CIAC

Nous avons implémenté deux canaux de communication : un canal stigmergique et un canal direct. Le canal stigmergique est aussi proche que possible d’une version continue de l’algorithme original, qui était conçu pour des problèmes combinatoires. En raison de ce parti pris, il peut avoir quelques ressemblances avec la recherche locale de CACO, qui est également inspirée du premier "Ant System". Chaque fourmi peut déposer une certaine quantité de phéromone sous la forme d’un point sur l’espace de recherche, proportionnellement à l’amélioration de la fonction objectif qu’elle découvre. Ces spots de phéromones peuvent être perçus par tous les autres membres de la population et diffusent dans l’environnement. Les fourmis sont attirées par chaque spot avec un intérêt variable selon sa distance et sa quantité de phéromone. Chaque fourmi se déplace en direction du centre de gravité du nuage des spots pondérés par l’intérêt de la fourmi pour ces spots.

Le canal direct inter-individuel est implémenté sous la forme d’envoi de messages d’une fourmi à une autre. Une fourmi artificielle recevant un message le stocke dans une pile, puis lit un message au hasard dans cette pile. Dans ce cas, l’information envoyée est la position de l’émetteur - un agent "fourmi" - ainsi que la valeur de la fonction objectif. Le receveur compare cette valeur avec la sienne et décide s’il doit ou non se déplacer dans la région de l’émetteur. La position finale est tirée au hasard dans une hyper-sphère ayant pour centre l’émetteur et pour rayon la distance maximum du receveur. Si la valeur de la fonction objectif du receveur est meilleure que celle de l’émetteur, alors le receveur envoie à son tour un message à un agent tiré au hasard dans la population. Ces deux canaux de communication sont faciles à combiner. Le déroulement de CIAC commence par une initialisation des paramètres, suivie, pour chaque fourmi, de la prise en compte du canal stigmergique, puis de la prise en compte du canal direct, jusqu’à ce qu’un critère d’arrêt soit atteint (amélioration trop faible, ou nombre maximum d’évaluations dépassé).

Réglage de l’algorithme

CIAC présente quatre paramètres nécessitant un réglage manuel : le nombre d’agents dans le système, un pourcentage de l’amplitude de l’espace de recherche, utilisé pour définir l’écart-type de la distribution de distances maximales de déplacement, la persistance $\rho $ de la phéromone, le nombre initial $\mu $ de messages. Après plusieurs essais utilisant un ensemble de 11 fonctions analytiques classiques, les valeurs par défaut des paramètres sont respectivement les suivantes : 100, 0.5, 0.1, 10. Les deux paramètres les plus sensibles sont ceux qui caractérisent les deux canaux de communication. On observe que $\rho $ définit une sensibilité aux optimums locaux et que $\mu $ est lié à une certaine forme "d’intensification" (c’est à dire d’exploration plus approfondie d’une région de l’espace de recherche). Un équilibre est donc nécessaire entre ces deux paramètres.

Un exemple de résultat

Pour illustrer le comportement de CIAC, nous avons choisi la fonction $B_2$ à deux dimensions qui possède un grand nombre d’optimums locaux et un minimum global de $B_2=0$ à $(x_1=0,x_2=0)$ (cf. Fig. [CIAC_res]a). Les deux canaux de communication jouent des rôles complémentaires. En effet le canal direct pilote une certaine intensification, en donnant une importance plus grande aux meilleurs spots et en rassemblant les agents, alors que le canal stigmergique encourage une forme de diversification en mémorisant plusieurs zones d’intérêt. Un résultat intéressant est que ces deux canaux de communication fonctionnent en synergie dans CIAC. En effet, en représentant l’écart-type en fonction du nombre d’évaluations (cf. Fig. [CIAC_res]b), on peut observer une certaine périodicité. Cela signifie que la population tend à se rassembler à un moment donné puis à se disperser dans un second temps, si on se réfère aux valeurs de la fonction objectif pour mesurer les distances entre les agents. En d’autres termes, le système alterne rapidement entre des phases d’intensification (écart-type faible) et de diversification (écart-type élevé). Ce mode de comportement d’auto-gestion de deux phases est émergent et ne peut être observé si les deux canaux ne sont pas présents.

Exemple de résultat obtenu avec CIAC sur la fonction $B_2$

Conclusion

Nous avons montré que le concept d’algorithme hétérarchique pouvait conduire à une nouvelle métaheuristique inspirée des colonies de fourmis en vue de l’optimisation de fonctions continues. CIAC est un algorithme hétérarchique, implémentant deux canaux de communication complémentaires, qui présente d’intéressantes propriétés émergentes, comme une auto-gestion de l’importance relative des deux canaux. Un réglage automatique des paramètres doit être mis au point avant de tester CIAC sur un large jeu de fonctions analytiques et de comparer son efficacité à celle des métaheuristiques concurrentes.

Références

Bilchev, G., Parmee, I.C. : The Ant Colony Metaphor for Searching Continuous Design Spaces. Lecture Notes in Computer Science 993 (1995) 25-39

Colorni, A., Dorigo, M., Maniezzo, V. : Distributed Optimization by Ant Colonies. Proceedings of ECAL’91 - European Conference on Artificial Life. Elsevier Publishing, Paris (december 1991) 134—142

Monmarché, N., Venturini, G., Slimane, M. : On how Pachycondyla apicalis ants suggest a new search algorithm. Future Generation Computer Systems 16 (2000) 937—946

Taillard, E.D., Gambardella, L., Gendreau, M., Potvin, J-Y. : Adaptive Memory Programming : A Unified View of Metaheuristics. European Journal of Operational Research 135 (1) 1—16

Wilson, E.O., H\ölldobler, B. : Dense Heterarchy and mass communication as the basis of organization in ant colonies. Trend in Ecology and Evolution 3 (1988) 65—68

Commentaires