Algorithme de colonies de fourmis

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Les algorithmes de colonies de fourmis forment une famille de métaheuristiques d'optimisation, qui s'inspirent du comportement collectif des fourmis.

Proposé par Dorigo et al. dans les années 90 [CDM91,Dor92], pour la recherche de chemins optimaux dans un graphe, l'algorithme original s'inspire du comportement des fourmis recherchant un chemin allant de leur colonie vers une source de nourriture. L'idée originale est depuis déclinée pour résoudre une classe plus large de problèmes.

En anglais, le terme consacré est « Ant Colony Optimization » (abbregé ACO), traduit diversmeent en français : algorithmes de colonies de fourmis, optimisation par colonies de fourmis, fourmis artificielles, ou diverses combinaisons de ces variantes.

Les comportements de déplacement collectif des fourmis ont inspiré des algorithmes d'optimisation.

Sommaire

1 Inspiration
2 Exemple : le « système fourmi »
3 Variantes
4 Définition
5 Références
- 5.1 Sources
- 5.2 Voir aussi

[modifier] Inspiration

L'idée originale est issue de l'observation du comportement collectif d'exploitation de la nourriture chez les fourmis. En effet, celles-ci, bien qu'ayant individuellement des capacités cognitives très limitées, sont capables collectivement de résoudre le problème de la découverte du plus court chemin entre une source de nourriture et leur nid.

1) la première fourmi trouve la source de nourriture (F), via un chemin quelconque (a), puis revient au nid (N) en laissant derrière elle une piste de phéromone (b). 2) les fourmis empruntent indifféremment les 4 chemins possibles, mais le renforcement de la piste rend plus attractif le chemin le plus court. 3) les fourmis empruntent le chemin le plus court, les portions longues des autres chemins voient la piste de phéromones s'évaporer.

Des biologistes ont ainsi observé, dans une série d'expériences menées à partir de 1989, qu'une colonie de fourmis ayant le choix entre deux chemins d'inégale longueur menant à une source de nourriture avait tendance à exploiter 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 piste longue ;
la piste courte sera donc de plus en plus renforcée, et donc de plus en plus attractive ;
la piste longue, elle, finira par disparaître, les phéromones étant plus ou moins volatiles.
à terme, l'ensemble des fourmis a donc « choisi » la piste la plus courte.

Les fourmis utilisent l'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 ». 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 piste attire d'autres fourmis qui vont la renforcer à leur tour) et négatives (l'évaporation de la piste 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. Ce système est à la limite d'un système chaotique, l'état où aucune branche n'est plus marquée qu'une autre est un point instable, les états où une branche est choisie sont des points stables.

De tels systèmes trouvent leur intérêt dans l'étude des systèmes complexes (à travers les systèmes massivement parallèles), et dans leur lien avec l'intelligence artificielle [MoMa88].

[modifier] Exemple : le « système fourmi »

Le premier algorithme de colonies de fourmis proposé est appelé le Ant system (système fourmi). Il vise à résoudre le problème du voyageur de commerce, où le but est de trouver le chemin le plus court 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'arrête entre deux ville est grande, plus le trajet aura de chance d'être choisi ;
une fois son trajet terminé, la fourmi dépose, sur l'ensemble des arrêtes parcourues, une piste de phéromone, dont l'intensité augmente si le trajet est court ;
les pistes de phéromones s'évaporent à chaque itération.

L'algorithme « Ant System » optimisant le problème du voyageur de commerce : 1) une fourmi choisi un trajet possible, et y dépose une piste de phéromone. 2) l'ensemble des fourmis va parcourir un certain nombre de trajets, chaque fourmi déposant une quantité de phéromone proportionnelle à la qualité du parcours. 3) chaque arrête du meilleur chemin est plus renforcée que les autres. 4) l'évaporation fait disparaître les mauvaises solutions.

La règle de déplacement est appelée « règle aléatoire de transition proportionnelle », et est écrite mathématiquement sous la forme suivante :

$p_{ij}^{k}\left(t\right)=\left\{ \begin{matrix}{ll} \frac{\tau_{ij}\left(t\right)^{\alpha}\cdot\eta_{ij}^{\beta}}{{\scriptscriptstyle \sum_{l\in J_{i}^{k}}}\tau_{il}\left(t\right)^{\alpha}\cdot\eta_{ij}^{\beta}} & \textrm{si}\, j\in J_{i}^{k}\\ 0 & \textrm{si}\, j\notin J_{i}^{k}\end{matrix}\right.$

Où J_i^k est la liste des mouvements possibles pour une fourmi k lorsqu'elle se trouve sur une ville i, η_ij la visibilité, qui est égale à l'inverse de la distance entre deux villes i et j (1/d_ij) et τ_ij(t) l'intensité de la piste à une itération donnée t. 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.

Il est nécessaire de régler α et β en faisant un compromis entre une intensification trop grande (α=0) ou une diversification trop poussée (β=0).

Une fois la tournée des villes effectuée, une fourmi dépose une certaine quantité de phéromone sur chaque arête de son parcours :

$\Delta\tau_{ij}^{k}(t)=\left\{ \begin{matrix}{ll} \frac{Q}{L^{k}(t)} & \textrm{si}\,(i,j)\in T^{k}(t)\\ 0 & \textrm{si}\,(i,j)\notin T^{k}(t)\end{matrix}\right.$

Où T^k(t) est la tournée parcourue par la fourmi k à l'itération t, L^k(t) la longueur du trajet effectué et Q un paramètre de réglage.

À la fin de chaque itération de l'algorithme, les pistes déposées par les fourmis s'évaporent :

$\tau_{ij}(t+1)=(1-\rho) \tau_{ij}(t) + \sum_{k=1}^{m}\Delta\tau_{ij}^{k}(t)$

Où m est le nombre de fourmis utilisé pour l'itération t et ρ un paramètre de réglage.

[modifier] Variantes

L'algorithme de colonies de fourmis a été à l'origine principalement 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 depuis ses débuts que son emploi se généralise à plusieurs domaines, depuis l'optimisation continue jusqu'à la classification ou encore le traitement d'image.

Une variante efficace du Ant System est le Max-Min Ant System, où les dépots de phéromones sont limités 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é à n'importe quelle solution). Cet algorithme atteint de meilleurs résultats que l'original, et évite notamment une convergence trop précoce.

Les variantes combinatoires peuvent avoir un avantage, par rapport aux autres métaheuristiques, dans le cas où le graphe étudié peut changer dynamiquement au cours de l'exécution : la colonie de fourmis s'adaptera de façon relativement flexible aux changements. Ceci semble être intéressant pour le routage réseau (cas de l'algorithme AntNet par exemple).

Il est possible, pour certaines versions, de prouver que l'algorithme est convergent (au sens mathématique du terme).

[modifier] Définition

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éplacant sur l'espace de recherche. Les fourmis marquent les meilleures solutions, et tiennent compte des marquages précédents pour effectuer leurs recherches.

Avec un algorithme de colonies de fourmis, le plus court chemin, au sein d'un graphe, entre deux points A et B, est construit à partir de la combinaison de plusieurs chemins.

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 évaluée directement. 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.

On observe en pratique qu'un grand nombre d'algorithmes se réclament d'une inspiration « colonies fourmis », sans toujours partager un large fond commun avec l'optimisation par colonies de fourmis canonique (en anglais Ant Colony Optimisation, abbrégé ACO). En pratique, l'utilisation d'un échange d'informations entre fourmis via le « dépot » d'une « piste de phéromone » 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 ».

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ée 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.

[modifier] Références

[modifier] Sources

(en) [MoMa88] F. Moyson, B. Manderick, The collective behaviour of Ants : an Example of Self-Organization in Massive Parallelism, Actes de AAAI Spring Symposium on Parallel Models of Intelligence, Stanford, Californie, 1988.
(en) [CDM91] A. 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.
(it) [Dor92] M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.
(en) [BDT99] Éric Bonabeau, Marco Dorigo et Guy Theraulaz, Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press, 1999. ISBN 0195131592
(fr) [DPT+03] Johann Dréo, Alain Petrowski, Éric Taillard, Patrick Siarry, Métaheuristiques pour l'optimisation difficile, Français, Éd. Eyrolles, Paris, septembre 2003, Broché, 356 pages, ISBN 2-212-11368-4 extrait concernant les algorithmes de colonies de fourmis.