Cours4 - Algorithmes de Recherche Locale (PDF)

Les algorithmes de recherche locale La recherche Tabou 1  La méthode de descente V(s) A chaque itération, la meilleure solution s ’ de V(s) est sélectionnée Carences...

Les algorithmes de recherche locale La recherche Tabou 1  La méthode de descente V(s) A chaque itération, la meilleure solution s ’ de V(s) est sélectionnée Carences et solutions Taille du voisinage ⇒ exploration partielle Blocage en optima locaux ⇒ autorisation de l ’acceptation de mouvements de dégradation Recherche Tabou 2  La méthode de recherche Tabou (RT) Glover (1986), Hansen (1986) Acceptation de solutions moins bonnes que la solution courante Risque de « cycler » Liste de tabou : solutions interdites pour un nombre d ’itérations Critères d ’aspiration : conditions permettant de lever le statut tabou d ’une solution 3  La méthode de recherche Tabou : idee de base Tendance dans les années 70 : techniques d’amélioration des solutions par recherche locale 1983 : une nouvelle heuristique apparaît, le Recuit Simul 1986 : La RT est Développée dans un cadre particulier par Glover (et indépendamment par Hansen) puis généralisée en 1989-90. 4 é  La méthode de recherche Tabou : idee de base Développée dans un cadre particulier par Glover en 1986 (et indépendamment par Hansen en 1986) puis généralisée en 1989-90. Comme la descente, se déplace d’1 solution courante s vers une solution voisine s’ telle que mins’’∈N(s) F(s’’). Si optimum local rencontré, déplacement vers le “moins mauvais” des voisins : dégradation de la fonction objectif Mais risque de cycler autour de l’optimum local en faisant l’opération inverse à l’itération suivante!!! Idée : interdire la dernière opération Mais la « vallée » de l’optimum local est « profonde » : plusieurs itérations pour s’en extraire Idée : garder en mémoire les dernières solutions visitées et interdire le retour vers celles-ci pour un nombre fixé d’itérations 5  La méthode de recherche Tabou : mise en œuvre Dans la pratique : conservation à chaque étape d’une ou plusieurs liste T de solutions « Taboues » 2 alternatives : Une liste contient les solutions interdites (coûteux en place mémoire) OU Une liste des mouvements interdits (qui ramènent vers ces solutions déjà visitées Avantages : prend moins de place mémoire élimine plus de solutions que celles visitées effectivement Généralement les listes sont gérées en FIFO (first in first out) 6  La méthode de recherche Tabou : schéma général Configuration initiale s Liste tabou initiale vide Nouvelle configuration courante s=t Perturbation de s suivant N mouvements non tabous; Évaluation des N voisins Insertion du mouvement t→s dans la Sélection du meilleur voisin t liste tabou circulaire amélioration observée OUI NON stop 7 La méthode de recherche Tabou : schéma général 8  La méthode de recherche Tabou : aspiration Liste tabou des mouvements interdits élimine plus de solutions que celles visitées effectivement : + efficace que la liste des solutions taboues mais élimine éventuellement de très bonnes solutions !!! Idée : définition d’une fonction d’aspiration Possibilité de lever l’interdiction pour une solution si elle parait « prometteuse » permet d’explorer une nouvelle région voisine de s si s’ ∈ N(s), s’ ∈T, telle que F(s’) ≤ A F(s) alors s’ redevient candidate 9  La méthode de recherche Tabou : aspiration f(s) A(z) mouvement Tabou f(s’)