Usuario:Juan de Anda-suárez/Taller

En Ciencias de la computación, Symmetric-Approximation Energy-Based Estimation of Distribution (SEED)​ es un algoritmo de Optimización global en el esquema de Algoritmo de estimación de distribución, la estructura fundamental de SEED se semienta en Univariate Marginal Distribution Algorithm (UMDA ​), en donde se busca aproximar la distribución de Boltzmann mediante la mínima diferencia entre la distribución normal, la aproximación mencionada permite a SEED tener una mejor selección de elementos, ya que la distribución Boltzmann garantiza que la probabilidad de obtener elementos con menor energía (en problemas de maximización) es baja, lo que dota a SEED con un mejor desempeño.

Los Algoritmos evolutivos conciten en proponer diferentes individuos solución distribuidos en el espacio de búsqueda del problema y al conjunto de dichos individuos se le nombra población. Los Individuos son modificados a lo largo de la evolución, mediante tres operadores fundamentales conocidos como cruza, mutación y selección ​., SEED está especialmente diseñado para mejorar el operador de selección, como ya se menciono utilizando la distribución de Boltzmann, en la siguiente sección se explica a detalle la modificación al operador de selección de la población.

Fundamentos teóricos

El algoritmo SEED usa como método de selección de nuevos individuos la función de distribución de probabilidad de Boltzmann la cual es definida por

$$P_{x}=P(x;{\beta })={\frac {1}{Z}}e^{{\beta }g_{x}}$$

donde $Z$ es la función de partición del sistema, $\beta ={\frac {1}{T}}$ entendiéndose a $T$ como el nivel de energía ideal al que se desea llegar en el sistema, mientras que $g(x)$ representa la función de costo a optimizar. Sin embargo, estimar nueva población directamente de la distribución Boltzmann conlleva a dificultades técnicas, tales como la generación de Número pseudoaleatorio en dicha distribución, de manera que se ha optado en el estado del arte​,​ por estimar la nueva población en términos de los parámetros estadísticos $\mu$ y $\sigma$ de la distribución normal, la cual es definida por

$$Q_{x}=Q(x;\mu ,\nu )={\frac {1}{\sqrt {2\pi \nu }}}\exp \left({-{\frac {1}{2}}{\frac {(x-\mu )^{2}}{\nu }}}\right)$$

Para poder comparar las dos distribuciones de probabilidad en el espacio de probabilidades se han definido diferentes medidas de divergencia destacando para el procedimiento matemático la Jeffrey's divergence, devido a que es una medida que garantiza al menos dos criterios de una métrica, la que ha sido definida como​

$$D_{\text{J}}(Q_{x}||P_{x})=\int _{x}P_{x}\left({{\frac {Q_{x}}{P_{x}}}-1}\right){\text{log}}\left({\frac {Q_{x}}{P_{x}}}\right)dx$$

minimizando la $D_{\text{J}}(Q_{x}||P_{x})$ con respecto a el parámetro $\theta _{i}=[\mu ,\nu ]$, nos da como resultado

$${\begin{aligned}{\frac {\partial D_{\text{J}}}{\partial \theta _{i}}}=-\int _{x}{\frac {P_{x}}{Q_{x}}}{\frac {\partial Q_{x}}{\partial \theta _{i}}}dx+\int _{x}\left({1+{\text{log}}\left({\frac {Q_{x}}{P_{x}}}\right)}\right){\frac {\partial Q_{x}}{\partial \theta _{i}}}dx\end{aligned}}$$

Comenzamos inicialmente estimando un valor para el parámetro $\mu$, y considerando que ${\frac {\partial Q_{x}}{\partial \mu }}=Q_{x}{\frac {(x-\mu )}{\nu }}$, entonces

$${\frac {\partial D_{\text{J}}}{\partial \mu }}=-{\frac {1}{Z\nu }}\int _{x}{\text{exp}}\left({\beta g_{x}}\right)(x-\mu )dx+{\frac {\partial D_{\text{KL}}(Q||P)}{\partial \mu }}$$

donde $D_{\text{KL}}(Q||P)$ es la Divergencia de Kullback-Leibler, la cual es derivada parcial por $\mu$ dando como resultado

$${\begin{aligned}{\frac {\partial D_{\text{KL}}(Q||P)}{\partial \mu }}=&{\frac {1}{\nu }}\int _{x}(x-\mu )Q_{x}dx-{\frac {1}{2\nu ^{2}}}\int _{x}(x-\mu )^{3}Q_{x}dx\\&-\,{\frac {{\text{log}}(2\pi \nu )}{2\nu }}\int _{x}(x-\mu )Q_{x}dx\\&+\,{\frac {{\text{log}}(Z)}{\nu }}\int _{x}(x-\mu )Q_{x}dx\\&-\,{\frac {\beta }{\nu }}\int _{x}g_{x}(x-\mu )Q_{x}dx\end{aligned}}$$

resolviendo la ecuación anterior mediante Momento central $\int _{\chi }(x-\mu )Q_{x}dx=0$ y $\int _{\chi }(x-\mu )^{3}Q_{x}dx=0$ dando nos como resultado las siguiente ecuación

$${\begin{aligned}{\frac {\partial D_{\text{J}}}{\partial \mu }}=&-{\frac {1}{Z\nu }}\int _{x}{\text{exp}}\left({\beta g_{x}}\right)xdx+{\frac {\mu }{Z\nu }}\int _{x}{\text{exp}}\left({\beta g_{x}}\right)dx\\&-{\frac {\beta }{\nu }}\int _{x}xg_{x}Q_{x}dx+{\frac {\mu }{\nu }}\int _{x}\beta g_{x}dx\end{aligned}}$$note se que $\int _{\chi }P_{x}dx=1$ y ${\frac {\partial D_{J}}{\partial \mu }}=0$ , entonces despejando el resultado para $\mu$ tenemos el resultado de

$$\mu ={\frac {{\frac {1}{Z\beta }}\int _{x}{\text{exp}}\left({\beta g_{x}}\right)xdx+\int _{x}xg_{x}Q_{x}dx}{{\frac {1}{\beta }}+\int _{x}g_{x}Q_{x}dx}}$$A hora vamos a trabajar en deducir un fórmula para hacer la estimación del parámetro $\nu$, la cual parte del siguiente resultado

$${\begin{aligned}{\frac {\partial D_{\text{J}}}{\partial \nu }}=&-{\frac {1}{Z}}\int _{x}{\text{exp}}\left({\beta g_{x}}\right)\left[{{\frac {(x-\mu )^{2}}{2\nu ^{2}}}-{\frac {1}{2\nu }}}\right]dx-{\frac {1}{2\nu }}\\&\,-{\frac {\beta }{2\nu ^{2}}}\int _{x}g_{x}(x-\mu )^{2}Q_{x}dx+{\frac {\beta }{2\nu }}\int _{x}g_{x}Q_{x}dx\end{aligned}}$$expandiendo la integral anterior tenemos

$${\begin{aligned}{\frac {\partial D_{\text{J}}}{\partial \nu }}=&-{\frac {1}{2\nu ^{2}Z}}\int _{x}{\text{exp}}\left({\beta g_{x}}\right)(x-\mu )^{2}dx\\&+\,{\frac {1}{2\nu Z}}\int _{x}{\text{exp}}\left({\beta g_{x}}\right)dx-{\frac {1}{2\nu }}\\&-\,{\frac {\beta }{2\nu ^{2}}}\int _{x}g_{x}(x-\mu )^{2}Q_{x}dx\\&+\,{\frac {\beta }{2\nu }}\int _{x}g_{x}Q_{x}dx\end{aligned}}$$calculando para ${\frac {\partial D_{J}}{\partial \nu }}=0$, y resolviendo para $\nu$

$${\begin{aligned}\nu ={\frac {{\frac {1}{Z\beta }}\int _{x}{\text{exp}}\left({\beta g_{x}}\right)(x-\mu )^{2}dx+\int _{x}g_{x}(x-\mu )^{2}Q_{x}dx}{\int _{x}g_{x}Q_{x}dx}}\end{aligned}}$$Con los resultados teóricos encontrados en la presente sección vamos a construir un nuevo algoritmo para la optimización en el espacio continuo y donde el problema de optimización contenga la restricción de ser de variables independientes.

Algoritmo SEED

Para construir el algoritmo SEED necesitamos hacer modificaciones a los resultados teóricos presentados en la sección anterior

initialize $m$, $\sigma$, $C=I$, $p_{\sigma }=0$, $p_{c}=0$  // initialize state variables
while not terminate do  // iterate
    for $i$ in $\{1...\lambda \}$ do  // sample $\lambda$ new solutions and evaluate them
        $x_{i}$ = sample_multivariate_normal(mean=$m$, covariance_matrix=$\sigma ^{2}C$)
        $f_{i}$ = fitness($x_{i}$)
    $x_{1...\lambda }$ ← $x_{s(1)...s(\lambda )}$ with $s(i)$ = argsort($f_{1...\lambda }$, $i$)  // sort solutions
    $m'$ = $m$  // we need later $m-m'$ and $x_{i}-m'$       
    $m$ ← update_m$(x_{1},...,$ $x_{\lambda })$  // move mean to better solutions 
    $p_{\sigma }$ ← update_ps$(p_{\sigma },$ $\sigma ^{-1}C^{-1/2}(m-m'))$  // update isotropic evolution path
    $p_{c}$ ← update_pc$(p_{c},$ $\sigma ^{-1}(m-m'),$ $||p_{\sigma }||)$  // update anisotropic evolution path
    $C$ ← update_C$(C,$ $p_{c},$ ${(x_{1}-m')}/{\sigma },...,$ ${(x_{\lambda }-m')}/{\sigma })$  // update covariance matrix
    $\sigma$ ← update_sigma$(\sigma ,$ $||p_{\sigma }||)$  // update step-size using isotropic path length
return $m$ or $x_{1}$