Algoritmos Geneticos

Algoritmos Geneticos

Algoritmos Evolutivos y Memeticos Curso de Postgrado – UC3M – Junio 16,17,18 - 2004

AGs repaso rapido
• Desarrollados en los EEUU en los 70s • primeros promotores J. Holland, K. DeJong, D. Goldberg • Tipicamente aplicados a optimisacion discreta • Propiedades atribuidas:
– no son muy rapidos – buenas heuristicas para problemas combinatoriales

• Propiedadesespeciales:
– hacen incapie en combinar buenas soluciones de los padres por medio del crossover – muchas variantes: dependen de los operadores de seleccion de padres y de generacion siguiente
Algoritmos Evolutivos y Memeticos Curso de Postgrado – UC3M – Junio 16,17,18 - 2004

Algoritmos Geneticos
• Los algoritmos originales de J. Hollan se conocen ahora como los Algoritmos Geneticos Simples • Otrosalgoritmos geneticos usan distintas:
– – – – Representaciones Mutaciones Crossovers Mecanismos de seleccion

Algoritmos Evolutivos y Memeticos Curso de Postgrado – UC3M – Junio 16,17,18 - 2004

Tableau tecnica de los AGS
Representacion Recombinacion Mutacion Seleccion de padres Seleccion de sobrevivientes Especialidad cadenas binarias N-point o uniforme “Bitwise bit-flipping” conprobabilidad fija Proporcional al fitness Los hijos reemplazan a los padres Enfasis en el crossover

Algoritmos Evolutivos y Memeticos Curso de Postgrado – UC3M – Junio 16,17,18 - 2004

Representacion
Espacion fenotipico Codificacion (representacion) Espacion genotipico = {0,1}L 10010001 10010010 010001001 011101001 Decodificacion (representacion inversa)

Algoritmos Evolutivos y Memeticos Curso dePostgrado – UC3M – Junio 16,17,18 - 2004

Ciclo de reproduccion
1. Seleccionar padres para el conjunto reproductivo (mating pool, |mating pool| = tamanio de la poblacion) 2. mezclar el mating pool 3. Para cada par consecutivo del mating pool aplicar crossover con probabilidad Pc, sino copiar padres 4. Para cada nuevo individuo aplicar mutacion (bit-flip con probabilidad pm independiente encada bit) 5. Reemplazar toda la poblacion con los nuevos individuos
Algoritmos Evolutivos y Memeticos Curso de Postgrado – UC3M – Junio 16,17,18 - 2004

Operadores del AGs: 1-point crossover
• • • • Seleccionar un punto al azar en ambos padres Cortar los padres en este punto Crear hijos intercambiando las colas Pc tipicamente en el rango (0.6, 0.9)

Padres

Hijos
Algoritmos Evolutivos yMemeticos Curso de Postgrado – UC3M – Junio 16,17,18 - 2004

Operadores del AGs: mutacion
• Alterar cada gene con una probabilidad independiente pm • pm se llama la probabilidad de mutacion
– Tipicamente entre [1/pop_size, 1/tamanio_cromosoma]
Padres

Hijos
Algoritmos Evolutivos y Memeticos Curso de Postgrado – UC3M – Junio 16,17,18 - 2004

Operadores del AGs: Seleccion
• Ideaprincipal:los mejores individuos tienen mas chances – Chaces proporcionales al fitness – Implementacion: tecnica de la ruleta – Asignar a cada individuo una parte de la ruleta proporcional a su fitness » rotar la ruleta n veces para obtener n individuos
1/6 = 17%

A
3/6 = 50%

B

fitness(A) = 3 fitness(B) = 1 fitness(C) = 2

C

2/6 = 33%

Algoritmos Evolutivos y Memeticos Curso de Postgrado –UC3M – Junio 16,17,18 - 2004

Un ejemplo de Goldberg ‘89 (1)
• Problema simple: max x2 sobre {0,1,…,31} • Enfoque AG:
– – – – – Representacion: codigo binario, 01101 ↔ 13 Tamanio poblacion: 4 1-point xover, bitwise mutacion Seleccion de ruleta Inicializacion al azar

• Ejecutamos a mano una generacion:
Algoritmos Evolutivos y Memeticos Curso de Postgrado – UC3M – Junio 16,17,18 - 2004x2 ejemplo: seleccion

Algoritmos Evolutivos y Memeticos Curso de Postgrado – UC3M – Junio 16,17,18 - 2004

X2 ejemplo: crossover

Algoritmos Evolutivos y Memeticos Curso de Postgrado – UC3M – Junio 16,17,18 - 2004

X2 ejemplo: mutacion

Algoritmos Evolutivos y Memeticos Curso de Postgrado – UC3M – Junio 16,17,18 - 2004

The simple GA
• Ha sido ampliamente estudiado
– aun se lo...