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.
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.
El algoritmo asume que las variables del problema a optimizar están codificadas como un vector de números reales.
La longitud de estos vectores (n)es igual al número de variables del problema, y la población está compuesta de NP (Número de padres)vectores.
, en donde p es el índice del individuo en la población (p = 1...NP) y g es la generación correspondiente.
Cada vector está a su vez compuesto de las variables del problema
Se asume que el dominio de las variables del problema está restringido entre valores mínimos y máximos
ED se compone básicamente de 4 pasos: La inicializació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 solución alcanzada, entre otras).
La población es inicializada (primera generación) aleatoriamente, considerando los valores mínimos y máximos de cada variable:
+ r a n d ( 0 , 1 ) ⋅ (
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),
) son obtenidos de la siguiente manera:
{\displaystyle n_{p}^{g}=x_{c}+F\cdot (x_{a}-x_{b})}
F es un parámetro que controla la tasa de mutación, y se encuentra en el rango [0,2].
Una vez obtenidos los NP vectores aleatorios ruidosos, la recombinación se efectúa de manera aleatoria, comparándolos con los vectores originales (
), obteniendo los vectores de prueba (trial vectors,
) de la siguiente manera:
r a n d ( 0 , 1 ) <
{\displaystyle t_{p,m}^{g}={\begin{cases}n_{p,m}^{g}{\mbox{ si }}rand(0,1) GR es un parámetro que controla la tasa de recombinación. Nótese que la comparación se hace variable por variable, por lo que el vector de prueba será una mezcla de los vectores aleatorios ruidosos y original. 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: