CG Projet

Probléme du voyageur de commerce TSP

Complexité et

graphes

Avril, 2022

A. Chanson et A. Farouzi

Tests

Nearest Neighoor

Etude expérimentale

Probléme TSP

Introduction

L’optimisation par colonie de fourmis

Plan de présentation

Conclusion

Avril, 2022

Un représentant de commerce peut vendre sa marchandise dans un certain nombre de villes, il doit donc

planifier sa tournée de manière à passer par toutes les villes en voyageant au total le moins possible

Introduction

+ Info

Avril, 2022

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.

Travel Salesman Problem

Probléme TSP

Travel Salesman Problem

Le problème du voyageur de commerce, ou TSP pour

Traveling-Salesman-Problem, consiste, pour un graphe donné,

de déterminer un cycle hamiltonien dont la longueur est

minimale.

1 => 2 => 4 => 3

10+25+30+15= 80

Travel Salesman Problem

Nous avons n points, qui sont les villes, avec un ensemble de distances entre toutes les villes. Il s'agit donc de parcourir tout les circuit possible pour trouver enfin le circuit avec la longueur minimale.
Pour résoudre ce problème il existe 3 méthodes: Par algorithme d'approximation, par méthode heuristique ou par un solveur exact.

Plus proche voisin

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

Optimisation par colonie de fourmis

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.

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.

Optimisation par colonie de fourmis

+ Info

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

L’algorithme optimisant le problème du voyageur de commerce :

1) une fourmi choisit un trajet, et trace une piste de phéromone.

2) l’ensemble 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.

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

Avril, 2022

Rime Boutkhil

Houda Birouk

Dounia Ait Ali Oumghar

Riane Smili

CG Projet

More creations to inspire you

C2C VOLUNTEER ORIENTATION

LAYOUT ORGANIZATION

TALK ABOUT DYS TEACHER-TEACHER

TALK ABOUT DYS WITH TEACHER

ESSENTIAL OILS PRESENTATION

ANCIENT EGYPT FOR KIDS PRESENTATION

CIRQUE DU SOLEIL

Transcript