Algorithme de colonies de fourmis

Les algorithmes de colonies de fourmis sont des algorithmes inspirés du comportement des fourmis et qui forment une famille de métaheuristiques d'optimisation.


Catégories :

Métaheuristique - Sciences de la complexité - Fourmi

Recherche sur Google Images :


Source image : kimonte.com
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • http ://www. eyrolles. com/Chapitres/9782212113686/chap4_Dreo. pdf - Pages identiques Application d'un algorithme `a colonie de fourmis `a la d´etection... avons introduit dans le concept des algorithmes `a colonie de fourmis...... Ici, nous utilisons un algorithme `a colonies de fourmis dont la capacité `a... (source : eyrolles)

Les algorithmes de colonies de fourmis sont des algorithmes inspirés du comportement des fourmis et qui forment une famille de métaheuristiques d'optimisation.

Originellement proposé par Marco Dorigo et al. dans les années 1990[1], [2], 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 «Ant Colony Optimization» (abrégé ACO). Les spécialistes réservent ce terme à un type spécifique 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 : algorithmes de colonies de fourmis, optimisation par colonies de fourmis, fourmis artificielles, ou diverses combinaisons de ces variantes.

Certains comportements des fourmis sont à l'origine d'algorithmes d'optimisation (ici, des fourmis légionnaires du genre Dorylus).

Origine

L'idée originale provient de l'observation de l'exploitation des ressources alimentaires chez les fourmis. En effet, celles-ci, quoiqu'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.

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 quatre chemins envisageables, 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 perdent leur piste de phéromones.

Des biologistes ont ainsi observé, dans une série d'expériences menées à partir de 1989[3], [4], 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 :

  1. une fourmi (appelée «éclaireuse») parcourt plus ou moins au hasard l'environnement autour de la colonie ;
  2. 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 ;
  3. ces phéromones étant attractives, les fourmis passant à proximité vont avoir tendance à suivre, de façon plus ou moins directe, cette piste ;
  4. en revenant au nid, ces mêmes fourmis vont renforcer la piste ;
  5. si deux pistes sont envisageables 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 ;
  6. la piste courte sera par conséquent de plus en plus renforcée, et par conséquent de plus en plus attractive ;
  7. la longue piste, elle , finira par disparaître, les phéromones étant volatiles ;
  8. à terme, la totalité des fourmis a par conséquent déterminé et «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». L'information échangée a une portée locale, seule une fourmi localisée à l'endroit où les phéromones ont été déposées y a accès. Ce dispositif porte le nom de «stigmergie», et se retrouve chez plusieurs animaux sociaux (il a surtout été étudié dans le cas de la construction de piliers dans les nids de termites).

Le mécanisme servant à résoudre un problème trop complexe pour être abordé par des fourmis seules est un bon exemple de dispositif auto-organisé. Ce dispositif 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 dispositif de s'emballer). Théoriquement, si la quantité de phéromone restait semblable au cours du temps sur l'ensemble des branches, aucune piste ne serait choisie. Or, du fait des rétroactions, une faible variation sur une branche va être augmenté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 constitué des «meilleures» branches.

Exemple : le «système fourmi»

Le premier algorithme de colonies de fourmis proposé est nommé le Ant system[5] (système fourmi). Il vise surtout à résoudre le problème du voyageur de commerce, où l'objectif est de trouver le plus court chemin servant à relier un ensemble de villes.

L'algorithme général est assez simple, et repose sur un ensemble de fourmis, chacune parcourant un trajet parmi ceux envisageables. À chaque étape, la fourmi choisit de passer d'une ville à une autre selon quelques règles :

  1. elle ne peut visiter qu'une fois chaque ville ;
  2. plus une ville est loin, moins elle a de chance d'être choisie (c'est la «visibilité»)  ;
  3. 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 ;
  4. une fois son trajet terminé, la fourmi dépose, sur la totalité des arêtes parcourues, plus de phéromones si le trajet est court ;
  5. 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 choisit un trajet, et trace une piste de phéromone. 2) la totalité des fourmis parcourt un certain nombre de trajets, chaque fourmi déposant une quantité de phéromone proportionnelle à la qualité du parcours. 3) chaque arê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 nommée «règle aléatoire de transition proportionnelle», et est écrite mathématiquement sous la forme suivante :

Jik est la liste des déplacements envisageables pour une fourmi k quand elle se trouve sur une ville i, ηij la visibilité, qui est égale à l'inverse de la distance de deux villes i et j (1/dij) 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.

Une fois la tournée des villes effectuée, une fourmi k dépose une quantité \Delta\tauˆk_{ij} de phéromone sur chaque arête de son parcours :


\Delta\tau_{ij}ˆ{k}(t)=\left\{ \begin{matrix}
\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.

Tk (t) est la tournée faite par la fourmi k à l'itération t, Lk (t) la longueur du trajet et Q 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 :

ρτij (t)

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.


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

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

Principales variantes

L'algorithme de colonies de fourmis a été à l'origine en particulier utilisé pour produire des solutions quasi-optimales au problème du voyageur de commerce, puis, d'une façon plus générale, 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[réf.  nécessaire] ou encore le traitement d'image[réf.  nécessaire].

Le cadre «ACO»

Une partie des algorithmes (surtout ceux conçus par M. Dorigo et ses collègues) sont désormais 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, avec 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) [6], où seules les meilleures fourmis tracent des pistes et où le dépôt de phéromones est limité par une limite supérieure (empêchant une piste d'être trop renforcée) et une limite 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 surtout une convergence prématurée.

L'autre variante la plus connue est le Ant Colony System (ACS) [7], 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 envisageable, 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 majorité des métaheuristiques, il est particulièrement complexe d'estimer théoriquement la vitesse de convergence.

En 2004, Zlochin et ses collègues ont montré[8] 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 complexe

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.

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 fluctuer selon les auteurs et les usages.

D'une façon particulièrement générale, les algorithmes de colonies de fourmis sont reconnus 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 qui ont précédé 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 précisément son aspect constructif. En effet, dans les problèmes combinatoires, il est envisageable 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 indispensable qu'une fourmi parcoure effectivement le chemin le plus court : ce dernier 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 dispositifs biologiques a donné lieu au concept d'«intelligence en essaim», qui est un cadre particulièrement général, dans lequel s'inscrivent les algorithmes de colonies de fourmis.

Algorithmes stigmergiques

On observe en pratique qu'la plupart 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»[9].

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.

Applications

Problème du sac à dos. Les fourmis en nombre limité privilégient la goutte de miel, en plus petite quantité mais plus intéressante que l'eau sucrée, plus abondante mais moins nutritive.

Les variantes combinatoires peuvent avoir un avantage, comparé 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 assez flexible aux changements. Ceci semble être intéressant pour le routage réseau[10].

Les algorithmes de colonies de fourmis ont été appliqués à la plupart de problèmes d'optimisation combinatoire, allant de l'assignement quadratique au replis de protéine ou au routage de véhicules. Comme énormément de métaheuristiques, l'algorithme de base a été adapté aux problèmes dynamiques, en variables réelles, aux problèmes stochastiques, multi-objectifs ou aux implémentations parallèles, etc.

Historique

Chronologie des algorithmes de colonies de fourmis.

Sources

Notes et références

  1. 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.
  2. M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.
  3. S. 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
  4. 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
  5. M. 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.
  6. T. Stützle et H. H. Hoos, MAX MIN Ant System, Future Generation Computer Systems, volume 16, pages 889-914, 2000
  7. 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.
  8. M. Zlochin, M. Birattari, N. Meuleau, et M. Dorigo, Model-based search for combinatorial optimization : A critical survey, Annals of Operations Research, vol. 131, pp. 373-395, 2004.
  9. A. Ajith; G. Crina; R. Vitorino (éditeurs), Stigmergic Optimization, Studies in Computational Intelligence, volume 31, 299 pages, 2006. ISBN 978-3-540-34689-0
  10. K. M. Sim, W. H. Sun, Ant colony optimization for routing and load-balancing : survey and new directions, IEEE Transactions on Systems, Man and Cybernetics, Part A, volume 33, numéro 5, pages 560-572, 2003
  11. P. -P. Grassé, La reconstruction du nid et les coordinations inter-individuelles chez Belicositermes natalensis et Cubitermes sp. La théorie de la Stigmergie : Essai d'interprétation du comportement des termites constructeurs, Insectes Sociaux, numéro 6, p. 41-80, 1959.
  12. J. L. Denebourg, J. M. Pasteels et J. C. Verhæghe, Probabilistic Behaviour in Ants : a Strategy of Errors?, Journal of Theoretical Biology, numéro 105, 1983.
  13. 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.
  14. M. Ebling, M. Di Loreto, M. Presley, F. Wieland, et D. Jefferson, An Ant Foraging Model Implemented on the Time Warp Operating System, Proceedings of the SCS Multiconference on Distributed Simulation, 1989
  15. Dorigo M., V. Maniezzo et A. Colorni, Positive feedback as a search strategy, rapport technique numéro 91-016, Dip. Elettronica, Politecnico di Milano, Italy, 1991
  16. G. Bilchev et I. C. Parmee, The Ant Colony Metaphor for Searching Continuous Design Spaces, Proceedings of the AISB Workshop on Evolutionary Computation. Terence C. Fogarty (éditeurs), Evolutionary Computing Springer-Verlag, pages 25-39, avril 1995.
  17. R. Schoonderwœrd, O. Holland, J. Bruten et L. Rothkrantz, Ant-based load balancing in telecommunication networks, Adaptive Behaviour, volume 5, numéro 2, pages 169-207, 1997
  18. A. Martinoli, M. Yamamoto, et F. Mondada, On the modelling of bioinspired collective experiments with real robots, Fourth European Conference on Artificial Life ECAL-97, Brighton, UK, juillet 1997.
  19. M. Dorigo, ANTS'98, From Ant Colonies to Artificial Ants : First International Workshop on Ant Colony Optimization, ANTS 98, Bruxelles, Belgique, octobre 1998.
  20. T. Stützle, Parallelization Strategies for Ant Colony Optimization, Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, Springer-Verlag, volume 1498, pages 722-731, 1998.
  21. É. Bonabeau, M. Dorigo et G. Theraulaz, Swarm intelligence, Oxford University Press, 1999.
  22. M. Dorigo, G. Di Caro et T. Stützle, special issue on "Ant Algorithms", Future Generation Computer Systems, volume 16, numéro 8, 2000
  23. W. J. Gutjahr, A graph-based Ant System and its convergence, Future Generation Computer Systems, volume 16, pages 873-888, 2000.
  24. S. Iredi, D. Merkle et M. Middendorf, Bi-Criterion Optimization with Multi Colony Ant Algorithms, Evolutionary Multi-Criterion Optimization, First International Conference (EMO'01), Zurich, Springer Verlag, pages 359-372, 2001.
  25. L. Bianchi, L. M. Gambardella et M. Dorigo, An ant colony optimization approach to the probabilistic traveling salesman problem, PPSN-VII, Seventh International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Springer Verlag, Berlin, Allemagne, 2002.

Voir aussi

Liens externes

Goldenwiki 2.png

Recherche sur Amazone (livres) :



Principaux mots-clés de cette page : fourmis - algorithmes - ant - colonies - dorigo - piste - system - phéromone - problèmes - chemins - colony - optimization - volume - comportement - première - optimisation - source - numéro - solutions - collègues - métaheuristiques - nourriture - court - villes - itération - intelligence - applications - recherche - terme - aco -

Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Algorithme_de_colonies_de_fourmis.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 27/10/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu