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:solution_knapsack

====== Master 4TYE814U/4TYE808U MIAGE & e-MIAGE -- Processus stochastiques et simulation ====== ===== Séance de travaux dirigé ===== ==== Le problème du sac à dos ==== On suppose déjà disposer du code permettant de charger la liste des produits, de leurs poids et leurs valeurs respectives. <file python Liste_produits.py> # -*- coding:utf-8 -*- import random produits = [] poids = [] valeurs = [] # la liste des articles avec prix fp = open('/Users/melancon/Documents/Enseignements/4TYE814U_4TYE808U_MIAGE/listeCourses_avec_prix.csv', 'rU') # fp = open('/Users/melancon/Documents/Enseignements/4TYE814U_4TYE808U_MIAGE/knapsack.csv', 'rU') line = fp.readline() # capacite max du sac (en grammes) capacite = float(line.split(';')[1]) print capacite line = fp.readline() # headers line = fp.readline() while line != '': prod_poids = line.split(';') produits.append(prod_poids[0]) poids.append(float(prod_poids[1])) valeurs.append(float(prod_poids[2])) line = fp.readline() fp.close() </file> A la sortie, les produits, leurs poids et leurs valeurs sont stockés dans les variables ''produits'', ''poids'', ''valeurs''. La capacité du sac à dos est stockée dans la variable du même nom. ---- On met au point la chaîne de Markov irréductible et symétrique parcourant tous les remplissages possibles du sac à dos dont le poids total n'excède pas la capacité du sac -- il y en a de l'ordre de $2^N$ (si la liste contient $N$ articles). Les états de cette chaîne sont les remplissages possibles du sac à dos. On désignera les états soit par la variable ''etat'', soit par la variable ''sac''. On convient de décrire le contenu du sac à dos à l'aide d'un tableau de 0 et de 1 indiquant si l'objet est présente dans le sac. Ainsi, le sac vide correspond à: ''sac_vide = [0 for i in range(len(produits))]'' La fonction de transition propose, //à partir d'un remplissage donné du sac// (qui est un //état// de la chaîne) un nouveau remplissage fabriqué au hasard de la manière suivante: * On suppose donné un ''etat = [obj_0, obj_1, ..., obj_N-1]'' (on écrira aussi ''sac = [obj_0, obj_1, ..., obj_N-1]'') * On choisit un objet de la liste au hasard, c'est-à-dire un nombre uniformément au hasard parmi 0, 1, ..., N-1 * Si l'objet est présent dans le sac à dos, on le retire, * S'il n'y est pas, on l'ajoute //à condition de ne pas excéder la capacité du sac// * Sinon, on ne modifie pas le sac <code python> def poids_total(sac): return sum([poids[i] if sac[i] == 1 else 0 for i in range(len(produits))]) def transition(sac): global capacite, poids # sac_alt est une copie de sac sac_alt = sac[:] i = random.randint(0, len(produits) - 1) if sac_alt[i] == 1: # suppression prod sac_alt[i] = 0 else: p = poids[i] if poids_total(sac) + poids[i] < capacite: sac_alt[i] = 1 return sac_alt </code> ---- L'algorithme de Metropolis se sert de cette chaîne pour explorer des remplissages candidats. 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 valeur totale des objets contenus dans le sac à dos. <code python> def valeur_totale(sac): return sum([valeurs[i] if sac[i] == 1 else 0 for i in range(len(produits))]) </code> Il faut former une distribution cible, $\pi'$, qui à un état (un remplissage du sac) associe une valeur $\pi'($''etat''$)$. Une //bonne//solution ''etat = [obj_0, obj_1, ..., obj_N-1]'' aura une ''valeur_totale([obj_0, obj_1, ..., obj_N-1])'' plus élevée. On peut se contenter de prendre comme distribution cible, la valeur d'une solution. On peut aussi forcer le trait en prenant plutôt le carré de cette valeur: <code python> def distribution_cible(sac): return valeur_totale(sac)**2 </code> ---- La fonction de transition implémentant l'algorithme de Metropolis suit le schéma: * On suppose donné un ''etat = [obj_0, obj_1, ..., obj_N-1]'' * On utilise la chaîne de Markov de départ proposant une transition vers un nouvel état ''nouv_etat = transition(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) 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 </code> ---- L'ensemble de cette solution est reprise ci-dessous. <file python SacADos.py> # -*- coding:utf-8 -*- import random produits = [] poids = [] valeurs = [] # la liste des articles avec prix # fp = open('/Users/melancon/Documents/Enseignements/4TYE814U_4TYE808U_MIAGE/listeCourses_avec_prix.csv', 'rU') fp = open('/Users/melancon/Documents/Enseignements/4TYE814U_4TYE808U_MIAGE/knapsack.csv', 'rU') line = fp.readline() # capacite max du sac capacite = float(line.split(';')[1]) print capacite line = fp.readline() # headers line = fp.readline() while line != '': prod_poids = line.split(';') produits.append(prod_poids[0]) poids.append(float(prod_poids[1])) valeurs.append(float(prod_poids[2])) line = fp.readline() fp.close() def contenu(sac): c = [] for i in range(len(produits)): if sac[i] == 1: c.append(produits[i]) return c def poids_total(sac): return sum([poids[i] if sac[i] == 1 else 0 for i in range(len(produits))]) def transition(sac): global capacite, poids # sac_alt est une copie de sac sac_alt = sac[:] i = random.randint(0, len(produits) - 1) if sac_alt[i] == 1: # suppression prod sac_alt[i] = 0 else: p = poids[i] if poids_total(sac) + poids[i] < capacite: sac_alt[i] = 1 return sac_alt def valeur_totale(sac): # alternative moins discrimante # return valeur_totale(sac) # alternative plus discrimante # return exp(valeur_totale(sac)) mais attention aux valeurs trop grandes if sac == None: return 0.0 return sum([valeurs[i] if sac[i] == 1 else 0 for i in range(len(produits))]) def distribution_cible(sac): return valeur_totale(sac)**2 def transitionMetropolis(etat): nouv_etat = transition(etat) try: p = min(distribution_cible(nouv_etat) /distribution_cible(etat), 1.0) except ZeroDivisionError: p = 1.0 if random.random() < p: return nouv_etat else: return etat # cette fonction effectue une marche de Metropolis # les transitions sont celle de la chaine de # Markov symetrique, elle sont acceptees conditionnellement # en fonction de la fonction de cout (la "distribution cible") # on garde sous le coude les 10 meilleurses solutions vues au cours de la marche # qu'on retourne ensuite def marcheMetropolis(nb_pas): # 10 meilleures solutions solutions = [None for i in range(10)] # sac vide au depart sac = [0 for i in range(len(produits))] for i in range(nb_pas): sac = transitionMetropolis(sac) maj_meilleures_solutions(solutions, sac) return solutions def maj_meilleures_solutions(solutions, sac): i = 0 while i < 10 and valeur_totale(solutions[i]) < valeur_totale(sac): i += 1 solutions.insert(i, sac) solutions.pop(0) if __name__ == '__main__': # la recherche d'une solution optimale se fait en effectuant # une marche aleatoire sur la chaine nb_pas = 100000 solutions = marcheMetropolis(nb_pas) print map(lambda x: [contenu(x), poids_total(x), valeur_totale(x)], solutions) </file> Vous avez été nombreux à souligner que la solution sur laquelle s'arrête la chaîne de Markov n'ets souvent pas la meilleure, alors qu'une meilleure solution a été visitée peu avant lors de lamarche aléatoire ! C'est une excellente observation. Ce que garantit le procédé de Metropolis c'est de guider la marche dans les voisinages où on trouve les meilleures solutions. Mais il est impossible de dire s'il faut marcher 10000 fois, 9999 fois ou 15000 fois. Une astuce -- qui est implémenter ici -- est de garder sous le coude les 10 meilleures solutions vues au cours de la marche. --- [[miage:metropolis_suite|Retourner au TD]]

miage_solution/solution_knapsack.txt · Last modified: 2017/04/26 15:22 by melancon