C omputo Evolutivo - INAOE - Pa.morales/EC/pdf/ClaseED.pdfEvoluci on Diferencial (ED) Paso 1: Inicializaci on Un conjunto de individuos (vectores) son generados aleatoriamente En este

Computo Evolutivo

Dra. Ma. Guadalupe Martınez

Instituto Nacional de Astrofısica, Optica y Electronica

[email protected]

February 20, 2019

Dra. Ma. Guadalupe Martınez (INAOE) February 20, 2019 1 / 29

Outline

1 Evolucion Diferencial

2 Inteligencia Colectiva - PSO


Outline




Evolucion Diferencial (ED)

La ED es una estrategia de busqueda poblacional, muy similar a unalgoritmo evolutivo (AE)estandar.

Fue propuesto por Storn & Price en 1995.

Su principal diferencia con otros AEs son sus operadores de cruza ymutacion.

Considerado como uno de los AEs mas buenos para resolverproblemas de optmizacion numerica.



En ED el operador de mutacion no esta basado en una funcion dedistribucion de probabilidad predefinida. En su lugar, la distribuciondel operador de mutacion depende de la distribucion actual de lassoluciones (llamadas vectores) en la poblacion.

En ED una solucion potencial al problema de optimizacion es llamadavector: ~xi ,g = (~x1,i ,g , . . . , xD,i ,g )

Diferencias entre vectores son realizadas durante los operadores devariacion.



El proceso evolutivo de ED estandar (DE/rand/1/bin). Consiste en 4pasos principales:

Inicializacion

Mutacion

Cruza

Seleccion



Diseno de ED

Codificacion: Vectores de numeros reales

Mutacion:Basada en la distribucion de la poblacion

Cruza: Binomial o exponencial

Seleccion de padres: Determinıstica, cada padre(target) crea un solohijo (trial) usando los operadores de ED

Seleccion de sobrevivientes: Determinıstica



Paso 1: Inicializacion

Un conjunto de individuos (vectores) son generados aleatoriamente

En este paso, la dimensionalidad del problema D y los lımites de lasvariables deben ser considerados.



Paso 2: Mutacion

El operador de mutacion consiste en una diferencia aritmetica entrepares de vectores seleccionados aleatoriamente.

Se obtiene un vector de ruido o mutante el cual se calcula como ladiferencia escalada entre dos vectores (r1, r2) de tres vectoresseleccionados aleatoriamente, sumadas al valor del tercer vector (r0)llamado vector base. F es un parametro definido por el usuario.

~vi ,g = ~xr0,g + F (~xr1,g −~x r2,g )

r0 6= r1 6= r2 6= i

0 < F > 2



Mutacion



Paso 3: Cruza

Se realiza entre el vector mutante ~vi ,g y el target ~xi ,g para generar eltrial (hijo) correspondiente.

Durante este proceso, cada vector ~xi ,g de la poblacion es padre.

La cruza en ED es controlada por el parametro CR donde:0 ≤ CR ≤ 1.

uj ,i ,g+1 =

{vj ,i ,g if (rand j [0, 1] < CR) or (j = Jrand)

xj ,i ,g otherwise

(1)

Jrand ∈ rand [1,D] es una posicion aleatoria del vector

j ∈ [1,D] es el j-th variable del vector



Cruza



Paso 3: Cruza



Paso 4: Seleccion

Determina quien entre el target y el trial pasara a la siguientegeneracion.

Elitismo implıcito, los vectores pueden permanecer en la poblacionmas de una generacion.

~xi ,g+1 =

{~ui ,g Si ~ui ,g es mejor o igual a ~xi ,g

~xi ,g de otra manera(2)



Pseudocodigo de DE/rand/1/bin



Variantes

Las variantes mas populares



DE/best/1/bin



DE/target-to-rand/1

DE/target-to-best/1


Outline




Inteligencia colectiva

Diferente a los AEs, la Inteligencia colectiva esta basada encomportamientos sociales de individuos trabajando en grupos.

La poblacion de los algoritmos de inteligencia colectiva estacaracterizada por una colaboracion y no por competencia, como enlos AEs.


Optimizacion mediante Cumulos de Partıculas (PSO)

PSO

El PSO fue propuesto por Kennedy y Eberhart (1995)

Algoritmo de busqueda poblacional basado en la simulacion delcomportamiento social de los pajaros dentro de una parvada.

En PSO los individuos son llamados partıculas y vuelan a traves de unespacio de busqueda multidimensional.

Los cambios de posicion de las partıculas en el espacio de busqueda sebasan en la tendencia de los individuos a emular el exito de otrosindividuos.



PSO

Un cumulo consiste en un conjunto de partıculas, donde cadapartıcula representa una solucion potencial al problema.

La posicion de cada partıcula cambia de acuerdo a su propiaexperiencia y la de sus vecinos.

El status de una partıcula en el espacio de busqueda es definido pordos factores: su posicion ~xi (t) y la velocidad ~Vi (t)

La posicion de ~xi (t) cambia al agregarse una velocidad ~Vi (t):

~xi (t + 1) = ~xi (t) + ~Vi (t + 1) (3)



Diseno de PSO

Codificacion: Vectores de numeros reales

Operadores: Formula de Vuelo

Seleccion de lıderes: Pbest, Gbest, Lbest

Seleccion de sobrevivientes: Las partıculas solo vuelan en el espaciode busqueda, no mueren y no se crean nuevas





Operadores

Formula de vuelo

En la version de PSO llamada global-best, el vector de velocidadcambia de la siguiente manera:

~vi (t +1) = W ~vi (t)+C1r1 (pbest i (t)− ~xi (t))+C2r2 (gbest(t)− ~xi (t))(4)

Donde W coeficiente de inercia, C1 y C2 son coeficientes deaceleracion, usualmente definidos como constantes, y r1 y r2 ∈ [0, 1]son numeros aleatorios. Despues se ejecuta el vuelo:

~xi (t + 1) = ~xi (t) + ~Vi (t + 1) (5)



Seleccion lıderes (variantes PSO)

Individual-best: Cada partıcula compara unicamente su posicionactual con respecto a su mejor posicion (pbest)

Global-best: Cada partıcula es influenciada por la mejor solucion detodo el cumulo (gbest), ası como su propia experiencia (pbest)

Local-best: Cada partıcula es influenciada por la mejor solucion dentrode un vencindario (lbest), ası como por su propia experiencia (pbest)



Tipos de vecindarios

La estructura social en PSO esta determinada mediante la formacion devecindarios:

Topologıa de estrella: Cada partıcula se comunica con todas lasdemas partıculas. Una red totalmente conectada (modelo gbest).

Topologıa de anillo: Cada partıcula se comunica con sus n vecinosinmediatos (modelo lbest).



Pseudocodigo general PSO


The End


Documents

C omputo Evolutivo - INAOE - Pa.morales/EC/pdf/ClaseED.pdfEvoluci on Diferencial (ED) Paso 1: Inicializaci on Un conjunto de individuos (vectores) son generados aleatoriamente En este