Algorithme de colonies de fourmis

Images, Génie Informatique Spécialité : Automatique Par Marie SAWADOGO Intégration de l’impact environnemental, sociétal et économique du transport intermodal au sein des chaînes logistiques vertes : Optimisation multiobjectif par les colonies de fourmis Soutenue le 23 Novembre 2011, devant le jury composé de : Teodor Gabriel CRAINIC Université du Québec à Montréal Jin-Kao HAO Université d’Angers Didier ANCIAUX Université Paul Verlaine de Metz niversité Patrick BURLAT École Nationale Supérieure

problème d’ordonnancement de tâches 17 Mémoire à long terme 18 Avantages et inconvénients 18 2.4 La méthode GRASP 19 Avantages et inconvénients 20 2.5 Les algorithmes génétiques 20 Principe de l’algorithme génétique 21 Opérateurs de sélection 21 Opérateurs de variation 23 Avantages et inconvénients 24 2.6 Les algorithmes de colonies de fourmi 25 Principe de l’algorithme 26 Paramétrage 27 Généralisation et variantes 28 Avantages et Inconvénients 28 3. Stratégies de recherche 30 3.1 Intensification

………………..42 5.3.2 Recherche Tabou…………………………………………………………...…45 5.3.3. Algorithme de colonies de fourmis……………………………………...…...46 5.3.3.1. Introduction……………………………………………………..…46 5.3.3.2 Comportement………………………………………………..….….46 5.3.3.3 Pont binaire de Deneubourg………………………………..…….…49 5.3.3.4. Expérience de double pont binaire……………………….…….….50 5.3.3.5 Effet de la coupure d’une piste de phéromone…………….……….52 5.3.3.6 Voyageur de commerce : Algorithme Ant System (AS)….…….….53 5.3.3.7. Choix des paramètres………………………………………

27 5.1. L’optimisation par essaim particulaire 27 5.2. Les algorithmes à estimation de distribution 27 5.3. Extensions 28 Conclusion 29 Conclusion générale 30 Liste des figures Figure 1 : exemple du problème du sac à dos 8 Figure 2 : exemple du problème de tourné de véhicule 9 Figure 3 : Évolution d’une solution dans la méthode de descente 19 Figure 4 : Principe de fonctionnement d’un algorithme génetique 23 Introduction générale Les ingénieurs

Les fourmis (famille des formicidés ou Formicidae) sont des insectes sociaux formant des colonies, appelées fourmilières, parfois extrêmement complexes, contenant de quelques dizaines à plusieurs millions d’individus. Certaines espèces forment des supercolonies à plusieurs centaines de millions d’individus et à plus de 50 colonies qui peuvent contenir plus d'un million d'individus. Les fourmis sont classées dans l’ordre des hyménoptères, comme les guêpes et les abeilles. Les termites, parfois appelés

.................................................................................................... 6 DEFINITION : .............................................................................................................................. 6 ALGORITHME : .......................................................................................................................... 7 4.1. L’ALGORITHME DE METROPOLIS : ..................................................................................

d’atelier Résultats de complexité De nombreux travaux ont été effectués sur la complexité des problèmes d’atelier. Très peu de problèmes d’atelier peuvent être résolus en temps polynomial. Dans la quasi-totalité des cas polynomiaux, LB les algorithmes sont conçus pour construire des ordonnancements de durée Cmax . Les cas les plus connus sont les problèmes à deux machines ou préemptifs. Nous allons résumer les principaux résultats connus à ce jour. Nous nous focaliserons sur le délai total

opérateurs de croisement et de mutation sont appliqués et une nouvelle population est créée le nombre d’itération est le nombre de génération que l’oon veux créér Colonies de fourmis « lancer » des fourmis, et à les laisser élaborer pas à pas la solution (construction progressive de solutions.) Afin de ne pas revenir sur ses pas, une fourmi tient à jour une liste Tabou, qui contient la liste des villes déjà visitées Descente Partir d'une solution existante une solution dans le voisinage et

combinatoire). On répondait à la question : combien y a-t-il d'objets ayant certaines propriétés ? • Enfin avec l'informatique, on traite des Problèmes combinatoires. On cherche à déterminer un objet ayant certaines propriétés, en définissant un algorithme calculant un coût. 16/03/2022 Optimisation combinatoire 5Optimisation: Terminologie • L’ensemble D de solutions réalisables: c’est l’espace de recherche (domaine réalisable). • A chaque solution est associé un réel, sa qualité, calculable par une

4e Conférence Francophone de MOdélisation et SIMulation «Organisation et Conduite d’Activités dans l’Industrie et les Services» MOSIM’03 – du 23 au 25 avril 2003 - Toulouse (France) UN ALGORITHME EVOLUTIONNISTE POUR LE PROBLEME DE TOURNEES SELECTIVES AVEC CONTRAINTES DE FENETRES DE TEMPS N. Hayari, M.-A. Manier, C. Bloch, A. El Moudni Laboratoire Systèmes et Transports UTBM, site de Belfort 90010 Belfort cedex Tel : (33) 3 84 58 33 97 Fax : (33) 3 84 58 33 42 Mél : (noureddine.hayari, marie-ange