CMA-ES

Algoritmo evolutivo

La estrategia de evolución de adaptación de matriz de covarianza (CMA-ES) es un tipo particular de estrategia para optimización numérica . Las estrategias de evolución (ES) son métodos estocásticos , sin derivadas, para la optimización numérica de problemas de optimización continua no lineal o no convexa . Pertenecen a la clase de algoritmos evolutivos y computación evolutiva . Un algoritmo evolutivo se basa ampliamente en el principio de evolución biológica , es decir, la interacción repetida de variación (a través de recombinación y mutación) y selección: en cada generación (iteración) se generan nuevos individuos (soluciones candidatas, denotadas como ) por variación de los individuos parentales actuales, generalmente de manera estocástica. Luego, se seleccionan algunos individuos para convertirse en los padres en la próxima generación en función de su aptitud o valor de función objetivo . De esta manera, se generan individuos con valores cada vez mejores a lo largo de la secuencia generacional. ${\displaystyle x}$ ${\displaystyle f(x)}$ ${\displaystyle f}$

En una estrategia de evolución , las nuevas soluciones candidatas suelen muestrearse de acuerdo con una distribución normal multivariante en . La recombinación equivale a seleccionar un nuevo valor medio para la distribución. La mutación equivale a añadir un vector aleatorio, una perturbación con media cero. Las dependencias por pares entre las variables de la distribución se representan mediante una matriz de covarianza . La adaptación de la matriz de covarianza (CMA) es un método para actualizar la matriz de covarianza de esta distribución. Esto es particularmente útil si la función está mal condicionada . ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle f}$

La adaptación de la matriz de covarianza equivale a aprender un modelo de segundo orden de la función objetivo subyacente similar a la aproximación de la matriz hessiana inversa en el método cuasi-Newton en la optimización clásica . A diferencia de la mayoría de los métodos clásicos, se realizan menos suposiciones sobre la función objetivo subyacente. Debido a que solo se explota una clasificación (o, equivalentemente, ordenación) de las soluciones candidatas, el método no requiere ni derivadas ni siquiera una función objetivo (explícita). Por ejemplo, la clasificación podría surgir de competencias por pares entre las soluciones candidatas en un torneo del sistema suizo .

Principios

Ilustración de una ejecución de optimización real con adaptación de la matriz de covarianza en un problema bidimensional simple. El paisaje de optimización esférico se representa con líneas continuas de valores iguales. La población (puntos) es mucho mayor de lo necesario, pero muestra claramente cómo cambia la distribución de la población (línea de puntos) durante la optimización. En este problema simple, la población se concentra por encima del óptimo global en unas pocas generaciones. ${\displaystyle f}$

En el algoritmo CMA-ES se explotan dos principios fundamentales para la adaptación de los parámetros de la distribución de búsqueda.

En primer lugar, un principio de máxima verosimilitud , basado en la idea de aumentar la probabilidad de soluciones candidatas exitosas y pasos de búsqueda. La media de la distribución se actualiza de modo que se maximice la probabilidad de soluciones candidatas exitosas anteriores. La matriz de covarianza de la distribución se actualiza (de manera incremental) de modo que se aumente la probabilidad de pasos de búsqueda exitosos anteriores. Ambas actualizaciones se pueden interpretar como un descenso de gradiente natural . Además, en consecuencia, el CMA realiza un análisis iterado de componentes principales de los pasos de búsqueda exitosos mientras conserva todos los ejes principales. Los algoritmos de estimación de distribución y el método de entropía cruzada se basan en ideas muy similares, pero estiman (de manera no incremental) la matriz de covarianza maximizando la probabilidad de puntos de solución exitosos en lugar de pasos de búsqueda exitosos .

En segundo lugar, se registran dos rutas de evolución temporal de la media de distribución de la estrategia, denominadas rutas de búsqueda o de evolución. Estas rutas contienen información significativa sobre la correlación entre pasos consecutivos. En concreto, si se dan pasos consecutivos en una dirección similar, las rutas de evolución se alargan. Las rutas de evolución se aprovechan de dos maneras. Una de ellas se utiliza para el procedimiento de adaptación de la matriz de covarianza en lugar de pasos de búsqueda únicos y exitosos, y facilita un aumento de la varianza posiblemente mucho más rápido en direcciones favorables. La otra ruta se utiliza para llevar a cabo un control adicional del tamaño de los pasos. Este control del tamaño de los pasos tiene como objetivo hacer que los movimientos consecutivos de la media de distribución sean ortogonales en la expectativa. El control del tamaño de los pasos evita eficazmente la convergencia prematura, pero permite una convergencia rápida hacia un valor óptimo.

Algoritmo

A continuación se describe el ( μ / μ _w ,  λ )-CMA-ES más comúnmente utilizado, donde en cada paso de iteración se utiliza una combinación ponderada de las μ mejores de λ nuevas soluciones candidatas para actualizar los parámetros de distribución. El ciclo principal consta de tres partes principales: 1) muestreo de nuevas soluciones, 2) reordenamiento de las soluciones muestreadas en función de su aptitud, 3) actualización de las variables de estado internas en función de las muestras reordenadas. Un pseudocódigo del algoritmo se ve como sigue.

set // número de muestras por iteración, al menos dos, generalmente > 4 initialize , , , , // inicializa variables de estado while not ends do // iterar for in do // muestrea nuevas soluciones y las evalúa sample_multivariate_normal(mean , covariance_matrix ) ← with // ordena soluciones // que necesitamos después and ← update_m // mueve la media a mejores soluciones ← update_ps // actualiza la ruta de evolución isotrópica ← update_pc // actualiza la ruta de evolución anisotrópica ← update_C // actualiza la matriz de covarianza ← update_sigma // actualiza el tamaño del paso usando la longitud de la ruta isotrópica return or ${\displaystyle \lambda }$  ${\displaystyle m}$ ${\displaystyle \sigma }$ ${\displaystyle C=I}$ ${\displaystyle p_{\sigma }=0}$ ${\displaystyle p_{c}=0}$    ${\displaystyle i}$   ${\displaystyle \{1\ldots \lambda \}}$  ${\displaystyle \lambda }$ ${\displaystyle x_{i}={}}$ ${\displaystyle {}=m}$ ${\displaystyle {}=\sigma ^{2}C}$ ${\displaystyle f_{i}=\operatorname {fitness} (x_{i})}$  ${\displaystyle x_{1\ldots \lambda }}$ ${\displaystyle x_{s(1)\ldots s(\lambda )}}$ ${\displaystyle s(i)=\operatorname {argsort} (f_{1\ldots \lambda },i)}$ ${\displaystyle m'=m}$ ${\displaystyle m-m'}$ ${\displaystyle x_{i}-m'}$  ${\displaystyle m}$ ${\displaystyle (x_{1},\ldots ,x_{\lambda })}$ ${\displaystyle p_{\sigma }}$ ${\displaystyle (p_{\sigma },\sigma ^{-1}C^{-1/2}(m-m'))}$ ${\displaystyle p_{c}}$ ${\displaystyle (p_{c},\sigma ^{-1}(m-m'),\|p_{\sigma }\|)}$ ${\displaystyle C}$ ${\displaystyle (C,p_{c},(x_{1}-m')/\sigma ,\ldots ,(x_{\lambda }-m')/\sigma )}$ ${\displaystyle \sigma }$ ${\displaystyle (\sigma ,\|p_{\sigma }\|)}$  ${\displaystyle m}$ ${\displaystyle x_{1}}$

El orden de las cinco asignaciones de actualización es relevante: deben actualizarse primero, deben actualizarse antes y deben actualizarse al final. Las ecuaciones de actualización para las cinco variables de estado se especifican a continuación. ${\displaystyle m}$ ${\displaystyle p_{\sigma }}$ ${\displaystyle p_{c}}$ ${\displaystyle C}$ ${\displaystyle \sigma }$

Se dan la dimensión del espacio de búsqueda y el paso de iteración . Las cinco variables de estado son ${\displaystyle n}$ ${\displaystyle k}$

${\displaystyle m_{k}\in \mathbb {R} ^{n}}$, la media de distribución y la solución favorita actual al problema de optimización,

${\displaystyle \sigma _{k}>0}$, el tamaño del paso,

${\displaystyle C_{k}}$, una matriz de covarianza simétrica y definida positiva con y ${\displaystyle n\times n}$ ${\displaystyle C_{0}=I}$

${\displaystyle p_{\sigma }\in \mathbb {R} ^{n},p_{c}\in \mathbb {R} ^{n}}$, dos caminos de evolución, inicialmente establecidos en el vector cero.

La iteración comienza con el muestreo de soluciones candidatas de una distribución normal multivariada , es decir, para ${\displaystyle \lambda >1}$ ${\displaystyle x_{i}\in \mathbb {R} ^{n}}$ ${\displaystyle \textstyle {\mathcal {N}}(m_{k},\sigma _{k}^{2}C_{k})}$ ${\displaystyle i=1,\ldots ,\lambda }$

${\displaystyle {\begin{aligned}x_{i}\ &\sim \ {\mathcal {N}}(m_{k},\sigma _{k}^{2}C_{k})\\&\sim \ m_{k}+\sigma _{k}\times {\mathcal {N}}(0,C_{k})\end{aligned}}}$

La segunda línea sugiere la interpretación como perturbación imparcial (mutación) del vector de solución favorito actual (el vector de media de distribución). Las soluciones candidatas se evalúan en la función objetivo que se debe minimizar. Denotando las soluciones candidatas ordenadas como ${\displaystyle m_{k}}$ ${\displaystyle x_{i}}$ ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle f}$

${\displaystyle \{x_{i:\lambda }\mid i=1\dots \lambda \}=\{x_{i}\mid i=1\dots \lambda \}{\text{ and }}f(x_{1:\lambda })\leq \dots \leq f(x_{\mu :\lambda })\leq f(x_{\mu +1:\lambda })\leq \cdots ,}$

El nuevo valor medio se calcula como

${\displaystyle {\begin{aligned}m_{k+1}&=\sum _{i=1}^{\mu }w_{i}\,x_{i:\lambda }\\&=m_{k}+\sum _{i=1}^{\mu }w_{i}\,(x_{i:\lambda }-m_{k})\end{aligned}}}$

donde los pesos positivos (de recombinación) suman uno. Normalmente, y los pesos se eligen de manera que . La única retroalimentación utilizada de la función objetivo aquí y en lo sucesivo es un ordenamiento de las soluciones candidatas muestreadas debido a los índices . ${\displaystyle w_{1}\geq w_{2}\geq \dots \geq w_{\mu }>0}$ ${\displaystyle \mu \leq \lambda /2}$ ${\displaystyle \textstyle \mu _{w}:=1/\sum _{i=1}^{\mu }w_{i}^{2}\approx \lambda /4}$ ${\displaystyle i:\lambda }$

El tamaño del paso se actualiza mediante la adaptación acumulativa del tamaño del paso (CSA), a veces también denominada control de longitud de ruta . La ruta de evolución (o ruta de búsqueda) se actualiza primero. ${\displaystyle \sigma _{k}}$ ${\displaystyle p_{\sigma }}$

${\displaystyle p_{\sigma }\gets \underbrace {(1-c_{\sigma })} _{\!\!\!\!\!{\text{discount factor}}\!\!\!\!\!}\,p_{\sigma }+\overbrace {\sqrt {1-(1-c_{\sigma })^{2}}} ^{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{complements for discounted variance}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\underbrace {{\sqrt {\mu _{w}}}\,C_{k}^{\;-1/2}\,{\frac {\overbrace {m_{k+1}-m_{k}} ^{\!\!\!{\text{displacement of }}m\!\!\!}}{\sigma _{k}}}} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{distributed as }}{\mathcal {N}}(0,I){\text{ under neutral selection}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}}$

${\displaystyle \sigma _{k+1}=\sigma _{k}\times \exp {\bigg (}{\frac {c_{\sigma }}{d_{\sigma }}}\underbrace {\left({\frac {\|p_{\sigma }\|}{\operatorname {E} \|{\mathcal {N}}(0,I)\|}}-1\right)} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{unbiased about 0 under neutral selection}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}{\bigg )}}$

dónde

${\displaystyle c_{\sigma }^{-1}\approx n/3}$es el horizonte temporal hacia atrás para la trayectoria de evolución y mayor que uno ( es reminiscente de una constante de decaimiento exponencial como donde es la vida útil asociada y la vida media), ${\displaystyle p_{\sigma }}$ ${\displaystyle c_{\sigma }\ll 1}$ ${\displaystyle (1-c_{\sigma })^{k}\approx \exp(-c_{\sigma }k)}$ ${\displaystyle c_{\sigma }^{-1}}$ ${\displaystyle c_{\sigma }^{-1}\ln(2)\approx 0.7c_{\sigma }^{-1}}$

${\displaystyle \mu _{w}=\left(\sum _{i=1}^{\mu }w_{i}^{2}\right)^{-1}}$es la varianza de la masa de selección efectiva y por definición de , ${\displaystyle 1\leq \mu _{w}\leq \mu }$ ${\displaystyle w_{i}}$

${\displaystyle C_{k}^{\;-1/2}={\sqrt {C_{k}}}^{\;-1}={\sqrt {C_{k}^{\;-1}}}}$es la única raíz cuadrada simétrica de la inversa de , y ${\displaystyle C_{k}}$

${\displaystyle d_{\sigma }}$El parámetro de amortiguamiento suele ser cercano a uno. Para o el tamaño del paso permanece sin cambios. ${\displaystyle d_{\sigma }=\infty }$ ${\displaystyle c_{\sigma }=0}$

El tamaño del paso aumenta si y solo si es mayor que el valor esperado ${\displaystyle \sigma _{k}}$ ${\displaystyle \|p_{\sigma }\|}$

${\displaystyle {\begin{aligned}\operatorname {E} \|{\mathcal {N}}(0,I)\|&={\sqrt {2}}\,\Gamma ((n+1)/2)/\Gamma (n/2)\\&\approx {\sqrt {n}}\,(1-1/(4\,n)+1/(21\,n^{2}))\end{aligned}}}$

y disminuye si es menor. Por esta razón, la actualización del tamaño de paso tiende a hacer que los pasos consecutivos sean -conjugados , en el sentido de que después de que la adaptación haya sido exitosa . ^[1] ${\displaystyle C_{k}^{-1}}$ ${\displaystyle \textstyle \left({\frac {m_{k+2}-m_{k+1}}{\sigma _{k+1}}}\right)^{T}\!C_{k}^{-1}{\frac {m_{k+1}-m_{k}}{\sigma _{k}}}\approx 0}$

Finalmente se actualiza la matriz de covarianza , donde nuevamente se actualiza primero la respectiva trayectoria de evolución.

${\displaystyle p_{c}\gets \underbrace {(1-c_{c})} _{\!\!\!\!\!{\text{discount factor}}\!\!\!\!\!}\,p_{c}+\underbrace {\mathbf {1} _{[0,\alpha {\sqrt {n}}]}(\|p_{\sigma }\|)} _{\text{indicator function}}\overbrace {\sqrt {1-(1-c_{c})^{2}}} ^{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{complements for discounted variance}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\underbrace {{\sqrt {\mu _{w}}}\,{\frac {m_{k+1}-m_{k}}{\sigma _{k}}}} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{distributed as}}\;{\mathcal {N}}(0,C_{k})\;{\text{under neutral selection}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}}$

${\displaystyle C_{k+1}=\underbrace {(1-c_{1}-c_{\mu }+c_{s})} _{\!\!\!\!\!{\text{discount factor}}\!\!\!\!\!}\,C_{k}+c_{1}\underbrace {p_{c}p_{c}^{T}} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{rank one matrix}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}+\,c_{\mu }\underbrace {\sum _{i=1}^{\mu }w_{i}{\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\left({\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\right)^{T}} _{\operatorname {rank} \min(\mu ,n){\text{ matrix}}}}$

donde denota la transposición y ${\displaystyle T}$

${\displaystyle c_{c}^{-1}\approx n/4}$es el horizonte temporal hacia atrás para la trayectoria de evolución y mayor que uno, ${\displaystyle p_{c}}$

${\displaystyle \alpha \approx 1.5}$y la función indicadora evalúa a uno si y solo si o, en otras palabras, , que suele ser el caso, ${\displaystyle \mathbf {1} _{[0,\alpha {\sqrt {n}}]}(\|p_{\sigma }\|)}$ ${\displaystyle \|p_{\sigma }\|\in [0,\alpha {\sqrt {n}}]}$ ${\displaystyle \|p_{\sigma }\|\leq \alpha {\sqrt {n}}}$

${\displaystyle c_{s}=(1-\mathbf {1} _{[0,\alpha {\sqrt {n}}]}(\|p_{\sigma }\|)^{2})\,c_{1}c_{c}(2-c_{c})}$Compensa en parte la pequeña pérdida de varianza en caso de que el indicador sea cero,

${\displaystyle c_{1}\approx 2/n^{2}}$es la tasa de aprendizaje para la actualización de rango uno de la matriz de covarianza y

${\displaystyle c_{\mu }\approx \mu _{w}/n^{2}}$es la tasa de aprendizaje para la actualización de rango de la matriz de covarianza y no debe exceder . ${\displaystyle \mu }$ ${\displaystyle 1-c_{1}}$

La actualización de la matriz de covarianza tiende a aumentar la probabilidad de que y de sean muestreados a partir de . Esto completa el paso de iteración. ${\displaystyle p_{c}}$ ${\displaystyle (x_{i:\lambda }-m_{k})/\sigma _{k}}$ ${\displaystyle {\mathcal {N}}(0,C_{k+1})}$

El número de muestras candidatas por iteración, , no se determina a priori y puede variar en un amplio rango. Valores más pequeños, por ejemplo , conducen a un comportamiento de búsqueda más local. Valores más grandes, por ejemplo con el valor predeterminado , hacen que la búsqueda sea más global. A veces, el algoritmo se reinicia repetidamente con un aumento de un factor de dos para cada reinicio. ^[2] Además de la configuración (o posiblemente en su lugar, si por ejemplo está predeterminado por el número de procesadores disponibles), los parámetros introducidos anteriormente no son específicos de la función objetivo dada y, por lo tanto, no están destinados a ser modificados por el usuario. ${\displaystyle \lambda }$ ${\displaystyle \lambda =10}$ ${\displaystyle \lambda =10n}$ ${\displaystyle \mu _{w}\approx \lambda /4}$ ${\displaystyle \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle \mu }$ ${\displaystyle \lambda }$

Código de ejemplo en MATLAB/Octave

función  xmin = purecmaes % ( mu/mu_w, lambda ) - CMA - ES % -------------------- Inicialización -------------------------------- % Parámetros de entrada definidos por el usuario (deben editarse) strfitnessfct = 'frosenbrock' ; % nombre de la función objetivo/aptitud N = 20 ; % número de variables objetivo/dimensión del problema xmean = rand ( N , 1 ); % punto inicial de las variables objetivo sigma = 0.3 ; % desviación estándar por coordenadas (tamaño del paso) stopfitness = 1e-10 ; % parada si la aptitud < stopfitness (minimización) stopeval = 1e3 * N ^ 2 ; % parada después de stopeval número de evaluaciones de la función % Configuración de parámetros de estrategia: Selección lambda = 4 + floor ( 3 * log ( N )); % tamaño de la población, número de descendientes mu = lambda / 2 ; % número de padres/puntos para pesos de recombinación = log ( mu + 1 / 2 ) - log ( 1 : mu ) ' ; % matriz muXone para recombinación ponderada mu = floor ( mu ); pesos = pesos / suma ( pesos ); % normalizar matriz de pesos de recombinación mueff = suma ( pesos ) ^ 2 / suma ( pesos .^ 2 ); % efectividad de varianza de la suma w_i x_i                                                   % Configuración de parámetros de estrategia: Adaptación cc = ( 4 + mueff / N ) / ( N + 4 + 2 * mueff / N ); % constante de tiempo para acumulación para C cs = ( mueff + 2 ) / ( N + mueff + 5 ); % constante t para acumulación para control sigma c1 = 2 / (( N + 1.3 ) ^ 2 + mueff ); % tasa de aprendizaje para actualización de rango uno de C cmu = min ( 1 - c1 , 2 * ( mueff - 2 + 1 / mueff ) / (( N + 2 ) ^ 2 + mueff )); % y para actualización de rango mu amortiguamientos = 1 + 2 * máx ( 0 , sqrt (( mueff - 1 ) / ( N + 1 )) - 1 ) + cs ; % amortiguamiento para sigma % usualmente cerca de 1 % Inicializar parámetros y constantes de estrategia dinámica (interna) pc = zeros ( N , 1 ); ps = zeros ( N , 1 ); % trayectorias de evolución para C y sigma B = eye ( N , N ); % B define el sistema de coordenadas D = ones ( N , 1 ); % diagonal D define la escala C = B * diag ( D .^ 2 ) * B ' ; % matriz de covarianza C invsqrtC = B * diag ( D .^- 1 ) * B '                                                                      ; % C^-1/2 eigeneval = 0 ; % actualización de seguimiento de B y D chiN = N ^ 0.5 * ( 1 - 1 / ( 4 * N ) + 1 / ( 21 * N ^ 2 )); % expectativa de % ||N(0,I)|| == norm(randn(N,1)) % -------------------- Bucle de generación -------------------------------- counteval = 0 ; % las siguientes 40 líneas contienen las 20 líneas de código interesante mientras counteval < stopeval % Generar y evaluar la descendencia lambda para k = 1 : lambda arx (:, k ) = xmean + sigma * B * ( D .* randn ( N , 1 )); % m + sig * Normal(0,C) arfitness ( k ) = feval ( strfitnessfct , arx (:, k )); % llamada a la función objetivo counteval = counteval + 1 ; fin % Ordenar por aptitud y calcular la media ponderada en xmean [ arfitness , arindex ] = sort ( arfitness ); % minimización xold = xmean ; xmean = arx (:, arindex ( 1 : mu )) * pesos ; % recombinación, nuevo valor medio % Acumulación: Actualizar rutas de evolución ps = ( 1 - cs ) * ps ... + sqrt ( cs * ( 2 - cs ) * mueff ) * invsqrtC * ( xmean - xold ) / sigma ; hsig = norm ( ps ) / sqrt (                                                                           1 - ( 1 - cs ) ^ ( 2 * counteval / lambda )) / chiN < 1.4 + 2 / ( N + 1 ); pc = ( 1 - cc ) * pc ... + hsig * sqrt ( cc * ( 2 - cc ) * mueff ) * ( xmean - xold ) / sigma ;                 % Adaptar la matriz de covarianza C artmp = ( 1 / sigma ) * ( arx (:, arindex ( 1 : mu )) - repmat ( xold , 1 , mu )); C = ( 1 - c1 - cmu ) * C ...   % considerar la matriz anterior + c1 * ( pc * pc ' ...   % más actualización de rango uno + ( 1 - hsig ) * cc * ( 2 - cc ) * C ) ...  % corrección menor si hsig==0 + cmu * artmp * diag ( pesos ) * artmp ' ; % más actualización de rango mu                                 % Adaptar tamaño de paso sigma sigma = sigma * exp ( ( cs / amortiguamientos ) * ( norma ( ps ) / chiN - 1 )); % Descomposición de C en B*diag(D.^2)*B' (diagonalización) si counteval - eigeneval > lambda / ( c1 + cmu ) / N / 10 % para lograr O(N^2) eigeneval = counteval ; C = triu ( C ) + triu ( C , 1 ) ' ; % imponer simetría [ B , D ] = eig ( C ); % descomposición propia, B==vectores propios normalizados D = sqrt ( diag ( D )); % D es un vector de desviaciones estándar ahora invsqrtC = B * diag ( D .^- 1 ) * B ' ; fin % Break, si la aptitud es suficientemente buena o la condición excede 1e14, se recomiendan mejores métodos de terminación si arfitness ( 1 ) <= stopfitness || max ( D ) > 1e7 * min ( D ) break ; fin                                                         fin % while, fin del bucle de generación  xmin = arx (:, arindex ( 1 )); % Devuelve el mejor punto de la última iteración. % Nótese que se espera que xmean sea incluso % mejor. fin % --------------------------------------------------------------- function f = frosenbrock ( x ) if size ( x , 1 ) < 2 error ( 'la dimensión debe ser mayor que uno' ); fin f = 100 * suma (( x ( 1 : fin - 1 ) .^ 2 - x ( 2 : fin )) .^ 2 ) + suma (( x ( 1 : fin - 1 ) - 1 ) .^ 2 ); fin                    

Fundamentos teóricos

Dados los parámetros de distribución (media, varianzas y covarianzas), la distribución de probabilidad normal para el muestreo de nuevas soluciones candidatas es la distribución de probabilidad de entropía máxima sobre , es decir, la distribución de muestra con la cantidad mínima de información previa incorporada en la distribución. A continuación se realizan más consideraciones sobre las ecuaciones de actualización de CMA-ES. ${\displaystyle \mathbb {R} ^{n}}$

Métrica variable

El CMA-ES implementa un método estocástico de métrica variable . En el caso muy particular de una función objetivo convexa-cuadrática

${\displaystyle f(x)={\textstyle {\frac {1}{2}}}(x-x^{*})^{T}H(x-x^{*})}$

La matriz de covarianza se adapta a la inversa de la matriz hessiana , hasta un factor escalar y pequeñas fluctuaciones aleatorias. De manera más general, también en la función , donde es estrictamente creciente y, por lo tanto, preserva el orden, la matriz de covarianza se adapta a , hasta un factor escalar y pequeñas fluctuaciones aleatorias. Para la razón de selección (y, por lo tanto, el tamaño de la población ), las soluciones seleccionadas producen una matriz de covarianza empírica que refleja la matriz hessiana inversa incluso en estrategias de evolución sin adaptación de la matriz de covarianza. Este resultado se ha demostrado para en un modelo estático, basándose en la aproximación cuadrática. ^[3] ${\displaystyle C_{k}}$ ${\displaystyle H}$ ${\displaystyle g\circ f}$ ${\displaystyle g}$ ${\displaystyle C_{k}}$ ${\displaystyle H^{-1}}$ ${\displaystyle \lambda /\mu \to \infty }$ ${\displaystyle \lambda \to \infty }$ ${\displaystyle \mu }$ ${\displaystyle \mu =1}$

Actualizaciones de máxima verosimilitud

Las ecuaciones de actualización de la matriz de media y covarianza maximizan una probabilidad, al mismo tiempo que se asemejan a un algoritmo de maximización de expectativas . La actualización del vector de media maximiza una probabilidad logarítmica, de modo que ${\displaystyle m}$

${\displaystyle m_{k+1}=\arg \max _{m}\sum _{i=1}^{\mu }w_{i}\log p_{\mathcal {N}}(x_{i:\lambda }\mid m)}$

dónde

${\displaystyle \log p_{\mathcal {N}}(x)=-{\frac {1}{2}}\log \det(2\pi C)-{\frac {1}{2}}(x-m)^{T}C^{-1}(x-m)}$

denota la verosimilitud logarítmica de una distribución normal multivariada con media y cualquier matriz de covarianza definida positiva . Para ver que es independiente de , observe primero que este es el caso para cualquier matriz diagonal , porque el maximizador por coordenadas es independiente de un factor de escala. Entonces, la rotación de los puntos de datos o la elección de una matriz no diagonal son equivalentes. ${\displaystyle x}$ ${\displaystyle m}$ ${\displaystyle C}$ ${\displaystyle m_{k+1}}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C}$

La actualización de rango de la matriz de covarianza, es decir, el sumando más a la derecha en la ecuación de actualización de , maximiza una verosimilitud logarítmica en que ${\displaystyle \mu }$ ${\displaystyle C_{k}}$

${\displaystyle \sum _{i=1}^{\mu }w_{i}{\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\left({\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\right)^{T}=\arg \max _{C}\sum _{i=1}^{\mu }w_{i}\log p_{\mathcal {N}}\left(\left.{\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\right|C\right)}$

para (de lo contrario es singular, pero se obtiene sustancialmente el mismo resultado para ). Aquí, denota la probabilidad de a partir de una distribución normal multivariada con media cero y matriz de covarianza . Por lo tanto, para y , es el estimador de máxima verosimilitud anterior . Consulte la estimación de matrices de covarianza para obtener detalles sobre la derivación. ${\displaystyle \mu \geq n}$ ${\displaystyle C}$ ${\displaystyle \mu <n}$ ${\displaystyle p_{\mathcal {N}}(x|C)}$ ${\displaystyle x}$ ${\displaystyle C}$ ${\displaystyle c_{1}=0}$ ${\displaystyle c_{\mu }=1}$ ${\displaystyle C_{k+1}}$

Descenso de gradiente natural en el espacio de distribuciones de muestras

Akimoto et al. ^[4] y Glasmachers et al. ^[5] descubrieron de forma independiente que la actualización de los parámetros de distribución se asemeja al descenso en dirección de un gradiente natural muestreado del valor de la función objetivo esperado (a minimizar), donde la expectativa se toma bajo la distribución de muestra. Con la configuración de parámetros de y , es decir, sin control del tamaño del paso y actualización de rango uno, CMA-ES puede verse como una instanciación de Estrategias de Evolución Natural (NES). ^{[4] [5]} El gradiente natural es independiente de la parametrización de la distribución. Tomado con respecto a los parámetros θ de la distribución de muestra p , el gradiente de puede expresarse como ${\displaystyle Ef(x)}$ ${\displaystyle c_{\sigma }=0}$ ${\displaystyle c_{1}=0}$ ${\displaystyle Ef(x)}$

${\displaystyle {\begin{aligned}{\nabla }_{\!\theta }E(f(x)\mid \theta )&=\nabla _{\!\theta }\int _{\mathbb {R} ^{n}}f(x)p(x)\,\mathrm {d} x\\&=\int _{\mathbb {R} ^{n}}f(x)\nabla _{\!\theta }p(x)\,\mathrm {d} x\\&=\int _{\mathbb {R} ^{n}}f(x)p(x)\nabla _{\!\theta }\ln p(x)\,\mathrm {d} x\\&=\operatorname {E} (f(x)\nabla _{\!\theta }\ln p(x\mid \theta ))\end{aligned}}}$

donde depende del vector de parámetros . La llamada función de puntuación , , indica la sensibilidad relativa de p con respecto a θ , y la expectativa se toma con respecto a la distribución p . El gradiente natural de , que cumple con la métrica de información de Fisher (una medida de distancia informativa entre distribuciones de probabilidad y la curvatura de la entropía relativa ), ahora se lee ${\displaystyle p(x)=p(x\mid \theta )}$ ${\displaystyle \theta }$ ${\displaystyle \nabla _{\!\theta }\ln p(x\mid \theta )={\frac {\nabla _{\!\theta }p(x)}{p(x)}}}$ ${\displaystyle Ef(x)}$

${\displaystyle {\begin{aligned}{\tilde {\nabla }}\operatorname {E} (f(x)\mid \theta )&=F_{\theta }^{-1}\nabla _{\!\theta }\operatorname {E} (f(x)\mid \theta )\end{aligned}}}$

donde la matriz de información de Fisher es la esperanza del hessiano de −ln p y hace que la expresión sea independiente de la parametrización elegida. Combinando las igualdades anteriores obtenemos ${\displaystyle F_{\theta }}$

${\displaystyle {\begin{aligned}{\tilde {\nabla }}\operatorname {E} (f(x)\mid \theta )&=F_{\theta }^{-1}\operatorname {E} (f(x)\nabla _{\!\theta }\ln p(x\mid \theta ))\\&=\operatorname {E} (f(x)F_{\theta }^{-1}\nabla _{\!\theta }\ln p(x\mid \theta ))\end{aligned}}}$

Una aproximación de Monte Carlo de la última expectativa toma el promedio sobre λ muestras de p

${\displaystyle {\tilde {\nabla }}{\widehat {E}}_{\theta }(f):=-\sum _{i=1}^{\lambda }\overbrace {w_{i}} ^{\!\!\!\!{\text{preference weight}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\underbrace {F_{\theta }^{-1}\nabla _{\!\theta }\ln p(x_{i:\lambda }\mid \theta )} _{\!\!\!\!\!{\text{candidate direction from }}x_{i:\lambda }\!\!\!\!\!}\quad {\text{with }}w_{i}=-f(x_{i:\lambda })/\lambda }$

donde se utiliza la notación anterior y por lo tanto son monótonamente decrecientes en . ${\displaystyle i:\lambda }$ ${\displaystyle w_{i}}$ ${\displaystyle i}$

Ollivier et al. ^[6] finalmente encontraron una derivación rigurosa para los pesos, , tal como se definen en el CMA-ES. Los pesos son un estimador asintóticamente consistente de la CDF de en los puntos del estadístico de orden th , tal como se definió anteriormente, donde , compuesto con una transformación fija monótonamente decreciente , es decir, ${\displaystyle w_{i}}$ ${\displaystyle f(X)}$ ${\displaystyle i}$ ${\displaystyle f(x_{i:\lambda })}$ ${\displaystyle X\sim p(.|\theta )}$ ${\displaystyle w}$

${\displaystyle w_{i}=w\left({\frac {{\mathsf {rank}}(f(x_{i:\lambda }))-1/2}{\lambda }}\right)}$.

Estos pesos hacen que el algoritmo sea insensible a los valores específicos. En términos más concisos, si se utiliza el estimador CDF de en lugar de sí mismo, el algoritmo solo depende de la clasificación de los valores, pero no de su distribución subyacente. Esto hace que el algoritmo sea invariante a las transformaciones estrictamente crecientes . Ahora definimos ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f}$

${\displaystyle \theta =[m_{k}^{T}\operatorname {vec} (C_{k})^{T}\sigma _{k}]^{T}\in \mathbb {R} ^{n+n^{2}+1}}$

tal que es la densidad de la distribución normal multivariante . Entonces, tenemos una expresión explícita para la inversa de la matriz de información de Fisher donde es fija ${\displaystyle p(\cdot \mid \theta )}$ ${\displaystyle {\mathcal {N}}(m_{k},\sigma _{k}^{2}C_{k})}$ ${\displaystyle \sigma _{k}}$

${\displaystyle F_{\theta \mid \sigma _{k}}^{-1}=\left[{\begin{array}{cc}\sigma _{k}^{2}C_{k}&0\\0&2C_{k}\otimes C_{k}\end{array}}\right]}$

y para

${\displaystyle \ln p(x\mid \theta )=\ln p(x\mid m_{k},\sigma _{k}^{2}C_{k})=-{\frac {1}{2}}(x-m_{k})^{T}\sigma _{k}^{-2}C_{k}^{-1}(x-m_{k})-{\frac {1}{2}}\ln \det(2\pi \sigma _{k}^{2}C_{k})}$

y, después de algunos cálculos, las actualizaciones en el CMA-ES resultan como ^[4]

${\displaystyle {\begin{aligned}m_{k+1}&=m_{k}-\underbrace {[{\tilde {\nabla }}{\widehat {E}}_{\theta }(f)]_{1,\dots ,n}} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{natural gradient for mean}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\\&=m_{k}+\sum _{i=1}^{\lambda }w_{i}(x_{i:\lambda }-m_{k})\end{aligned}}}$

y

${\displaystyle {\begin{aligned}C_{k+1}&=C_{k}+c_{1}(p_{c}p_{c}^{T}-C_{k})-c_{\mu }\operatorname {mat} (\overbrace {[{\tilde {\nabla }}{\widehat {E}}_{\theta }(f)]_{n+1,\dots ,n+n^{2}}} ^{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{natural gradient for covariance matrix}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!})\\&=C_{k}+c_{1}(p_{c}p_{c}^{T}-C_{k})+c_{\mu }\sum _{i=1}^{\lambda }w_{i}\left({\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\left({\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\right)^{T}-C_{k}\right)\end{aligned}}}$

donde mat forma la matriz apropiada a partir del subvector de gradiente natural respectivo. Esto significa que, al establecer , las actualizaciones de CMA-ES descienden en la dirección de la aproximación del gradiente natural mientras se utilizan diferentes tamaños de paso (tasas de aprendizaje 1 y ) para los parámetros ortogonales y respectivamente. Las versiones más recientes también permiten una tasa de aprendizaje diferente para la media . ^[7] La ​​versión más reciente de CMA-ES también utiliza una función diferente para y con valores negativos solo para este último (el llamado CMA activo). ${\displaystyle c_{1}=c_{\sigma }=0}$ ${\displaystyle {\tilde {\nabla }}{\widehat {E}}_{\theta }(f)}$ ${\displaystyle c_{\mu }}$ ${\displaystyle m}$ ${\displaystyle C}$ ${\displaystyle m}$ ${\displaystyle w}$ ${\displaystyle m}$ ${\displaystyle C}$

Estacionariedad o imparcialidad

Es relativamente fácil ver que las ecuaciones de actualización de CMA-ES satisfacen algunas condiciones de estacionariedad, en el sentido de que son esencialmente imparciales. Bajo una selección neutral, donde , encontramos que ${\displaystyle x_{i:\lambda }\sim {\mathcal {N}}(m_{k},\sigma _{k}^{2}C_{k})}$

${\displaystyle \operatorname {E} (m_{k+1}\mid m_{k})=m_{k}}$

y bajo algunas suposiciones adicionales leves sobre las condiciones iniciales

${\displaystyle \operatorname {E} (\log \sigma _{k+1}\mid \sigma _{k})=\log \sigma _{k}}$

y con una corrección menor adicional en la actualización de la matriz de covarianza para el caso donde la función indicadora evalúa a cero, encontramos

${\displaystyle \operatorname {E} (C_{k+1}\mid C_{k})=C_{k}}$

Invariancia

Las propiedades de invariancia implican un rendimiento uniforme en una clase de funciones objetivo. Se ha argumentado que son una ventaja, porque permiten generalizar y predecir el comportamiento del algoritmo y, por lo tanto, fortalecen el significado de los resultados empíricos obtenidos en funciones individuales. Se han establecido las siguientes propiedades de invariancia para CMA-ES.

• Invariancia bajo transformaciones que preservan el orden del valor de la función objetivo , en el sentido de que para cualquier el comportamiento es idéntico en para todos los valores estrictamente crecientes . Esta invariancia es fácil de verificar, porque solo se utiliza el ordenamiento en el algoritmo, que es invariante bajo la elección de . ${\displaystyle f}$ ${\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle f:x\mapsto g(h(x))}$ ${\displaystyle g:\mathbb {R} \to \mathbb {R} }$ ${\displaystyle f}$ ${\displaystyle g}$
• Invariancia de escala , en el sentido de que para cualquier comportamiento es independiente de para la función objetivo dada y . ${\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle \alpha >0}$ ${\displaystyle f:x\mapsto h(\alpha x)}$ ${\displaystyle \sigma _{0}\propto 1/\alpha }$ ${\displaystyle m_{0}\propto 1/\alpha }$
• Invariancia bajo rotación del espacio de búsqueda en el sentido de que para cualquier y cualquier el comportamiento en es independiente de la matriz ortogonal , dado . De manera más general, el algoritmo también es invariante bajo transformaciones lineales generales cuando además se elige como matriz de covarianza inicial . ${\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle z\in \mathbb {R} ^{n}}$ ${\displaystyle f:x\mapsto h(Rx)}$ ${\displaystyle R}$ ${\displaystyle m_{0}=R^{-1}z}$ ${\displaystyle R}$ ${\displaystyle R^{-1}{R^{-1}}^{T}}$

Cualquier método serio de optimización de parámetros debe ser invariante en cuanto a la traducción, pero la mayoría de los métodos no exhiben todas las propiedades de invariancia descritas anteriormente. Un ejemplo destacado con las mismas propiedades de invariancia es el método Nelder-Mead , donde el símplex inicial debe elegirse respectivamente.

Convergencia

Consideraciones conceptuales como la propiedad de invariancia de escala del algoritmo, el análisis de estrategias de evolución más simples y evidencia empírica abrumadora sugieren que el algoritmo converge en una gran clase de funciones rápidamente al óptimo global, denotado como . En algunas funciones, la convergencia ocurre independientemente de las condiciones iniciales con probabilidad uno. En algunas funciones la probabilidad es menor que uno y típicamente depende de las condiciones iniciales y . Empíricamente, la tasa de convergencia más rápida posible en para métodos de búsqueda directa basados ​​en rangos a menudo se puede observar (dependiendo del contexto denotado como convergencia lineal o convergencia log-lineal o exponencial ). De manera informal, podemos escribir ${\displaystyle x^{*}}$ ${\displaystyle m_{0}}$ ${\displaystyle \sigma _{0}}$ ${\displaystyle k}$

${\displaystyle \|m_{k}-x^{*}\|\;\approx \;\|m_{0}-x^{*}\|\times e^{-ck}}$

para algunos , y con mayor rigor ${\displaystyle c>0}$

${\displaystyle {\frac {1}{k}}\sum _{i=1}^{k}\log {\frac {\|m_{i}-x^{*}\|}{\|m_{i-1}-x^{*}\|}}\;=\;{\frac {1}{k}}\log {\frac {\|m_{k}-x^{*}\|}{\|m_{0}-x^{*}\|}}\;\to \;-c<0\quad {\text{for }}k\to \infty \;,}$

o de manera similar,

${\displaystyle \operatorname {E} \log {\frac {\|m_{k}-x^{*}\|}{\|m_{k-1}-x^{*}\|}}\;\to \;-c<0\quad {\text{for }}k\to \infty \;.}$

Esto significa que, en promedio, la distancia al óptimo disminuye en cada iteración en un factor "constante", es decir, en . La tasa de convergencia es aproximadamente , dado que no es mucho mayor que la dimensión . Incluso con óptimos y , la tasa de convergencia no puede superar ampliamente a , dado que los pesos de recombinación anteriores son todos no negativos. Las dependencias lineales reales en y son notables y son en ambos casos lo mejor que se puede esperar en este tipo de algoritmo. Sin embargo, falta una prueba rigurosa de convergencia. ${\displaystyle \exp(-c)}$ ${\displaystyle c}$ ${\displaystyle 0.1\lambda /n}$ ${\displaystyle \lambda }$ ${\displaystyle n}$ ${\displaystyle \sigma }$ ${\displaystyle C}$ ${\displaystyle c}$ ${\displaystyle 0.25\lambda /n}$ ${\displaystyle w_{i}}$ ${\displaystyle \lambda }$ ${\displaystyle n}$

Interpretación como transformación del sistema de coordenadas

El uso de una matriz de covarianza no identidad para la distribución normal multivariada en estrategias de evolución es equivalente a una transformación del sistema de coordenadas de los vectores de solución, ^[8] principalmente porque la ecuación de muestreo

${\displaystyle {\begin{aligned}x_{i}&\sim \ m_{k}+\sigma _{k}\times {\mathcal {N}}(0,C_{k})\\&\sim \ m_{k}+\sigma _{k}\times C_{k}^{1/2}{\mathcal {N}}(0,I)\end{aligned}}}$

puede expresarse de forma equivalente en un "espacio codificado" como

${\displaystyle \underbrace {C_{k}^{-1/2}x_{i}} _{{\text{represented in the encode space}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\sim \ \underbrace {C_{k}^{-1/2}m_{k}} {}+\sigma _{k}\times {\mathcal {N}}(0,I)}$

La matriz de covarianza define una transformación biyectiva (codificación) para todos los vectores de solución en un espacio, donde el muestreo se lleva a cabo con una matriz de covarianza identidad. Debido a que las ecuaciones de actualización en el CMA-ES son invariantes bajo transformaciones de sistemas de coordenadas lineales, el CMA-ES puede reescribirse como un procedimiento de codificación adaptativa aplicado a una estrategia de evolución simple con una matriz de covarianza identidad. ^[8] Este procedimiento de codificación adaptativa no se limita a algoritmos que toman muestras de una distribución normal multivariada (como las estrategias de evolución), sino que, en principio, puede aplicarse a cualquier método de búsqueda iterativo.

Rendimiento en la práctica

A diferencia de la mayoría de los demás algoritmos evolutivos , el CMA-ES es, desde la perspectiva del usuario, casi libre de parámetros. El usuario tiene que elegir un punto de solución inicial, , y el tamaño de paso inicial, . Opcionalmente, el usuario puede modificar el número de muestras candidatas λ (tamaño de la población) para cambiar el comportamiento de búsqueda característico (ver arriba) y las condiciones de terminación pueden o deben ajustarse al problema en cuestión. ${\displaystyle m_{0}\in \mathbb {R} ^{n}}$ ${\displaystyle \sigma _{0}>0}$

El CMA-ES ha tenido éxito empíricamente en cientos de aplicaciones y se considera que es útil en particular en funciones objetivo no convexas, no separables, mal condicionadas, multimodales o ruidosas. ^[9] Una encuesta de optimizaciones de caja negra descubrió que superó a otros 31 algoritmos de optimización, con un desempeño especialmente sólido en "funciones difíciles" o espacios de búsqueda de dimensiones más grandes. ^[10]

La dimensión del espacio de búsqueda varía normalmente entre dos y unos pocos cientos. Suponiendo un escenario de optimización de caja negra, donde los gradientes no están disponibles (o no son útiles) y las evaluaciones de funciones son el único costo considerado de la búsqueda, es probable que el método CMA-ES sea superado por otros métodos en las siguientes condiciones:

• en funciones de baja dimensión, digamos , por ejemplo mediante el método simplex descendente o métodos basados ​​en sustitutos (como kriging con mejora esperada); ${\displaystyle n<5}$
• sobre funciones separables sin o con dependencias insignificantes entre las variables de diseño, en particular en el caso de multimodalidad o de gran dimensión, por ejemplo mediante evolución diferencial ;
• en funciones cuadráticas (casi) convexas con un número de condición bajo o moderado de la matriz hessiana , donde BFGS o NEWUOA o SLSQP son típicamente al menos diez veces más rápidos;
• en funciones que ya pueden resolverse con un número comparativamente pequeño de evaluaciones de funciones, digamos no más de , donde CMA-ES es a menudo más lento que, por ejemplo, NEWUOA o Multilevel Coordinate Search (MCS). ${\displaystyle 10n}$

En el caso de las funciones separables, la desventaja de rendimiento probablemente sea más significativa, ya que CMA-ES podría no ser capaz de encontrar soluciones comparables. Por otro lado, en el caso de las funciones no separables que están mal condicionadas o son difíciles de resolver o que solo se pueden resolver con más de una evaluación de función, CMA-ES muestra con mayor frecuencia un rendimiento superior. ${\displaystyle 100n}$

Variaciones y ampliaciones

El (1+1)-CMA-ES ^[11] genera sólo una solución candidata por paso de iteración que se convierte en la nueva media de distribución si es mejor que la media actual. El (1+1)-CMA-ES es una variante cercana de la adaptación gaussiana . Algunas estrategias de evolución natural son variantes cercanas del CMA-ES con configuraciones de parámetros específicos. Las estrategias de evolución natural no utilizan rutas de evolución (es decir, en la configuración CMA-ES ) y formalizan la actualización de varianzas y covarianzas en un factor de Cholesky en lugar de una matriz de covarianza. El CMA-ES también se ha extendido a la optimización multiobjetivo como MO-CMA-ES. ^[12] Otra extensión notable ha sido la adición de una actualización negativa de la matriz de covarianza con el llamado CMA activo. ^[13] El uso de la actualización CMA activa adicional se considera como la variante predeterminada en la actualidad. ^[7] ${\displaystyle c_{c}=1}$ ${\displaystyle c_{c}=c_{\sigma }=1}$

Véase también

• Optimización global  – Rama de las matemáticas
• Optimización estocástica  – Método de optimización
• Optimización sin derivadas  – Disciplina matemática
• Algoritmo de estimación de distribución  : familia de métodos de optimización estocástica

Referencias

1. Hansen, N. (2006), "La estrategia de evolución de CMA: una revisión comparativa", Hacia un nuevo cómputo evolutivo. Avances en la estimación de algoritmos de distribución , Springer, pp. 1769–1776, CiteSeerX  10.1.1.139.7369
2. Auger, A.; N. Hansen (2005). "Una estrategia de evolución de reinicio de CMA con un tamaño de población creciente" (PDF) . 2005 IEEE Congress on Evolutionary Computation, Actas . IEEE. págs. 1769–1776. Archivado desde el original (PDF) el 2016-03-04 . Consultado el 2012-07-13 .
3. Shir, OM; A. Yehudayoff (2020). "Sobre la relación covarianza-hessiana en las estrategias de evolución". Ciencias de la Computación Teórica . 801 . Elsevier: 157–174. arXiv : 1806.03674 . doi : 10.1016/j.tcs.2019.09.002 .
4. Akimoto, Y.; Y. Nagata; I. Ono; S. Kobayashi (2010). "Relación bidireccional entre las estrategias de evolución de CMA y las estrategias de evolución natural". Solución de problemas paralelos a partir de la naturaleza, PPSN XI . Springer. págs. 154–163.
5. Glasmachers, T.; T. Schaul; Y. Sun; D. Wierstra; J. Schmidhuber (2010). "Estrategias de evolución natural exponencial" (PDF) . Conferencia sobre computación genética y evolutiva GECCO . Portland, OR.
6. Ollivier, Y.; Arnold, L.; Auger, A.; Hansen, N. (2017). "Algoritmos de optimización geométrica de la información: una imagen unificadora a través de principios de invariancia" (PDF) . Revista de investigación en aprendizaje automático . 18 (18): 1−65.
7. Hansen, N. (2016). "La estrategia de evolución de CMA: un tutorial". arXiv : 1604.00772 [cs.LG].
8. Hansen, N. (2008). "Codificación adaptativa: cómo hacer que el sistema de coordenadas de búsqueda sea invariante". Resolución de problemas paralelos de la naturaleza, PPSN X . Springer. págs. 205–214.
9. "Referencias a aplicaciones CMA-ES" (PDF) .
10. Hansen, Nikolaus (2010). "Comparación de resultados de 31 algoritmos del estudio comparativo de optimización de caja negra BBOB-2009" (PDF) .
11. Igel, C.; T. Suttorp; N. Hansen (2006). "Una actualización de la matriz de covarianza computacionalmente eficiente y un (1+1)-CMA para estrategias evolutivas" (PDF) . Actas de la Conferencia sobre computación genética y evolutiva (GECCO) . ACM Press. págs. 453–460.
12. Igel, C.; N. Hansen; S. Roth (2007). "Adaptación de la matriz de covarianza para la optimización multiobjetivo". Computación evolutiva . 15 (1): 1–28. doi :10.1162/evco.2007.15.1.1. PMID  17388777. S2CID  7479494.
13. Jastrebski, GA; DV Arnold (2006). "Mejora de las estrategias de evolución mediante la adaptación de la matriz de covarianza activa". Actas del Congreso Mundial IEEE sobre Inteligencia Computacional de 2006. IEEE. págs. 9719–9726. doi :10.1109/CEC.2006.1688662.

Bibliografía

• Hansen N, Ostermeier A (2001). Autoadaptación completamente desaleatorizada en estrategias evolutivas. Computación evolutiva, 9(2) págs. 159–195. [1]
• Hansen N, Müller SD, Koumoutsakos P (2003). Reducción de la complejidad temporal de la estrategia de evolución desrandomizada con adaptación de matriz de covarianza (CMA-ES). Evolutionary Computation, 11(1) págs. 1–18. [2]
• Hansen N, Kern S (2004). Evaluación de la estrategia de evolución de CMA en funciones de prueba multimodales. En Xin Yao et al., editores, Parallel Problem Solving from Nature – PPSN VIII , págs. 282–291, Springer. [3]
• Igel C, Hansen N, Roth S (2007). Adaptación de la matriz de covarianza para la optimización multiobjetivo. Computación evolutiva, 15(1) págs. 1–28. [4]

Enlaces externos

• Una breve introducción a CMA-ES por N. Hansen
• La estrategia de evolución de la CMA: un tutorial
• Página de código fuente de CMA-ES