Subscribe:

viernes, 31 de julio de 2015

Implementando algoritmo de Evolución Diferencial v1.0

Estas vacaciones tuve la fortuna de ir a un escuela de verano en la que nos presentaron un algoritmo que se llama Evolución Diferencial, que forma parte de la gran familia de Algoritmos Evolutivos. Una de las ventajas que tiene este algoritmo, con respecto a otros evolutivos, es que está diseñado para trabajar con problemas de optimización continua y que converge rápido, sin llegar a caer en convergencia prematura.

El algoritmo se divide en 4 etapas, estas son inicialización, mutación, recombinación y selección (me robé eso de Wikipedia). El algoritmo trabaja con una población NP (con 100 individuos trabaja bien) de vectores, con un valor constante F (o µ, dependiendo de la literatura) que controla la mutación que va de (0,1) o (0,2), dependiendo de la literatura. También incluye otra constante CR [0,1] que es usada en la recombinación, ya que esta se hace valor a valor del vector generado. Para generar un nuevo candidato se toman 3 vectores al azar dentro de la población y se le aplica la fórmula P= Ir1 + F * (Ir2 - Ir3) donde Iri son los vectores escogidos al azar.

Para mayor información, dejo aquí el enlace al artículo en que presentaron el algoritmo. La implementación que hice fue la siguiente:

La implementación, si bien puede mejorarse bastante, funciona. Fue probado con f(x,y) = x^2 + y^2 siendo 0 el mínimo que se quería alcanzar. Entre las cosas que se pueden mejorar está el tipo de estructura usado para representar los datos, arreglando eso se puede usar ciclos para ahorrar código. De igual manera, no se calcula el error de cada iteración, sólo se tomo como condición de paro el crear 200 generaciones.

Espero les sirva. Hasta luego.

0 Comentarios:

Publicar un comentario