unidad vi algoritmos genéticos (continuación) -...
Post on 03-Oct-2018
234 Views
Preview:
TRANSCRIPT
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
viernes 7 de noviembre de 14
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
viernes 7 de noviembre de 14
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
viernes 7 de noviembre de 14
Análisis, Diseño e Implementación de un Algoritmo Genético.
• 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]
viernes 7 de noviembre de 14
Análisis, Diseño e Implementación de un Algoritmo Genético.
• 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)
viernes 7 de noviembre de 14
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:
viernes 7 de noviembre de 14
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
viernes 7 de noviembre de 14
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
viernes 7 de noviembre de 14
Población Inicial
# cromosomacromosomacromosoma
1 1 0 1
2 0 0 1
3 1 0 0
NIPOP 0 0 0
Paso 1
viernes 7 de noviembre de 14
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
viernes 7 de noviembre de 14
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
viernes 7 de noviembre de 14
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
viernes 7 de noviembre de 14
Mating Pool
• Primero se rankean los cromosomas en base a los costos de los NIPOP, desde el mas bajo al mas alto.
viernes 7 de noviembre de 14
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
viernes 7 de noviembre de 14
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
viernes 7 de noviembre de 14
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=
viernes 7 de noviembre de 14
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
viernes 7 de noviembre de 14
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
viernes 7 de noviembre de 14
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
viernes 7 de noviembre de 14
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
viernes 7 de noviembre de 14
Random pairing
• Las parejas serían:
• cromosoma 1 con cromosoma 5
• cromosoma 1 con cromosoma 3
• cromosoma 5 con cromosoma 3
viernes 7 de noviembre de 14
top related