Principe
Il s’agit d’un algorithme à solution unique. Tabu search fonctionne exactement comme la Recherche Locale, sauf qu’afin d’éviter de rester bloquer dans un optimum local, on va maintenir une liste tabou qui est un vecteur de taille k FIFO. Ce vecteur va retenir les k dernières solutions sur lesquelles nous somme passés. Les solutions stockées dans ce vecteur sont “tabou” et l’algorithme en peut plus repasser dessus. Cela pousse l’algorithme à aller explorer des zones qui sont moins optimale.
Warning
Certains problèmes peuvent avoir solutions qui ont énormément de variables. Cela va poser problème pour les stocker dans notre taboo list. Ainsi pour éviter de stocker des grosses quantité de données, on va plutôt stocker le mouvement pour atteindre la solution ce qui est beaucoup plus compacte.
Variables
- k (la longueur de liste tabou), ni trop longue ni trop courte
- It (nombre d’itération)
- Voisinage (aka le mouvement) #metaheuristiques metaheuristiques_algo_solution_unique