Evolució diferencial

La Evolució Diferencial (ED) és un método d'optimisació pertanyent a la categoria de computació evolutiva, aplicat en la resolució de problemes complexos. De la mateixa manera que atres algoritmes d'esta categoria, la ED manté una població de solucions candidates, les quals es recombinan i mutan per a produir nous individus els quals seran elegits d'acort al valor del seu funció d'eixercite. Lo que caracterisa a la ED és l'us de vectores de prova, els quals competixen en els individus de la població actual a fi de sobreviure.

Història

El primer artícul sobre ED va ser publicat per Kenneth Price i Rainer Storn en octubre de 1995 baix el nom de "Differential Evolution -- a simple and efficient adaptive scheme for global optimization over continuous spaces". Originalment, el método estava enfocat en la resolució del problema d'ajust de polinomi de Tchebychev utilisant una variant del método cridat Recocido Genètic (Genetic Annealing), el qual havia segut desenrollat per Price l'any anterior. En 1996, ED va ser presentat en el First International Contest on Evolutionary Optimization, que buscava comparar el potencial de distints métodos d'optimisació de computació evolutiva, finalisant ED en tercer lloc.

Hui en dia, ED representa una de les corrents principals de l'investigació en computació evolutiva.

Algoritme

L'algoritme assumix que les variables del problema a optimisar estan codificades com un vector de número real. La llongitut d'estos vectores (n)és igual al número de variables del problema, i la població està composta de NP (Número de pares)vectores. Es definix un vector $x_p^g$, en a on p és l'índex de l'individu en la població (p = 1...NP) i g és la generació corresponent. Cada vector està a la seua volta compost de les variables del problema $x_{p,m}^g$, en a on m és l'índex de la variable en l'individu (m = 1...n).

S'assumix que el domini de les variables del problema està restringit entre valors mínims i màxims $x_m^{min}$ i $x_m^{max}$, respectivament.

ED es compon bàsicament de 4 passos:

• Inicialisació
• Mutació
• Recombinació
• Selecció

La inicialisació es realisa al principi de l'eixecució de la busca, i els passos de mutació-recombinació-selecció es realisen repetides voltes, fins que una condició de terme siga satisfeta (número de generacions, temps transcorregut, o calitat de solució alcançada, entre atres).

Inicialisació

La població és inicializada (primera generació) aleatoriamente, considerant els valors mínims i màxims de cada variable:

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

per a p = 1...NP, m = 1...n, i rand(0,1) un número aleatori en el ranc [0,1].

Mutació

La mutació consistix en la construcció de NP vectores aleatoris sorollosos (noisy random vectors), els quals són creats a partir de tres individus elegits a l'encert, cridats vectores objectiu (target vectors), $x_a,x_b,x_c$. Els vectores aleatoris sorollosos ($n_p^t$) són obtinguts de la següent manera:

$n_p^g=x_c+F\cdot (x_a-x_b)$

en p, a, b i c distints entre sí, i p=1...NP

F és un paràmetro que controla la taxa de mutació, i es troba en el ranc [0,2].

Recombinació

Una volta obtinguts els NP vectores aleatoris sorollosos, la recombinació s'efectua de manera aleatòria, comparant-los en els vectores originals ($x_p{,}^g$), obtenint els vectores de prova (trial vectors, $t_m^g$) de la següent manera:

$t_{p,m}^g=\{\begin{array}{c}{n}_{p,m}^g\text{ si }rand(0,1)<GR\\ x_{p,m}^g\text{ en otro caso}\end{array}$

per a p = 1...NP, m = 1...n.

GR és un paràmetro que controla la taxa de recombinació. Note's que la comparació es fa variable per variable, per lo que el vector de prova serà una mescla dels vectores aleatoris sorollosos i original.

Selecció

Finalment, la selecció es realisa simplement comparant els vectores de prova en els originals, de manera que el vector de la generació següent serà aquell que tinga el millor valor de funció d'eixercite fit:

$x_p^{g+1}=\{\begin{array}{c}{t}_p^g\text{ si }fit(t_p^g)>fit(x_p^g)\\ x_p^g\text{ en otro caso}\end{array}$

Referències

• Pàgina sobre ED
• Bibliografia sobre ED

Bibliografia

• Carmona, Enrique J.; Fernández, Severino (2020). Fonaments de la Computació Evolutiva. Marcombo. ISBN 978-8426727558.