evolutionary-algorithm differential-evolution

evolutionary algorithm - Explicar el método de evolución diferencial.



evolutionary-algorithm differential-evolution (3)

¿Alguien puede explicar el método de evolución diferencial? La definition Wikipedia es extremadamente técnica.

Una explicación tonta hacia abajo seguida de un ejemplo simple sería apreciada :)

Aquí hay una descripción simplificada . DE es una técnica de optimización que modifica iterativamente una población de soluciones candidatas para hacerla converger a un óptimo de su función.

Primero inicia sus soluciones candidatas al azar. Luego, en cada iteración y para cada solución candidata, haga lo siguiente:

  1. produce un vector de prueba: v = a + (b - c) / 2, donde a, b, c son tres soluciones candidatas distintas elegidas al azar entre su población.
  2. intercambias aleatoriamente componentes vectoriales entre x y v para producir v ''. Al menos un componente de v debe ser intercambiado.
  3. reemplaza x en tu población con v ''solo si es un mejor candidato (es decir, optimiza mejor tu función).

(Tenga en cuenta que el algoritmo anterior es muy simplificado; no codifique desde él, busque las especificaciones adecuadas en otro lugar)

Desafortunadamente el artículo de Wikipedia carece de ilustraciones. Es más fácil de entender con una representación gráfica, encontrará algunas en estas diapositivas: http://www-personal.une.edu.au/~jvanderw/DE_1.pdf .

Es similar al algoritmo genético (GA), excepto que las soluciones candidatas no se consideran como cadenas binarias (cromosoma) sino (generalmente) como vectores reales. Un aspecto clave de DE es que el tamaño del paso de mutación (consulte el paso 1 para la mutación) es dinámico, es decir, se adapta a la configuración de su población y tenderá a cero cuando converja. Esto hace que DE sea menos vulnerable a la deriva genética que GA.

El funcionamiento del algoritmo DE es muy simple. Considere que necesita optimizar (minimizar, por ejemplo,) ∑Xi ^ 2 (modelo de esfera) dentro de un rango dado, digamos [-100,100] . Sabemos que el valor mínimo es 0. Veamos cómo funciona DE.

DE es un algoritmo basado en la población. Y para cada individuo en la población, habrá un número fijo de cromosomas (imagínalo como un conjunto de seres humanos y cromosomas o genes en cada uno de ellos). Déjame explicar DE wrt por encima de la función

Necesitamos corregir el tamaño de la población y la cantidad de cromosomas o genes (nombrados como parámetros). Por ejemplo, consideremos una población de tamaño 4 y cada uno de los individuos tiene 3 cromosomas (o genes o parámetros). Llamemos a los individuos R1, R2, R3, R4.

Paso 1: Inicializar la población.

Necesitamos inicializar aleatoriamente la población dentro del rango [-100,100]

G1 G2 G3 objective fn value R1 -> |-90 | 2 | 1 | =>8105 R2 -> | 7 | 9 | -50 | =>2630 R3 -> | 4 | 2 | -9.2| =>104.64 R4 -> | 8.5 | 7 | 9 | =>202.25

el valor de la función objetivo se calcula utilizando la función objetivo dada. En este caso, es ∑Xi ^ 2 . Entonces, para R1, el valor obj fn será -90 ^ 2 + 2 ^ 2 + 2 ^ 2 = 8105 . Del mismo modo se encuentra para todos.

Paso 2: Mutación

Corrija un vector objetivo, por ejemplo, por ejemplo, R1 y luego seleccione aleatoriamente otros tres vectores (individuos) por ejemplo, por ejemplo, R2, R3, R4 y realiza la mutación. La mutación se hace de la siguiente manera,

MutantVector = R2 + F(R3-R4)

(Los vectores se pueden elegir al azar, no es necesario que estén en ningún orden). F (factor de escala / constante de mutación) dentro del rango [0,1] es uno de los pocos parámetros de control que tiene DE. En palabras simples, describe qué tan diferente se vuelve el vector mutado. Mantengamos F = 0.5.

| 7 | 9 | -50 | + 0.5 * | 4 | 2 | -9.2| + | 8.5 | 7 | 9 |

Ahora realizando Mutación dará el siguiente Vector Mutante.

MV = | 13.25 | 13.5 | -50.1 | =>2867.82

Paso 3: Crossover

Ahora que tenemos un vector objetivo (R1) y un vector mutante MV formado a partir de R2, R3 y R4, necesitamos hacer un cruce. Considere R1 y MV como dos padres y necesitamos un hijo de estos dos padres. El cruce se realiza para determinar cuánta información se debe tomar de los padres. Está controlado por la tasa de cruce (CR) . Cada gen / cromosoma del niño se determina como sigue,

se genera un número aleatorio entre 0 y 1, si es mayor que CR, luego se hereda un gen del objetivo (R1) del mutante (MV).

Vamos a establecer CR = 0.9. Ya que tenemos 3 cromosomas para individuos, necesitamos generar 3 números aleatorios entre 0 y 1. Digamos, por ejemplo, que esos números son 0.21,0.97,0.8 respectivamente. El primero y el último son menores que el valor de CR, por lo que las posiciones en el vector del niño se llenarán con los valores de MV y la segunda posición se llenará con el gen tomado del objetivo (R1).

Objetivo-> |-90 | 2 | 1 | |-90 | 2 | 1 | Mutante-> | 13.25 | 13.5 | -50.1 | | 13.25 | 13.5 | -50.1 |

random num - 0.21, => `Child -> |13.25| -- | -- |` random num - 0.97, => `Child -> |13.25| 2 | -- |` random num - 0.80, => `Child -> |13.25| 2 | -50.1 |` Trial vector/child vector -> | 13.25 | 2 | -50.1 | =>2689.57

Paso 4: Selección

Ahora tenemos hijo y objetivo. Compare el objeto de ambos, vea cuál es más pequeño (problema de minimización). Seleccione ese individuo de los dos para la próxima generación

R1 -> |-90 | 2 | 1 | =>8105 Trial vector/child vector -> | 13.25 | 2 | -50.1 | =>2689.57

Claramente, el niño es mejor, así que reemplace target (R1) con el niño. Así se convertirá la nueva población.

G1 G2 G3 objective fn value R1 -> | 13.25 | 2 | -50.1 | =>2689.57 R2 -> | 7 | 9 | -50 | =>2500 R3 -> | 4 | 2 | -9.2 | =>104.64 R4 -> | -8.5 | 7 | 9 | =>202.25

Este procedimiento continuará hasta que la cantidad de generaciones deseadas haya alcanzado o hasta que obtengamos el valor deseado. Espero que esto te ayude.

Respondiendo a mi propia pregunta ...

Visión general

  • La principal diferencia entre los algoritmos genéticos y la evolución diferencial (DE) es que los algoritmos genéticos se basan en el cruce, mientras que las estrategias evolutivas utilizan la mutación como mecanismo de búsqueda principal.
  • DE genera nuevos candidatos al agregar una diferencia ponderada entre dos miembros de la población a un tercer miembro (más sobre esto más adelante).
  • Si el candidato resultante es superior al candidato con el que se comparó, lo reemplaza; de lo contrario, el candidato original se mantiene sin cambios.

Definiciones

  • La población está formada por candidatos del NP .
  • Xi = Un candidato principal en el índice i (los índices oscilan entre 0 y NP-1 ) de la generación actual. También conocido como el vector objetivo .
  • Cada candidato contiene parámetros D
  • Xi(j) = El parámetro j th en el candidato Xi .
  • Xa , Xb , Xc = tres candidatos parentales aleatorios.
  • Vector de diferencia = (Xb - Xa)
  • F = Un peso que determina la tasa de evolución de la población.
    • Valores ideales: [0.5, 1.0]
  • CR = La probabilidad de que se produzca un cruce.
    • Rango: [0, 1]
  • Xc` = Un vector mutante obtenido a través de la operación de mutación diferencial. También conocido como el vector donante .
  • Xt = El hijo de Xi y Xc` . También conocido como el vector de prueba .

Algoritmo

  1. Para cada candidato en la población.
    • for (int i = 0; i<NP; ++i)
  2. Elija tres padres distintos al azar (deben diferir entre sí y i )

do { a = random.nextInt(NP); } while (a == i) do { b = random.nextInt(NP); } while (b == i || b == a); do { c = random.nextInt(NP); } while (c == i || c == b || c == a);

  1. (Paso de mutación) Agregar un vector de diferencia ponderada entre dos miembros de la población a un tercer miembro
    • Xc` = Xc + F * (Xb - Xa)
  2. (Paso de cruce) Para cada variable en Xi , aplique un cruce uniforme con probabilidad CR para heredar de Xc` ; De lo contrario, hereda de Xi . Al menos una variable debe ser heredada de Xc`

int R = random.nextInt(D); for (int j=0; j < D; ++j) { double probability = random.nextDouble(); if (probability < CR || j == R) Xt[j] = Xc`[j] else Xt[j] = Xi[j] }

  1. (Paso de selección) Si Xt es superior a Xi entonces Xt reemplaza a Xi en la próxima generación. De lo contrario, Xi se mantiene sin modificar.

Recursos