Evolución diferencial

La Evolución Diferencial (ED) es un método de optimización perteneciente a la categoría de computación evolutiva, aplicado en la resolución de problemas complejos. Al igual que otros algoritmos de esta categoría, la ED mantiene una población de soluciones candidatas, las cuales se recombinan y mutan para producir nuevos individuos los cuales serán elegidos de acuerdo al valor de su función de desempeño. Lo que caracteriza a la ED es el uso de vectores de prueba, los cuales compiten con los individuos de la población actual a fin de sobrevivir.

Historia

El primer artículo sobre ED fue publicado por Kenneth Price y Rainer Storn en octubre de 1995 bajo el nombre de "Differential Evolution -- a simple and efficient adaptive scheme for global optimization over continuous spaces". Originalmente, el método estaba enfocado en la resolución del problema de ajuste de polinomio de Tchebychev utilizando una variante del método llamado Recocido Genético (Genetic Annealing), el cual había sido desarrollado por Price el año anterior. En 1996, ED fue presentado en el First International Contest on Evolutionary Optimization, que buscaba comparar el potencial de distintos métodos de optimización de computación evolutiva, finalizando ED en tercer lugar.

Hoy en día, ED representa una de las corrientes principales de la investigación en computación evolutiva.

Algoritmo

El algoritmo asume que las variables del problema a optimizar están codificadas como un vector de números reales. El largo de estos vectores (n)es igual al número de variables del problema, y la población está compuesta de NP vectores. Se define un vector $x_{p}^{g}$, en donde p es el índice del individuo en la poblacion (p = 1...NP) y g es la generación correspondiente. Cada vector está a su vez compuesto de las variables del problema $x_{p,m}^{g}$, en donde m es el índice de la variable en el individuo (m = 1...n).

Se asume que el dominio de las variables del problema está restingido entre valores mínimos y máximos $x_{m}^{min}$ y $x_{m}^{max}$, respectivamente.

ED se compone básicamente de 4 pasos:

• Inicialización
• Mutación
• Recombinación
• Selección

La incialización se realiza al principio de la ejecución de la búsqueda, y los pasos de mutación-recombinación-selección se realizan repetidas veces, hasta que una condición de término sea satisfecha (número de generaciones, tiempo transcurrido, o calidad de soución alcanzada, entre otras)

Inicialización

La población es inicializada (primera generación) aleatoriamente, considerando los valores mínimos y máximos de cada variable:

$x_{p,m}^{1}=x_{m}^{min}+rand(0,1)\cdot (x_{m}^{max}-x_{m}^{min})$

para p = 1...NP, m = 1...n, y rand(0,1) un número aleatorio en el rango [0,1].

Mutación

La mutación consiste en la construcción de NP vectores aleatorios ruidosos (noisy random vectors), los cuales son creados a partir de tres individuos elegidos al azar, llamados vectores objetivo (target vectors), $x_{a},x_{b},x_{c}$. Los vectores aleatorios ruidosos ($n_{p}^{t}$) son obtenidos de la siguiente manera:

$n_{p}^{g}=x_{c}+F\cdot (x_{a}-x_{b})$

con p, a, b y c distintos entre sí, y p=1...NP

F es un parámetro que controla la tasa de mutación, y se encuentra en el rango [0,2].

Recombinación

Una vez obtenidos los NP vectores aleatorios ruidosos, la recombinación se efectúa de manera aleatoria, comparándolos con los vectores originales ($x_{p},^{g}$), obteniendo los vectores de prueba (trial vectors, $t_{m}^{g}$) de la siguiente manera:

$t_{p,m}^{g}={\begin{cases}n_{p,m}^{g}{\mbox{ si }}rand(0,1)<GR\\x_{p,m}^{g}{\mbox{ en otro caso}}\end{cases}}$

para p = 1...NP, m = 1...n.

GR es un parámetro que controla la tasa de recombinación. Nótese que la comparacón se hace variable por variable, por lo que el vector de prueba será una mezcla de los vectores aleatorios ruidosos y original.

Selección

Finalmente, la selección se realiza simplemente comparando los vectores de prueba con los originales, de manera que el vector de la generación siguiente será aquel que tenga el mejor valor de función de desempeño fit:

$x_{p}^{g+1}={\begin{cases}t_{p}^{g}{\mbox{ si }}fit(t_{p}^{g})>fit(x_{p}^{g})\\x_{p}^{g}{\mbox{ en otro caso}}\end{cases}}$

Referencias

• Página sobre ED
• Bibliografía sobre ED