Saltar al contenido
Volver a los resultados

Búsqueda Tabú Multiobjetivo (MOTS) — Metaheurística para soluciones Pareto-óptimas

Propuesto por
Hansen, M. P.; building on Glover (1989) Tabu Search
Año
1997
Tipo
Metaheuristic multi-objective optimization
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?

La Búsqueda Tabú Multiobjetivo (MOTS) es un algoritmo metaheurístico que extiende el marco clásico de Búsqueda Tabú para optimizar simultáneamente dos o más funciones objetivo en conflicto.

En lugar de un único óptimo, busca aproximar el frente de Pareto — el conjunto de soluciones donde ningún objetivo puede mejorarse sin empeorar otro — lo que lo hace adecuado para problemas complejos de optimización combinatoria y continua en ingeniería, logística e investigación de operaciones.

La intuición detrás del método

Imagine explorar un paisaje accidentado con muchas colinas y valles, pero tiene varios mapas que muestran diferentes terrenos (uno por objetivo) que se contradicen entre sí. MOTS navega por este espacio moviéndose a soluciones vecinas, manteniendo una lista de memoria a corto plazo (la lista tabú) de lugares visitados recientemente para evitar ciclos, y manteniendo un archivo de soluciones no dominadas encontradas hasta ahora. Periódicamente, la diversificación estratégica empuja la búsqueda hacia regiones inexploradas del frente de Pareto, equilibrando la explotación de áreas prometedoras con la exploración global.

Historia

La Búsqueda Tabú Multiobjetivo extiende la Búsqueda Tabú de un solo objetivo introducida por Fred Glover en 1989. La primera formulación sistemática de MOTS — incluyendo el archivo de Pareto y los criterios de aspiración multiobjetivo — fue presentada por M. P. Hansen en la conferencia MCDM de 1997. Trabajos posteriores de Gandibleux, Teghem y otros formalizaron variantes para problemas combinatorios, y MOTS ha sido aplicado desde entonces a problemas de planificación, logística y diseño de ingeniería como una alternativa competitiva a los algoritmos evolutivos multiobjetivo.

Cuándo usarlo

Utilice MOTS cuando se enfrente a un problema de optimización combinatoria o de enteros mixtos con dos o más objetivos en conflicto (p. ej., costo vs. calidad, tiempo vs. riesgo) y los métodos exactos sean computacionalmente intratables. Sobresale en problemas de planificación, enrutamiento de vehículos, diseño de redes y selección de carteras donde el espacio de búsqueda es demasiado grande para la enumeración exhaustiva. Prefiera MOTS sobre la búsqueda puramente aleatoria cuando la estructura del vecindario sea significativa y se puedan definir operadores de movimiento de forma clara. NO utilice MOTS cuando: el problema tenga un solo objetivo (la Búsqueda Tabú simple es suficiente); cuando el frente de Pareto pueda enumerarse exactamente; cuando se disponga de información de gradiente y el paisaje sea convexo (utilice programación matemática en su lugar); o cuando las decisiones en tiempo real requieran resultados deterministas y reproducibles sin variación estocástica.

Limitaciones y consideraciones

  • El rendimiento es muy sensible a la longitud de la lista tabú, la definición del vecindario y la estrategia de diversificación — requiriendo una cuidadosa sintonización de parámetros.
  • No hay garantía de convergencia al verdadero frente de Pareto; la calidad de la solución depende de la longitud de la ejecución y la estructura del problema.
  • Computacionalmente costoso por iteración cuando los vecindarios son grandes o las evaluaciones de objetivos son costosas.
  • Mantener y actualizar el archivo de Pareto puede volverse costoso a medida que crece el número de objetivos y el tamaño del archivo.
  • La implementación paralela no es trivial debido a la naturaleza secuencial basada en memoria del mecanismo tabú.

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

Fortalezas

  • Evita revisitar soluciones recientes a través de la lista tabú, reduciendo el riesgo de ciclos en paisajes complejos.
  • Los criterios de aspiración permiten anular las restricciones tabú cuando un movimiento conduce a una mejora excepcional, equilibrando la memoria con la flexibilidad.
  • No requiere información de gradiente, lo que lo hace aplicable a funciones objetivo no diferenciables, discretas o de caja negra.
  • Produce una aproximación de todo el frente de Pareto en una sola ejecución, apoyando la toma de decisiones multicriterio.
  • El diseño flexible del vecindario y de los operadores de movimiento permite la personalización específica del problema.
  • Los mecanismos de diversificación permiten escapar de óptimos locales y una mejor cobertura del frente de Pareto.

Aplicaciones

  • Enrutamiento de vehículos multiobjetivo y planificación logística (minimizar costo y tiempo de entrega simultáneamente)
  • Planificación de proyectos biobjetivo: minimizar el tiempo de finalización y el costo de recursos bajo restricciones de precedencia
  • Optimización de carteras: equilibrar el rendimiento esperado frente al riesgo en múltiples clases de activos
  • Diseño de redes: minimizar el costo de instalación mientras se maximiza la confiabilidad o el rendimiento
  • Planificación de procesos de fabricación: optimizar conjuntamente el tiempo de ciclo, el uso de energía y las métricas de calidad
  • Gestión ambiental: equilibrar la producción económica frente al impacto de la contaminación o ecológico

Cómo funciona

Cómo funciona

1

Inicializar la búsqueda con una o más soluciones de partida (generadas aleatoriamente o construidas heurísticamente). Establecer una lista tabú vacía de longitud fija L e inicializar el archivo de Pareto con soluciones no dominadas de la población de partida.

2

Generar el vecindario N(s) de la solución actual s aplicando operadores de movimiento (intercambios, inserciones, perturbaciones). Evaluar todas las soluciones vecinas en cada función objetivo para identificar candidatos a la progresión.

3

Aplicar el filtro tabú: excluir vecinos cuyos movimientos definitorios aparezcan en la lista tabú, a menos que satisfagan un criterio de aspiración — típicamente que el vecino domine a todos los miembros actuales del archivo o mejore el mejor valor conocido en al menos un objetivo. Esto evita ciclos y fuerza la exploración.

4

Seleccionar el mejor vecino no tabú (o ganador por criterio de aspiración) como la siguiente solución actual. Actualizar el archivo de Pareto añadiendo la nueva solución si no está dominada; eliminar cualquier miembro del archivo que esté dominado por la nueva entrada.

5

Aplicar estrategias de diversificación cuando la búsqueda se estanca: la memoria de frecuencia a largo plazo identifica regiones poco visitadas; reiniciar desde soluciones de élite del archivo o soluciones perturbadas aleatoriamente para extender la cobertura del frente de Pareto.

6

Repetir los pasos de vecindario, filtro y archivo hasta que se cumpla un criterio de parada — típicamente un número máximo de iteraciones, evaluaciones de funciones o tiempo de CPU transcurrido. Devolver el archivo de Pareto como el frente Pareto-óptimo aproximado.

Errores comunes

  • Establecer la lista tabú demasiado corta provoca ciclos; establecerla demasiado larga restringe excesivamente la búsqueda y se pierden buenas soluciones — la calibración empírica es esencial.
  • Descuidar la diversificación conduce a una convergencia prematura en una región del frente de Pareto, produciendo una mala aproximación.
  • Aplicar MOTS con más de tres objetivos degrada el rendimiento porque la gestión del archivo y el mantenimiento de la diversidad se vuelven computacionalmente onerosos; considere métodos basados en descomposición para problemas con muchos objetivos.
  • El uso de operadores de movimiento genéricos sin un diseño específico del problema limita severamente la calidad de la solución en comparación con implementaciones personalizadas.
  • Informar solo el archivo final sin examinar el historial de convergencia puede ocultar un estancamiento prematuro.

Preguntas frecuentes

¿Cómo maneja MOTS la lista tabú cuando hay múltiples objetivos?

La lista tabú almacena movimientos (no soluciones), por lo que opera de la misma manera que en la Búsqueda Tabú de un solo objetivo. La diferencia clave es que la selección entre vecinos no tabú utiliza la dominancia multiobjetivo o una función de एकमेarización, y el criterio de aspiración se redefine para permitir un movimiento tabú si la solución resultante no está dominada por todos los miembros actuales del archivo.

¿Qué es el archivo de Pareto y cuán grande debería ser?

El archivo de Pareto almacena todas las soluciones no dominadas encontradas durante la búsqueda. Su tamaño máximo suele estar limitado (p. ej., 100-500 soluciones) para mantener manejables los costos de memoria y actualización. Cuando el archivo está lleno, la poda por distancia de aglomeración o basada en cuadrículas elimina soluciones de regiones superpobladas para mantener la diversidad.

¿Cómo se compara MOTS con NSGA-II para problemas multiobjetivo?

NSGA-II utiliza un enfoque evolutivo basado en poblaciones con cruce y mutación, lo que lo hace mejor en la exploración global al principio de la búsqueda. MOTS se basa en movimientos de vecindario y memoria, lo que a menudo proporciona una calidad de búsqueda local más fina. En la práctica, MOTS tiende a superar a los problemas combinatorios con una fuerte estructura de vecindario, mientras que NSGA-II se utiliza más ampliamente para problemas continuos.

¿Cuántas iteraciones se necesitan típicamente?

No hay una regla universal. La práctica común es presupuestar evaluaciones de funciones en lugar de iteraciones — típicamente de 10.000 a 100.000 evaluaciones dependiendo del tamaño del problema — y realizar múltiples inicios independientes para evaluar la calidad de la solución y la estabilidad del frente de Pareto.

¿Puede MOTS manejar más de dos objetivos?

Sí, pero la efectividad se degrada a medida que el número de objetivos supera tres (la 'maldición de la dimensionalidad' en el espacio de objetivos). Para cuatro o más objetivos, el tamaño del archivo explota y el mantenimiento de la diversidad se vuelve difícil; a menudo se prefieren enfoques basados en descomposición o basados en indicadores.

Métodos relacionados

Fuentes

  1. Hansen, M. P. (1997). Tabu search for multiobjective optimization: MOTS. Presented at the 13th International Conference on Multiple Criteria Decision Making (MCDM), Cape Town, South Africa.

    Abrir referencia de la publicación
    Copiado.
  2. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    Abrir referencia DOI
    Copiado.