Module projet.solvers.SolverHC
module pour le solver Hill Climbing
Expand source code
""" module pour le solver Hill Climbing """
from projet.etape3.Solution import Solution
class SolverHC :
"""
implementation du hillclimbing. Differentes versions.
"""
# attribut
# //////////////////////////////////////////////
__nbSolutionsExplores__ : int = 0
""" metriques pour comparer les solutions : nb de solutions explorees """
# methodes
# //////////////////////////////////////////////
def hilClimbing2(eRef : Solution, nbEssai: int) :
""" implementation du hillclimbing avec plusieurs essais possibles et,
a chaque essai, tirage aleatoire d'une nouvelle solution de depart
:param eRef: solution de depart
:param nbEssai: nb d'essais à faire
:return renverra la meilleure solution trouvee
"""
SolverHC.__nbSolutionsExplores__ = 0
best : Solution = eRef
e : Solution = eRef
bestval : float = eRef.eval()
for i in range(0, nbEssai) :
flag : bool = True
while (flag) :
SolverHC.__nbSolutionsExplores__ = SolverHC.__nbSolutionsExplores__ + 1
flag = False
v : Solution = e.unVoisin()[0]
if (v.eval() < e.eval()) :
# on ameliore
e = v
flag = True
# plus d'amelioration pour cet essai
if (e.eval() < bestval) :
bestval = e.eval()
best = e
# tirage nelle solution pour essai suivant
e = eRef.nelleSolution()
SolverHC.__affMetriques__(best,nbEssai,1)
return best
def hilClimbing(e : Solution, nbEssai : int = None) :
""" implementation du hillclimbing avec un seul ou plusieurs essais possibles
:param e: solution de depart
:param nbEssai: nb d'essais à faire (si param absent alors un seul essai)
:return renverra la meilleure solution trouvee
"""
SolverHC.__nbSolutionsExplores__ = 0
best : Solution = e
bestval : float = e.eval()
flag : bool = True
if nbEssai == None :
while (flag) :
SolverHC.__nbSolutionsExplores__ = SolverHC.__nbSolutionsExplores__ +1
flag = False
v : Solution = e.unVoisin()[0]
if (v.eval() < e.eval()) :
e = v
flag = True
else :
for i in range(0, nbEssai) :
SolverHC.__nbSolutionsExplores__ = SolverHC.__nbSolutionsExplores__ + 1
v : Solution= e.unVoisin()[0]
if (v.eval() < e.eval()) :
e = v
if (e.eval() < bestval) :
bestval = e.eval()
best = e
if nbEssai == None :
SolverHC.__affMetriques__(best,1,2)
else :
SolverHC.__affMetriques__(best,nbEssai,3)
return best
# affichage des metriques
def __affMetriques__(sol : Solution, nbEssais : int, cas :int) :
""" affichage des resultats
:param sol: la solution obtenue par le solver
:param nbEssais: le nb d'essais utilises pour obtenir cette solution
:param cas: le type de solver utilise
-> 1 : HC avec plusieurs essais et tirage aleatoire d'une nelle solution pour chaque essai
-> 2 : HC avec un seul essai
-> 3 : HC avec plusieurs essais mais pas de tirage aleatoire d'une nelle solution
pour chaque essai
"""
if cas == 1 :
print("HC avec plusieurs essais et tirage aleatoire d'une nelle solution pour chaque essai")
else :
if cas == 2 :
print("HC avec un seul essai")
else :
if cas == 3 :
print("HC avec plusieurs essais mais pas de tirage aleatoire d'une nelle solution pour chaque essai")
else :
print("Pas normal !!")
print("\nLa meilleure solution obtenue : "+str(sol)+"=======(arret apres "
+str(nbEssais)+" essais : nb d'etats explores = "
+str(SolverHC.__nbSolutionsExplores__)+")========\n")
Classes
class SolverHC
-
implementation du hillclimbing. Differentes versions.
Expand source code
class SolverHC : """ implementation du hillclimbing. Differentes versions. """ # attribut # ////////////////////////////////////////////// __nbSolutionsExplores__ : int = 0 """ metriques pour comparer les solutions : nb de solutions explorees """ # methodes # ////////////////////////////////////////////// def hilClimbing2(eRef : Solution, nbEssai: int) : """ implementation du hillclimbing avec plusieurs essais possibles et, a chaque essai, tirage aleatoire d'une nouvelle solution de depart :param eRef: solution de depart :param nbEssai: nb d'essais à faire :return renverra la meilleure solution trouvee """ SolverHC.__nbSolutionsExplores__ = 0 best : Solution = eRef e : Solution = eRef bestval : float = eRef.eval() for i in range(0, nbEssai) : flag : bool = True while (flag) : SolverHC.__nbSolutionsExplores__ = SolverHC.__nbSolutionsExplores__ + 1 flag = False v : Solution = e.unVoisin()[0] if (v.eval() < e.eval()) : # on ameliore e = v flag = True # plus d'amelioration pour cet essai if (e.eval() < bestval) : bestval = e.eval() best = e # tirage nelle solution pour essai suivant e = eRef.nelleSolution() SolverHC.__affMetriques__(best,nbEssai,1) return best def hilClimbing(e : Solution, nbEssai : int = None) : """ implementation du hillclimbing avec un seul ou plusieurs essais possibles :param e: solution de depart :param nbEssai: nb d'essais à faire (si param absent alors un seul essai) :return renverra la meilleure solution trouvee """ SolverHC.__nbSolutionsExplores__ = 0 best : Solution = e bestval : float = e.eval() flag : bool = True if nbEssai == None : while (flag) : SolverHC.__nbSolutionsExplores__ = SolverHC.__nbSolutionsExplores__ +1 flag = False v : Solution = e.unVoisin()[0] if (v.eval() < e.eval()) : e = v flag = True else : for i in range(0, nbEssai) : SolverHC.__nbSolutionsExplores__ = SolverHC.__nbSolutionsExplores__ + 1 v : Solution= e.unVoisin()[0] if (v.eval() < e.eval()) : e = v if (e.eval() < bestval) : bestval = e.eval() best = e if nbEssai == None : SolverHC.__affMetriques__(best,1,2) else : SolverHC.__affMetriques__(best,nbEssai,3) return best # affichage des metriques def __affMetriques__(sol : Solution, nbEssais : int, cas :int) : """ affichage des resultats :param sol: la solution obtenue par le solver :param nbEssais: le nb d'essais utilises pour obtenir cette solution :param cas: le type de solver utilise -> 1 : HC avec plusieurs essais et tirage aleatoire d'une nelle solution pour chaque essai -> 2 : HC avec un seul essai -> 3 : HC avec plusieurs essais mais pas de tirage aleatoire d'une nelle solution pour chaque essai """ if cas == 1 : print("HC avec plusieurs essais et tirage aleatoire d'une nelle solution pour chaque essai") else : if cas == 2 : print("HC avec un seul essai") else : if cas == 3 : print("HC avec plusieurs essais mais pas de tirage aleatoire d'une nelle solution pour chaque essai") else : print("Pas normal !!") print("\nLa meilleure solution obtenue : "+str(sol)+"=======(arret apres " +str(nbEssais)+" essais : nb d'etats explores = " +str(SolverHC.__nbSolutionsExplores__)+")========\n")
Methods
def hilClimbing(e: Solution, nbEssai: int = None)
-
implementation du hillclimbing avec un seul ou plusieurs essais possibles
:param e: solution de depart
:param nbEssai: nb d'essais à faire (si param absent alors un seul essai)
:return renverra la meilleure solution trouvee
Expand source code
def hilClimbing(e : Solution, nbEssai : int = None) : """ implementation du hillclimbing avec un seul ou plusieurs essais possibles :param e: solution de depart :param nbEssai: nb d'essais à faire (si param absent alors un seul essai) :return renverra la meilleure solution trouvee """ SolverHC.__nbSolutionsExplores__ = 0 best : Solution = e bestval : float = e.eval() flag : bool = True if nbEssai == None : while (flag) : SolverHC.__nbSolutionsExplores__ = SolverHC.__nbSolutionsExplores__ +1 flag = False v : Solution = e.unVoisin()[0] if (v.eval() < e.eval()) : e = v flag = True else : for i in range(0, nbEssai) : SolverHC.__nbSolutionsExplores__ = SolverHC.__nbSolutionsExplores__ + 1 v : Solution= e.unVoisin()[0] if (v.eval() < e.eval()) : e = v if (e.eval() < bestval) : bestval = e.eval() best = e if nbEssai == None : SolverHC.__affMetriques__(best,1,2) else : SolverHC.__affMetriques__(best,nbEssai,3) return best
def hilClimbing2(eRef: Solution, nbEssai: int)
-
implementation du hillclimbing avec plusieurs essais possibles et, a chaque essai, tirage aleatoire d'une nouvelle solution de depart
:param eRef: solution de depart
:param nbEssai: nb d'essais à faire
:return renverra la meilleure solution trouvee
Expand source code
def hilClimbing2(eRef : Solution, nbEssai: int) : """ implementation du hillclimbing avec plusieurs essais possibles et, a chaque essai, tirage aleatoire d'une nouvelle solution de depart :param eRef: solution de depart :param nbEssai: nb d'essais à faire :return renverra la meilleure solution trouvee """ SolverHC.__nbSolutionsExplores__ = 0 best : Solution = eRef e : Solution = eRef bestval : float = eRef.eval() for i in range(0, nbEssai) : flag : bool = True while (flag) : SolverHC.__nbSolutionsExplores__ = SolverHC.__nbSolutionsExplores__ + 1 flag = False v : Solution = e.unVoisin()[0] if (v.eval() < e.eval()) : # on ameliore e = v flag = True # plus d'amelioration pour cet essai if (e.eval() < bestval) : bestval = e.eval() best = e # tirage nelle solution pour essai suivant e = eRef.nelleSolution() SolverHC.__affMetriques__(best,nbEssai,1) return best