Recherche taboue

La recherche taboue est une méthode de l'optimisation mathématique , appartenant à la classe des techniques locales de la recherche . La recherche taboue augmente l'exécution d'une méthode locale de recherche en employant des structures de mémoire : une fois qu'une solution potentielle a été déterminée, elle est marquée comme " ; " tabou du ; (ainsi le nom) de sorte que l'algorithme ne visite pas cette possibilité à plusieurs reprises. La recherche taboue est généralement attribuée au gantier de Fred.

Détails de base

La recherche taboue emploie un procédé de gens du pays ou de recherche de voisinage pour se déplacer itérativement d'une solution $x$ à un $x'< de solution/à math> à proximité de x, jusqu'à ce qu'un certain critère de arrêt ait été satisfait. Pour explorer des régions de l'espace de recherche de qui serait laissé encore inconnu par le procédé de recherche local (voir l'optimalité locale ), la recherche taboue modifie la structure de voisinage de chaque solution pendant que la recherche progresse. Les solutions admises à N^*(x), le nouveau voisinage, sont déterminées par l'utilisation des structures de mémoire spéciales. La recherche progresse alors en se déplaçant itérativement d'une solution x à un x' de solution dans N^*(x) .$

Peut-être le type le plus important de mémoire à court terme pour déterminer les solutions dans $N^*(x)$ , aussi celui qui donne son nom à la recherche taboue, est l'utilisation d'une liste taboue. Sous sa forme plus simple, une liste taboue contient les solutions qui ont été visitées dans le passé récent (moins que $n$ se déplace il y a, où $n$ est la tenure taboue). Des solutions dans la liste taboue sont exclues de $N^*(x)$ . D'autres structures taboues de liste interdisent les solutions qui ont certains attributs (par exemple, solutions au problème (TSP) de représentant de commerce de qui incluent les arcs indésirables) ou empêchent certains mouvements (par exemple un arc qui a été ajouté à une excursion de TSP ne peut pas être enlevé dans les prochains mouvements de $n$ ). Les attributs choisis dans les solutions ont récemment visité sont marqués " ; tabou-active" ;. Les solutions qui contiennent les éléments tabou-actifs sont " ; tabu" ;. Ce type de mémoire à court terme s'appelle également le " ; recency-based" ; mémoire.

Les listes taboues contenant des attributs sont beaucoup plus efficaces, bien qu'elles soulèvent un nouveau problème. Quand on interdit un attribut simple comme tabou, ceci a typiquement comme conséquence plus d'une solution étant taboue. Certaines de ces solutions qui doivent maintenant être évitées pourraient être d'excellente qualité et ne pourraient pas avoir été visitées. Pour atténuer ce problème, " ; criteria" d'aspiration ; sont présentés : ceux-ci dépassent l'état tabou d'une solution, de ce fait comprenant la solution autrement-exclue dans l'ensemble permis. Un critère utilisé généralement d'aspiration est de permettre les solutions qui sont meilleures que la meilleure solution courant-connue.

Méthodes relatives

de recuit simulé par
Algorithmes génétiques
PRISE, ou procédé de recherche adaptative randomisé avide
Optimisation de colonie de fourmi de
Optimisation d'essaim de particules de
méthode de Croix-entropie de
Recherche locale guidée par
Recherche d'harmonie de

Plus de liens

Une introduction à la recherche taboue

Random links: