Sommaire

Recherche tabou

La recherche tabou est une amélioration de la recherche par descente de gradient. En effet, cette dernière reste bloquée dans le premier optimum rencontré.

Dans le cas de la recherche tabou, à chaque itération, on se déplace vers le meilleur voisin même s’il est moins bon que la solution actuelle. De plus, on retient la liste des positions déjà visitées, qui ne sont plus sélectionnables (d’où le nom, les anciennes solutions devenant taboues).

De cette façon, l’algorithme se "promène" dans l’espace de solution et ne s’arrête pas au premier optimum découvert. On s’arrête lorsque tous les voisins ont été visités, au bout d’un nombre d’itérations maximal décidé ou lorsqu’aucune amélioration suffisante n’est détectée en x coups.

images/05DP09.png

La principale difficulté de cette recherche est le choix de la longueur de la liste de positions taboues. En effet, si cette liste est trop courte, on risque de boucler autour des mêmes positions. Au contraire, une liste trop longue peut empêcher de tester d’autres chemins partant d’une même solution potentielle. Il n’existe cependant aucun moyen de connaître la longueur de la liste idéale, elle doit être choisie de manière purement empirique.

Cette liste est souvent implémentée sous la forme d’une ...