Remerciez-le!

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

الوطنية للمهندسين بتونس لمدرسة ا Ecole nationale d’ingénieurs de Tunis ﺭﺎنﻣلﺍ س

الوطنية للمهندسين بتونس لمدرسة ا Ecole nationale d’ingénieurs de Tunis ﺭﺎنﻣلﺍ سنﻭﺗ ةﻌﻣﺎﺠ Université de Tunis El Manar Département Génie Industriel Projet en méta heuristique Résolution d'un problème de voyageur de commerce avec le recuit simulé Réalisé par : ABIDI Oussama BEN BRAHIM Ali Classe : 3AGI3 Année universiaire 2015/201 Sommaire : Chapitre 1 : Revue de littérature.......................................................5 1.1. Problème de voyageur de commerce :.........................................................6 1.1.1. Définition du problème :........................................................................6 1.1.2. Formulation par un programme linéaire binaire :...................................6 1.1.2.1. Formulation 1...................................................................................6 1.1.2.2. Formulation 2:..................................................................................7 1.1.3. Applications :.........................................................................................7 1.1.4. Caractéristique :.....................................................................................8 1.1.5. Résolution :............................................................................................8 1.1.6. Exemples :.............................................................................................8 1.1.7. Recherche d’une solution approchée :...................................................9 1.2. Le recuit simulé :........................................................................................10 1.2.1. Historique :..........................................................................................10 1.2.2. Définition :...........................................................................................10 1.2.3. Principes du recuit simulé :..................................................................10 1.2.4. Analogie entre recuit thermique et recuit simulé :...............................13 1.2.5. L’algorithme du recuit simulé :............................................................13 1.2.6. Etat initial de l’algorithme :..................................................................13 1.2.7. Paramètre de température:..................................................................14 1.2.8. Application du recuit simulé au problème de voyageur de commerce : .......................................................................................................................14 1.2.9. Avantages et inconvénients:................................................................16 2. Chapitre 2 : Algorithme et Implémentation...............................17 2.1. Introduction :..............................................................................................18 2.2. Les éléments de l’algorithme de recuit simulé :.........................................18 2.2.1. Solution initiale : « INITIAL ( ) »............................................................18 2.2.2. Voisinage « VOISIN ( ) »:......................................................................18 2.2.3. Algorithme principale MAIN_RECUIT ( ):...............................................19 2.3. Définition du problème et Résolution:........................................................19 2.3.1. Définition de problème :.......................................................................19 2.3.2. Résolution :..........................................................................................21 2.3.2.1. Résolution approché(recuit simulé)................................................21 2.3.2.2. Résolution exacte :........................................................................22 Liste des figures Figure 1: Blocage d’une heuristique classique dans un minima local.....................9 Figure 2 : Diagramme de modélisation du recuit simulé......................................12 Figure 3 : Un ensemble de villes (nœuds) reliés entre eux par des routes (arcs). 14 Figure 4: trajet de la solution initiale....................................................................21 Figure 5 : trajet de la meilleure solution trouvée :................................................22 Figure 6 :Code Cplex............................................................................................23 Figure 7: donné du problème................................................................................23 Figure 8: La solution optimale fournie par Cplex pour la 1’Instance n=10...........24 Liste des tableaux T ableau 1 : coordonnée des points.......................................................................20 T ableau 2 : distances entre les différents points :................................................20 Chapitre 1 : Revue de littérature 1.1. Problème de voyageur de commerce : 1.1.1. Définition du problème : Le nom du problème du voyageur de commerce vient de la situation fictive d’un vendeur qui désire visiter un certain nombre de villes, débutant et finissant son parcours dans la même ville en visitant chacune des autres villes une et une seule fois.. A l’échelle d’un pays comme les États-Unis, le coût en argent et en temps d’un tel voyage peut devenir prohibitif si l’on ne prévoit pas un trajet optimal à l’avance. Donc le défi du problème est que le voyageur de commerce veut minimiser la durée totale du voyage. 1.1.2. Formulation par un programme linéaire binaire : 1.1.2.1. Formulation 1 Variables de décision : xij = 1 si le client j est visité immédiatement après le client i = 0 sinon. Fonction objectif : La fonction objective consiste à minimiser distance parcourue par le voyageur. Min ∑ i=1 n ∑ j=1 n d ijxij Sc ∑ i=1eti≠j n x ij= 1 ∀ j=1..n (1) ∑ j=1et i≠j n x ij =1 ∀ i=1..n (2) ∑ j S ϵ et i S ϵ n x ij ≤ |S|-1 ∀ S ∁ N tq 2 ≤ |S| ≤∨¿ N|-2 (3) xij = 1 ou 0 (4) (1) Et (2) : traduit le faite que le voyageur de commerce doit passer par toutes les villes et une seule fois. (3) : oblige de ne pas avoir deux cycles ou plus qui ne sont pas lié (4) : contraintes d’intégrités 1.1.2.2. Formulation 2: Variables de décision : xij = 1 si le client j est visité immédiatement après le client i = 0 sinon. ui est un variable avec lui on assure la formation d’un seule tour Avec u(i)>=1 et u(i) <= n Fonction objectif : La fonction objective consiste à minimiser distance parcourue par le voyageur. Min ∑ i=1 n ∑ j=1 n d ijxij Sc ∑ i=1eti ≠j n x ij= 1 ∀ j=1..n (1) ∑ j=1et i≠j n x ij =1 ∀ i=1..n (2) u1=1; 2 ≤ui ≤n ∀ i=2.. n ui-uj-n*xij ≤(n-1) (3) ∀ i=1..n ∀ j=1..n i,j< >1 xij = 1 ou 0 ∀ i,j =1..n (4) (1) et (2) : traduit le faite que le voyageur de commerce doit passer par toutes les villes et une seule fois. (3) : oblige de ne pas avoir deux cycles ou plus qui ne sont pas lié. (4) : contraintes d’intégrités. 1.1.3. Applications : Le problème de voyageur de commerce s’applique dans différent domaine tel que routage autour des villes, Câblage informatique qui consiste à relier les composantes informatiques en minimisant l’utilisation du fil de câblage, ordonnancement des taches afin de minimiser le temps entre les taches. 1.1.4. Caractéristique : Le nombre de chemins ou de cycles possibles dans notre problème est en (N-1)!/2 avec N le nombre de villes, donc ce problème fait partie d’une famille de problèmes trop complexes appelé NP difficile pour qu’une solution soit recherchée de façon systématique parmi toutes les solutions possibles [1]. 1.1.5. Résolution : La première idée qui vient à l’esprit lorsque l’on veut résoudre le problème de voyageur de commerce est certainement celle de la recherche exhaustive. Le principe en est très simple, mais au prix d’une complexité en temps très élevée : il consiste à déterminer toutes les solutions, à en évaluer la valeur, puis à sélectionner la meilleure de ces solutions. Dans notre contexte, cela se traduit par la recherche de tous les cycles hamiltoniens. Or il y a (N-1)!/2 visites possibles, sachant que l’évaluation d’un tour nécessite un temps de O(n), nous obtenons une complexité totale en temps de O (n!) [2] 1.1.6. Exemples : 50 villes -> 49! Solutions possibles, i.e. 6,08.1062 tournées possibles Prenons un ordinateur de 1 millimètre calculant un milliard de solutions par seconde. Sachant que le diamètre équatorial de la terre est de 12 756 kilomètres, on peut mettre 12 756 000 000 de ces ordinateurs les uns à la suite des autres sur l'équateur. On peut ainsi calculer Nombre de ville Nombre de possibilité 5 20 30 120 1018 1032 Nombre de ville Nombre de possibilité Temps d’exécution 5 20 30 120 1018 1032 0,12 10-12 40 min 1010 ans 12 576 000 000 000 000 000 solutions par seconde (1,25. 1019) Pour être certain de trouver la tournée la plus courte, il faut considérer toutes les tournées possibles. Il nous faudra alors 4,766.1043 secondes avec le super ordinateur que l'on vient de présenter [3]. Note : 4,766.1042 est l'équivalent de 1,51.1034 siècle Remarque : La résolution exacte d’un tel problème avec n villes exige de vérifier (n-1)! Visites, ce qui nécessite un grand temps et de matériels informatique de capacité énorme même pour les petites instances ce qui parait inutile pour la plupart des problèmes, donc l’idée est de faire recours à des résolutions approchées qui peuvent servir pour quelque problème. 1.1.7. Recherche d’une solution approchée : Pour palier à ces problèmes, les chercheurs ont introduit des méthodes approchées appelées heuristiques, elles présentent l'avantage d'un temps de calcul réduit mais ne donnent aucune information sur la qualité de la solution trouvée, de plus elles ne sont en général applicables qu'a un seul type de problèmes. (Autin, 2006) Par exemple la méthode de la descente consiste à partir d’une solution S à choisir une solution S’ dans un voisinage de S, telle que S’ améliore la solution. La recherche s’arrête donc au premier minimum (ou maximum) local rencontré, c’est là son principal défaut. Pour améliorer les résultats, on peut relancer plusieurs fois l’algorithme mais la performance de cette technique décroît rapidement. Ce qui a poussé les chercheurs à proposer de nouvelles méthodes générales (applicables à la plupart des problèmes d'optimisation) appelées méta-heuristiques, dont la méthode du recuit simulé ; conçu pour rechercher un optimum global parmi plusieurs minimas (ou maximas) locaux [4]. Figure 1: Blocage d’une heuristique classique dans un minima local 1.2. Le recuit simulé : 1.2.1. Historique : La méthode de recuit simulé était réalisée par Metropolis et al. (1953) pour simuler l'évolution de ce processus de recuit physique (Metropolis53). Elle a été mise au point par trois chercheurs de la société IBM,. Kirkpatrick, C.D. Gelatt et M.P. Vecchi en 1983 aux Etats-Unis, et indépendamment par V. Černy en 1985 en Slovaquie. Son utilisation pour la résolution des problèmes d'optimisation combinatoire est beaucoup plus récente. Ainsi, le recuit simulé est la première métaheuristique qui a été proposée pour ce genre de problème. 1.2.2. Définition : La méthode du recuit simulé (simulated annealing) s'inspire du processus du recuit physique. Ce processus utilisé en métallurgie pour améliorer la qualité d'un solide cherche un état d'énergie minimale qui correspond à une structure stable du solide. En partant d'une haute température à laquelle le solide est devenu liquide, la phase de refroidissement conduit la matière liquide à retrouver sa forme solide par une diminution progressive de la température. Chaque température est maintenue jusqu'à ce que la matière trouve un équilibre thermodynamique. Quand la température tend vers zéro, seules les transitions d'un état à un état d'énergie uploads/Voyage/ voyageur-de-commerce-recuit-simule.pdf