CG Projet
Rim Boutkhil
Created on April 6, 2022
More creations to inspire you
C2C VOLUNTEER ORIENTATION
Presentation
LAYOUT ORGANIZATION
Presentation
TALK ABOUT DYS TEACHER-TEACHER
Presentation
TALK ABOUT DYS WITH TEACHER
Presentation
ESSENTIAL OILS PRESENTATION
Presentation
ANCIENT EGYPT FOR KIDS PRESENTATION
Presentation
CIRQUE DU SOLEIL
Presentation
Transcript
Complexité et
Etude expérimentale
Introduction
Plan de présentation
Un représentant de commerce peut vendre sa marchandise dans un certain nombre de villes, il doit donc
Introduction
C'est un problème d'optimisation qui consiste à déterminer, étant donné une liste de villes et les distances entre toutes les paires de villes, le plus court circuit qui passe par chaque ville une et une seule fois.
Probléme TSP
Travel Salesman Problem
Le problème du voyageur de commerce, ou TSP pour
1 => 2 => 4 => 3
10+25+30+15= 80
Travel Salesman Problem
Pour résoudre ce problème il existe 3 méthodes: Par algorithme d'approximation, par méthode heuristique ou par un solveur exact.
Nearest Neighboor
Pour un ensemble n de points ou villes, on choisit une ville au hasard, On ajoute les ville dans une liste ou l'on va construire le chemin. L'algorithme consiste donc à vérifier les distances de toutes les villes voisines à cette ville. Une fois la plus proche choisie, on l'ajoute à la liste, et on fait du même pour cette ville, et ainsi de suite, jusqu'en arriver à la ville de départ. Enfin, nous allons avoir une liste, avec toutes les villes, qui représente le plus petit chemin.
Nearest neighbor pour TSP
Ant colony optimization
Les algorithmes de colonies de fourmis sont des algorithmes inspirés du comportement des fourmis et qui constituent une méthode heuristique d’optimisation.
Optimisation par colonie de fourmis
Comportement des fourmis
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.
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 de phéromones, et donc celui utilisé par la colonie entiére.
Optimisation par colonie de fourmis pour TSP
Pour k=1 à m faire
Choisir une ville au hasard
Pour chaque ville non visitée i faire
Choisir une ville j, dans la liste des villes qui restent
Fin Pour
Déposer une piste sur le trajet (t)
Fin Pour
Evaporer les pistes
Etude expérimentale
Merci pour votre attention
Rime Boutkhil