Re: Formulation formelle

[^] # Re: Formulation formelle

Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) le 22 juin 2025 à 15:08. En réponse au message programme et algo de tri. Évalué à 9.

Le code est en deux parties. Un premier fichier qui me génère une liste d'élèves. Pour vous ça permettra de voir le format des données à produire pour faire tourner le code.

#!/usr/bin/env python3
"""Ce programme créé une liste (aléatoire) d'élèves qui sera 
lue par le programme suivant qui optimisera la répartition
des étudiants en classes.
INTERET : permet de comprendre comment les données sont
structurées dans le programme suivant.
USAGE : Lancer le code suivi du nom du fichier dans lequel les
données seront écrites. 
Exemple : python3 createList.py eleves.dat"""
import sys
import numpy as np
nbEleve = 170
nbLV2Esp = 40
nbFoot = 15
def writeEleve(fout,n,sexe,espagnol,foot):
 """Ecrit la liste des élèves dans le descripteur de fichier "fout".
 C'est là qu'il faut faire d'éventuelles modifications pour rajouter 
 des options, etc."""
 fout.write("%7d%4d%7d%5d\n"%(n,sexe,espagnol,foot))
 return n+1
if __name__ == "__main__":
 try:
 fout = open(sys.argv[1],"w")
 except:
 print("Run this code followed by the name of the file where you intend to write")
 exit()
 fout.write("#Numéro sexe espagnol foot\n") #Commentaire en tête de fichier
 n=0
 nF=0
 nE=0
 """ le fichier est structuré ainsi :
 D'abord les footbaleurs, puis les hispanisant, suivi des autres."""
 while nF < nbFoot :
 foot = 1
 espagnol = 0
 sexe=int(np.random.rand()*2) # donne 0, ou 1 !
 n=writeEleve(fout,n,sexe,espagnol,foot)
 nF+=1
 while nE < nbLV2Esp :
 foot = 0
 espagnol = 1
 sexe=int(np.random.rand()*2)
 n=writeEleve(fout,n,sexe,espagnol,foot)
 nE+=1 
 while n < nbEleve :
 foot = 0
 espagnol = 0
 sexe=int(np.random.rand()*2)
 n=writeEleve(fout,n,sexe,espagnol,foot)
 fout.close()

Voici le code qui applique l'algorithme.

#!/usr/bin/env python3
import sys
import numpy as np
""" Ce programme consomme une liste d'élèves (en argument) avec leurs options.
Il les répartis ensuite entre classe en utilisant l'algorithme de 
Monte-Carlo Metropolis.
Exemple : python3 metropolis.py eleves.dat
"""
def readList(fname):
 """ Lis le fichier dont le nom est fname (formaté en colonnes de chiffres)
 et retourne une matrice (de type np.array) dont chaque ligne correspont 
 à un élève et à ses options (0 ou 1 selon que l'option est choisie)."""
 data = np.loadtxt(fname,dtype=int)
 return data
class classe:
 """Une structure permettant de gérer les classes."""
 def __init__(self,ldata):
 """ création d'une classe vide,
 ldata est la liste complète des élèves du niveau de cette classe."""
 self.nbMembres = 0
 self.nbFemelles = 0
 self.nbMales = 0
 self.nbEspagnoles = 0
 self.nbFoot = 0
 self.listMembres = [] # Liste des identifiants des élèves de la classe
 self.ldata=ldata # Liste de l'ensemble des données sur TOUS les élèves
 def __iadd__(self,ide):
 """ Ajoute l'élève identifié par son numéro ide à la classe """
 self.listMembres.append(self.ldata[ide][0])
 self.nbMembres += 1
 if self.ldata[ide][1] == 0 :
 self.nbFemelles += 1
 else :
 self.nbMales += 1
 self.nbEspagnoles += self.ldata[ide][2]
 self.nbFoot += self.ldata[ide][3]
 return self
 def __isub__(self,ide):
 """ Retire l'élève identifier par son numéro à la classe """
 self.listMembres.remove(self.ldata[ide][0])
 self.nbMembres -= 1
 if self.ldata[ide][1] == 0 :
 self.nbFemelles -= 1
 else :
 self.nbMales -= 1
 self.nbEspagnoles -= self.ldata[ide][2]
 self.nbFoot -= self.ldata[ide][3]
 return self
 """ Deux méthode permettant de décrire la classe """
 def __str__(self):
 s="class nbEleves %d nbFemelles %d nbEspagnoles %d nbFoots %d"%(self.nbMembres,self.nbFemelles,self.nbEspagnoles,self.nbFoot)
 return s
 def __repr(self):
 return self.__str__()
def deplaceEleve(nouvelleClasse,ide,listeClasse,ldata):
 """ Fonction qui déplace un élève d'une classe à une autre : 
 nouvelleClasse et le numéro de la nouvelle classe dans
 listeClasse
 ide est le numéro de l'élève dans ldata """
 if ldata[ide][4] != None : # Vérifie que l'élève avait déjà été affecté à une classe auparavant
 listeClasse[ldata[ide][4]] -= ide
 if nouvelleClasse != None : # Vérifie que l'affectation se fait bien vers une nouvelle classe
 listeClasse[nouvelleClasse] += ide
 ldata[ide][4] = nouvelleClasse
def cout(listeClasse,ldata,nbEsp):
 """ Fonction de cout
 C'est la fonction essentielle du processus. C'est elle qui conditionne 
 la réussite du processus d'affectation. Elle doit augmenter quand un 
 élève n'est pas affecté conformément aux critère choisis. Elle doit 
 décroître quand les critères sont vérifiés.
 Actuellement 5 critères :
 a : les classes doivent toutes avoir le même nombre d'élèves.
 b : autant d'hispanisant dans chacune des classes qui en ont
 c : ceux qui font du foot doivent impérativement être dans la classe 3
 d : les hispanisants sont dans les classes 5 et 6
 e : tous les élèves doivent se voir affecter une classe
 """
 nbE = len(ldata) # nombre d'élèves
 nbC = len(listeClasse) # nombre de classes
 C = 0
 a = 1
 b=0.5
 c=10
 d=4
 e=50
 for i,classe in enumerate(listeClasse):
 ### équilibre des classes
 C += a*(classe.nbMembres-nbE/nbC)**2
 ### foot en classe 3 (#2)
 if i ==2 :
 C -= c*classe.nbFoot
 #print(i,C)
 else :
 C += c*classe.nbFoot
 #print(i,C)
 if i > 3 :
 C -= d*classe.nbEspagnoles
 else :
 C += d*classe.nbEspagnoles
 ### équilibre espagnoles
 C += b * (listeClasse[4].nbEspagnoles-listeClasse[5].nbEspagnoles)**2
 ### élève non affecté
 for i in range(nbE):
 if(ldata[i][4] == None):
 C+= e
 return C
def metropolis(lClasses,ldata,nbEsp,oldC,beta):
 # Choisie un élève au hasard, et une classe au hasard,
 # affecte l'élève dans la classe,
 # calcul la fonction de coût,
 # compare à l'ancienne valeure,
 # choisi de valider l'affectation ou de revenir à l'état précédent
 ide = int(np.random.rand()*len(ldata))
 cl = int(np.random.rand()*len(lClasses))
 #oldCl = len(lClasses)+1
 #if (ldata[ide][4] != None):
 oldCl = ldata[ide][4]
 deplaceEleve(cl,ide,lclasses,ldata)
 nC = cout(lClasses,ldata,nbEsp)
 p = np.random.rand()
 if np.exp(beta*(nC-oldC)) < p :
 return 1,lClasses,ldata,nC
 else :
 #print("ancien - nouveau",oldC,nC)
 deplaceEleve(oldCl,ide,lclasses,ldata)
 return 0,lClasses,ldata,oldC
def mainMetropolis(lClasses,ldata,nbEsp,oldC) :
 """ Applique l'algorithme de MC Metropolis
 Nloop fois. Plus l'affection est complexe, plus Nloop doit être grand.
 Si tout va bien, à la fin, les élèves sont affectés dans les classes 
 conformément aux critères."""
 C = cout(lClasses,ldata,nbEsp)
 # Paramètres de l'algorithme
 beta = 1 # conditionne la distribution de Boltzmann
 Nloop = 10000 # Nombre d'itérations à réaliser
 # Le taux d'acceptation des modifications des classes
 # doit avoisinner les 50 %. En fonction de ce taux (moyenné)
 # le paramètre Beta va être modifié pour faire tendre
 # le taux vers 50%
 accept_min=0.4 
 incr = 1.25
 accept_max=0.6
 decr = 0.8
 accept = 0.5
 mix = 0.95 # Paramètre pour calculer la moyenne glissante exponentielle :-)
 # Plus c'est grand, plus la moyenne est calculée sur un grand nombre
 #de configurations précédentes.
 for i in range(Nloop):
 acc,lClasses,ldata,C = metropolis(lClasses,ldata,nbEsp,C,beta)
 accept = (1-mix)*acc + mix*accept
 if accept < accept_min :
 beta *= incr
 if accept > accept_max :
 beta *= decr
 print(i,accept,C)
 return lClasses,ldata
if __name__ == "__main__":
 """ Lecture du fichier des élèves """
 try:
 data = readList(sys.argv[1])
 except:
 print("Run this code followed by the name of the file where you intend to read students data")
 exit()
 #print("OK\n ",data)
 ldata = []
 nbEsp = 0
 for e in data :
 le = list(e)
 le.append(None)
 ldata.append(le)
 nbEsp += e[2]
 #print(ldata)
 ##############
 ### create classes 
 C0 = classe(ldata)
 C1 = classe(ldata)
 C2 = classe(ldata)
 C3 = classe(ldata)
 C4 = classe(ldata)
 C5 = classe(ldata)
 print(C0)
 lclasses=[C0,C1,C2,C3,C4,C5]
 ###############
 ### Affectation manuelle d'élèves dans des classes
 ### Ici j'ai fait n'importe quoi, meilleur est
 ### l'état initial, plus rapide sera le succès final.
 print(lclasses[1])
 deplaceEleve(2,0,lclasses,ldata)
 deplaceEleve(2,1,lclasses,ldata)
 deplaceEleve(2,1,lclasses,ldata)
 deplaceEleve(2,3,lclasses,ldata)
 print(ldata[:5])
 C = cout(lclasses,ldata,nbEsp)
 print(C)
 deplaceEleve(2,2,lclasses,ldata)
 deplaceEleve(2,4,lclasses,ldata)
 deplaceEleve(2,5,lclasses,ldata)
 deplaceEleve(2,6,lclasses,ldata)
 C = cout(lclasses,ldata,nbEsp)
 print(C) 
 deplaceEleve(2,7,lclasses,ldata)
 deplaceEleve(2,8,lclasses,ldata)
 deplaceEleve(2,9,lclasses,ldata)
 deplaceEleve(2,10,lclasses,ldata)
 deplaceEleve(1,16,lclasses,ldata)
 deplaceEleve(1,17,lclasses,ldata)
 deplaceEleve(1,18,lclasses,ldata)
 deplaceEleve(1,19,lclasses,ldata)
 C = cout(lclasses,ldata,nbEsp)
 print(C) 
 #############
 ### OPtimisation
 mainMetropolis(lclasses,ldata,nbEsp,C)
 ### C'est fini
 for classe in lclasses:
 print(classe)
 # On peut rajouter une méthode dans "classe"
 # pour imprimer plus de détails. Par exemple la liste
 # des élèves de la classe.

J'ai essayé d'ajouter beaucoup de commentaires pour aider... J'espère que ça sera suffisant car mon code est assez brouillon.

« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace