Unidad VI Algoritmos Genéticos (Continuación) - …rvazquez.org/Misitio/IntroduccionIA_files/Presentacion-10-2014.pdf · 6.4 El Algoritmo Genético y los operadores genéticos

Unidad VIAlgoritmos Genéticos (Continuación)

Maestría en Sistemas ComputacionalesClave: MPSCO-0108 6 Créditos

Sesiones Sabados 10-13

Rafael Vázquez Pérez

viernes 7 de noviembre de 14

6.4 El Algoritmo Genético y los operadores genéticos.6.5 Análisis, Diseño e Implementación de unAlgoritmo Genético.

Agenda“Hemos descubierto los secretos de la vida”

Francis Crick


El Algoritmo Genético y los operadores genéticos.

Definición de:A)Parámetros de entrada

B)Función CostoC) Estimación Salida

Calculo de la PoblaciónInicial

Se cumplió laconvergencia

MatingPool

Selecciónde

Parejas

Cruce

Mutación

Se toma la nueva descendencia para integrarse

al mating pool

Se entrega el resultadodel valor optimo

No Si


Análisis, Diseño e Implementación de un Algoritmo Genético.

• Los algoritmos genéticos(AG) empiezan definiendo un cromosoma (representación de un miembro de la población) como un arreglo de valores de los parámetros a ser optimizados.

• Si el cromosoma tiene Npar parámetros (un problema de optimización Npar-dimensional) dado por:

p1,p2,p3,...........,pNpar



• El cromosoma es escrito como un arreglo de elementos de tamaño Npar

cromosoma=[p1,p2,p3,...........,pNpar]

• Por ejemplo: Caso 1: La empresa productora de la cerveza vudweiser les encarga el diseño de una lata con capacidad de 1 litro, ¿ Cuales deben ser las dimensiones para minimizar la cantidad de metal ?

• Npar=2

• altura=h radio=r

• cromosoma=[h,r]



• Cada cromosoma tiene un costo, que es calculado mediante la evaluación de la función costo

• costo=f(cromosoma)

• En caso de la lata

• f(h,r)


Población Inicial

• El algoritmo genético empieza con una gran comuna de cromosomas conocidos como población inicial

• La población inicial tiene NIPOP cromosomas y es una matriz de NIPOP x NBITS llenada aleatoriamente con ceros y unos (en el caso de ag´s binarios) generados de:


Población Inicial• Matriz IPOP = round{random(NIPOP x NBITS)}

• Ejemplo: Sea la función f(x)=x2-1 en el rango de 0≤x≤6 calcular la población inicial, obtener su valor maximo

• Primero debemos estimar NBITS (el tamaño del cromosoma)

• ¿Cuantos bits necesitamos para poder representar el valor máximo de x (6)?

• respuesta = 3 bits


Población Inicial• ¿ Cuanto vale NIPOP ?

• ¿ Cuantos elementos se deben considerar de la población inicial ?

• ¿ Cuantos Cromosomas ?

• Se debe hacer una estimación

• Para probar con pocos cromosomas

• La experiencia dirá cuantos

• Jamas NIPOP ≤ NBITS


Población Inicial

# cromosomacromosomacromosoma

1 1 0 1

2 0 0 1

3 1 0 0

NIPOP 0 0 0

Paso 1


Población Inicial

# cromosomacromosomacromosoma x

1 1 0 1 5

2 0 0 1 1

3 1 0 0 4

NIPO

P0 0 0

Paso 2


Población Inicial# cromosomacromosomacromosoma x costo

1 1 0 1 5 24

2 0 0 1 1 0

3 1 0 0 4 15

NIPOP 0 0 0 0 -1

Paso 2


Mating Pool

• Debido a que la población inicial es muy grande para los procesos iterativos de los algoritmos genéticos, una gran parte de los cromosomas con los costos mas altos son descartados por el proceso de Mating Pool.

• El resultado serán los cromosomas mas aptos


Mating Pool

• Primero se rankean los cromosomas en base a los costos de los NIPOP, desde el mas bajo al mas alto.


Mating Pool# cromosomacromosomacromosoma x costo

1 1 0 1 5 24

2 1 0 0 4 15

3 0 0 1 1 0

NIPOP 0 0 0 0 -1


Mating Pool

• A continuación se hace el primer muestreo, seleccionando a los primeros NPOP mejores para cada iteración, los demás son descartados.

• NPOP = random( 1, NIPOP)

• se debe cumplir NPOP≤NIPOP


Mating Pool• Supongamos que para nuestro ejemplo:

• NPOP = random(1, 4) = 3

# cromosomacromosomacromosoma x costo

1 1 0 1 5 24

2 1 0 0 4 15

3 0 0 1 1 0NPOP=


Mating Pool• De los NPOP cromosomas en una

generación, solamente los mas altos NGOOD

mejores sobreviven para su cruce y los peores NBAD son descartados para hacer espacio para la descendencia

NGOOD=random( 1, NPOP)NBAD= NPOP - NGOOD


Mating Pool

# cromosomacromosomacromosoma x costo

1 1 0 1 5 24

2 1 0 0 4 15

3 0 0 1 1 0

NPOP

Suponiendo que NGOOD= 2

NGOOD

NBAD


Mating PoolPermitir que solo unos cuantos cromosomas sobrevivan a la siguiente generación limita la disponibilidad de genes en los descendientes

Almacenar demasiados cromosomas permitirá que algunos muy malos pasen a la siguiente generación


Selección de Pareja• Del total de los NGOOD cromosomas, se seleccionan parejas para

producir nuevos descendientes con la operación genética de cruce

• METODOS DE SELECCION DE PAREJA

• Pairing from top to bottom

• Random pairing

• Weigthed random pairing

• rank weighting

• cost weighting

• Tournament


Pairing from top to bottom


Random pairing


Random pairing


Random pairing

• Las parejas serían:

• cromosoma 1 con cromosoma 5




Weigthed random pairing



Tabla ejemplo



padre pareja

pivoteSi ∑ Pi > random entonces n


padre pareja

1



padre pareja

1



padre pareja

1



padre pareja

1 1,3

3 1,1

1 3,2

1

3

2




Ejemplo







Cruce


Tipos de Cruce


Cruce Sencillo


Cruce Sencillo


Cruce Sencillo


Cruce sencillo


Cruce Doble


Cruce Sencillo


Cruce doble




Mutación


Mutación


Generaciones siguientes


Convergencia


Convergencia


Caso Practico

• Calcular el valor mínimo

• -500≤x≤500

• NIPOP=20

• Selección de Pareja = Ruleta

• Sin Mutación

• 1 iteración


Documents

Unidad VI Algoritmos Genéticos (Continuación) - …rvazquez.org/Misitio/IntroduccionIA_files/Presentacion-10-2014.pdf · 6.4 El Algoritmo Genético y los operadores genéticos