Algoritmo Genético Simple
Fabio González, Ph.D.Departamento de Ingeniería de Sistemas e Industrial
Universidad Nacional de Colombia
Genotipo y fenotipo
Espacio de Búsqueda yEspacio del Problema
punto en elpunto en elespacio delespacio delproblemaproblema
estructuraestructuracomputacional quecomputacional querepresenta el puntorepresenta el punto
(cromosoma)(cromosoma)
Espacio de Búsqueda yEspacio del Problema
cadenas
(cromosomas)
solución
del
problema
valor
de la
solución
codificación
decodificación
decodificación
Genotipo Fenotipo
ambiente
función
objetivo
Adaptabilidad
Adaptabilidad en la naturalezay en los AGs
Problema
asignación deadaptabilidad
selección
replicación
recombinacióncruce
mutaciónbúsquedagenética
búsquedagenética
codificación desoluciones
función objetivo
operadores genéticos
conocimientoespecífico
Solución
Solución de Problemas conAEs
Ciclo Generacional de un GA
Terminar
Inicializar
población
Crear descendientes a
través de variación
aleatoria
Evaluar la adaptabilidad de
cada solución candidata
Aplicar selección
NO
SI
Algoritmo Genético
selección
cruce
mutación
selección
cruce
mutación
Poblaciónno
sobrelapada
Poblaciónsobrelapada
AG generacional
Política de Reemplazo
AG de estado estable (steady state)
Representacióncromosoma
gen alelo
selección
cruce
mutación
población
cruce de un solo punto
Operadores GenOperadores Genééticos ticos ((ccruceruce))
cruce de dos puntos
+ padre 2
hijo 1 padre 1
hijo 2
Operadores GenOperadores Genééticosticos((mutacimutacióónn))
mutación de varios puntos
mutación global
mutación de un punto
A cada solución (cromosoma) se leasigna un valor de adaptabilidaddependiendo de que tan bueno es elcromosoma solucionando el problema.
F: Cromosomas Æ R+
x Æ F(x)
Evaluación de la adaptabilidad(fitness)
• Imagine una ruleta donde se han ubicado todoslos cromosomas en la población, cada uno tiene sulugar de acuerdo con su función de adaptabilidad
Los miembros más aptos tienen una tajadamás grande
Para escoger un cromosoma, se gira la ruleta y seescoge el cromosoma del punto en donde se detenga
cromosoma1cromosoma2cromosoma3cromosoma4
Selección por ruleta (1)
Selección por ruleta (2)
Tipos de Selección
® Ruleta
® Elitista® Estado estable® Escalafón
…
POBLACION
ORIGINAL
POBLACION
SELECCIONADA
cromosoma1cromosoma2cromosoma3cromosoma4
Evaluaciónpor la función
deadaptabilidad
f Selección
Selección por ruleta (3)
maximizar la función f(x)= x2, donde x puede variarentre 0 y 31.
f(x)=x_
0
200
400
600
800
1000
1200
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Series2
Ejemplo
Planteamienton Representación:
n Cadena de 5 bits
n Función de adaptación:n f(a4…a0) = (24a4+…+20a0)2
n Operadores genéticos:n Mutación de un punton Cruce de un punto
n Selección:n Ruleta
n Política de reemplazo:n AG generacional
No. cadena
población inicial
x f(x) pselecti cantidad esperada
cantidad real
1 0 1 1 0 1 13 169 0.14 0.58 1
2 1 1 0 0 0 24 576 0.49 1.97 2
3 0 1 0 0 0 8 64 0.06 0.22 0
4 1 0 0 1 1 19 361 0.31 1.23 1
suma 1170 1.00 4.00 4.0
prom 293 0.25 1.00 1.0
max 576 0.49 1.97 2.0
Ejemplo a mano (1)
Ejemplo a mano (2)
No.cadena
Cadena pareja NuevaPoblac
x F(x)
1 0110|1 2 01100 12 144
2 1100|0 1 11001 25 625
3 11|000 4 11011 27 729
4 10|011 3 10000 16 256
Linksn http://cs.felk.cvut.cz/~xobitko/ga/example_f.html
n http://alife.fusebox.com/morph_lab.html
Top Related