Metaeuristica

Contenido
Metaheuristica tabu 1
Ejemplo: Problema del Viajante 2
Enunciado 3
Situación actual respecto de su resolución 4
Casuística 4
Convergencia del problema 5
Aplicaciones 5
Optimización combinatoria 5
Bibliografía 8

Metaheuristica tabu
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 rendimientodel 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. La búsqueda tabú es atribuída a Fred Glover.
La búsqueda tabú es un algoritmo metaheurístico que puede utilizarse para resolver problemas de optimización combinatoria, tales como elproblema del viajante (TSP, del inglés Travelling Salesman Problem). La búsqueda tabú utiliza un procedimiento de búsqueda local o por vecindades para moverse iterativamente desde una solución x hacia una solución x' en la vecindad de x, hasta satisfacer algún criterio de parada. Para poder explorar regiones del espacio de búsqueda que serían dejadas de lado por el procedimiento de búsqueda local(ver óptimo local), la búsqueda tabú modifica la estructura de vecinos para cada solución a medida que la búsqueda progresa. Las soluciones admitidas para N * (x), el nuevo vecindario, son determinadas mediante el uso de estructuras de memoria. La búsqueda entonces progresa moviéndose iterativamente de una solución x hacia una solución x' en N * (x).
Quizás la estructura de memoria más importanteusada para determinar las soluciones permitidas a un N * (x), sea la lista tabú. En su forma más simple, una lista tabú es una memoria de corto plazo que contiene las soluciones que fueron visitadas en el pasado reciente (menos de n iteraciones atrás, donde n es el número de soluciones previas que van a ser almacenadas (n también es llamado el tenor del tabú)). La búsqueda tabú excluye lassoluciones en la lista tabú de N * (x). Una variación de la lista tabú prohíbe soluciones que tienen ciertos atributos (i.e., soluciones al problema del viajante de comercio (TSP) que incluyen aristas no deseadas) o prevenir ciertos movimientos (i.e., un arco que fue agregado a un recorrido del TSP no puede ser eliminado en los siguientes n movimientos). Los atributos seleccionados de las solucionesrecientemente visitadas son denominados "tabú-activos." Las posibles soluciones que contengan elementos tabú-activos son "tabú".
Las listas tabú que contienen atributos pueden ser más efectivas para algunos dominios, pese a que presentan un nuevo problema. Cuando sólo un atributo es marcado como tabú, esto por lo general resulta en que más de una solución es marcada como tabú. Algunas de estassoluciones, que ahora deben ser evitadas, podrían ser de excelente calidad y no serían visitadas. Para mitigar este problema, se introducen los "criterios de aspiración": estos pueden modificar el estado de tabú de una solución, por lo tanto incluyendo la antes excluida solución en el conjunto de soluciones permitidas. Un criterio de aspiración muy utilizado es admitir soluciones que son mejores que lamejor solución conocida al momento.
Ejemplo: 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, ladistancia 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....