QUASAR: An Evolutionary Algorithm to Accelerate High-Dimensional Numerical Optimization

Resumen Técnico: QUASAR – Un Algoritmo Evolutivo para la Optimización de Alta Dimensión

Planteamiento del Problema
La optimización numérica de alta dimensión sigue siendo un desafío persistente en la ciencia computacional, particularmente en campos como el aprendizaje automático, la ingeniería y las finanzas. El obstáculo principal es la "maldición de la dimensionalidad", donde el crecimiento exponencial del espacio de búsqueda vuelve ineficaces los métodos tradicionales de búsqueda paramétricos y basados en gradientes. Si bien las metaheurísticas, específicamente la Evolución Diferencial (DE), se han consolidado como optimizadores robustos, las variantes estándar de DE suelen tener dificultades para mantener un equilibrio efectivo entre la exploración global y la explotación local en espacios de alta dimensión. Esto frecuentemente conduce al estancamiento o a la convergencia prematura, lo que requiere reinicios frecuentes o un ajuste extensivo de hiperparámetros, limitando su utilidad práctica.

Metodología: El Algoritmo QUASAR
Para abordar estas limitaciones, el artículo presenta Quasi-Adaptive Search with Asymptotic Reinitialization (QUASAR). Conceptualmente inspirado en la búsqueda probabilística de estabilidad en los núcleos estelares y en el comportamiento de las partículas cuánticas, QUASAR extiende el marco de DE a través de tres mecanismos altamente estocásticos diseñados para equilibrar dinámicamente la exploración y la explotación:

1. Estrategias de Mutación Probabilística:
   En lugar de una estrategia de mutación fija, QUASAR emplea un enfoque de "empuje y tracción" utilizando tres estrategias distintas seleccionadas dinámicamente según una "tasa de entrelazamiento" (por defecto 0.33):

   • Spooky-Best (Local/Explotación): Similar a DE/best/1, esta estrategia explota el espacio de búsqueda inmediato alrededor de la mejor solución actual ($X_{best}$) utilizando un factor de mutación muestreado de una distribución normal $N(0, 0.33^2)$.
   • Spooky-Current y Spooky-Random (Global/Exploración): Estas estrategias impulsan la exploración no local. Utilizan una distribución bimodal para el factor de mutación, $N(0.5, 0.25^2) + N(-0.5, 0.25^2)$, para fomentar saltos de mayor magnitud. Notablemente, la estrategia Spooky-Random utiliza el mismo vector aleatorio dos veces en su formulación.

2. Cruce Basado en Rango:
   QUASAR utiliza una tasa de cruce binomial dinámica ($CR_i$) inversamente proporcional al rango de aptitud (fitness) de la solución. Las mejores soluciones (rango 0) se les asigna una tasa de cruce más alta (con un límite mínimo de 0.33), lo que permite que recombinen rápidamente componentes de los vectores mutantes. Esto asegura que las soluciones de alta calidad hereden rasgos beneficiosos mientras mantienen la diversidad.

3. Reinicialización de Covarianza Asintótica:
   Una innovación principal de QUASAR es su mecanismo de reinicialización. En las primeras generaciones, el 33% de la población con peor desempeño es reinicializada. La probabilidad de este evento decae asintóticamente hacia un objetivo de 0.33 a medida que avanzan las generaciones.

   • Mecanismo: Las nuevas soluciones se muestrean de una distribución normal multivariante definida por la media ($\mu$) y la matriz de covarianza ($\Sigma$) del 25% superior de la población.
   • Ruido: Se añade un vector de ruido a la distribución muestreada para promover aún más la exploración.
   • Restricción: Este mecanismo se omite si el tamaño de la población ($N$) es menor que la dimensionalidad ($D$) para evitar matrices de covarianza singulares.

Diseño Experimental
La eficacia de QUASAR fue evaluada rigurosamente contra la DE estándar (implementación de SciPy) y el estado del arte L-SHADE (implementación de MealPy) utilizando la suite de pruebas de referencia CEC2017 de 29 funciones de prueba.

• Parámetros: Los experimentos utilizaron los hiperparámetros por defecto para todos los algoritmos para asegurar una comparación justa.
• Variantes: Los ensayos se realizaron en diversas dimensiones ($D \in [10, 30, 50, 100]$) con un tamaño de población fijo ($N=1000$), y variando los tamaños de población ($N \in [100, 5000]$) con una dimensión fija ($D=100$).
• Métricas: El rendimiento se midió mediante sumas de rangos de Friedman, factores de reducción de error de la media geométrica ($R_{error}$) y razones de tiempo de ejecución de optimización ($R_{time}$). La significancia estadística fue verificada mediante la prueba de suma de rangos de Wilcoxon.

Resultados Clave
QUASAR demostró un rendimiento superior en todas las métricas en comparación con DE (implementación de SciPy) y L-SHADE:

• Ranking General: Utilizando la prueba de Friedman, QUASAR alcanzó la suma de rangos más baja (367), superando significativamente a L-SHADE (452) y DE (735).
• Calidad de la Solución: Las comparaciones de la media geométrica revelaron que QUASAR mejoró la calidad de la solución final en un promedio de 3.85× sobre DE y 2.07× sobre L-SHADE ($p \ll 0.001$). Las ganancias más significativas se observaron en dimensiones más altas (ej. 100D) y tamaños de población más grandes.
• Eficiencia Computacional: QUASAR fue 1.40× más rápido que DE y 5.16× más rápido que L-SHADE en promedio. El algoritmo escaló linealmente con la dimensionalidad, manteniendo la eficiencia incluso cuando la complejidad del problema aumentaba.
• Robustez: El algoritmo funcionó eficazmente utilizando sus parámetros por defecto, sin requerir un ajuste manual de hiperparámetros.

Significancia y Reivindicaciones
El artículo postula que QUASAR establece un nuevo estándar para los algoritmos evolutivos en problemas de optimización complejos, de alta dimensión y no diferenciables. Su significancia radica en:

1. Efectividad: Logra mejoras estadísticamente significativas en la calidad de la solución sin requerir un ajuste extensivo de parámetros.
2. Eficiencia: Ofrece aceleraciones sustanciales sobre los métodos actuales de vanguardia, haciéndolo viable para aplicaciones del mundo real computacionalmente costosas.
3. Facilidad de Uso: La dependencia de los parámetros por defecto y una implementación simplificada (disponible como un paquete de Python de código abierto, hdim_opt) permite una integración fluida en flujos de trabajo existentes.

Los autores concluyen que QUASAR es una herramienta poderosa y lista para usar para los desafíos de optimización de alta dimensión de la próxima generación, aunque señalan que trabajos futuros podrían explorar matrices de covarianza ponderadas (similares a CMA-ES) y la verificación en problemas con restricciones o multiobjetivo.