Saltar al contenido
Volver a los resultados

Recocido simulado multiobjetivo (Multi-Objective Simulated Annealing, MOSA)

Propuesto por
Serafini, P.; Czyzak, P. and Jaszkiewicz, A.
Año
1992–1998
Tipo
Metaheuristic / Pareto-based 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

Tamaño de letra

¿Qué hace?

El recocido simulado multiobjetivo (MOSA) extiende la metaheurística clásica de recocido simulado a problemas con dos o más funciones objetivo en conflicto.

En lugar de converger a un único óptimo, MOSA explora el espacio de soluciones estocásticamente y mantiene un archivo de soluciones no dominadas (óptimas de Pareto), ofreciendo a los decisores un frente diverso de compromisos (trade-offs) en lugar de una única respuesta prescrita.

La intuición detrás del método

El recocido simulado clásico imita el enfriamiento controlado de los metales para escapar de los óptimos locales —aceptando ocasionalmente peores soluciones a alta temperatura, y volviéndose más selectivo a medida que la temperatura desciende. MOSA aplica este mismo mecanismo probabilístico de escape a través de múltiples objetivos simultáneamente. Cuando una solución candidata empeora algunos objetivos pero mejora otros, la lógica de dominancia determina si entra en el archivo de Pareto. El esquema de enfriamiento reduce gradualmente la aleatoriedad, enfocando la búsqueda cerca de la frontera de Pareto. El resultado es una aproximación del verdadero frente de Pareto alcanzado sin requerir información de gradiente ni suposiciones de convexidad.

Historia

El recocido simulado fue introducido por Kirkpatrick et al. en 1983. Serafini (1992) fue uno de los primeros en proponer formalmente su extensión a múltiples objetivos. Czyzak y Jaszkiewicz (1998) desarrollaron Pareto Simulated Annealing (PSA), que estableció el archivo de Pareto como la estructura de salida central y proporcionó la formulación del criterio de aceptación ampliamente adoptada hoy en día. Desde entonces, MOSA se ha aplicado en diseño de ingeniería, planificación y logística.

Cuándo usarlo

Utilice MOSA cuando se enfrente a un problema de optimización con dos o más objetivos en conflicto y variables de decisión continuas o combinatorias, particularmente cuando el panorama de objetivos no es convexo, es multimodal o no tiene gradientes. Es muy adecuado para problemas de planificación, enrutamiento, diseño de ingeniería y asignación de recursos donde un frente explícito de compromisos (trade-offs) es más útil que un único agregado ponderado. Prefiera MOSA sobre Monte Carlo puramente estocástico cuando necesite optimización en lugar de cuantificación de la incertidumbre. NO utilice MOSA cuando el problema tenga un solo objetivo (el recocido simulado clásico es suficiente), cuando el frente de Pareto deba encontrarse exactamente (los algoritmos exactos son mejores para problemas pequeños), cuando el número de objetivos supere aproximadamente cinco (los métodos basados en el hipervolumen escalan mejor), o cuando la evaluación de objetivos sea extremadamente costosa por llamada (los métodos basados en sustitutos son preferibles).

Limitaciones y consideraciones

  • La calidad de la solución y la cobertura del frente de Pareto son sensibles a la elección de la temperatura inicial, la tasa de enfriamiento y el operador de vecindad, lo que requiere un ajuste específico del problema.
  • La convergencia a un frente de Pareto de alta calidad puede requerir muchas evaluaciones de objetivos, lo que la hace lenta para simulaciones de caja negra costosas.
  • El mantenimiento y la actualización del archivo de Pareto introducen sobrecarga y el archivo puede crecer mucho, aumentando los costos de memoria y comparación.
  • A diferencia de los métodos basados en poblaciones (p. ej., NSGA-II), la naturaleza de trayectoria única del MOSA básico puede producir una cobertura desigual del frente de Pareto.
  • Las garantías teóricas de convergencia requieren un esquema de enfriamiento infinitamente lento, lo cual no es práctico; los esquemas finitos sacrifican la garantía de optimalidad.

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

Fortalezas

  • No requiere información de gradiente y maneja paisajes de objetivos no convexos, discontinuos y multimodales.
  • La aceptación probabilística de soluciones inferiores permite escapar de frentes de Pareto locales que atrapan enfoques puramente codiciosos.
  • Produce una aproximación diversa del frente de Pareto completo en una sola ejecución, brindando a los decisores opciones explícitas de compromiso.
  • La implementación es sencilla y el esquema de enfriamiento proporciona un parámetro intuitivo para ajustar el equilibrio entre exploración y explotación.
  • Aplicable a problemas de optimización tanto continuos como combinatorios con una reformulación mínima.

Aplicaciones

  • Programación multiobjetivo de talleres (job-shop) y de líneas de producción (flow-shop) (minimizando simultáneamente el makespan o tiempo total de finalización y la tardanza)
  • Problemas de diseño de redes y enrutamiento con objetivos de costo y confiabilidad
  • Optimización de diseño de ingeniería (p. ej., minimizar peso y tensión en componentes estructurales)
  • Optimización de carteras que equilibra el rendimiento esperado y el riesgo
  • Planificación del uso del suelo y espacial con objetivos económicos y ambientales contrapuestos
  • Asignación de recursos sanitarios que equilibra costo, cobertura y calidad del servicio

Cómo funciona

Cómo funciona

1

Generar una solución inicial (aleatoria o heurística), establecer una temperatura inicial T_0 suficientemente alta para permitir una exploración amplia, inicializar el archivo de Pareto con cualquier solución no dominada encontrada y definir criterios de parada (máximo de iteraciones o un umbral mínimo de temperatura).

2

Perturbar la solución actual utilizando un operador de vecindad apropiado para la estructura del problema (p. ej., intercambio, inserción o perturbación gaussiana para variables continuas) para producir una o más soluciones vecinas candidatas.

3

Evaluar todas las funciones objetivo para el vecino candidato. Determinar si domina, es dominado por, o no está dominado en relación con la solución actual y las soluciones en el archivo de Pareto. Los candidatos no dominados se añaden al archivo; los miembros dominados del archivo se eliminan.

4

Aplicar un criterio de aceptación multiobjetivo. Si el vecino no está dominado con respecto a la solución actual, se acepta. Si está dominado, aún puede ser aceptado con probabilidad P = exp(−ΔF / T) donde ΔF agrega el deterioro del objetivo, permitiendo escapar de frentes de Pareto locales.

Fórmula
P(\text{accept}) = \exp\!\left(-\frac{\Delta f}{T}\right)
5

Reducir la temperatura según un esquema de enfriamiento, comúnmente geométrico: T_{k+1} = α · T_k con α ∈ (0.8, 0.99). Las temperaturas más bajas restringen la aceptación de movimientos inferiores, intensificando progresivamente la búsqueda cerca de las regiones prometedoras del frente de Pareto.

Fórmula
T_{k+1} = \alpha \cdot T_k, \quad \alpha \in (0,1)
6

Devolver el archivo de Pareto final como resultado. Realizar un postprocesamiento para eliminar soluciones dominadas que puedan haberse acumulado y presentar el archivo como una aproximación discreta del frente de Pareto-óptimo para la selección por parte del decisor.

Errores comunes

  • Establecer la temperatura inicial demasiado baja provoca una convergencia prematura a una región local del frente de Pareto; siempre calibre T_0 de modo que la tasa de aceptación inicial sea de alrededor del 70-90%.
  • Usar una tasa de enfriamiento α demasiado cercana a 1.0 hace que la ejecución sea prohibitivamente larga; demasiado cerca de 0 provoca una convergencia rápida antes de que el frente de Pareto se explore adecuadamente.
  • Definir ΔF para la probabilidad de aceptación con una suma ingenua de diferencias de objetivos mezcla escalas incomparables — normalice cada objetivo antes de la agregación.
  • No eliminar periódicamente las soluciones dominadas del archivo lo infla y degrada la calidad del resultado final.
  • Evaluar el éxito en una sola ejecución es engañoso dada la variación estocástica; siempre agregue resultados de múltiples ejecuciones independientes.

Preguntas frecuentes

¿Cómo difiere MOSA de NSGA-II?

NSGA-II es un algoritmo evolutivo basado en poblaciones que evoluciona un conjunto de soluciones simultáneamente utilizando cruce, mutación y ordenación no dominada. MOSA es un método basado en trayectorias que explora una solución a la vez utilizando movimientos probabilísticos. MOSA tiende a ser más simple de implementar y funciona bien para problemas combinatorios, mientras que NSGA-II generalmente proporciona una mejor cobertura del frente de Pareto para problemas continuos y escala de manera más predecible.

¿Cómo debo establecer la temperatura inicial T_0?

Una heurística común es ejecutar una fase preliminar corta y elegir T_0 de modo que se acepten aproximadamente el 80% de los movimientos aleatorios de vecinos. Esto asegura una exploración amplia al principio. Se recomienda la calibración específica del problema porque la escala de temperatura apropiada depende de la magnitud de las diferencias de las funciones objetivo.

¿Puede MOSA manejar más de dos objetivos?

Sí, pero el rendimiento se degrada a medida que aumenta el número de objetivos. El costo de gestión del archivo de Pareto aumenta y la fracción de soluciones no dominadas crece rápidamente, lo que hace que el criterio de aceptación sea menos discriminatorio. Para problemas con más de cuatro o cinco objetivos, generalmente se prefieren métodos basados en el indicador de hipervolumen o métodos basados en descomposición (p. ej., MOEA/D).

¿Cómo sé cuándo detener el algoritmo?

Los criterios de parada comunes incluyen alcanzar una temperatura mínima, agotar un presupuesto máximo de iteraciones o no observar mejora en el indicador de hipervolumen del archivo de Pareto durante un número especificado de iteraciones. En la práctica, comparar la calidad del archivo en múltiples ejecuciones con diferentes presupuestos de iteraciones es una forma fiable de diagnosticar la convergencia.

¿Es MOSA adecuado para modelos de simulación costosos?

Generalmente no sin modificaciones. Cada iteración requiere al menos una evaluación de la función objetivo, y MOSA típicamente necesita miles de iteraciones para una buena aproximación del frente de Pareto. Cuando cada evaluación implica una simulación costosa, son preferibles las versiones de MOSA asistidas por sustitutos (que utilizan metamodelos para aproximar los objetivos).

Métodos relacionados

Fuentes

  1. Czyzak, P., Jaszkiewicz, A. (1998). Pareto simulated annealing — a metaheuristic technique for multiple-objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 7(1), 34–47.

    Abrir referencia DOI
    Copiado.
  2. Serafini, P. (1992). Simulated annealing for multi-objective optimization problems. In Proceedings of the Tenth International Conference on Multiple Criteria Decision Making, Taipei, Taiwan, pp. 87–96.

    Abrir referencia de la publicación
    Copiado.