Maximum Dispersion, Maximum Concentration: Enhancing the Quality of MOP Solutions

Resumen Técnico: Máxima Dispersión, Máxima Concentración

Definición del Problema
Los problemas de optimización multiobjetivo (MOP) requieren equilibrar objetivos en conflicto, con el objetivo típico de aproximarse al Frente de Pareto (PF) en el espacio de objetivos. Si bien los algoritmos evolutivos multiobjetivo (MOEA) tradicionales convergen eficazmente al PF, a menudo sufren una limitación crítica: las soluciones tienden a agruparse en regiones específicas del espacio de decisión. Esta falta de diversidad en el espacio de decisión ($\Omega$) crea un sesgo de implementación, donde se presenta a los tomadores de decisiones un conjunto estrecho de opciones que pueden volverse inviables si las condiciones iniciales cambian. Por el contrario, aunque existen métodos basados en preferencias para centrar los esfuerzos de búsqueda en una Región de Interés (ROI) específica en el espacio de objetivos para mejorar la convergencia, rara vez abordan la necesidad simultánea de máxima dispersión en el espacio de decisión. El artículo identifica un vacío en la literatura respecto a la optimización simultánea de la concentración de soluciones en el espacio de objetivos y la dispersión en el espacio de decisión.

Metodología: El Algoritmo C-DWU
Los autores proponen el algoritmo C-DWU (Cone-Dominance Weighted Uniformity), una adaptación del enfoque existente de Uniformidad Ponderada por Dominancia (DWU). La metodología integra las preferencias del tomador de decisiones, definidas por un cono de preferencia $C$ (caracterizado por un vector de eje $v$ y un ángulo de apertura $\theta$), en el proceso evolutivo a través de dos modificaciones específicas:

1. Clasificación No Dominada Penalizada: Durante la fase de clasificación, las soluciones ubicadas fuera del cono de preferencia $C$ son penalizadas. La penalización es proporcional a la distancia angular ($\phi$) entre el vector de objetivos de la solución y el eje del cono $v$. Esto se calcula mediante una función de penalización $P_{\alpha,\theta}(\phi) = \lfloor e^{\alpha(\phi-\theta)} \rfloor$, la cual aumenta el nivel del frente de no dominancia de las soluciones externas, empujando eficazmente la búsqueda hacia la ROI.
2. Heurística de Selección Modificada (C-wd): La heurística de selección DWU estándar, que maximiza la uniformidad en el espacio de decisión, se modifica para incorporar el cono de preferencia. Una nueva función, C-wd, aplica un término de penalización $P_{\beta,\theta}(\phi)$ al cálculo de la uniformidad ponderada por dominancia para las soluciones fuera del cono. Esto asegura que, mientras el algoritmo busca maximizar la distancia entre soluciones en el espacio de decisión (dispersión), priorice aquellas que también satisfagan las restricciones de concentración dentro de la ROI del espacio de objetivos.

El algoritmo tiene como objetivo encontrar un subconjunto de soluciones que sean Pareto-óptimas, concentradas dentro de la ROI definida en el espacio de objetivos y máximamente dispersas en el espacio de decisión.

Configuración Experimental y Resultados
Los autores evaluaron el C-DWU frente a una versión modificada de NSGA-II (denotada como C-NSGAII), que aplica la misma penalización basada en el cono al NSGA-II estándar pero carece del mecanismo de dispersión en el espacio de decisión. Los experimentos se realizaron en problemas de optimización restringida bi-objetivo utilizando los conjuntos de prueba WFG4, WFG9 (multimodal) y DTLZ2 (unimodal) con dimensiones de espacio de decisión de 5, 7 y 9.

• Convergencia (Espacio de Objetivos): Medida por la Distancia Generacional Invertida (IGD) relativa a la ROI. Los resultados indican que el C-NSGAII logró una convergencia ligeramente mejor (valores de IGD más bajos) en la mayoría de las instancias.
• Dispersión (Espacio de Decisión): Medida por una métrica de uniformidad basada en la distancia mínima entre soluciones. El C-DWU superó significativamente al C-NSGAII, logrando valores de uniformidad mucho más altos.
• Visualización: La visualización de alta dimensión (usando CAP-VIZ) del problema WFG4 reveló que las soluciones de C-NSGAII se agrupaban fuertemente en un solo sector del espacio de decisión (cerca del eje $e_9$), mientras que las soluciones de C-DWU se distribuían a través de múltiples sectores (7, 8 y 9) con mayor variabilidad tanto en la distancia angular como en la norma euclidiana.

Contribuciones Clave

• Optimización de Doble Objetivo: El artículo introduce un marco que maximiza simultáneamente la concentración de soluciones en una ROI específica del espacio de objetivos y maximiza la dispersión de las soluciones en el espacio de decisión.
• Adaptación Algorítmica: El desarrollo de C-DWU, que modifica el algoritmo DWU para aceptar restricciones de cono de preferencia sin sacrificar la diversidad en el espacio de decisión.
• Mitigación del Sesgo: El enfoque aborda el problema de las soluciones "polarizadas" en el espacio de decisión, ofreciendo a los tomadores de decisiones un conjunto diverso de opciones de implementación que son todas óptimas dentro de una región preferida del espacio de objetivos.

Significancia y Reivindicaciones
Los autores afirman que el método propuesto mejora la calidad de las soluciones MOP al equilibrar la diversidad y la precisión. Argumentan que, si bien el algoritmo C-DWU puede exhibir una reducción marginal en las tasas de convergencia en comparación con C-NSGAII, este compromiso está justificado por la ganancia sustancial en la diversidad de soluciones. La principal significancia radica en proporcionar a los tomadores de decisiones un conjunto robusto de opciones; la diversidad de soluciones en el espacio de decisión permite flexibilidad si ocurren cambios imprevistos en el escenario del mundo real, evitando la necesidad de una re-optimización costosa. El artículo concluye que definir una ROI mediante un cono de preferencia es un método efectivo y fácilmente ajustable para integrar las preferencias del tomador de decisiones en los algoritmos evolutivos preservando la representatividad del conjunto de soluciones.