Evolución diferencial

Evolución diferencial

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.

Contenido

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), xa,xb,xc. 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 (xp,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

Obtenido de "Evoluci%C3%B3n diferencial"

Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Formación y evolución del Sistema Solar — Artículo principal: Sistema Solar Las teorías concernientes a la formación y evolución del Sistema Solar son variadas y complejas, involucrando varias disciplinas científicas, desde la astronomía y la física hasta la geología y la ciencia… …   Wikipedia Español

  • Imagen de evolución temporal — En mecánica cuántica, existen diversas formas de presentar las ecuaciones de movimiento de un sistema. En la imagen de Schrödinger la evolución temporal del mismo afecta al estado cuántico que lo representa. Es la manera «estándar» de introducir… …   Wikipedia Español

  • Algoritmo evolutivo — Los algoritmos evolutivos son métodos de optimización y búsqueda de soluciones basados en los postulados de la evolución biológica. En ellos se mantiene un conjunto de entidades que representan posibles soluciones, las cuales se mezclan, y… …   Wikipedia Español

  • Optimización combinatoria — La optimización combinatoria es una rama de la optimización en matemáticas aplicadas y en ciencias de la computación, relacionada a la investigación de operaciones, teoría de algoritmos y teoría de la complejidad computacional. También está… …   Wikipedia Español

  • Movimiento rectilíneo uniformemente acelerado — Evolución respecto del tiempo de la posición, de la velocidad y de la aceleración de un cuerpo sometido a un movimiento rectilíneo uniformemente acelerado, según la mecánica clásica. El movimiento rectilíneo uniformemente acelerado (MRUA),… …   Wikipedia Español

  • Mitsubishi lancer evolution — Saltar a navegación, búsqueda El Mitsubishi Lancer Evolution, coloquialmente conocido como el Lancer Evo o Evo [1], es un coche fabricado por Mitsubishi Motors. Ha habido diez versiones oficiales hasta la fecha, y la designación de cada modelo es …   Wikipedia Español

  • Leucemia linfática crónica — Para la secuenciación del genoma de la LLC, véase Genoma de la leucemia linfática crónica. Leucemia linfática crónica Frote sanguíneo mostrando linfocitos (morados) en una LLC …   Wikipedia Español

  • Síndrome neuroléptico maligno — Clasificación y recursos externos CIE 10 G21.0 …   Wikipedia Español

  • Selección natural — Ilustraciones realizadas por Charles Darwin para ilustrar las variaciones del pico de los pinzones de las Islas Galápagos debido a la actuación de la selección natural. En su forma inicial, la teoría de la evolución por selección natural… …   Wikipedia Español

  • Flor — Para otros usos de este término, véase Flor (desambiguación). Partes de la flor …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”