Busca tabú

La busca tabú és un método d'optimisació matemàtica, pertanyent a la classe de tècniques de busca local. La busca tabú aumenta el rendiment del método de busca local per mig de l'us d'estructures de memòria: una volta que una potencial solució és determinada, li la marca com "tabú" de modo que l'algoritme no torne a visitar eixa possible solució. La busca tabú és atribuïda a Fred Glover.

Detalls Bàsics

La busca tabú és un algoritme metaheurístico que pot utilisar-se per a resoldre problemes d'optimisació combinatòria, tals com el problema del viajante (TSP, de l'anglés Travelling Salesman Problem). La busca tabú utilisa un procediment de busca local o per veïnats per a moure's iterativamente des d'una solució $x$ cap a una solució $x^{\prime }$ en el veïnat de $x$, fins a satisfer algun criteri de parada. Per a poder explorar regions del espai de busca que serien deixades de costat pel procediment de busca local (vore òptim local), la busca tabú modifica l'estructura de veïns per a cada solució a mida que la busca progressa. Les solucions admeses per a $N^{*}(x)$, el nou veïnat, són determinades per mig de l'us d'estructures de memòria. La busca llavors progressa movent-se iterativamente d'una solució $x$ cap a una solució $x^{\prime }$ en $N^{*}(x)$.

Potser l'estructura de memòria més important usada per a determinar les solucions permeses a un $N^{*}(x)$, siga la llistatabú. En la seua forma més simple, una llistatabú és una memòria de curt determini que conté les solucions que varen ser visitades en el passat recent (menys de $n$ iteraciones arrere, a on $n$ és el número de solucions prèvies que van a ser almagasenades ($n$ també és cridat el tenor del tabú)). La busca tabú exclou les solucions en la llistatabú de $N^{*}(x)$. Una variació de la llistatabú prohibix solucions que tenen certs atributs (i.i., solucions al problema del viajante de comerç (TSP) que inclouen arestes no desijades) o previndre certs moviments (i.i., un arc que va ser agregat a un recorregut de el TSP no pot ser eliminat en els següents $n$ moviments). Els atributs seleccionats de les solucions recentment visitades són denominats "tabú-actius." Les possibles solucions que continguen elements tabú-actius són "tabú".

Les llestes tabú que contenen atributs poden ser més efectives per a alguns dominis, pese a que presenten un nou problema. Quan solament un atribut és marcat com a tabú, açò per lo general resulta en que més d'una solució és marcada com a tabú. Algunes d'estes solucions, que ara deuen ser evitades, podrien ser d'excelent calitat i no serien visitades. Per a mitigar este problema, s'introduïxen els "criteris d'aspiració": estos poden modificar l'estat de tabú d'una solució, per lo tant incloent l'abans exclosa solució en el conjunt de solucions permeses. Un criteri d'aspiració molt utilisat és admetre solucions que són millors que la millor solució coneguda al moment.

Eixemple: Problema del Viajante

El problema del viajante (TSP), és comunament utilisat per a mostrar la funcionalitat de la busca tabú. El TSP requerix buscar un orde en el qual viajar entre ciutats, tal que la distància recorreguda siga minimisada. Per eixemple, si les ciutats A i B estan una al costat de l'atra, mentres que la ciutat C està més llunt, la distància total recorreguda serà més curta si les ciutats A i B són visitades una despuix de l'atra, abans de visitar C. Com trobar un orde òptim per a visitar les ciutats en el TSP és un problema NP-difícil. els métodos d'aproximació basats en heurístiques són útils per a conseguir la optimalidad.

La busca tabú pot utilisar-se per a trobar una solució satisfactòria per a el TSP. Primer, la busca tabú comença en una solució inicial, que pot ser generada en l'algoritme del veí més propenc. Per a crear noves solucions, l'orde en que dos ciutats són visitades és intercanviat. La distància total recorreguda entre totes les ciutats és utilisada per a jujar quànt millor és una solució que una atra. Per a previndre cicles i per a eixir dels òptims locals, una solució és agregada a la llistatabú si és que és acceptada en N*(x), el veïnat de solucions. Es continuen creant noves solucions fins que es complix algun criteri de parada, com per eixemple un número arbitrari de iteraciones. Una volta que la busca tabú es deté, la millor solució és aquella que la distància total de la qual a recórrer entre les ciutats és la menor.

Vore també

• Simulated annealing
• Algoritmes genètics
• GRASP, o Greedy Randomized Adaptive Search Procedure (Procediment de Busca Goloso, Aleatori i Adaptatiu)
• Busca local dirigida

Bibliografia

• Glover, F. and M. Estany. (1997). Tabu Search. Kluwer, Norwell, MA.
• Glover, F. "Tabu Search — Part I", ORSA Journal on Computing 1989 1: 3, 190-206.
• Glover, F. "Tabu Search — Part II", ORSA Journal on Computing 1990 2: 1, 4-32.
• Cvijovic, D.; Klinowski, J. "Taboo search - an approach to the multiple minima problem". Science 1995 267, 664-666.