Búsqueda Tabú Estocástica — Metaheurística Aleatorizada con Memoria
- Propuesto por
- Glover, F. (base TS); stochastic extensions by various authors (1990s–2000s)
- Año
- 1990s
- Tipo
- Stochastic metaheuristic optimizer
- Familia
- Simulation / optimization
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ú Estocástica (BTE) es una extensión de la Búsqueda Tabú clásica que introduce aleatoriedad en las fases de exploración del vecindario y selección de movimientos.
Al combinar la memoria tabú —que prohíbe soluciones visitadas recientemente— con la aceptación probabilística o el muestreo aleatorio de candidatos, la BTE escapa de los óptimos locales de manera más efectiva y explora paisajes de soluciones complejos que la Búsqueda Tabú (BT) determinista podría no lograr atravesar.
La intuición detrás del método
La Búsqueda Tabú clásica navega por un espacio de soluciones moviéndose siempre al mejor vecino permitido, utilizando una memoria a corto plazo (la lista tabú) para evitar ciclos. En la práctica, sin embargo, el mejor movimiento permitido aún puede atrapar al algoritmo en una región del paisaje. La Búsqueda Tabú Estocástica inyecta aleatoriedad controlada: el siguiente movimiento se elige probabilísticamente de un conjunto de vecinos candidatos en lugar de hacerlo de forma voraz, y ocasionalmente se introducen perturbaciones aleatorias para diversificar la búsqueda. Esto preserva la disciplina guiada por la memoria de la BT, al tiempo que añade el poder exploratorio del que carece el descenso determinista puro.
Historia
La Búsqueda Tabú fue introducida formalmente por Fred Glover en 1986 y elaborada en artículos seminales entre 1989 y 1990. Las extensiones estocásticas surgieron en la década de 1990 cuando los investigadores reconocieron que la evaluación determinista del vecindario era un cuello de botella en problemas a gran escala. El muestreo aleatorio de candidatos, la aceptación probabilística de movimientos y la inyección de ruido se incorporaron para mejorar la diversificación, dando lugar a lo que se conoce ampliamente como Búsqueda Tabú Estocástica. La técnica se aplica ampliamente en investigación de operaciones, diseño de ingeniería y optimización de hiperparámetros de aprendizaje automático.
Cuándo usarlo
Utilice la Búsqueda Tabú Estocástica al resolver problemas de optimización de caja negra combinatorios o continuos con paisajes complejos y multimodales donde la búsqueda local determinista queda atrapada consistentemente (por ejemplo, programación, enrutamiento, selección de características). Es especialmente valiosa cuando la evaluación completa del vecindario es computacionalmente costosa, haciendo necesario el submuestreo aleatorio. NO use BTE cuando el problema es convexo o unimodal —los métodos basados en gradiente o exactos son más rápidos y óptimos. Evítela cuando necesite una garantía de optimalidad global, ya que la BTE no ofrece garantía de convergencia más allá de las mejores soluciones encontradas heurísticamente. También evítela cuando la función objetivo es barata de evaluar completamente y una BT determinista con búsqueda exhaustiva de vecinos es factible.
Limitaciones y consideraciones
- No hay garantía teórica de encontrar el óptimo global; la calidad de la solución depende en gran medida de la configuración de los parámetros.
- La tenencia tabú y el tamaño de la lista de candidatos requieren un ajuste específico del problema; malas elecciones conducen a una convergencia prematura o un progreso lento.
- Las ejecuciones estocásticas no son reproducibles sin una semilla aleatoria fija, lo que complica la evaluación comparativa y la auditoría.
- La sobrecarga de memoria crece con el tamaño de la lista tabú; se necesitan representaciones tabú basadas en atributos para grandes espacios de soluciones.
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 los óptimos locales de manera más efectiva que la Búsqueda Tabú determinista al combinar la memoria con la exploración probabilística.
- Escala a grandes estructuras de vecindario mediante el submuestreo de candidatos, reduciendo el costo computacional por iteración.
- La memoria tabú previene el ciclado, un modo de fallo común de los métodos puramente estocásticos como el ascenso de colina con reinicio aleatorio.
- Marco flexible: la probabilidad de perturbación y la tenencia tabú pueden ajustarse para equilibrar la intensificación y la diversificación.
- Aplicable tanto a problemas combinatorios (TSP, programación) como a la optimización continua con una adaptación menor.
Aplicaciones
- Optimización de rutas de vehículos y logística bajo demanda incierta
- Programación de talleres de trabajo (job-shop) y talleres abiertos (open-shop) con tiempos de procesamiento estocásticos
- Selección de características en conjuntos de datos de aprendizaje automático de alta dimensión
- Diseño de redes y optimización de topologías
- Optimización de carteras con restricciones combinatorias de selección de activos
- Ajuste de hiperparámetros para modelos de simulación complejos
Cómo funciona
Cómo funciona
Genere una solución inicial x0 (aleatoria o heurística). Establezca la lista tabú T como vacía, defina la tenencia tabú tau, el límite de iteraciones I_max y los parámetros estocásticos (por ejemplo, tamaño de la lista de candidatos k, probabilidad de perturbación p_perturb).
En cada iteración, muestree aleatoriamente un subconjunto N_s del vecindario completo N(x_current) en lugar de evaluar todos los vecinos. Esto reduce el costo por iteración e introduce estocasticidad en las regiones del espacio que se exploran.
Seleccione la siguiente solución x_next de N_s: (a) elija el mejor candidato no tabú con probabilidad 1-p_perturb, o (b) con probabilidad p_perturb elija un candidato no tabú aleatorio para diversificar. Los criterios de aspiración pueden anular el estado tabú si x_next mejora la mejor solución conocida.
Añada x_current (o el atributo del movimiento) a la lista tabú T. Elimine la entrada más antigua si |T| > tau. Actualice la mejor solución actual x_best si f(x_next) < f(x_best).
Repita el muestreo_del_vecindario hasta la actualización_tabú hasta que se alcance I_max iteraciones, se cumpla un valor objetivo, o no haya habido mejora durante una ventana de paciencia. Devuelva x_best como la solución final.
Errores comunes
- Establecer una tenencia tabú demasiado corta permite el ciclado a pesar de la lista tabú; demasiado larga bloquea regiones prometedoras innecesariamente.
- Usar una lista de candidatos demasiado pequeña (submuestreo agresivo) puede hacer que la búsqueda pierda buenos vecinos consistentemente.
- Ignorar los criterios de aspiración hace que el algoritmo rechace movimientos que mejoran globalmente y que resultan ser tabú.
- Informar solo una única ejecución sin múltiples reinicios o semillas da una imagen engañosa de la calidad típica de la solución.
- Confundir la Búsqueda Tabú Estocástica con el Recocido Simulado: ambos son estocásticos pero difieren fundamentalmente —la BTE utiliza memoria explícita mientras que el Recocido Simulado (RS) utiliza aceptación probabilística basada en la temperatura sin memoria.
Preguntas frecuentes
¿En qué se diferencia la Búsqueda Tabú Estocástica del Recocido Simulado?
Ambas son metaheurísticas estocásticas, pero la BTE utiliza una memoria tabú explícita para prohibir movimientos visitados recientemente, evitando el ciclado. El RS no tiene memoria —acepta soluciones peores con una probabilidad que disminuye con el tiempo (esquema de temperatura). La BTE es generalmente más potente en problemas combinatorios donde revisitar movimientos es un peligro claro.
¿Cuántas iteraciones (I_max) debo ejecutar?
No hay una regla universal. Una práctica común es ejecutar múltiples ensayos independientes (por ejemplo, 10-30 reinicios) con un presupuesto proporcional al tamaño del problema, y luego informar los mejores y promedio resultados. Para la evaluación comparativa, iguale el presupuesto total de evaluación de funciones utilizado por los métodos competidores.
¿Puede la Búsqueda Tabú Estocástica manejar variables continuas?
Sí, pero requiere definir un vecindario continuo (por ejemplo, perturbación gaussiana alrededor de la solución actual) y un atributo adecuado para la lista tabú (por ejemplo, una región o dirección). La mayoría de la literatura sobre BTE se centra en problemas combinatorios; para espacios continuos, la Evolución Diferencial o CMA-ES son a menudo alternativas más naturales.
¿Cuál es el papel de los criterios de aspiración?
Los criterios de aspiración anulan el estado tabú de un movimiento si aceptarlo produce una solución mejor que la mejor encontrada hasta el momento. Sin aspiración, el algoritmo podría rechazar permanentemente movimientos que mejoran globalmente y que resultan ser tabú, limitando severamente la calidad de la solución.
¿Debo fijar la semilla aleatoria para la reproducibilidad?
Sí, fije la semilla al informar los resultados en la investigación para asegurar la reproducibilidad. En la práctica, ejecute con múltiples semillas e informe estadísticas (media, mejor, desviación estándar) para dar una imagen fiable del rendimiento del algoritmo en el paisaje estocástico.
Métodos relacionados
Fuentes
Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.
Abrir referencia DOICopiado.Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568.
Abrir referencia DOICopiado.