User Tools

Site Tools


Sidebar

* [[http://www.labri.fr/perso/melancon|Me as a researcher]] --- * [[start|Home]] * [[proj_techno:start|Projets technologiques - Licence 3 Informatique]] 4TIN601U * [[proj_CMI_L2:start|Projet de programmation - CMI ISI]] 4TCM401U * [[MIAGE:processus_stoch_simulation|Processus stochastiques et simulation - MIAGE et e-MIAGE]] 4TYE814U / 4TYE808U ---- * **Fête de la Science** - [[mathc2+:analyse|"Analyse de réseau appliquée aux réseau sociaux"]] ---- * Master U de Bx * [[http://www.labri.fr/perso/melancon/Visual_Analytics_Course/|Visual Analytics]] * [[e-miage_ubx_i|e-MIAGE U de Bx]] * [[estia:estia|ESTIA DataViz / Data Science]] * [[Enseignements passés]] ---- * [[http://www.labri.fr/perso/melancon|Research]] ---- * [[admin:Site admin]]

A PCRE internal error occured. This might be caused by a faulty plugin
miage_solution:voyageur

====== Master 4TYE814U/4TYE808U MIAGE & e-MIAGE -- Processus stochastiques et simulation ====== ===== Séance de travaux dirigé ===== ==== Le voyageur de commerce ==== On suppose déjà disposer d'une classe permettant de calculer (par requête) la distance entre deux villes. <file python DistanceCalculator.py> # -*- coding:utf-8 -*- import urllib import lxml.html class DistanceCalculator(object): """docstring for Distance""" def __init__(self): super(DistanceCalculator, self).__init__() def distance(self, ville1, ville2): url = 'http://fr.distance24.org/' + ville1 + '/' + ville2 file = urllib.urlopen(url) data = file.read().decode('utf8') file.close() doc = lxml.html.document_fromstring(data) distance_oiseau = doc.xpath('//div[@id="air"]//strong//text()') res = distance_oiseau[0] try: return int(res.split('k')[0]) except: print ville1, ville2, res </file> Le traitement d'exception en fin de code (instruction ''try:'' ... ''except:'') permet de détecter les cas où le serveur distant ne sait pas identifier les villes (mais c'est un traitement bien léger, j'en conviens, ce n'est pas ce sur quoi nous portons notre attention). ---- On suppose donné une liste de villes dont on connaît les noms. On prendra dans l'exemple ici les villes, dans cet ordre: * Pau, Gradignan, La Réole, Bazas, Bordeaux, Talence, Anglet, Langoiran, Langon, Captieux, Orthez, Biarritz, Bayonne Les connaisseurs de la région du Sud-Ouest les reconnaîtront et admettront qu'il ne s'agit pas là d'un parcours optimal pour aller de Pau à Bayonne en passant par toutes les villes intermédiaires. Le parcours qui fait 837 kilomètres n'est cependant pas le "pire". On met au point des méthodes réalisant la chaîne de Markov irréductible et symétrique parcourant tous les ordres possibles dans lesquels on peut traverser ces villes (il y en a 13!, soit 6227020800). La fonction de transition choisit, //à partir d'un parcours donné// (qui est un //état// de la chaîne) un nouveua parcours choisit au hasard de la manière suivante: * On suppose donné un ''etat = [ville_0, ville_1, ville_2, ..., ville_N-1]'' (c'est-à-dire ''etat[i]'' est égal à ''ville_i'') * On choisit un nombre uniformément au hasard parmi 0, 1, ..., N-2 * On échange les villes ville_i et ville_i+1 pour obtenir un nouveau parcours * ''nouv_etat = [ville_0, ville_1, ..., ville_i+1, ville_i, ville_i+2, ..., ville_N-1]'' <code python> def transition(etat): i = random.randint(0,self.nb_villes-2) nouv_etat = etat[0:i] + [etat[i+1]] + [etat[i]] + etat[i+2:len(etat)] return nouv_etat </code> L'algorithme de Metropolis se sert de cette chaîne pour explorer des solutions candidates. Une nouvelle fonction de transition permet de choisir les solutions les "meilleures" (ou les moins mauvaises) et de rejeter les plus mauvaises. Le critère qui désigne les meilleures solutions repose sur la distance totale parcourue lors de la visite des villes ''[ville_0, ville_1, ville_2, ..., ville_N-1]''. <code python> def distance_totale(etat, matrice_distances): s = 0.0 for i in range(nb_villes - 2): try: d = matrice_distances[etat[i] + etat[i+1]] except: try: d = matrice_distances[etat[i+1] + etat[i]] except: d = dc.distance(etat[i], etat[i+1]) matrice_distances[etat[i] + etat[i+1]] = d matrice_distances[etat[i+1] + etat[i]] = d s += d return s </code> Cette fonction envoie au besoin une requête au serveur (via la classe ''DistanceCalculator''), mais stocke le résultat dans la variable ''matrice_distances'' pour éviter de reformuler la même requête trop souvent. Par ailleurs, la variable ''matrice_distances'' n'est en réalité pas une matrice mais une table de hachage indexé par une clé formé des noms des deux villes. Il faut former une distribution cible, $\pi'$, qui à un état (une suite ordonnée des villes) associe une valeur. Une //bonne//solution ''etat = [ville_0, ville_1, ville_2, ..., ville_N-1]'' aura une valeur $\pi'([v_0, v_1, \ldots, v_{N-1}])$ plus élevée. Une //bonne// solution permet de parcourir //moins// de kilomètres. Ainsi, la première qui vient est d'utiliser la distribution cible: $\pi'(''etat''$) =$ ''1/distance_totale(etat, matrice_distances)'' <code python> def distribution_cible(etat, matrice_distances): return 1.0 / distance_totale(etat, matrice_distances) </code> On peut aussi utiliser une distribution ciel plus discriminante calculant ''math.exp(-distance_totale(etat, matrice_distances))''. ---- La fonction de transition implémentant l'algorithme de Metropolis est: * On suppose donné un ''etat = [ville_0, ville_1, ville_2, ..., ville_N-1]'' * On utilise la chaîne de Markov de départ proposant une transition vers un nouvel état ''nouv_etat'' * On calcule le ratio: $$ p = \min(\frac{\pi'(nouv\_etat)}{\pi'(etat)}, 1)$$ * On effectue la transition ''etat'' $\to$ ''nouv_etat'' avec probabilité $p$ <code python> def transitionMetropolis(etat, matrice_distances): nouv_etat = transition(etat) try: p = min(distribution_cible(nouv_etat, matrice_distances) /distribution_cible(etat, matrice_distances), 1.0) if random.random() < p: return nouv_etat else: return etat except ZeroDivisionError: return nouv_etat </code> Les valeurs ''math.exp(-distance_totale(etat, matrice_distances))'' peuvent parfois être extrêmement faible, voire nulle. Le traitement de l'exception ''ZeroDivisionError'' permet de détecter cette situation (qui conduit à accepter la transition puisque le nouvel état a une valeur "infiniment" plus grande que celle de l'état précédent). ---- L'ensemble de cette solution est reprise ci-dessous sous forme d'une classe (ce qui permet d'alléger les déclarations des fonctions puisqu'alors elles ont accès aux attributs de la classe): <file python Voyageur.py> # -*- coding:utf-8 -*- from DistanceCalculator import * import random import math class Voyageur(object): ''' Donne un ensemble de villes (une liste), calcule un parcours "optimal" (distance totale min) a l'aide de l'algorithme de Metropoli.s Un etat de la chaine correspond a une liste ordonnee des villes. Une transition correspond a permuter deux villes successives dans le parcours. ''' def __init__(self, ensemble_villes): super(Voyageur, self).__init__() self.ensemble_villes = ensemble_villes self.nb_villes = len(self.ensemble_villes) self.dc = DistanceCalculator() self.matrice_distances = {} def transition(self, etat): i = random.randint(0,self.nb_villes-2) nouv_etat = etat[0:i] + [etat[i+1]] + [etat[i]] + etat[i+2:len(etat)] return nouv_etat def distance_totale(self, etat): s = 0.0 for i in range(self.nb_villes - 2): try: d = self.matrice_distances[etat[i] + etat[i+1]] except: try: d = self.matrice_distances[etat[i+1] + etat[i]] except: d = self.dc.distance(etat[i], etat[i+1]) self.matrice_distances[etat[i] + etat[i+1]] = d self.matrice_distances[etat[i+1] + etat[i]] = d s += d return s def distribution_cible(self, etat): return math.exp(-self.distance_totale(etat)) # return 1.0 / self.distance_totale(etat) def transitionMetropolis(self, etat): nouv_etat = self.transition(etat) try: p = min(self.distribution_cible(nouv_etat)/self.distribution_cible(etat), 1.0) if random.random() < p: return nouv_etat else: return etat except ZeroDivisionError: return nouv_etat def marche_Metropolis(self, nb_pas): etat = self.ensemble_villes for i in range(nb_pas): if i % (nb_pas / 20) == 0: print etat, self.distance_totale(etat) etat = self.transitionMetropolis(etat) return etat if __name__ == '__main__': liste_villes = ['Pau', 'Gradignan', 'La Réole', 'Bazas', 'Bordeaux',\ 'Talence', 'Anglet', 'Langoiran', 'Langon', 'Captieux', 'Orthez',\ 'Biarritz', 'Bayonne'] vc = Voyageur(liste_villes) print vc.marche_Metropolis(100000) </file> En effectuant une marche de Metropolis de 100000 pas, et avec la distribution cible utilisant la fonction exponentielle, on arrive à trouver une solution relativement bonne: ['La Réole', 'Bordeaux', 'Talence', 'Biarritz', 'Anglet', 'Bayonne', 'Orthez', 'Pau', 'Captieux', 'Langon', 'Langoiran', 'Gradignan', 'Bazas'] qui ne met que 504 kilomètres ... (plutôt que les 837 du départ, et bien moins que les solutions les plus farfelues). Essayez ! --- [[miage:td_metropolis|Retourner au TD]]

miage_solution/voyageur.txt · Last modified: 2017/04/25 16:07 by melancon