Module projet.solvers.SolverTabou

module pour le solver Tabou

Expand source code
""" module pour le solver Tabou """

import sys

from projet.etape3.Solution import Solution

class SolverTabou :
    """ 
    Implementation du tabou 
    """ 
    
    #    attribut
    #    //////////////////////////////////////////////
    __nbSolutionsExplores__ : int = 0 
    """ metriques pour comparer les solutions : nb de solutions explorees """
    
    #    methodes
    #    //////////////////////////////////////////////
    def tabou(e : Solution, nb : int) :
        """  implementation du tabou (liste de tabou non limitee)
        
        :param e: solution de depart
        
        :param nb: nb d'essais
        
        :return renverra la meilleure solution trouvee d'apres l'algo du tabou
        """  
        
        em : Solution = e
        bestval : float = e.eval() #    meilleure valeur de reference
        courant : Solution = e
        cval : float = courant.eval() #    valeur courante
        T : list = []
        
        for i in range(0, nb) :
            
            SolverTabou.__nbSolutionsExplores__ = SolverTabou.__nbSolutionsExplores__ +1
            voisins = courant.lesVoisins()
            y : Solution = SolverTabou.__getBest__(voisins, T)
            if(y==None) :
                SolverTabou.__affMetriques__(em,nb,T) 
                return em
            
            yval : float = y.eval()
            if(yval>=cval) :
                #    le voisin est pire ou egal a la valeur courante
                #    ==> le courant devient tabou
                T.append(courant)
            if(yval<bestval) :
            
                #    le voisin est meilleur que le meilleur de reference
                #    ===> il devient le nouveau meilleur
                em=y
                bestval=yval
            
            #    ds ts les cas le voisin devient le nouveau courant
            courant=y
            cval=yval
        
        SolverTabou.__affMetriques__(em,nb,T) 
        return em
    
    
    #    recuperation du meilleur des voisins qui ne soit pas tabou
    def __getBest__(voisins : list, T : list) :
        """ methode de recuperation du meilleur voisin ds la liste des voisins qui n'est pas tabou
        
        :param voisins: liste des voisins
        
        :param T: liste des tabous
        """
        
        best : Solution = None
        val : float = sys.maxsize
        for e in voisins :
            
            v : float = e.eval()
            if (v < val) and (e not in T) :
                
                best = e
                val = v
            
        
        return best
    
    
    #    affichage des metriques
    def __affMetriques__(sol : Solution, nbEssais : int, T :list) :
        """ affichage de la solution
        
        :param sol: la solution obtenue par le solver
        
        :param nbEssais: le nb d'essais utilises pour obtenir cette solution
        
        :param T: liste des tabous
        """
        
        print("\t Il y a " +str(len(T))+" tabou(s) :")
        print("\nLa meilleure solution obtenue : "+str(sol)+"=======(arret apres "
                           +str(nbEssais)+" essais : nb d'etats explores = "
                           +str(SolverTabou.__nbSolutionsExplores__)+")========\n")
    

Classes

class SolverTabou

Implementation du tabou

Expand source code
class SolverTabou :
    """ 
    Implementation du tabou 
    """ 
    
    #    attribut
    #    //////////////////////////////////////////////
    __nbSolutionsExplores__ : int = 0 
    """ metriques pour comparer les solutions : nb de solutions explorees """
    
    #    methodes
    #    //////////////////////////////////////////////
    def tabou(e : Solution, nb : int) :
        """  implementation du tabou (liste de tabou non limitee)
        
        :param e: solution de depart
        
        :param nb: nb d'essais
        
        :return renverra la meilleure solution trouvee d'apres l'algo du tabou
        """  
        
        em : Solution = e
        bestval : float = e.eval() #    meilleure valeur de reference
        courant : Solution = e
        cval : float = courant.eval() #    valeur courante
        T : list = []
        
        for i in range(0, nb) :
            
            SolverTabou.__nbSolutionsExplores__ = SolverTabou.__nbSolutionsExplores__ +1
            voisins = courant.lesVoisins()
            y : Solution = SolverTabou.__getBest__(voisins, T)
            if(y==None) :
                SolverTabou.__affMetriques__(em,nb,T) 
                return em
            
            yval : float = y.eval()
            if(yval>=cval) :
                #    le voisin est pire ou egal a la valeur courante
                #    ==> le courant devient tabou
                T.append(courant)
            if(yval<bestval) :
            
                #    le voisin est meilleur que le meilleur de reference
                #    ===> il devient le nouveau meilleur
                em=y
                bestval=yval
            
            #    ds ts les cas le voisin devient le nouveau courant
            courant=y
            cval=yval
        
        SolverTabou.__affMetriques__(em,nb,T) 
        return em
    
    
    #    recuperation du meilleur des voisins qui ne soit pas tabou
    def __getBest__(voisins : list, T : list) :
        """ methode de recuperation du meilleur voisin ds la liste des voisins qui n'est pas tabou
        
        :param voisins: liste des voisins
        
        :param T: liste des tabous
        """
        
        best : Solution = None
        val : float = sys.maxsize
        for e in voisins :
            
            v : float = e.eval()
            if (v < val) and (e not in T) :
                
                best = e
                val = v
            
        
        return best
    
    
    #    affichage des metriques
    def __affMetriques__(sol : Solution, nbEssais : int, T :list) :
        """ affichage de la solution
        
        :param sol: la solution obtenue par le solver
        
        :param nbEssais: le nb d'essais utilises pour obtenir cette solution
        
        :param T: liste des tabous
        """
        
        print("\t Il y a " +str(len(T))+" tabou(s) :")
        print("\nLa meilleure solution obtenue : "+str(sol)+"=======(arret apres "
                           +str(nbEssais)+" essais : nb d'etats explores = "
                           +str(SolverTabou.__nbSolutionsExplores__)+")========\n")

Methods

def tabou(e: Solution, nb: int)

implementation du tabou (liste de tabou non limitee)

:param e: solution de depart

:param nb: nb d'essais

:return renverra la meilleure solution trouvee d'apres l'algo du tabou

Expand source code
def tabou(e : Solution, nb : int) :
    """  implementation du tabou (liste de tabou non limitee)
    
    :param e: solution de depart
    
    :param nb: nb d'essais
    
    :return renverra la meilleure solution trouvee d'apres l'algo du tabou
    """  
    
    em : Solution = e
    bestval : float = e.eval() #    meilleure valeur de reference
    courant : Solution = e
    cval : float = courant.eval() #    valeur courante
    T : list = []
    
    for i in range(0, nb) :
        
        SolverTabou.__nbSolutionsExplores__ = SolverTabou.__nbSolutionsExplores__ +1
        voisins = courant.lesVoisins()
        y : Solution = SolverTabou.__getBest__(voisins, T)
        if(y==None) :
            SolverTabou.__affMetriques__(em,nb,T) 
            return em
        
        yval : float = y.eval()
        if(yval>=cval) :
            #    le voisin est pire ou egal a la valeur courante
            #    ==> le courant devient tabou
            T.append(courant)
        if(yval<bestval) :
        
            #    le voisin est meilleur que le meilleur de reference
            #    ===> il devient le nouveau meilleur
            em=y
            bestval=yval
        
        #    ds ts les cas le voisin devient le nouveau courant
        courant=y
        cval=yval
    
    SolverTabou.__affMetriques__(em,nb,T) 
    return em