Evolución Estratégica (CMA-ES) — Adaptación de la Matriz de Covarianza
- Propuesto por
- Nikolaus Hansen & Andreas Ostermeier
- Año
- 2001
- Tipo
- Derivative-free continuous black-box optimizer
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
CMA-ES, siglas en inglés de Covariance Matrix Adaptation Evolution Strategy, es un optimizador moderno sin derivadas para funciones continuas de caja negra introducido por Hansen y Ostermeier en 2001.
Mantiene una población de soluciones candidatas extraídas de una distribución normal multivariante y actualiza iterativamente la media, el tamaño del paso y la matriz de covarianza completa de la distribución para dirigir la búsqueda hacia regiones mejores del espacio de parámetros. Se ha convertido en el estándar de facto para la optimización continua de caja negra y se utiliza ampliamente en la búsqueda de arquitecturas neuronales y la optimización de políticas de aprendizaje por refuerzo.
La intuición detrás del método
Imagine que está buscando el punto más bajo en un paisaje montañoso pero no puede ver el terreno — solo puede sondear ubicaciones individuales y conocer sus alturas. CMA-ES funciona como un enjambre guiado: deja caer una nube de sondas alrededor de la mejor suposición actual, mide qué tan buena es cada sonda y luego remodela la nube para la siguiente ronda. La nube no es una esfera simple — aprende la forma alargada e inclinada del valle en el que está descendiendo recordando qué direcciones condujeron a mejoras. A lo largo de generaciones sucesivas, la nube se estrecha y se inclina para alinearse con la curvatura de la superficie de pérdida, permitiendo que el algoritmo navegue por valles largos y estrechos que atraparían a métodos más simples.
Historia
Las estrategias evolutivas se introdujeron en las décadas de 1960 y 1970 como una familia de optimizadores basados en población inspirados en la evolución biológica. El mecanismo de adaptación de la matriz de covarianza fue desarrollado por Hansen y Ostermeier y descrito completamente en su artículo de 2001 en Evolutionary Computation, que demostró que la auto-adaptación completamente derandomizada — el aprendizaje de la geometría completa de segundo orden del paisaje de búsqueda a partir del historial de pasos exitosos — superó drásticamente a las estrategias evolutivas anteriores en problemas mal condicionados y no separables. El tutorial de Hansen de 2016 consolidó el algoritmo y sus propiedades teóricas, convirtiendo a CMA-ES en el método de referencia estándar para la evaluación comparativa de optimización continua de caja negra.
Cuándo usarlo
CMA-ES es apropiado cuando la función objetivo es continua, posiblemente no convexa, multimodal o ruidosa, y cuando la información de gradiente no está disponible o es demasiado costosa de calcular. El rango de dimensionalidad ideal es aproximadamente de 10 a 1000 parámetros; por debajo de 10 dimensiones, los métodos más simples suelen ser suficientes, y por encima de 1000, el costo de memoria cuadrática de la matriz de covarianza puede volverse prohibitivo. No hay un requisito de tamaño de muestra mínimo en el sentido estadístico — el algoritmo genera sus propios puntos de evaluación. CMA-ES es una opción natural para la optimización de hiperparámetros, la búsqueda de arquitecturas neuronales, la optimización de políticas de aprendizaje por refuerzo y problemas de diseño de ingeniería donde el simulador solo proporciona salidas de caja negra.
Limitaciones y consideraciones
- El costo computacional cuadrático de memoria y por generación en función del número de dimensiones limita la aplicabilidad más allá de aproximadamente 1000 parámetros sin variantes de reducción de dimensionalidad.
- Converge a un óptimo local en ausencia de reinicios; para paisajes altamente multimodales, se necesitan múltiples reinicios (IPOP-CMA-ES o BIPOP-CMA-ES).
- No es adecuado para espacios de búsqueda discretos o combinatorios — el método se define intrínsecamente sobre vectores continuos de valores reales.
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 — funciona en cualquier función objetivo invocable, incluidas las ruidosas o basadas en simulaciones.
- Aprende la curvatura local del paisaje de búsqueda a través de la adaptación de la covarianza, lo que le permite navegar por espacios de búsqueda alargados y mal condicionados que derrotan a los métodos sin gradiente con distribuciones de búsqueda fijas.
- Invariante a transformaciones que preservan el orden de la función objetivo y a rotaciones del espacio de búsqueda, lo que lo hace robusto en una amplia variedad de geometrías de problemas.
- Bien adaptado para problemas continuos de dimensionalidad moderada a alta (10-1000 parámetros) con un único hiperparámetro sintonizable — el tamaño de paso inicial.
Aplicaciones
- Optimización de hiperparámetros para modelos de aprendizaje automático, incluidas arquitecturas de redes neuronales y agentes de aprendizaje por refuerzo.
- Búsqueda de arquitecturas neuronales — optimización de parámetros de arquitectura codificados de forma discreta mediante relajación continua.
- Optimización de políticas de aprendizaje por refuerzo cuando la política está parametrizada por un vector continuo.
- Optimización de diseño de ingeniería, como optimización de forma aerodinámica y ajuste de parámetros estructurales, donde solo se dispone de salidas del simulador.
- Calibración de modelos científicos — ajuste de modelos de simulación a datos experimentales cuando la verosimilitud no es diferenciable o es computacionalmente costosa.
Cómo funciona
Cómo funciona
El algoritmo se inicia con un vector de solución inicial y un tamaño de paso inicial (sigma). La matriz de covarianza comienza como la matriz identidad — una nube de búsqueda perfectamente esférica. Se establece el tamaño de la población, típicamente alrededor de 4 + floor(3 * ln(dimensión)).
En cada generación, se muestrea una población de soluciones candidatas de la distribución normal multivariante actual definida por el vector medio, el tamaño del paso y la matriz de covarianza. Debido a que la distribución es normal multivariante, las muestras reflejan tanto la mejor estimación actual como la forma aprendida del espacio de búsqueda.
Cada solución candidata se pasa a la función objetivo y recibe una puntuación de aptitud. No se requiere información de gradiente — solo se necesita el valor objetivo escalar en cada punto muestreado. Esto hace que CMA-ES sea adecuado para objetivos ruidosos, no diferenciables y basados en simulaciones.
La media se mueve hacia las soluciones de mejor rango. La matriz de covarianza y el tamaño del paso se actualizan utilizando dos caminos de adaptación complementarios — actualizaciones de rango uno y rango mu — de modo que las direcciones que produjeron buenas mejoras sean más probables en la próxima generación. Este es el mecanismo central por el cual CMA-ES aprende la geometría local del paisaje.
El algoritmo repite el ciclo de muestreo-evaluación-actualización hasta que se cumple un criterio de parada: un número máximo de evaluaciones de la función, una tolerancia en el cambio de la media o el tamaño del paso, o una degeneración detectada de la matriz de covarianza. Se devuelve la mejor solución encontrada en todas las generaciones.
Errores comunes
- Establecer el tamaño de paso inicial demasiado pequeño atrapa la búsqueda en un vecindario estrecho e impide la exploración; demasiado grande y las primeras generaciones desperdician evaluaciones lejos del óptimo. Una regla general común es establecer sigma de modo que el óptimo se encuentre dentro de tres sigma del punto de partida.
- Aplicar CMA-ES a problemas de dimensionalidad muy baja (menos de cinco parámetros) suele ser un desperdicio — la búsqueda en cuadrícula simple o Nelder-Mead son suficientes, y la sobrecarga de población de CMA-ES no aporta ningún beneficio.
- Ejecutar una sola instancia de CMA-ES en un paisaje multimodal corre el riesgo de no encontrar el óptimo global; utilice reinicios múltiples o estrategias de reinicio basadas en población (IPOP/BIPOP) cuando se sepa que el paisaje es altamente multimodal.
- Tratar la mejor solución devuelta como el verdadero óptimo global sin verificación de reinicio es un error común — siempre confirme con múltiples ejecuciones independientes cuando el objetivo es altamente no convexo.
Preguntas frecuentes
¿Cómo difiere CMA-ES de un algoritmo genético simple?
Un algoritmo genético clásico mantiene una población y aplica cruce y mutación con operadores fijos. CMA-ES, en cambio, modela la población como muestras de una distribución normal multivariante y adapta continuamente esa distribución — su media, tamaño de paso y matriz de covarianza completa — basándose en qué soluciones tuvieron éxito. Esto permite a CMA-ES aprender la forma del paisaje de pérdida y navegar por espacios correlacionados y mal condicionados de manera mucho más eficiente que un algoritmo genético con operadores fijos.
¿Garantiza CMA-ES encontrar el óptimo global?
No. CMA-ES es un método de búsqueda local en el sentido de que una sola ejecución puede converger a un óptimo local. Para paisajes multimodales, se recomiendan múltiples reinicios independientes — posiblemente con tamaños de población crecientes (IPOP-CMA-ES) — para mejorar la cobertura del espacio de búsqueda.
¿Cuál es el hiperparámetro más importante a configurar?
El tamaño de paso inicial sigma es el hiperparámetro más influyente. Una buena heurística es establecerlo de modo que el óptimo esperado se encuentre aproximadamente a tres sigma del punto de partida. El tamaño de la población y el número máximo de evaluaciones son controles secundarios; la fórmula de tamaño de población predeterminada (4 + floor(3 * ln(dimensión))) funciona bien en la práctica.
¿Puede CMA-ES manejar funciones objetivo ruidosas?
Sí. Dado que CMA-ES solo utiliza información de orden de rango de la población — no valores absolutos de la función — es relativamente robusto al ruido. Para evaluaciones muy ruidosas, aumentar el tamaño de la población o promediar múltiples evaluaciones por candidato puede mejorar aún más la robustez.
Métodos relacionados
Fuentes
Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.
Abrir referencia DOICopiado.Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.
Abrir referencia de la publicaciónCopiado.