La búsqueda tabú es un método de optimización matemática, perteneciente a la clase de técnicas de búsqueda local. La búsqueda tabú aumenta el rendimiento del método de búsqueda local mediante el uso de estructuras de memoria: una vez que una potencial solución es determinada, se la marca como "tabú" de modo que el algoritmo no vuelva a visitar esa posible solución.
Vimos en clase un ejemplo "El problema del Viajante", aqui les dejo la definicion y la explicacion de este problema que se puede resolver con busqueda Tabú.
Problema del Viajante
El problema del viajante (TSP), es comúnmente utilizado para mostrar la funcionalidad de la búsqueda tabú.
El TSP requiere buscar un orden en el cual viajar entre ciudades, tal que la distancia recorrida sea minimizada.
Por ejemplo, si las ciudades A y B están una al lado de la otra, mientras que la ciudad C está más lejos, la distancia total recorrida será más corta si las ciudades A y B son visitadas una después de la otra, antes de visitar C.
Como encontrar un orden óptimo para visitar las ciudades en el TSP es un problema NP-difícil. los métodos de aproximación basados en heurísticas son útiles para lograr la optimalidad.
La búsqueda tabú puede utilizarse para encontrar una solución satisfactoria para el TSP. Primero, la búsqueda tabú comienza con una solución inicial, que puede ser generada con el algoritmo del vecino más cercano.
Para crear nuevas soluciones, el orden en que dos ciudades son visitadas es intercambiado. La distancia total recorrida entre todas las ciudades es utilizada para juzgar cuanto mejor es una solución de otra. Para prevenir ciclos y para salir de los óptimos locales, una solución es agregada a la lista tabú si es que es aceptada en N*(x), el vecindario de soluciones.
Se continúan creando nuevas soluciones hasta que algún criterio de parada, como por ejemplo un número arbitrario de iteraciones, es encontrado.
Una vez que la búsqueda tabú se detiene, la mejor solución es aquella que cuya distancia total a recorrer entre las ciudades es la menor.
Referencias.... +2
ResponderEliminar