CMA-ES

CMA-ES significa la Estrategia de Evolución de Adaptación de la Matriz de la Covariancia. Las estrategias de evolución (ES) son métodos estocásticos, sin derivados para la optimización numérica de problemas de optimización continuos no lineales o no convexos. Pertenecen a la clase de algoritmos evolutivos y cálculo evolutivo. Un algoritmo evolutivo está ampliamente basado en el principio de la evolución biológica, a saber la interacción repetida de la variación (vía mutación y nueva combinación) y selección: en cada generación (iteración) los nuevos individuos (soluciones del candidato, denotadas como) son generados por la variación, por lo general de un modo estocástico, y luego algunos individuos se seleccionan para la próxima generación basada en su condición física o valor de función objetivo. Como esto, sobre la secuencia de generación, individuos con mejor y mejor - los valores se generan.

En una estrategia de evolución, las nuevas soluciones del candidato se prueban según una distribución normal de la multivariante aleatoria en el. Las dependencias pares entre las variables en esta distribución son representadas por una matriz de la covariancia. La adaptación de la matriz de la covariancia (CMA) es un método de actualizar la matriz de la covariancia de esta distribución. Esto es particularmente útil, si la función es de mal carácter.

La adaptación de la matriz de la covariancia asciende al aprendizaje de un segundo modelo de pedido de la función objetiva subyacente similar a la aproximación de la matriz de Arpillera inversa en el método de Quasi-Newton en la optimización clásica. En contraste con la mayoría de los métodos clásicos, menos asunciones en la naturaleza de la función objetiva subyacente se hacen. Sólo la clasificación entre soluciones del candidato se explota para aprender la distribución de la muestra y ni derivados, ni hasta los propios valores de función son requeridos por el método.

Principios

Dos principios principales para la adaptación de parámetros de la distribución de búsqueda se explotan en el algoritmo CMA-ES.

En primer lugar, un principio de probabilidad máxima, basado en la idea de aumentar la probabilidad de soluciones del candidato acertadas y pasos de búsqueda. La media de la distribución se actualiza tal que la probabilidad de soluciones del candidato antes acertadas se maximiza. La matriz de la covariancia de la distribución se actualiza (incrementalmente) tal que la probabilidad de pasos de búsqueda antes acertados se aumenta. Ambas actualizaciones se pueden interpretar como un descenso del declive natural. También, en la consecuencia, el CMA conduce un análisis de componentes principal iterado de pasos de búsqueda acertados reteniendo todas las hachas principales. La valoración de algoritmos de distribución y el Método de la Entropía Enfadada está basada en ideas muy similares, pero estima (no incrementalmente) la matriz de la covariancia maximizando la probabilidad de puntos de solución acertados en vez de pasos de búsqueda acertados.

En segundo lugar, dos caminos de la evolución del tiempo de la distribución media de la estrategia se registran, se llaman caminos de evolución o búsqueda. Estos caminos contienen la información significativa sobre la correlación entre pasos consecutivos. Expresamente, si las medidas consecutivas se toman en una dirección similar, los caminos de evolución se hacen largos. Los caminos de evolución se explotan de dos modos. Un camino se usa para el procedimiento de adaptación de la matriz de la covariancia en el lugar de la búsqueda acertada sola anda y facilita un aumento del desacuerdo posiblemente mucho más rápido de direcciones favorables. El otro camino es usado para conducir un control de la talla del paso adicional. Este control de la talla del paso pretende hacer movimientos consecutivos de la distribución medios ortogonal en la expectativa. El control de la talla del paso con eficacia previene la convergencia prematura que aún permite la convergencia rápida a un grado óptimo.

Algoritmo

En el siguiente el más comúnmente usado (μ/μ, λ)-CMA-ES se perfila, donde en cada paso de iteración una combinación ponderada del μ mejor de nuevas soluciones del candidato λ es usada para actualizar los parámetros de distribución. El lazo principal consiste en tres partes principales: 1) prueba de nuevas soluciones, 2) nuevo pedido de las soluciones probadas basadas en su condición física, 3) actualización de las variables estatales internas basadas en las muestras pedidas de nuevo. Un pseudocódigo del algoritmo mira así.

juego//número de muestras por iteración, al menos dos, generalmente> 4

inicialice,//inicializan variables estatales

mientras no terminal//iteran

ya que en//muestra nuevas soluciones y los evalúan

= el sample_multivariate_normal (significan =, covariance_matrix =)

= bienestar corporal

← con = argsort //soluciones de la clase

=//necesitamos más tarde y

← los update_m//se mueven medio con mejores soluciones

← los update_ps//actualizan el camino de evolución isotropic

← los update_pc//actualizan el camino de evolución anisotropic

← los update_C//actualizan la matriz de la covariancia

← los update_sigma//actualizan la talla del paso usando isotropic la longitud del camino

vuelva o

</código>

El pedido de las cinco asignaciones de actualización es relevante. En el siguiente, las ecuaciones de actualización para las cinco variables estatales se especifican.

Dado son la dimensión de la área de búsqueda y el paso de iteración. Las cinco variables estatales son

:, la distribución solución favorita media y corriente del problema de optimización,

:, la talla del paso,

:, una matriz de la covariancia definida simétrica y positiva con y

:, dos caminos de evolución, al principio juego al vector cero.

La iteración comienza con la prueba de soluciones del candidato de una distribución normal de la multivariante aleatoria, es decir

para

::

Los \begin {alinean }\

x_i \&\\sim\\mathcal {N} (m_k, \sigma_k^2 C_k)

\\&\\sim\m_k + \sigma_k\times\mathcal {N} (0, C_k)

Los \end {alinean }\

</matemáticas>

La segunda línea sugiere la interpretación como la perturbación (la mutación) del vector de solución favorito corriente (la distribución vector medio). Las soluciones del candidato se evalúan en la función objetiva para minimizarse. La denotación el - soluciones del candidato clasificadas como

:

\{x_ {i:\lambda }\\; | \; i=1\dots\lambda\} = \{x_i \; | \; i=1\dots\lambda\} \; \; \text {y }\\; \;

f (x_ {1:\lambda}) \le\dots\le f (x_ {\\mu:\lambda}) \le f (x_ {\\mu+1:\lambda}) \dots,

</matemáticas>

el nuevo valor medio se calcula como

::

Los \begin {alinean }\

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)

Los \end {alinean }\

</matemáticas>

donde los positivos (nueva combinación) pesos suman a uno. Típicamente, y los pesos se eligen tales que. La única reacción usada de la función objetiva aquí y en lo siguiente es un pedido de las soluciones del candidato probadas debido a los índices.

La talla del paso se actualiza usando la adaptación de la talla del paso acumulativa (CSA), a veces también denotado como el control de longitud del camino. El camino de evolución (o el camino de búsqueda) se actualizan primero.

::

¡

p_\sigma \gets \underbrace {(1-c_\sigma)} _ {\\! ¡\! ¡\! ¡\! ¡\! ¡los \text {rebajan el factor }\\! ¡\! ¡\! ¡\! ¡\! }\\, p_\sigma

+ \overbrace {\\sqrt {1 - ^2 (1-c_\sigma)}} ^ {\

¡

\! \! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! \!\text {complementos para desacuerdo rebajado }\

¡

\! \! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\!} \underbrace {\\sqrt {\\mu_w}

\, C_k^ {\\; ¡-1/2} \, \frac {\\sobreabrazadera {m_ {k+1} - m_k} ^ {\\! ¡\! ¡\! \text {desplazamiento de }\\; ¡m \! ¡\! ¡\! ¡}} {\\sigma_k}} _ {\\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\!

\text {distribuido como }\\; \mathcal {N} (0, I) \; \text {bajo selección neutra }\

¡

\! \! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! }\

</matemáticas>

::

\sigma_ {k+1} = \sigma_k \times \exp\bigg (\frac {c_\sigma} {d_\sigma }\

El \underbrace {\\se fue (\frac {\\|p_\sigma \|} {E \|\mathcal {N} (0, I) \| ¡} - 1\right)} _ {\\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\!

\text {imparcial aproximadamente 0 bajo selección neutra }\

¡

\! \! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\!

}\\bigg)

</matemáticas>

donde

: es el horizonte temporal atrasado para el camino de evolución y más grande que uno,

: es el desacuerdo masa de selección eficaz y por definición de,

: es la raíz cuadrada simétrica única del inverso de, y

: es el parámetro que se debilita por lo general cerca de uno. Para o la talla del paso permanece sin alterar.

La talla del paso se aumenta si y sólo si es más grande que el valor esperado

:

Los \\&\\aprox. \sqrt {n }\\, (1-1 / (4 \, n) +1 / (21 \, n^2)) \end {alinean} </matemáticas>

y disminuido si es más pequeño. Por esta razón, la actualización de la talla del paso tiende a hacer pasos consecutivos - conjugados, en esto después de que la adaptación ha tenido éxito.

Finalmente, la matriz de la covariancia se actualiza, donde otra vez el camino de evolución respectivo se actualiza primero.

::

¡

p_c \gets \underbrace {(1-c_c)} _ {\\! ¡\! ¡\! ¡\! ¡\! ¡los \text {rebajan el factor }\\! ¡\! ¡\! ¡\! ¡\! }\\,

p_c +

\underbrace {\\mathbf {1} _ {[0, \alpha\sqrt {n}]} (\|p_\sigma \|)} _ {\\texto {función del indicador}}

\overbrace {\\sqrt {1 - ^2 (1-c_c)}} ^ {\

¡

\! \! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! \!\text {complementos para desacuerdo rebajado }\

¡

\! \! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! }\

\underbrace {\\sqrt {\\mu_w}

\, ¡\frac {m_ {k+1} - m_k} {\\sigma_k}} _ {\\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\!

\text {distribuido como }\\; \mathcal {N} (0, C_k) \; \text {bajo selección neutra }\

¡

\! \! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! }\

</matemáticas>

::

¡

C_ {k+1} = \underbrace {(1 - c_1 - c_\mu + c_s)} _ {\\! ¡\! ¡\! ¡\! ¡\! ¡los \text {rebajan el factor }\\! ¡\! ¡\! ¡\! ¡\! }\

\, C_k + c_1 \underbrace {p_c p_c^T} _ {\

¡

\! \! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\!

Los \text {clasifican un }de la matriz \

¡

\! \! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\!}

+ \, 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} _ {\

\text {fila} \; \min (\mu, n) \; \text }{de la matriz} \

</matemáticas>

donde denota transportar y

: es el horizonte temporal atrasado para el camino de evolución y más grande que uno,

: y la función del indicador evalúa a un iff o, en otras palabras, que es por lo general el caso,

: hace en parte para la pequeña pérdida del desacuerdo por si el indicador sea el cero,

: es el precio de aprendizaje para la fila una actualización de la matriz de la covariancia y

: es el precio de aprendizaje para la fila - la actualización de la matriz de la covariancia y no debe exceder.

La actualización de la matriz de la covariancia tiende a aumentar la probabilidad para y para probarse de. Esto completa el paso de iteración.

El número de muestras del candidato por iteración, no se determina a priori y puede variar en una amplia gama. Los valores más pequeños, por ejemplo, llevan a más comportamiento de búsqueda local. Los valores más grandes, por ejemplo con el valor por defecto, dan la búsqueda más global. A veces el algoritmo es repetidamente reanudado con el aumento por un factor de dos para cada uno se reactivan. Además de ponerse (o posiblemente en cambio, si por ejemplo es predeterminado por el número de procesadores disponibles), los susodichos parámetros introducidos no son específicos para la función objetiva dada y por lo tanto no destinados ser modificados por el usuario.

Ejemplo de código en Matlab/Octave

funcione xmin=purecmaes el % (mu/mu_w, lambda)-CMA-ES

% Inicialización de----------------------------------------------------

% El usuario definió parámetros de la entrada (se tiene que corregir)

strfitnessfct = 'frosenbrock'; el nombre de % del objetivo/bienestar corporal funciona

N = 20; número de % de dimensión de variables/problema objetiva

xmean = rand (N, 1); la inicial de variables del objetivo del % señala

sigma = 0.5; coordenada de % desviación estándar sabia (talla del paso)

stopfitness = 1e-10; parada de % si bienestar corporal

eigeneval = counteval;

C = triu (C) + triu (C, 1)'; el % hace cumplir la simetría

[B, D] = eig (C); el % eigen descomposición, B == normalizó eigenvectors

D = sqrt (diag (D)); el % D es un vector de desviaciones estándares ahora

invsqrtC = B * diag (D.^-1) * B';

final

% La ruptura, si el bienestar corporal está bastante bien o condición excede 1e14, los mejores métodos de la terminación son aconsejable

si arfitness (1)

ruptura;

final

el % del final mientras, termine el lazo de generación

xmin = arx (: arindex (1)); Vuelta de % el mejor punto de última iteración.

% Note que se espera que xmean sea hasta

% mejor.

%---------------------------------------------------------------

funcione f=frosenbrock (x)

si talla (x, 1)

Fundaciones teóricas

Considerando la distribución parameters—mean, desacuerdos y covariances—the la distribución de probabilidad normal para probar nuevas soluciones del candidato es la distribución de probabilidad de la entropía máxima terminada, es decir la distribución de la muestra con la cantidad mínima de la información previa incorporada en la distribución. Más consideraciones en las ecuaciones de actualización de CMA-ES se hacen en el siguiente.

Variable métrica

El CMA-ES pone en práctica un método variable y métrico estocástico. En el caso muy particular de una función objetiva convexa y cuadrática

::

la matriz de la covariancia se adapta al inverso de la matriz de Arpillera, hasta un factor escalar y pequeñas fluctuaciones arbitrarias. Más general, también en la función, donde aumenta estrictamente y por lo tanto piden la conservación y es convexo y cuadrático, la matriz de la covariancia se adapta a, hasta un factor escalar y pequeñas fluctuaciones arbitrarias.

Actualizaciones de probabilidad máxima

Las ecuaciones de actualización para medio y matriz de la covariancia maximizan una probabilidad pareciéndose a un algoritmo de maximización de la expectativa. La actualización del vector medio maximiza una probabilidad del tronco, tal que

::

donde

::

- \frac {1} {2} \log\det (2\pi C) - \frac {1} {2} (x-m) ^T C^ {-1} (x-m) </matemáticas>

denota la probabilidad del tronco de una distribución normal de la multivariante aleatoria con el medio y cualquier matriz de la covariancia definida positiva. Para ver esto es independiente del comentario primero que es así para cualquier matriz diagonal, porque maximizer coordinativo y sabio es independiente de un factor de escalamiento. Entonces, la rotación de las funciones de datos o la elección de la no diagonal son equivalentes.

La fila - la actualización de la matriz de la covariancia, es decir el derecho la mayor parte de summand en la ecuación de actualización de, maximiza una probabilidad del tronco en esto

::

\left (\frac {x_ {i:\lambda} - m_k} {\\sigma_k} \right) ^T

= el \arg\max_ {C} \sum_ {i=1} ^\\mu w_i \log p_\mathcal {N }\\se fue (\left.\frac {x_ {i:\lambda} - m_k} {\\sigma_k} \right | C\right) </matemáticas>

para (por otra parte es singular, pero considerablemente el mismo resultado sostiene para

Descenso del declive natural en el espacio de distribuciones de la muestra

Akimoto. recientemente encontró que la actualización de los parámetros de distribución se parece a bajar en la dirección de un declive natural probado del valor de función objetivo esperado (para minimizarse), donde la expectativa se toma bajo la distribución de la muestra. Con el ajuste del parámetro de y, es decir sin la talla del paso controlan y clasifican una actualización, CMA-ES se puede así ver como un instantiation de Natural Evolution Strategies (NES).

El declive natural es independiente del parameterization de la distribución. Tomado con respecto a los parámetros de la distribución de la muestra, el declive de se puede expresar como

::

¡

{\\nabla} _ {\\! \theta} E (f (x) | \theta)

¡

&= \nabla_ {\\! \theta} \int_ {\\mathbb R^n} f (x) p (x) \mathrm {d} x

\\¡&= \int_ {\\mathbb R^n} f (x) \frac {p (x)} {p (x)} \nabla_ {\\! \theta} p (x) \mathrm {d} x

\\¡&= \int_ {\\mathbb R^n} f (x) p (x) \nabla_ {\\! \theta} \ln p (x) \mathrm {d} x

\\&= E (¡f (x) \nabla_ {\\! \theta} \ln p (x |\theta))

Los \end {alinean} </matemáticas>

donde depende del vector del parámetro, la llamada función del resultado, indica la sensibilidad relativa de w.r.t., y la expectativa se toma con respecto a la distribución. El declive natural de, cumpliendo con la información de Fisher métrica (una medida de la distancia informativa entre distribuciones de probabilidad y la curvatura de la entropía relativa), ahora lee

::

\tilde {\\nabla} E (f (x) | \theta)

¡

&= F^ {-1} _ \theta \nabla_ {\\! \theta} E (f (x) | \theta)

Los \end {alinean} </matemáticas>

donde la matriz de información de Fisher es la expectativa de la Arpillera de y da la expresión independiente de parameterization elegido. Combinando las igualdades anteriores conseguimos

::

\tilde {\\nabla} E (f (x) | \theta)

&= F^ {-1} _ \theta E (¡f (x) \nabla_ {\\! \theta} \ln p (x |\theta))

\\&= E (¡f (x) F^ {-1} _ \theta \nabla_ {\\! \theta} \ln p (x |\theta))

Los \end {alinean} </matemáticas>

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

::

donde la nota desde encima se usa y por lo tanto disminuye monótonamente en.

Podríamos usar, para una aproximación más robusta, mejor dicho como definido en el CMA-ES y cero para y dejar

a

::

tal que es la densidad de la distribución normal de la multivariante aleatoria. Entonces, tenemos una expresión explícita para

::

y para

::

\, - \, \frac {1} {2 }\\ln\det (2\pi\sigma_k^2 C_k) </matemáticas>

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

::

m_ {k+1}

&= m_k - \underbrace {[\tilde {\\nabla} \widehat {E} _ \theta (f)] _ {1, \dots, n}} _ {\

¡

\! \! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\!

\text {declive natural para }medio \

¡

\! \! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\!

}

\\

&= m_k + \sum_ {i=1} ^\\lambda w_i (x_ {i:\lambda} - m_k)

Los \end {alinean} </matemáticas>

y

::

C_ {k+1}

&= C_k + c_1 (p_c p_c^T - C_k)

- \frac {c_\mu} {\\sigma_k^2 }\\, \mathrm {estera} (\overbrace {[\tilde {\\nabla} \widehat {E} _ \theta (f)] _ {n+1, \dots, n+n^2}} ^ {\

¡

\! \! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\!

\text {declive natural para matriz de la covariancia}

¡

\! \! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\!

}) \\

&= C_k + c_1 (p_c p_c^T - C_k)

+ \frac {c_\mu} {\\sigma_k^2} \sum_ {i=1} ^\\lambda w_i \left ({(x_ {i:\lambda} - m_k)} {} \left ({x_ {i:\lambda} - m_k} {}\\derecho) ^T - \sigma_k^2 C_k\right)

Los \end {alinean} </matemáticas>

</envergadura>

donde la estera forma la matriz apropiada del subvector del declive natural respectivo. Esto significa, ajuste, las actualizaciones de CMA-ES descienden en la dirección de la aproximación del declive natural usando tallas del paso diferentes (aprendizaje de precios) para los parámetros ortogonales y respectivamente.

Stationarity o Unbiasedness

Es

comparativamente fácil ver que las ecuaciones de actualización de CMA-ES satisfacen algunas condiciones stationarity, en esto son esencialmente imparciales. Bajo la selección neutra, donde, encontramos esto

::

y bajo algunas asunciones adicionales suaves en las condiciones iniciales

::

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

::

Invariance

Las propiedades de Invariance implican el rendimiento uniforme en una clase de funciones objetivas. Se han argumentado para ser una ventaja, porque permiten generalizar y predecir el comportamiento del algoritmo y por lo tanto reforzar el sentido de resultados empíricos obtenidos en funciones solas. Las propiedades invariance siguientes se han establecido para CMA-ES.

Cualquier método de optimización del parámetro serio debería ser la invariante de la traducción, pero la mayor parte de métodos no exponen todas las susodichas propiedades invariance descritas. Un ejemplo prominente con las mismas propiedades invariance es el método del Nelder-prado, donde la inicial simplex se debe elegir respectivamente.

Convergencia

Las consideraciones conceptuales como la propiedad de la escala-invariance del algoritmo, el análisis de estrategias de evolución más simples y evidencia empírica aplastante sugieren que el algoritmo converge en una clase grande de funciones rápido al grado óptimo global, denotado como. En algunas funciones, la convergencia ocurre independientemente de las condiciones iniciales con la probabilidad un. En algunas funciones la probabilidad es más pequeña que una y típicamente depende de la inicial y. Empíricamente, el precio de convergencia más rápido posible en para métodos de búsqueda directos basados en la fila a menudo se puede observar (según el contexto denotado como la convergencia lineal o lineal por el tronco o exponencial). Informalmente, podemos escribir

::

</matemáticas>

para unos, y más rigurosamente

::

\; = \; \frac {1} {k }\\log\frac {\\|m_k - x^* \|} {\\|m_ {0} - x^* \| }\

\; \to \;-c

o del mismo modo,

::

\; \to \;-c

Esto significa que por término medio la distancia al grado óptimo es disminuida en cada iteración por un factor "constante", a saber por. El precio de convergencia es aproximadamente, dado no es mucho más grande que la dimensión. Incluso con el óptimo y, el precio de convergencia no puede exceder en gran parte, dado los susodichos pesos de la nueva combinación son toda la no negativa. Las dependencias lineales actuales en y son notables y están en ambos casos que el mejor puede esperar en esta clase del algoritmo. Aún, una prueba rigurosa de la convergencia falla.

Interpretación como transformación del sistema coordenado

La utilización de una matriz de la covariancia de no identidad para la distribución normal de la multivariante aleatoria en estrategias de evolución es equivalente a una transformación del sistema coordenado de los vectores de solución, principalmente porque la ecuación de prueba

:

Los \begin {alinean }\

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)

Los \end {alinean }\

</matemáticas>

se puede equivalentemente expresar en un "espacio codificado" como

:

\underbrace {C_k^ {-1/2} x_i} _ {\\texto {representado en }espacial codificar \

¡

\! \! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\! ¡\!}

\sim\\underbrace {C_k^ {-1/2} m_k} {} + \sigma_k \times\mathcal {N} (0, yo)

</matemáticas>

La matriz de la covariancia define una transformación bijective (codificación) para todos los vectores de solución en un espacio, donde la prueba ocurre con la matriz de la covariancia de identidad. Como las ecuaciones de actualización en el CMA-ES son invariantes bajo transformaciones del sistema coordenado (transformaciones lineales generales), el CMA-ES se puede volver a escribir como un procedimiento de codificación adaptable aplicado a una estrategia de evolución simple con la matriz de la covariancia de identidad.

Este procedimiento de codificación adaptable no se encajona a algoritmos que muestra de una distribución normal de la multivariante aleatoria (como estrategias de evolución), pero se puede en principio aplicar a cualquier método de búsqueda iterativo.

Rendimiento en la práctica

En contraste con la mayor parte de otros algoritmos evolutivos, el CMA-ES es, desde el punto de vista de usuarios, casi sin parámetros. Sin embargo, el número de muestras del candidato &lambda; (talla demográfica) puede ser ajustado por el usuario a fin de cambiar el comportamiento de búsqueda característico (ver encima). CMA-ES ha tenido empíricamente éxito en cientos de aplicaciones y se considera ser útil en particular en funciones objetivas no convexas, no separables, de mal carácter, multimodales o ruidosas. La dimensión de la área de búsqueda se extiende típicamente entre dos y unos cientos. Asumiendo un guión de optimización de la caja negra, donde los declives no están disponibles (o no útiles) y las evaluaciones de función son el único coste considerado de la búsqueda, el método CMA-ES probablemente será superado por otros métodos en las condiciones siguientes:

En funciones separables la desventaja de rendimiento probablemente será la más significativa, en que CMA-ES no podría ser capaz de encontrar en todas las soluciones comparables. la otra mano, en funciones no separables que son de mal carácter o rugosas o sólo se pueden solucionar con más que evaluaciones de función, los espectáculos de CMA-ES rendimiento el más a menudo superior.

Variaciones y extensiones

(El 1+1)-CMA-ES

genera sólo una solución del candidato por paso de iteración que sólo se hace la nueva distribución media, si es mejor que el viejo medio. Ya que es una variante cercana de la adaptación de Gaussian. El CMA-ES también se ha ampliado a la optimización multiobjetiva como MO-CMA-ES

. Otra extensión notable ha sido la adición de una actualización negativa de la matriz de la covariancia con llamado CMA activo

.

Véase también

Bibliografía

http://mitpress.mit.edu/journals/pdf/evco_11_1_1_0.pdf http://www.lri.fr/~hansen/ppsn2004hansenkern.pdf http://www.mitpressjournals.org/doi/pdfplus/10.1162/evco.2007.15.1.1

Enlaces externos



Buscar