DE-2LS: Differential Evolution with Lightweight Late Local Search for Constrained Numerical Optimization

Resumen Técnico: DE-2LS para la Optimización Numérica con Restricciones

Planteamiento del Problema
La optimización numérica de un solo objetivo con restricciones requiere equilibrar tres factores contrapuestos: viabilidad (satisfacer las restricciones), convergencia del objetivo y eficiencia computacional, todo dentro de un presupuesto fijo de evaluaciones de función. Si bien la Evolución Diferencial (DE) es un algoritmo basado en población robusto, las variantes estándar suelen tener dificultades en las etapas finales de la optimización. Específicamente, tras el descubrimiento de una región factible, el presupuesto de búsqueda restante puede emplearse en generar vectores de prueba que son demasiado gruesos o estocásticos para refinar eficientemente la solución actual. Esta limitación es crítica en entornos de puntuación por pares (como las competiciones IEEE CEC), donde pequeñas mejoras en la calidad o velocidad de la solución final pueden impactar decisivamente en el ranking general.

Metodología
El artículo propone DE-2LS (Differential Evolution with Lightweight Late Local Search), una variante del marco RDEx diseñada para la optimización con restricciones. La filosofía de diseño central es "no hacer daño": los componentes originales de RDEx permanecen enteramente sin cambios, preservando sus fortalezas establecidas en la búsqueda global, el descubrimiento de la viabilidad y la velocidad.

En lugar de modificar el motor evolutivo, DE-2LS introduce una búsqueda local (LS) ligera de patrón de coordenadas como un mecanismo de "pulido guardado". Las características metodológicas clave incluyen:

• Activación en Etapa Tardía: La búsqueda local no está activa durante las etapas iniciales o medias de la ejecución para evitar la explotación prematura o el consumo de evaluaciones en cuencas no prometedoras. Se activa solo cuando se cumplen condiciones específicas:
  1. La búsqueda ha progresado más allá de un umbral (p. ej., el 85% del presupuesto), el mejor global se ha estancado durante un número determinado de generaciones, y el incumbente es factible o casi factible.
  2. Un activador de respaldo de "muy etapa tardía" (p. ej., el 95% del presupuesto) asegura un intento final de pulido incluso si los criterios de estancamiento no se cumplen estrictamente.
• Búsqueda de Patrón de Coordenadas: La LS opera alrededor de la mejor solución actual ($x_b$). Examina movimientos candidatos a lo largo de cada dimensión de coordenada ($x_d \pm \Delta$). Si un candidato mejora la solución, el centro se actualiza inmediatamente (regla de primera mejora). Si no se encuentra ninguna mejora en todas las coordenadas, el tamaño del paso $\Delta$ se reduce a la mitad.
• Aceptación Consciente de la Viabilidad: Los candidatos se aceptan según la misma lógica utilizada por RDEx: se prefiere una solución si es factible con un valor de objetivo menor, o si reduce la violación de restricciones cuando ambas soluciones son infactibles.
• Inyección de Población: Si la LS encuentra una mejor solución, esta se inyecta de nuevo en la población de RDEx. Crucialmente, no se reemplaza toda la población y la memoria de historial de éxito no se reinicia, asegurando que la dinámica adaptativa de RDEx se preserve.
• Restricciones de Presupuesto: La LS está estrictamente limitada por el presupuesto (p. ej., 0.5% del presupuesto total por llamada, con un máximo de dos llamadas), asegurando que actúe como una herramienta de refinamiento en lugar de una estrategia de búsqueda dominante.

Contribuciones Clave

1. Propuesta Algorítmica: La introducción de DE-2LS, un algoritmo de optimización con restricciones que mejora RDEx mediante una búsqueda local controlada en etapa tardía sin alterar los operadores evolutivos centrales.
2. Principio de Diseño: Un enfoque conservador que separa el descubrimiento de la viabilidad global (gestionado por RDEx) de la explotación final (gestionada por LS), evitando la interrupción de las ventajas de velocidad de RDEx.
3. Especificidad del Mecanismo: La implementación de una regla de aceptación consciente de la viabilidad dentro de la búsqueda local y una lógica de activación específica que evita la explotación prematura.
4. Validación Empírica: Estudios de ablación exhaustivos y experimentos comparativos que demuestran que el refinamiento controlado en etapa tardía es superior a las estrategias de búsqueda local agresivas o prematuras.

Resultos
El artículo evalúa DE-2LS en 28 problemas restringidos de un solo objetivo del conjunto de pruebas CEC (dimensión $D=30$, MaxFEs = $20000 \times D$). El rendimiento se mide utilizando el U-score, una métrica combinada de precisión y velocidad derivada de comparaciones por pares.

• Estudio de Ablación: Entre varias configuraciones (diferentes presupuestos, tiempos de inicio y tamaños de paso), la configuración finalizada de DE-LS logró el U-score más alto (178,749), superando a las variantes con presupuestos mayores o activación más temprana. Esto confirma que un presupuesto pequeño y tardío es óptimo.
• Comparación Directa vs. RDEx: DE-2LS mejoró el U-score de la base de RDEx en un 5.58% (de 33,369.5 a 35,230.5). Esta ganancia fue impulsada por mejoras tanto en la precisión (+6.17%) como en la velocidad (+4.99%), indicando que la búsqueda local refinó la solución sin sacrificar la velocidad de convergencia del algoritmo.
• Comparación de Cuatro Algoritmos: Comparado contra RDEx, CL-SRDE y UDE-III, DE-2LS logró el U-score general más alto (80,968) y el mejor ranking total (48).
  • Mientras que UDE-III logró la puntuación de precisión total más alta, su puntuación de velocidad significativamente menor resultó en un U-score general más bajo.
  • DE-2LS equilibró con éxito una alta precisión final con las características de convergencia rápida de RDEx.
• Estabilidad: El análisis de media y desviación estándar mostró que DE-2LS mantuvo una calidad de solución final y una estabilidad competitivas, con la búsqueda local actuando como un mecanismo de pulido controlado en lugar de desestabilizar la población.

Significancia y Reivindicaciones
El artículo sostiene que DE-2LS demuestra que el refinamiento controlado en etapa tardía es una estrategia más efectiva para la optimización con restricciones que la búsqueda local agresiva o prematura. Al preservar el marco original de RDEx, el método retiene las capacidades inherentes de velocidad y manejo de viabilidad del algoritmo, abordando al mismo tiempo su debilidad en la explotación local de grano fino.

Los autores concluyen que DE-2LS proporciona un perfil de rendimiento más equilibrado y robusto para la optimización numérica con restricciones bajo el criterio de puntuación combinada de velocidad-precisión. El trabajo sugiere que, en lugar de reformar los marcos evolutivos exitosos, añadir un componente de búsqueda local ligero y estrictamente controlado puede generar ganancias de rendimiento significativas en entornos de pruebas competitivos. El código fuente se pone a disposición para facilitar la investigación posterior.