An insight into evolutionary algorithms for continuous optimization: Learning by competitions
Motivación
Optimización continua
- Aplicaciones del mundo real como problemas continuos
- Técnicas exactas inapropiadas por su complejidad
- Metaheurísticas más adecuadas
Evaluación de metaheurísticas
- ¿En problemas reales?
- Gran diversidad de problemas
- En ocasiones, muy costosos de evaluar
Evaluación de metaheurísticas
- Se proponen benchmarks específicos…
- …Y competiciones asociadas
Aprendamos de la Historia
- Muchos datos de competiciones en más de 10 años.
- ¿Qué podemos aprender de ellas?
- Este trabajo es un análisis a partir de las competiciones.
Vamos a centrarnos en
- Mejores algoritmos en cada sesión.
- Algoritmos influyentes.
- Técnicas de los mejores algoritmos.
- Tendencias.
Tipos de competiciones
- Centradas en distintos objetivos
- Optimización global, dimensión media.
- Alta dimensionalidad.
- Otras (multimodal, restricciones).
Competiciones de Optimización Global
Tres competiciones principales
- IEEE Real-Coding Special Sessions
- GECCO Black-Box Optimizacion Benchmarking
- BBComp
IEEE Real-Coding Special Sessions
- Origen en sesión especial de 2005
- Desde 2011 se repite anualmente (salvo 2012)
- Problemas de hasta dimensión 100.
Resultados en competiciones de CEC
| Rank | … | 2014 | 2015 | 2016 | 2017 |
|---|---|---|---|---|---|
| 1 | … | L-SHADE | SPS-L-SHADE-EIG | UMOEA-II | jSO* |
| 2 | … | UMOEA | DEsPA | LSHADE-EpSin | LSHADE-cnEpSin |
| 3 | … | MVMO-SH | MVMO/LSHADE-ND | i-LSHADE | LSHADE_SPACMA |
GECCO Black-Box Optimizacion Benchmarking
- Desde 2009 se repite (casi) anualmente
- Principalmente en GECCO (salvo CEC 2015)
- Problemas de hasta 40 dimensiones
- Software para automatizar la experimentación
Resultados de las competiciones en BBOB
| Rank | … | 2014 | 2015 | 2016 | 2017 |
|---|---|---|---|---|---|
| 1 | … | HCMA | R-LSHADE* | Sin mejoras | Sin mejoras |
| 2 | … | HMLSL | CMA-TPA/MSR | Sin mejoras | Sin mejoras |
- Dominio absoluto de versiones de CMA-ES.
- Sin mejoras significativas los últimos años.
BBComp
- Desde 2015 en varios congresos (GECCO, CEC, EMO)
- Realmente black-box
- Evaluación en servidor
- Sin acceso al código por parte de los usuarios
- Problemas de hasta 64 dimensiones
Resultados de las competiciones en BBComp
| Rank | GECCO'2015 | CEC'2015 | GECCO'2016 | GECCO'2017 |
|---|---|---|---|---|
| 1 | KNITRO | UMOEA | two-stage | DTS-CMAES |
| 2 | MVMO | two-stage | - | two-stage |
| 3 | NSMO | KNITRO | - | - |
- Participación de propuestas no publicadas.
- KNITRO, software comercial.
- two-stage robusto en distintas competiciones.
Lecciones aprendidas
Lecciones aprendidas
- Dos comunidades prácticamente aisladas
- Sin influencia mutua en el desarrollo de nuevas técnicas
- Difícil comparar y trasladar resultados
- En BBOB: variantes de CMA-ES
- En CEC: DEs avanzados
- Mucho desarrollo desde el DE básico
Competiciones en alta dimensionalidad
CEC LSGO Special Sessions
- Primera edición en 2008
- Ininterrumpidamente desde 2012
- Problemas de 1000D
- Varias etapas
- Primeros años (2008-2010)
- Auge del algoritmo DE (2010-2011)
- El reino de MOS (2011-2018)
- ¿Una nueva era? (2018)
Primeros años
- Gran variedad de algoritmos
- Evolución del benchmark (2008 vs. 2010)
- Co-evolución vs. hibridación
- Algoritmos relevantes: MTS y MA-SW-Chains
Auge del DE
- Special Issue de Soft Computing en 2011
- Benchmark de funciones escalables (basado en el de CEC 2008)
- Más de la mitad de las propuestas basadas en DE
- Los tres primeros lo usan
- Un ganador claro: MOS
El reino de MOS
El reino de MOS
- Primeros resultados relevantes en ISDA 2009 y BBOB 2010
- Irrupción en Special Issue SOCO 2011
- Mejores resultados en los siguientes benchmarks
- CEC 2008, CEC 2010, SOCO 2011, CEC 2013
- No un algoritmo sino un framework de hibridación
¿Una nueva era?
- Nuevo ganador en CEC 2018: SHADE-ILS
- Mejor resultado final que MOS (aunque convergencia más lenta)
- ¿Actualización de MOS?
- Reemplazo de DE básico por SHADE
- Incorporación de otras LSs
Lecciones aprendidas
Lecciones aprendidas
- Dos aproximaciones: co-evolución e hibridación
- Uso de distintas versiones de DE
- Necesaria componente de intensificación
- Gestión del uso de FEs (regiones interesantes)
- Mecanismos especializados en características de funciones
- Problemas de muy alta dimensionalidad (GPUs, etc.)
Optimización multimodal
CEC niching competitions
- 3 ediciones: 2013, 2015 y 2016
- Versiones modificadas de algoritmos de optimización global
- Ganador de 2013 (NEA2) todavía entre los mejores en 2016
Optimización con restricciones
CEC constraint optimization competitions
- Sólo 2 ediciones: 2006 y 2010
- Mejores algoritmos basados en DE
- Ganador de 2010 versión actualizada de ganador de 2006
- Pocos datos para identificar tendencias
Tendencias tras una década de competiciones
Algoritmos influyentes
Influencia de CMA-ES
- Ganadores de varias ediciones del BBOB
- Usado como búsqueda local (DRMA-LSCh-CMA)
- O como componente hibridado (iCMAES-ILS)
- También en alta dimensionalidad (CC-CMA-ES)
Influencia de CMA-ES
Influencia de L-SHADE
- Evolución de SHADE (a su vez de JADE)
- Posibilidad de reducir población
- Pasó de 4º en 2013 a ganador en 2014
- Ganadores de 2015 y 2016 también se basan en L-SHADE
Influencia de L-SHADE
Influencia de MVMO
- Ganador en la sesión de expensive optimization
- Primera version tampoco ganó su competición
- Evolución…
Influencia de MVMO
Técnicas y componentes populares
- Parameter tuning vs. self-adaptation
- Hibridización de múltiples componentes
- Selección dinámica de componentes
- Frameworks de hibridación de algoritmos completos (MOS)
- Algoritmos meméticos
- Adaptación del tamaño de la población
- Mejor uso de información (soluciones buenas vs. malas)
Algoritmos meméticos en LSGO
Conclusiones
- Diversidad de competiciones y benchmarks
- Difícil mantenerse al día
- Análisis estructurado de los últimos 10 años
- Algoritmos influyentes: CMA-ES, L-SHADE, MVMO and MOS
- Identificación de técnicas populares
Questions
