Búsqueda Tabú

Introducción

“Los procedimientos meta-heurísticos son una clase de métodos aproximados que están diseñados para resolver problemas difíciles de optimización combinatorio, en los que los heurísticos clásicos no son ni efectivos ni eficientes. Las meta-heurística proporcionan un marco general para crear nuevos algoritmos híbridos combinando diferentes conceptos derivados de: inteligencia artificial, evolución biológica y mecanismos estadísticos.”

Búsqueda Tabú (Tabu Search)

La Búsqueda Tabú (Tabu Search - TS) es un procedimiento meta-heurístico cuya característica distintiva es el uso de memoria adaptativa y de estrategias especiales de resolución de problemas. Su filosofía se basa en la explotación de diversas estrategias inteligentes para la resolución de problemas, basadas en procedimientos de aprendizaje. El marco de memoria adaptativa de TS explota la historia del proceso de resolución del problema haciendo referencia a cuatro dimensiones principales, consistentes en la propiedad de ser reciente, en frecuencia, en calidad, y en influencia.

La búsqueda tabú sirve para resolver problemas que estén relacionados con los siguientes ámbitos:

·         planificación de los recursos,

·         telecomunicaciones,

·         diseño VLSI,

·         análisis financiero,

·         programación, planificación del espacio,

·         la distribución de energía,

·         moleculares ingeniería, logística,

·         clasificación de patrones,

·         de fabricación flexible,

·         la gestión de residuos,

·         la exploración de minerales,

·         análisis biomédico,

·         la conversación del medio ambiente y

·         decenas de otros problemas.

Optimización de ruteo aplicando métodos heurísticos con el uso de búsqueda tabú

El problema de ruteo de vehículos es uno de los problemas más analizados en la actualidad. Una gran cantidad de técnicas, heurísticas han sido empleadas para darle solución a este problema, entre ellas Búsqueda Tabú.

Búsqueda Tabú

Son muchas las técnicas existentes para la optimización de problemas. Esta técnica emplea métodos que pueden ser globales o locales. Los globales, como global de un problema, mientras que los locales se concentran en la vecindad de las solución generada inicialmente, por lo que necesitan de otras técnicas adicionales para encontrar el óptimo global.

Los métodos de búsqueda global lo que persiguen es no caer en óptimos locales, explorando con más eficiencia el espacio de la búsqueda. Esto lo hacen trabajando generalmente con un componente aleatorio de búsqueda, que hace que si se encuentran en un óptimo local, salten a otro punto del espacio de búsqueda, donde pueden encontrar otro óptimo local o posiblemente global

La búsqueda tabú es un procedimiento iterativo y heurístico para resolver problemas discretos de optimización combinatoria y de gran escala. Fue propuesta inicialmente por Fred Glover, y desde entonces ha sido aplicada en la solución de una gran cantidad de problemas de optimización.

Esta técnica busca escapar de óptimos locales, empleando algunas metodologías como el uso de memorias flexibles. Además esta técnica impone y relaja restricciones con el fin de explorar áreas prohibidas, y de hacer cortes de la región factible, al tener en cuenta las restricciones que la limitan.

La Búsqueda Tabú se cimienta en tres puntos principales:

1.       El uso de estructuras de memoria basadas en atributos diseñados para permitir criterios de evaluación e información de búsqueda histórica, la cual se explota más a fondo que las estructuras de memoria rígida (como en ramificación y acotamiento) o por sistemas de periódica de memoria (como recorrido simulado y otro métodos aleatorizados.)

2.       Un mecanismo asociado de control, mediante el empleo de estructuras de memoria, basado en el interjuego entre las condiciones que registren y liberan al proceso de búsqueda (envuelto en las restricciones tabú y el criterio de aspiración.)

3.       La incorporación de funciones de memoria de diferentes lapsos de tiempo, para implantar estrategias que refuercen la combinación de movimientos y las características de solución que históricamente se han encontrado buenas, mientras que las estrategias de diversificación manejan la búsqueda dentro de nuevas regiones.

La búsqueda tabú se basa en dos procesos principales clave que son: restringir la búsqueda al clasificar un movimiento como tabú o prohibido, y liberar la búsqueda empelando una función de memoria de término corto que proporciona una estrategia de olvido. Estos últimos debido a que después de varias interacciones se pueden levantar la clasificación de tabú para un movimiento según el nivel de aspiraciones como se menciono anteriormente.

La búsqueda tabú emplea dos estrategias para encontrar el óptimo local, las cuales están relacionadas con la memoria a largo plazo, que son la intensificación (a término medio) y la diversificación (a término largo). La primera de ellas consiste en regresar a regiones catalogadas como buenas, con el fin de explorarlas mejor; mientras que la otra consiste en analizar nueva áreas no exploradas del espacio de soluciones.

Hay que tener en cuenta que el tamaño de la lista tabú es un parámetro, el cual no puede ser muy pequeño para evitar el ciclado, ni muy grande para no restringir la búsqueda, pues se puede impedir llegar a valles profundos, es decir, obtener el óptimo local. Este tamaño puede determinar mediante pruebas empíricas preliminares. También existen las listas tabú múltiples, cada una desarrollada para un atributo en particular, cada uno de los cuales puede tener un peso, para determinar el status tabú de los movimientos que contiene.

Nota: El contenido de esta entrada esta basado en el atrículo de una tesis "Optimización de ruteo de vehiculos empleando búsqueda tabú" el cual recomiento  apliamente ya que ahi se expone un algoritmo para esta optimización.