Guy Melançon - Enseignement

====== Master 4TYE814U/4TYE808U MIAGE & e-MIAGE -- Processus stochastiques et simulation ====== ;;# "It is a part of probability that many improbabilities will happen." ;;# ;;# Aristotle ;;# ---- ===== Epreuve de TP noté du 07/03/2017 -- Durée : 45 minutes ===== ==== Au début de l'épreuve ==== __**<color red/#efefef>Dans une fenêtre terminal</color>**__ * **<color red/#efefef>Depuis votre répertoire d'accueil</color>** * **<color red/#efefef>Exécutez la commande:</color>** **''~gmelanco/MIAGe/TP_note/debut.sh''** * Des fichiers de code seront copiés dans un répertoire de travail. * Ces fichiers de code sont à compléter selon les instructions du sujet. * D'autres fichiers vous permettent de tester votre code. * <color red/#efefef>Prêtez attention à ne pas déplacer ces fichiers hors du répertoire. La bonne exécution du code exige de garder tous ces fichiers dans un même répertoire.</color> ---- ==== En fin d'épreuve ==== __**<color red/#efefef>Dans une fenêtre terminal</color>**__ * **<color red/#efefef>Depuis le répertoire où se trouvent les fichiers sur lesquels vous avez travaillé</color>** * **<color red/#efefef>Exécutez la commande:</color>** **''~gmelanco/MIAGe/TP_note/fin.sh''** ---- ===== Formation en équipe ===== A l'école (c'était mon cas), les équipes (à la récré) étaient formées de manière relativement démocratique ... Deux "chefs" choisissaient les joueurs à tour de rôle. On peut penser qu'à l'arrivée, les équipes comprenaient, à peu de choses près, une bande de copains -- les liens de camaraderie dominaient. A l'inverse, rivalité oblige, il y avait moins de liens de camaraderie entre les équipes. On se propose de formuler un algorithme pour partager une assemblée de personnes en deux "équipes". Le but, ultimement, sera de proposer des équipes où les liens d'amitiés dominent //dans// les équipes, alors qu'il y en a moins //entre// les deux équipes. ==== Markov simple ==== Penchons-nous d'abord sur un procédé permettant d'explorer //toutes les formations// en deux équipes. ON ne cherche pas pour l'instant à optimiser les formations. On désignera les personnes par des numéros, des entiers de 1 à $N$. Une formation en deux équipes est donc une paire ''equipeA, equipeB'' où ''equipeA'' et ''equipeB'' sont des listes de taille $N/2$ (où on suppose $N$ pair). On peut donc prendre, au départ, la formation: <code> formation = [[i for i in range(nb_personnes/2)], [i for i in range(nb_personnes/2, nb_personnes)]] </code> où la variable ''nb_personnes'' a la valeur $N$. === Transition === Nous allons considérer une chaîne de Markov permettant d'explorer cet espace des formations. A partir d'une formation = ''equipeA, equipeB'', on "fabriquer" une autre formation en faisant: * On choisit au hasard de manière uniforme (de manière équiproblale) deux nombres $i, j$ entre 0 et $N/2 - 1$. * On échange les joueurs: le $i$ème joueur de l' ''équipe A'', et le $j$ème joueur de l' ''équipe B'' changent d'équipe. C'est ce qu'effectue la fonction: <code python> def transition(formation, nb_personnes): nouv_formation = formation[0][:], formation[1][:] # to do # modifier la copie de la formation reçue en paramètre # ... return nouv_formation '</code> Cette fonction est à implémenter dans le fichier ''Markov_simple.py''. ---- <color red/#efefef>Vous utiliserez le code fourni ici comme squelette. Vous retrouverez ce code dans les fichiers qui ont été copiés dans votre répertoire d'accueil. 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 fonctions</color>__ <color red/#efefef>et ajoutez votre code dans le corps des fonctions. Vous pouvez bien entendu ajoutez d'autres fonctions si vous le souhaitez.</color> ---- === Tester votre fonction de transition === Le code suivant doit fonctionner sans problème. La variable ''meme_equipe'' calcule la proportion de fois où deux équipiers sont membres d'une même équipe. En principe, sa valeur doit être proche de 0.5 (pour de grandes valeurs de la variable ''nb_pas''). Le code doit fonctionner pour différentes valeurs de la variables ''nb_personnes''. <code python Markov_simple_test.py> # -*- coding:utf-8 -*- import random from Markov_simple import * nb_personnes = 50 formation = [[i for i in range(nb_personnes/2)], [i for i in range(nb_personnes/2, nb_personnes)]] nb_pas = 100000 meme_equipe = 0.0 for i in range(nb_pas): equipeA = formation[0] equipeB = formation[1] if (21 in equipeA and 34 in equipeA) or (21 in equipeB and 34 in equipeB): meme_equipe += 1 formation = transition(formation, nb_personnes) print 'Proportion deux equipiers dans l\'equipe A: ', meme_equipe / nb_pas print '(Lorsque nb_pas est grand, la valeur affichee doit etre proche' print 'et osciller autour de 0.5, *quels que soient* les deux équipiers choisis.)' </code> ---- ==== Algorithme de Metropolis ==== Nous allons maintenant chercher à faire un bon choix de formation. On suppose connaître le réseau social (des liens de camaraderie) entre les personnes. {{ :miage:reseau_social_camarades.png?direct&500 |}} --- Un package ''Utils'' permet de charger le réseau social. Il positionne aussi des variables ''nb_personnes'' et ''nb_liens'' total de camaraderie dans le réseau. La variable ''reseau'' contient la description des liens dans le réseau. <code python> # -*- coding:utf-8 -*- from Utils import * reseau, nb_personnes, nb_liens = charger_reseau() </code> La fonction de transition de l'algorithme de Metropolis cherchera à favoriser les bonnes formations: celles où le nombre de liens //internes// aux équipes est le plus grand possible. Il faut donc pouvoir calculer combien de liens sont //internes// aux équipes. Nous allons procéder __ainsi__: * On calculera d'abord combien de liens sont //externes//. Un lien de camaraderie est //externe// lorsqu'il lie deux personnes qui ne sont pas de la même équipe. <code> equipeA = formation[0] equipeB = formation[1] nb_liens_externes = 0.0 pour chaque personne pA dans equipeA pour chaque personne pB dans equipeB si pA est liée à pB nb_liens_externes += 1.0 </code> en sortie de boucle, la variable ''nb_liens_externes'' contient le nombre de liens externes dans le réseau (par rapport à la formation donnée). Le nombre de liens //internes// est égal à: <code>nb_liens_internes = nb_liens - nb_liens_externes</code> Vous disposez déjà de la fonction (dans le package ''Utils''): <code>def sont_liees(personne1, personne2)</code> où ''personne1'' et ''personne2'' sont des entiers entre 0 et ''nb_personnes - 1''. --- Il vous faut construire la fonction: <code python> def nb_liens_externes(formation): global nb_liens equipeA = etat[0] equipeB = etat[1] nb_liens_ext = 0.0 # to do # ... return nb_liens_ext def nb_liens_internes(formation): global nb_liens return nb_liens - nb_liens_externes(formation) </code> --- La //distribution cible// de l'algorithme de Metropolis doit donc être basée sur le ratio ''nb_liens_internes''/''nb_liens''. <code python> def distribution_cible(formation): global nb_liens # to do # ... return ... # valeur associée à la formation </code> === Transition et Metropolis === Reste à construire la fonction qui effectue la transition comme dicté par l'algorithme de Metropolis. <code python> def transitionMetropolis(formation): # to do # ... </code> L'ensemble de ces fonctions est à implémenter dans le fichier ''Markov_Metropolis.py''. ---- === 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. <code python> # -*- coding:utf-8 -*- import random from Utils import * from Markov_simple import * from Markov_Metropolis import * reseau, nb_personnes, nb_liens = charger_reseau() formation = [[i for i in range(nb_personnes/2)], [i for i in range(nb_personnes/2, nb_personnes)]] nb_pas = 100 meme_equipe = 0.0 for i in range(nb_pas): equipeA = formation[0] equipeB = formation[1] equipier1 = 1 equipier2 = 2 if (equipier1 in equipeA and equipier2 in equipeA) or (equipier1 in equipeB and equipier2 in equipeB): meme_equipe += 1 formation = transitionMetropolis(formation, nb_personnes) print 'Proportion deux equipiers dans l\'equipe A: ', meme_equipe / nb_pas print '(Lorsque nb_pas est grand, la valeur affichee doit etre proche' print 'de 0.0 pour des personnes "eloignees" l\'une de l\'autre dans le reseau,' print 'et plus elevee pour des personnes "proches".)' </code> --- [[miage:processus_stoch_simulation|Retour à la page d'accueil du cours]] --- [[miage:processus_stoch_simulation|Retour à la page d'accueil du cours]]