Problème de voyageur de commerce bi-objectif et Algorithme de colonies

By 27 February 2014

PROBLEME DE VOYAGEUR DE COMMERCE BI-OBJECTIF – CHAPITRE III :

II. INTRODUCTION :
III. REPRESENTATION DU PVC BI-OBJECTIF :
III.1 OBJECTIF :
IV. COMPLEXITE
V. ALGORITHME GENETIQUE :
V. ALGORITHME DE COLONIES DE FOURMIS :
VI. CONCLUSION

Introduction :

Le problème du voyageur de commerce, étudié depuis le 19em siècle, est l’un des plus connus dans le domaine de la recherche opérationnelle. Jouez à trouver le meilleur parcours possible… et découvrez différentes méthodes informatiques proposées pour résoudre ce problème.

C’est déjà sous forme de jeu que William Rowan Hamilton a posé pour la première fois ce problème, dès 1859. Sous sa forme la plus classique, son énoncé est le suivant : « Un voyageur de commerce doit visiter une et une seule fois un nombre fini de villes et revenir à son point d’origine. Trouvez l’ordre de visite des villes qui minimise la distance totale parcourue par le voyageur ». Ce problème d’optimisation combinatoire appartient à la classe des problèmes NP-Complets.

Les domaines d’application sont nombreux : problèmes de logistique, de transport aussi bien de marchandises que de personnes, et plus largement toutes sortes de problèmes d’ordonnancement. Certains problèmes rencontrés dans l’industrie se modélisent sous la forme d’un problème de voyageur de commerce, comme l’optimisation de trajectoires de machines outils : comment percer plusieurs points sur une carte électronique le plus vite possible ?

II. Représentation du PVC bi-objectif :

Le problème du voyageur de commerce bi-objectif peut être modélisé à l’aide d’un graphe G=(X,U) constitué d’un ensemble de sommets X={1…..n} et d’un ensemble d’arêtes U={(xi,xj)|xi,xj ∈X}. Chaque sommet représente une ville, une arête symbolise le passage d’une ville à une autre, et on lui associe un coût C(i,j) pouvant représenter une distance ou un temps de parcours. À chaque objectif correspond donc une matrice de coûts.

Pour résoudre notre problème de voyageur de commerce bi-objectif on peut le transformer en deux problèmes mono-objectif. La meilleure solution est le compromis de deux solutions.

Représentation du PVC bi-objectif

Où les poids Représentation du PVC bi-objectif et k le nombre d’objectifs de notre problème qu’est k=2.

II.1 Objectif :

– Minimisation de la distance.

– Minimisation de temps.

On prend le cas ‘un voyageur de commerce souhaite parcourir toute les villes, le chemin idéale est celle de temps et de distance minimal, ce chemin n’existe pas donc on identifier le meilleur compromis.

Relation entre la Distance et le Temps
Figure III.1: Relation entre la Distance et le Temps

Exemple : Soit le graphe suit :

Exemple de graphe à 4 sommets
Figure III.2 : Exemple de graphe à 4 sommets.

Résoudre le problème du voyageur de commerce revient à trouver dans ce graphe dans un cycle passant par tous les sommets une seule fois (un tel cycle est dit « hamiltonien ») et qui soit de longueur minimale et d’un temps minimum. Dans se graphe complet les coûts à l’intérieur des carrés en rouge représente le temps et les coûts en noire représente la distance.

Le poids de première objectif « le temps » est 1 = 0,7 et le poids de deuxième « la distance » est 2 = 0,3 , Pour le graphe ci-dessus, la première solution serait le cycle 1, 2, 3, 4 et 1, correspondant à une distance totale de 23 et la deuxième serait le cycle 1, 3, 4, 2 et 1 correspondant à un temps totale de 21, Cette solution est optimale.

Comme il existe une arête entre chaque paire de sommets, on dit que ce graphe est « complet ». Pour tout graphe, une matrice de coût peut être établie. En lignes figurent les sommets d’origine des arêtes et en colonnes les sommets de destination ; le coût sur chaque arête apparaît à l’intersection de la ligne et de la colonne correspondantes. Pour notre exemple, cette matrice est la suivante :

Problème de voyageur de commerce bi-objectif

Dans cet exemple, le graphe est « non orienté », c’est-à-dire qu’une arête peut être parcourue indifféremment dans les deux sens, cela explique que la matrice soit symétrique. Cette symétrie n’est pas forcément respectée dans le cas d’un graphe orienté. Il existe alors deux catégories de problèmes : le cas symétrique (le poids de l’arc du sommet X vers Y est égal au poids de l’arc du sommet Y vers X) et le cas asymétrique (le poids de l’arc du sommet X vers Y peut être différent du poids de l’arc du sommet Y vers X).

III. Complexité

Ce problème est un représentant de la classe des problèmes NP-complets. L’existence d’un algorithme de complexit polynomiale reste inconnue. Un calcul rapide de la complexité montre qu’elle est en Complexité où n est le nombre de villes. En supposant que le temps pour évaluer un trajet est de 1µ ѕ, le tableau montre l’explosion combinatoire du PCV.

Nombre de possibilités de chemins et temps de calcul en fonction du nombre de villes (on suppose qu’il faut 1 µ ѕ pour évaluer une possibilité). [12]

possibilités de chemins

IV. Algorithme génétique : [3]

Les algorithmes génétiques (AGs) sont des algorithmes d’optimisation stochastiques itérés fondés sur les mécanismes de la sélection naturelle et de la génétique.

Les AGs ont été initialement développés par John Holland (1975). C’est au livre de Goldberg (1989) que nous devons leur popularisation. Leurs champs d’application sont très vastes. Outre l’économie (minimisation du risque des portefeuilles), ils sont utilisés pour l’optimisation de fonctions, en finance, en théorie du contrôle optimal (recherche opérationnelle), ou encore en théorie des jeux répétés et différentiels (en l’occurrence dans les jeux évolutionnaires et le dilemme du prisonnier) et la recherche d’information (Google) ainsi que la recherche des plus courts chemins en théorie des graphes (routages Internet ou GPS). La raison de ce grand nombre d’applications est claire : simplicité et efficacité. Bien sûr, d’autres techniques d’exploration stochastiques existent, la méthode de Monte-Carlo peut-être considéré comme un concept similaire.

Principe de fonctionnement :

Nous partons avec une population de solutions potentielles (chromosomes) initiales arbitrairement choisies.

Nous évaluons leur performance (fitness) relative

Sur la base de ces performances, nous créons une nouvelle population de solutions potentielles en utilisant des opérateurs évolutionnaires simples : la sélection, le croisement et la mutation.

Nous recommençons ce cycle jusqu’à ce que nous trouvions une solution satisfaisante.

V. Algorithme de colonies de fourmis : [13]

Les algorithmes s’inspirant des colonies de fourmis sont assez récents dans le domaine de l’optimisation. Ils ne sont pas encore en mesure de rivaliser avec les meilleurs algorithmes classiques, mais leurs résultats ont vite progressé. Nous présentons ici le principe d’un algorithme de fourmis appliqué à notre problème de voyageur de commerce, mais sans entrer dans les détails.

Le principe de l’algorithme s’appuie sur l’aptitude des fourmis à éviter les obstacles et à toujours trouver un plus court chemin entre deux points. Lorsque plusieurs fourmis effectuent des allers-retours entre deux points A et B, pour rapporter de la nourriture par exemple, elles se mettent au fur et à mesure à emprunter le plus court chemin entre A et B. Ce phénomène est dû aux phéromones que chaque fourmi sécrète. En effet, chaque fourmi dépose une certaine quantité de phéromones sur le chemin qu’elle emprunte. Et une fourmi a tendance à choisir le chemin qui possède la plus grande quantité de phéromones. Un autre facteur est à prendre en compte : l’atténuation, qui exprime le fait que la quantité de phéromones sur chaque arête diminue dans le temps.

Voici un exemple schématique avec deux chemins possibles entre A et B, évitant un obstacle :

de chemins pour évitant un obstacle
Figure III.3: de chemins pour évitant un obstacle.

Comme le chemin 1 est plus court que le chemin 2, une fourmi qui emprunte le chemin 1 fera plus d’allers-retours en un même temps qu’une fourmi empruntant le chemin 2. Elle laissera donc plus de phéromones sur le chemin 1 que l’autre fourmi sur le chemin 2. Ainsi, les autres fourmis emprunteront plus souvent le chemin 1 que le chemin 2, et laisseront encore plus de phéromones sur le chemin 1. La différence sera renforcée à cause de l’atténuation. À terme, les fourmis tendront à ne passer que par le chemin 1.

Ce principe peut être repris pour le problème du voyageur de commerce. Il suffit de simuler un certain nombre de fourmis et leurs déplacements dans le graphe. Il faut imposer un sommet de départ qui sera aussi celui du retour pour toutes les fourmis, et les contraindre à passer par tous les sommets. Chaque fourmi laissera à son passage sur chaque arête une quantité de phéromones dépendant du poids de l’arête (plus le poids est petit, plus la quantité de phéromones laissée par la fourmi sera forte). Lorsqu’une fourmi se trouve à un sommet, elle partira vers un sommet qu’elle n’a pas encore visité avec une probabilité d’autant plus élevée que l’arête qui les relie possède le plus grand taux de phéromones. Les différents paramètres (nombre de fourmis, taux de phéromones, atténuation) peuvent être ajustés pour améliorer l’efficacité de l’algorithme.

VI. Conclusion :

Le problème du voyageur de commerce est toujours d’actualité dans la recherche en informatique, étant donné le nombre important de problèmes réels auxquels il correspond. Les problèmes dérivés et les extensions en sont très nombreux. Par exemple, des fenêtres de temps peuvent y être ajoutées.

Ce concept consiste à imposer des contraintes de temps pour la traversée de chaque sommet. Autre exemple, il peut y avoir plusieurs voyageurs de commerce partant d’un même sommet, ou de sommets différents. Il suffit alors de considérer que les voyageurs de commerce sont des véhicules pour arriver à des problèmes de tournées de véhicules : étant donnée une flotte de véhicules, le problème consiste à déterminer les trajets de chacun pour livrer à moindre coût des clients en marchandise (chaque client est représenté par un sommet dans le graphe). Le nombre de véhicules peut être fixe ou non, les capacités des véhicules peuvent être les mêmes ou non, des fenêtres de temps peuvent être définies… Pour chacune de ces variantes, de nouvelles méthodes peuvent être explorées.

La Résolution du Problème de Voyageurs de Commerce Bi-Objectifs par La Métaheuristique d’Optimisation par Colonie de Fourmis Artificielles
Présenté pour l’obtention du diplôme de MASTER Option Réseaux et Multimédia
Département de Mathématique et d’Informatique