Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Colonies fourmis 200605 rapport

Optimisation par colonies de fourmis COSTANZO Andrea LUONG Thé Van mai MARILL Guillaume CTable des matières Introduction Pourquoi les fourmis Relation avec l ? informatique Comportement de la fourmi Optimisation par colonie de fourmis Historique Similarités et di ?érences avec les fourmis réelles Dréo Points communs Di ?érences Expériences Pont binaire de Deneubourg Dréo Expérience du double pont binaire Dorigo E ?et de la coupure d ? une piste de phéromone Dréo Conclusions Voyageur de commerce Algorithme Ant System AS Introduction Dé ?nitions Ant System Conventions Choix d ? implementation Fonctionnement de l ? algorithme Complexité Variantes Dorigo Choix des paramètres Considérations générales Dréo Résultats expérimentaux Les fourmis élitistes Résumé Performances de l ? algorithme Ant System Présentation générale Résultats sans fourmis élitistes Résultats avec fourmis élitistes Applications sur d ? autres tailles de données Un plus petit problème et un plus grand Conclusion des expériences CTABLE DES MATIÈRES Améliorations plus récentes de Ant System Évolution des algos TSP Nouvelles approches Introduction Ant-Q Dorigo Ant Colony System ACS Dorigo Max-Min Ant System MMAS Dorigo Optimisation des tables de routage Introduction Principe de l ? algorithme Dréo Les fourmis du net Mecanisme de antNet Comparaison aux algorithmes classiques Expériences Resultats Conclusion CChapitre Introduction Pourquoi les fourmis Nous présenterons dans notre travail d ? étude des nouvelles méta-heuristiques permettant de résoudre des problèmes tels que le voyageur de commerce en s ? inspirant du comportement social des fourmis Le comportement des fourmis est un comportement collectif Chaque fourmi a pour priorité le bien être de la communauté Chaque individu de la colonie est à priori indépendant et n ? est pas supervisé d ? une manière ou d ? une autre Ce concept est appellé Hétérarchie s ? opposant à la Hiérarchie Dréo chaque individu est aidé par la communauté dans son évolution et en retour il aide au bon fonctionnement de celle-ci La colonie est donc auto-controlé par le biais de mécanismes relativement simples à étudier Relation avec l ? informatique En observant une colonie de fourmis à la recherche de nourriture dans les environs du nid on s ? aperçoit qu ? elle résoud des problèmes tels que celui de la recherche du plus court chemin Les fourmis résolvent des problèmes complexes par des mécanismes assez simples a modéliser Il est ainsi assez simple de simuler leur comportement par des algorithmes Comportement de la fourmi Les pistes de phéromones En marchant du nid à la source de nourriture et vice-versa ce qui dans un premier temps se fait essentiellement de façon aléatoire les fourmis déposent au passage sur le sol une substance odorante appelée phéromones Cette substance permet ainsi donc de créer une piste chimique sur laquelle les fourmis s ? y retrouvent En e ?et d ? autres fourmis peuvent détecter les phéromones gr? ce à des capteurs sur leurs antennes Les phéromones ont un rôle de marqueur de chemin quand les fourmis choisissent leur chemin elles ont tendance à choisir la piste qui porte la plus forte concentration