Saltar al contenido
Volver a los resultados

Búsqueda Tabú Basada en Agentes — Optimización Metaheurística Distribuida Multiagente

Propuesto por
Glover, F. (tabu search); multi-agent extension by various researchers in the 1990s–2000s
Año
1989–1995
Tipo
Hybrid metaheuristic — agent-based distributed tabu search
Familia
Simulation / optimization

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

Búsqueda Tabú Basada en Agentes (ABTS) integra la metaheurística de búsqueda tabú dentro de un marco multiagente donde agentes autónomos ejecutan hilos de búsqueda tabú independientes o cooperativos, compartiendo soluciones prometedoras para escapar de óptimos locales y explorar colectivamente espacios de búsqueda combinatorios o continuos grandes de manera más efectiva que una implementación de hilo único.

La intuición detrás del método

La búsqueda tabú clásica puede quedarse atascada explorando una región estrecha incluso con su mecanismo de memoria a corto plazo. Al desplegar múltiples agentes autónomos, cada uno manteniendo su propia lista tabú y vecindario, la búsqueda se expande a través de diversos puntos de partida. Los agentes comparten periódicamente soluciones de élite (intensificación) y se dispersan deliberadamente a regiones inexploradas (diversificación). Esta estructura cooperativa pero independiente refleja el comportamiento de enjambre biológico: ningún agente individual tiene la imagen completa, pero el colectivo encuentra soluciones de alta calidad mucho más rápido que cualquier buscador individual.

Historia

La búsqueda tabú fue formalizada por Fred Glover en 1986-1989. Las variantes distribuidas y paralelas surgieron a principios de la década de 1990, ya que los investigadores buscaron explotar arquitecturas multiprocesador. Verhoeven y Aarts (1995) realizaron un estudio sistemático de la búsqueda local paralela, incluidas las estrategias cooperativas tabú. El encuadre basado en agentes se hizo prominente en la década de 2000, a medida que el vocabulario de modelado basado en agentes ingresó a la investigación de operaciones.

Cuándo usarlo

Utilizar Búsqueda Tabú Basada en Agentes al resolver problemas de optimización combinatoria o de enteros mixtos difíciles (planificación, enrutamiento, diseño de redes, asignación de recursos) donde la búsqueda tabú de hilo único se estanca y hay recursos de computación paralela disponibles. Es particularmente efectiva cuando el paisaje de búsqueda tiene muchos óptimos locales de calidad similar. Evitarla cuando el problema es lo suficientemente pequeño para solucionadores exactos (MILP, branch-and-bound), cuando una sola evaluación es computacionalmente prohibitiva (haciendo inviables muchas evaluaciones paralelas), o cuando los requisitos de reproducibilidad entran en conflicto con la dinámica no determinista de la interacción de agentes.

Limitaciones y consideraciones

  • La sobrecarga de sincronización y el costo de comunicación entre agentes pueden anular las ganancias de paralelismo en sistemas fuertemente acoplados o redes lentas.
  • Más hiperparámetros que la búsqueda tabú de hilo único: el número de agentes, la topología de comunicación, la frecuencia de sincronización y los desencadenantes de diversificación requieren ajuste.
  • Las garantías teóricas de convergencia son más débiles que los métodos exactos; la calidad de la solución depende en gran medida del ajuste y la estructura del problema.
  • La reproducibilidad es difícil de lograr porque las interacciones de los agentes introducen estocasticidad adicional más allá de la inicialización aleatoria.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • La exploración paralela reduce significativamente el tiempo hasta la solución en problemas combinatorios grandes en comparación con la búsqueda tabú de hilo único.
  • El marco multiagente soporta naturalmente la diversificación, reduciendo el riesgo de convergencia prematura a óptimos locales pobres.
  • La arquitectura flexible permite agentes heterogéneos con diferentes estructuras de vecindario, estrategias de tenencia tabú o incluso metaheurísticas mixtas.
  • El intercambio cooperativo de soluciones transfiere descubrimientos entre agentes, acelerando la intensificación alrededor de regiones de alta calidad.
  • Escala bien con los núcleos computacionales disponibles, haciéndola adecuada para entornos de computación modernos multi-núcleo y distribuidos.

Aplicaciones

  • Enrutamiento de vehículos y logística: coordinación de múltiples agentes que optimizan subproblemas de rutas.
  • Planificación de talleres y fabricación flexible: los agentes manejan subconjuntos de máquinas de forma cooperativa.
  • Diseño de redes de telecomunicaciones: asignación de canales distribuida y optimización de topología.
  • Planificación de la cadena de suministro: optimización de inventario y distribución multinivel.
  • Predicción de estructura de proteínas: búsqueda de vecindario paralela sobre espacios conformacionales.
  • Planificación académica y de horarios de cursos con agentes distribuidos a nivel de departamento.

Cómo funciona

Cómo funciona

1

Definir una población de agentes autónomos. A cada agente se le asigna un rol: algunos se centran en la intensificación (búsqueda local profunda alrededor de regiones prometedoras), otros en la diversificación (escape a áreas inexploradas). Cada agente mantiene su propia lista tabú de movimientos prohibidos, una solución actual y una estructura de vecindario adaptada al tipo de problema (por ejemplo, movimientos de intercambio, inserción o 2-opt para problemas combinatorios).

2

Inicializar agentes con soluciones de partida distintas, ya sea generadas aleatoriamente o sembradas mediante una heurística constructiva (por ejemplo, vecino más cercano para enrutamiento). La diversidad entre las soluciones de partida es crucial: inicios idénticos conducen a búsquedas paralelas redundantes. Evaluar la función objetivo para cada solución inicial y registrar la mejor solución global entre todos los agentes.

3

Cada agente ejecuta su propio bucle de búsqueda tabú: generar el vecindario de la solución actual, evaluar todas (o un subconjunto de) las soluciones vecinas, seleccionar el mejor vecino no tabú como siguiente movimiento (el criterio de aspiración permite anular la lista tabú si el candidato supera el mejor global), y actualizar la lista tabú añadiendo el movimiento inverso con una tenencia extraída de un rango fijo o adaptativo.

4

Los agentes se comunican en intervalos de sincronización definidos o desencadenantes de eventos. Las estrategias comunes incluyen transmitir la mejor solución global actual a todos los agentes (que pueden reiniciarse a partir de ella), inyectar la solución de élite en un grupo compartido que los agentes consultan periódicamente, o intercambio de soluciones entre pares entre agentes vecinos en una topología (anillo, totalmente conectada o aleatoria). Los controles de diversidad evitan la convergencia prematura penalizando a los agentes con soluciones idénticas.

5

Terminar cuando se alcanza un presupuesto máximo de iteraciones, un límite de tiempo de reloj o un criterio de estancamiento (por ejemplo, ninguna mejora en el mejor global durante un número determinado de iteraciones). Seleccionar la mejor solución global encontrada entre todos los agentes en todas las iteraciones como salida final. Opcionalmente, informar un frente de Pareto si se rastrean múltiples objetivos.

Errores comunes

  • Establecer todos los agentes con soluciones de partida idénticas desperdicia capacidad paralela: asegure una inicialización diversa.
  • Una comunicación demasiado frecuente fuerza a los agentes a la misma cuenca de soluciones, eliminando los beneficios de la diversificación y reduciendo efectivamente la búsqueda a un solo hilo.
  • Ignorar el criterio de aspiración en el diseño de la lista tabú puede hacer que los agentes pierdan soluciones obviamente mejores, particularmente en la fase inicial de la búsqueda.
  • Aplicar ABTS a problemas donde la evaluación del vecindario es extremadamente costosa sin un modelo sustituto resultará en tiempos de ejecución prohibitivos.

Preguntas frecuentes

¿En qué se diferencia la Búsqueda Tabú Basada en Agentes de simplemente ejecutar múltiples hilos de búsqueda tabú?

La diferencia clave es la cooperación. En ejecuciones paralelas independientes, los hilos nunca comparten información. En ABTS, los agentes intercambian activamente soluciones, actualizan un grupo de élite compartido o adoptan desencadenantes de diversificación basados en el estado colectivo, produciendo un comportamiento de búsqueda emergente ausente en ejecuciones independientes.

¿Cuántos agentes debo usar?

Un punto de partida común es un agente por núcleo de CPU disponible. La investigación sugiere rendimientos decrecientes más allá de 8-16 agentes para la mayoría de los problemas combinatorios, a medida que aumenta la sobrecarga de comunicación. Experimentos piloto con 4, 8 y 16 agentes ayudan a identificar el punto óptimo para un problema dado.

¿Puede ABTS manejar problemas multiobjetivo?

Sí. Los agentes pueden mantener aproximaciones locales de un frente de Pareto y compartir soluciones no dominadas a través de un archivo compartido. Esto a veces se denomina Búsqueda Tabú Basada en Agentes Multiobjetivo y es distinto de ABTS estándar de objetivo único.

¿Qué topología de comunicación es mejor?

Las topologías totalmente conectadas difunden las buenas soluciones más rápido pero crean un alto costo de comunicación. Las topologías de anillo o de mundo pequeño equilibran la difusión de información con la autonomía. Para la mayoría de los problemas prácticos, una topología de anillo o aleatoria dispersa funciona bien como predeterminada.

¿Cuándo debería preferir un algoritmo genético o de enjambre de partículas sobre ABTS?

Prefiera métodos basados en población (GA, PSO) cuando el problema tenga un paisaje continuo y suave o cuando los operadores de cruce/recombinación estén bien definidos. ABTS sobresale en problemas discretos y combinatorios con operadores de vecindario bien definidos donde la memoria tabú proporciona una fuerte ventaja de búsqueda.

Métodos relacionados

Fuentes

  1. Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    Abrir referencia DOI
    Copiado.
  2. Verhoeven, M. G. A., Aarts, E. H. L. (1995). Parallel local search. Journal of Heuristics, 1(1), 43–65.

    Abrir referencia DOI
    Copiado.