Búsqueda Tabú — Metaheurística de Búsqueda Local
- Propuesto por
- Fred Glover
- Año
- 1989
- Tipo
- Local-search metaheuristic
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
La Búsqueda Tabú es una metaheurística de búsqueda local introducida por Fred Glover en 1989 que utiliza una lista tabú —una memoria a corto plazo de soluciones visitadas recientemente— para prevenir el ciclado y escapar de óptimos locales.
Al prohibir explícitamente movimientos que revierten decisiones recientes, el algoritmo explora el espacio de búsqueda de manera más amplia y, a través de estructuras de memoria a largo plazo como criterios de aspiración, tiene como objetivo aproximarse al óptimo global incluso en problemas combinatorios grandes y complejos.
La intuición detrás del método
Imagine navegar por un paisaje montañoso en la oscuridad, intentando encontrar el pico más alto. Un simple escalador de búsqueda local siempre sube y se queda atascado en la colina más cercana que alcanza. La Búsqueda Tabú lleva un bloc de notas de lugares visitados recientemente y se niega a volver a ellos, incluso si retroceder pareciera tentador. Esta amnesia forzada sobre movimientos recientes saca a la búsqueda de callejones sin salida y la lleva a territorio inexplorado, permitiéndole eventualmente descubrir terrenos mucho más altos de lo que una simple búsqueda local podría.
Historia
La Búsqueda Tabú fue introducida por Fred Glover en un artículo fundamental de 1989 en el ORSA Journal on Computing, donde se presentó como una estrategia para guiar la búsqueda local explotando la memoria de movimientos pasados. Las ideas fundamentales se consolidaron y extendieron en la monografía de Springer de Glover y Laguna de 1997, que estableció la lista tabú canónica a corto plazo, los criterios de aspiración y las estrategias de diversificación e intensificación a largo plazo que siguen siendo centrales para el método hoy en día. Desde su introducción, la Búsqueda Tabú se ha aplicado extensamente en investigación de operaciones, planificación, logística y diseño combinatorio, y continúa siendo una metaheurística de referencia estándar junto con el recocido simulado y los algoritmos genéticos.
Cuándo usarlo
La Búsqueda Tabú es muy adecuada para problemas de optimización combinatoria y discreta donde el espacio de soluciones es demasiado grande para métodos exactos y la estructura del problema permite definir un vecindario significativo. Las aplicaciones típicas incluyen problemas de planificación, enrutamiento, asignación y secuenciación. Es particularmente efectiva cuando el paisaje de búsqueda tiene muchos óptimos locales que atrapan métodos más simples. No requiere que la función objetivo sea diferenciable o continua. La definición del vecindario y la tenencia tabú deben adaptarse cuidadosamente al problema específico; un vecindario mal elegido o una tenencia demasiado corta o demasiado larga pueden degradar significativamente el rendimiento. Se necesitan al menos varios cientos —y preferiblemente más de mil— iteraciones para que la búsqueda explore el espacio adecuadamente.
Limitaciones y consideraciones
- El rendimiento es sensible a la definición del vecindario y la tenencia tabú; malas elecciones pueden atrapar la búsqueda o hacerla ciclar a pesar del mecanismo tabú.
- Requiere un presupuesto mínimo de iteraciones —típicamente más de 1000 iteraciones— para explorar el vecindario suficientemente; con muy pocas iteraciones los resultados no son mejores que la búsqueda local simple.
- La lista tabú almacena atributos de movimiento en lugar de soluciones completas, por lo que el criterio de aspiración es necesario para evitar bloquear inadvertidamente movimientos genuinamente buenos.
- A diferencia de los solucionadores exactos, la Búsqueda Tabú no ofrece garantía de optimalidad y la calidad del resultado puede variar entre ejecuciones si la solución inicial o el vecindario son estocásticos.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Escapa de óptimos locales a través del mecanismo tabú sin requerir información de gradiente.
- Aplicable a problemas combinatorios, de tipo mixto e incluso continuos — no asume normalidad ni ninguna propiedad distributiva.
- Incorpora memoria a múltiples escalas temporales (lista tabú a corto plazo, diversificación/intensificación a largo plazo) permitiendo una exploración fundamentada del espacio de búsqueda.
- A menudo encuentra soluciones de alta calidad con presupuestos computacionales relativamente modestos en comparación con métodos exactos en instancias grandes.
Aplicaciones
- Planificación de talleres y líneas de producción — optimización de la secuencia de operaciones para minimizar el tiempo de finalización o el retraso.
- Enrutamiento de vehículos — búsqueda de rutas de entrega eficientes sujetas a restricciones de capacidad y ventanas de tiempo.
- Asignación y localización de instalaciones — asignación de tareas a recursos o localización de instalaciones para minimizar costos.
- Coloreo de grafos, diseño de redes y telecomunicaciones — resolución de problemas de optimización estructural discreta.
- Selección de características y búsqueda de hiperparámetros — exploración de espacios de configuración discretos en pipelines de aprendizaje automático.
Cómo funciona
Cómo funciona
La búsqueda comienza desde una solución candidata inicial, que puede construirse aleatoriamente o con una heurística voraz. La lista tabú se configura como una cola vacía de longitud fija, y se registra la mejor solución encontrada hasta el momento. La estructura del vecindario —la regla que define qué soluciones están a un paso de la solución actual— debe definirse de una manera que sea significativa para el problema específico.
Desde la solución actual, se generan y evalúan todos los movimientos en el vecindario definido contra la función objetivo. Cada movimiento corresponde a una pequeña perturbación, como intercambiar dos elementos en una secuencia o invertir una variable binaria. El vecindario debe ser lo suficientemente rico para permitir una exploración significativa pero lo suficientemente pequeño para ser tratable dentro de cada iteración.
Cada movimiento candidato se prueba contra la lista tabú. Si el movimiento —o el atributo que lo caracteriza— aparece en la lista, se clasifica como tabú y está prohibido, a menos que satisfaga un criterio de aspiración: típicamente, si la solución resultante fuera mejor que la mejor solución encontrada hasta el momento, el estado tabú se anula y el movimiento se permite. Este mecanismo de aspiración otorga flexibilidad al algoritmo sin abandonar su disciplina anticiclado.
Entre todos los movimientos no tabú (y cualquier movimiento tabú que supere el criterio de aspiración), se selecciona y ejecuta el movimiento de mejor rendimiento, incluso si empeora el valor objetivo. Esta disposición a aceptar el deterioro es lo que permite al algoritmo escapar de los óptimos locales, que es el rasgo definitorio de la Búsqueda Tabú en comparación con la simple escalada de colinas.
Después de ejecutar el movimiento, la lista tabú se actualiza añadiendo la inversión del movimiento recién realizado (o su atributo característico), y se elimina la entrada más antigua si la lista está llena, manteniendo su longitud fija — la tenencia tabú. Si la nueva solución es mejor que la mejor solución registrada, se actualiza la mejor solución. Las estructuras opcionales de memoria a largo plazo pueden rastrear la frecuencia o recencia de las soluciones para guiar la diversificación hacia regiones menos visitadas o la intensificación en torno a las prometedoras.
El algoritmo continúa iterando hasta que se cumple un criterio de parada: un número máximo de iteraciones, un valor objetivo objetivo o un número fijo de iteraciones sin mejora. Se devuelve como resultado la mejor solución encontrada durante toda la búsqueda. Elegir un presupuesto de iteración adecuado es crítico: muy pocas iteraciones impiden una exploración suficiente del vecindario.
Errores comunes
- Establecer la tenencia tabú demasiado corta permite que el ciclado recurra, frustrando el propósito del mecanismo tabú; la tenencia debe ajustarse al tamaño del problema.
- Establecer la tenencia demasiado larga restringe excesivamente la búsqueda e impide que el algoritmo vuelva a visitar regiones que puedan contener mejoras.
- Ejecutar menos de aproximadamente 1000 iteraciones significa que la búsqueda no ha explorado suficiente del vecindario; si el cómputo es limitado, recurra al recocido simulado, que puede producir resultados útiles más rápido con menos iteraciones.
- Usar un vecindario demasiado estrecho (por ejemplo, solo movimientos de intercambio simple en una estructura compleja) conduce a una búsqueda superficial; asegúrese de que el vecindario sea lo suficientemente rico como para conectar todas las regiones prometedoras del espacio de soluciones.
- Ignorar el criterio de aspiración puede bloquear permanentemente movimientos hacia el óptimo global si ese movimiento resulta ser tabú; implemente siempre al menos la anulación estándar de la mejor solución.
Preguntas frecuentes
¿Cómo se diferencia la Búsqueda Tabú del recocido simulado?
Ambos métodos aceptan movimientos que empeoran la solución para escapar de óptimos locales, pero difieren en el mecanismo. El recocido simulado acepta peores movimientos probabilísticamente, guiado por un parámetro de temperatura de enfriamiento. La Búsqueda Tabú acepta el mejor movimiento no tabú disponible de forma determinista, guiado por la memoria explícita de movimientos recientes. La Búsqueda Tabú es generalmente más efectiva en problemas combinatorios estructurados; el recocido simulado puede ser más fácil de ajustar en problemas con paisajes continuos o casi continuos y es preferible cuando el presupuesto de iteraciones es pequeño (por debajo de aproximadamente 1000 iteraciones).
¿Cuánto tiempo debe durar la lista tabú?
La tenencia tabú —el número de iteraciones que un movimiento permanece prohibido— depende del problema. Un punto de partida comúnmente citado es una tenencia proporcional a la raíz cuadrada del tamaño del problema, pero esto debe ajustarse empíricamente. Una tenencia demasiado corta permite el ciclado; una tenencia demasiado larga restringe excesivamente la búsqueda. Estrategias de tenencia adaptativa o aleatoria pueden reducir la sensibilidad a esta elección.
¿Garantiza la Búsqueda Tabú encontrar el óptimo global?
No. La Búsqueda Tabú es una metaheurística y no ofrece garantía de optimalidad. Su objetivo es encontrar soluciones de alta calidad de manera eficiente, pero el resultado depende de la estructura del vecindario, la tenencia, el número de iteraciones y la solución inicial. Para una garantía de optimalidad, se requiere un método exacto como la programación entera, aunque los métodos exactos pueden ser computacionalmente inviables para instancias grandes.
¿Qué es un criterio de aspiración y por qué es necesario?
Un criterio de aspiración es una regla que anula el estado tabú de un movimiento bajo condiciones especiales. El criterio más común es: si ejecutar un movimiento tabú produjera una solución mejor que la mejor solución encontrada hasta el momento, la restricción tabú se levanta y el movimiento se permite. Sin esta anulación, el mecanismo tabú podría bloquear permanentemente el camino hacia el óptimo global si ese camino pasa por un movimiento visitado recientemente.
Métodos relacionados
Fuentes
Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.
Abrir referencia de la publicaciónCopiado.Glover, F. & Laguna, M. (1997). Tabu Search. Springer.
ISBN: 9780792349907Copiado.