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_epreuve:tp_note_final_a

====== Master 4TYE814U/4TYE808U MIAGE & e-MIAGE -- Processus stochastiques et simulation ====== ;;# "It is a part of probability that many improbabilities will happen." ;;# ;;# Aristotle ;;# ---- ===== Sujet type de TP noté du 28/02/2017 ===== * Le sujet propose des fichiers de code à compléter. Ces fichiers doivent être composés séparément et doivent pouvoir être exécutés séparément (sans problème à l'aide des directives d'import). * Les fichiers de code sont directement téléchargeables (en cliquant dans l'entête). * La bonne exécution du code exige de placer tous ces fichiers dans un même répoertoire. ---- ==== Bulldozers ==== Cet exercice consiste à implémenter la solution au problème de réaffectation des bulldozers sur les chantiers, que l'on rappelle ici. --- Une société de location de matériel de chantier rencontre systématiquement le même problème chaque semaine et cherche une solution pouvant l'aider à minimiser le coût qui y est associé. En début de semaine, elle doit décider du déplacement de bulldozers quittant leurs chantiers pour être implantés sur d'autres chantiers qui débutent. Chacun des $n$ bulldozers, laissés sur des (\emph{a}nciens) chantiers $a_1, a_2, \ldots, a_n$ doivent être amenés sur les \emph{p}rochains chantiers $p_1, p_2, \ldots, p_n$. Les coûts de transport de ces machines, facturé au kilomètres parcourus, doit être tenu au minimum. On va noter par $\rho$ (la lettre grecque ``rho'' qui correspond au ``r'' latin, pour \emph{r}éaffectation) une réaffectation. C'est une fonction $i \mapsto \rho(i)$ qui code le fait que le bulldozer sur l'ancien chantier $a_i$ doit être affecté au nouveau chantier $p_{\rho(i)}$. Cette fonction est une \emph{permutation} des entiers $\{1, 2, \ldots, n\}$. Les distances entres les sites $a_1, a_2, \ldots, a_n$ et $p_1, p_2, \ldots, p_n$ entrent donc en jeu. Le but de cet exercice est d'élaborer une méthode pouvant trouver une solution acceptable au problème posé, applicable en toute généralité (quelle que soit la valeur de $n$, et les distances entre les sites). On notera $d(\rho)$ la distance associé à la réaffectation $\rho$ (la somme des distances $\sum_{i=1}^n d(a_i, p_{\rho(i)}$) de tous les déplacements des bulldozers impliqués par cette réaffectation). --- <color red/#efefef>Vous utiliserez le code fourni ici comme squelette. Ne modifiez pas le nom des fichiers au risque de difficultés qui prendront du temps à être ajustées/réparées.</color> <color red/#efefef>Vous préservez le nom des fonction et ajoutez votre code dans le corps des fonctions. Vous pouvez bin entendu ajoutez d'autres fonctions si vous le souhaitez.</color> ---- === Chaine de Markov symétrique et irréductible === Ce premier fichier ''bulldozer_markov.py'' contiendra les fonctions nécessaires à la marche aléatoire sur la chaîne de Markov symétrique et irréductible. * On convient d'un certain nombre de chantiers stocke dans la variable ''nb_chantiers''. * C'est une variable globale qui doit être fournie en paramètre aux fonctions. * Une affectation des bulldozers aux nouveaux chantiers est codée à l'aide d'une permutation de {''0'', ''1'', ..., ''nb_chantiers - 1''} * Le fichier contient donc la fonction de transition de la chaine, qui à partir d'une affectation en produit une autre selon la règle décrite plus haut. <file python bulldozer_markov.py> # -*- coding:utf-8 -*- import random import numpy ######################################################### # Partie A - chaine de Markov symetrique et irreductible ######################################################### # nb_chantiers = ... doit etre defini avant d'executer ce code ######################################################### # la fonction transition implemente les transitions de # la chaine de Markov symetrique et irreductible def transition(affectation, nb_chantiers): # to do # ... return # une affectation </file> ---- === Tester votre code : chaine de Markov symétrique et irréductible === Ce fichier doit pouvoir s'exécuter sans problème. Il charge le code des fonctions du premier fichier et effectue une marche aléatoire. Les résultats doivent permettre de vérifier que tout se passe bien, que la chaîne converger vers une distribution stationnaire uniforme, que la marche aléatoire visite tous les états avec même probabilité. <file python markov_test.py> # -*- coding:utf-8 -*- from bulldozer_markov import * ######################################################### # cette fonction cree une chaine de caracteres a partir d'une affectation # afin de pouvoir stocker les frequences dans un dictionnaire def affectation_tostring(affectation): return ';'.join(map(lambda x: str(x), affectation)) ######################################################### # le code suivant doit pouvoir s'executer sans probleme # les frequences affichees doivent correspondre a une distribution uniforme nb_chantiers = 3 # on stocke dans une variable les numeros des lieux ou seront reaffectes les bulldozers affectation_nouvelle = [2, 3, 1] # une permutation de {0, 1, ..., nb_chantiers - 1} nb_pas = 12000 frequence_affectations = {} for i in range(nb_pas): afstr = affectation_tostring(affectation_nouvelle) if afstr in frequence_affectations.keys(): frequence_affectations[afstr] += 1 else: frequence_affectations[afstr] = 1 affectation_nouvelle = transition(affectation_nouvelle, nb_chantiers) print frequence_affectations </file> ---- === Algorithme de Metropolis === Ce second fichier ''bulldozer_metropolis.py'' contiendra les fonctions nécessaires à l'algorithme de Metropolis construit sur la chaîne de Markov précédente. <file python bulldozer_metropolis.py> # -*- coding:utf-8 -*- import random import numpy from bulldozer_markov import * ######################################################### ######################################################### # Partie B - algorithme de Metropolis ######################################################### # la numerotation des lieux actuels ou se trouve les bulldozers importe peu # on suppose qu'ils correspondent aux numeros 0, 1, ..., des lignes de la matrice des distances ######################################################### # cette fonction retourne une matrice des distances generees aleatoirement # les distances varient entre 5 et 100 kilometres de maniere uniforme # la fonction retourne une matrice, # dont l'entree i, j donne la distance entre l'affectation actuelle numero i # et l'affectation sur le chantier j de la semaine qui suit def random_distance(nb_chantiers): // to do M = # ... # ... remplissez la matrice en generant des nombres aleatoires entre 5 et 100 return M ######################################################### # cette fonction calcule la distance parcourue lors du deplacement # des bulldozers sur les nouveaux chantiers # elle utilise la matrice des distances # # le parametre distance_chantiers est la matrice des distances generee # a l'aide de la fonction precedente def distance_totale(affectation, distance_chantiers, nb_chantiers): d = # ... # ... return d def distribution_cible(affectation, distance_chantiers, nb_chantiers): return # ... une valeur def Metropolis_transition(affectation, distance_chantiers, nb_chantiers): # to do # ... return # une affectation </file> ---- === Tester votre code: algorithme de Metropolis === Ce fichier doit pouvoir s'exécuter sans problème. Il charge le code des fonctions des second et premier fichier et effectue une marche aléatoire selon la transition de Metropolis et la distribution cible que vous aurez définie. Les résultats doivent permettre de vérifier que tout se passe bien, que l'algorithme tente de trouver ue solution optimale au déplacement des bulldozers. <file python metropolis_test1.py> # -*- coding:utf-8 -*- import random import numpy from bulldozer_markov import * from bulldozer_metropolis import * ######################################################### # le code suivant doit pouvoir s'executer sans probleme # les affichages permettent de verifier que les choses se passent comme prevues nb_chantiers = 3 affectation_actuelle = [i for i in range(nb_chantiers)] affectation_nouvelle = [i for i in range(nb_chantiers)] ######################################################### # on initialise la matrice des distances distance_chantiers = random_distance(nb_chantiers) print distance_chantiers ######################################################### # on marche nb_pas = 20 for i in range(nb_pas): print affectation_nouvelle, distance_totale(affectation_nouvelle, distance_chantiers, nb_chantiers) affectation_nouvelle = Metropolis_transition(affectation_nouvelle, distance_chantiers, nb_chantiers) print affectation_nouvelle, distance_totale(affectation_nouvelle, distance_chantiers, nb_chantiers) </file> Vous devez pouvoir exécuter ce second et troisième fichier test. * Le code du second fichier lance une simulation avec un nombre de chantiers égal à 10 (3628800 solutions possibles !!!). * La solution optimale trouvée est affichée. Faites tourner votre code à plusieurs reprises pour avoir un retour sur ce que l'algorithme est en mesure de trouver. * Le code du troisième fichier calcule plusieurs solutions possibles et fait une moyenne de la distance totale à parcourir sur l'ensemble des solutions. <file python metropolis_test2.py> # -*- coding:utf-8 -*- import random import numpy from bulldozer_markov import * from bulldozer_metropolis import * ######################################################### # le code suivant doit pouvoir s'executer sans probleme # les affichages permettent de verifier que les choses se passent comme prevues ######################################################### # on initialise la matrice des distances nb_chantiers = 10 affectation_actuelle = [i for i in range(nb_chantiers)] affectation_nouvelle = [i for i in range(nb_chantiers)] distance_chantiers = random_distance(nb_chantiers) ######################################################### # on marche nb_pas = 10000 for i in range(nb_pas): affectation_nouvelle = Metropolis_transition(affectation_nouvelle, distance_chantiers, nb_chantiers) print affectation_nouvelle, distance_totale(affectation_nouvelle, distance_chantiers, nb_chantiers) </file> ---- <file python metropolis_test3.py> # -*- coding:utf-8 -*- import random import numpy from bulldozer_markov import * from bulldozer_metropolis import * ######################################################### # le code suivant doit pouvoir s'executer sans probleme # les affichages permettent de verifier que les choses se passent comme prevues ######################################################### # on initialise la matrice des distances nb_chantiers = 10 affectation_actuelle = [i for i in range(nb_chantiers)] affectation_nouvelle = [i for i in range(nb_chantiers)] distance_chantiers = random_distance(nb_chantiers) ######################################################### # on calcule la distance moyenne d'une solution (ur 100 solutions generees, avec 10000 pas chacune) dist_moy = 0.0 nb_essais = 100 for j in range(nb_essais): affectation_nouvelle = [i for i in range(nb_chantiers)] nb_pas = 100000 for i in range(nb_pas): affectation_nouvelle = Metropolis_transition(affectation_nouvelle, nb_chantiers) dist_moy += distance_totale(affectation_nouvelle, nb_chantiers) dist_moy /= nb_essais print 'Distance moyenne parcourue pour une reaffectation "optimale":', dist_moy </file> --- [[miage:processus_stoch_simulation|Retour à la page d'accueil du cours]]

miage_epreuve/tp_note_final_a.txt · Last modified: 2017/02/24 19:03 by melancon