Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple...
Transcript of Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple...
![Page 1: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/1.jpg)
Algoritmo Genético Simple
Fabio González, Ph.D.Departamento de Ingeniería de Sistemas e Industrial
Universidad Nacional de Colombia
![Page 2: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/2.jpg)
Genotipo y fenotipo
![Page 3: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/3.jpg)
Espacio de Búsqueda yEspacio del Problema
punto en elpunto en elespacio delespacio delproblemaproblema
estructuraestructuracomputacional quecomputacional querepresenta el puntorepresenta el punto
(cromosoma)(cromosoma)
![Page 4: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/4.jpg)
Espacio de Búsqueda yEspacio del Problema
![Page 5: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/5.jpg)
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
![Page 6: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/6.jpg)
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
![Page 7: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/7.jpg)
Ciclo Generacional de un GA
![Page 8: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/8.jpg)
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
![Page 9: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/9.jpg)
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)
![Page 10: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/10.jpg)
Representacióncromosoma
gen alelo
selección
cruce
mutación
población
![Page 11: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/11.jpg)
cruce de un solo punto
Operadores GenOperadores Genééticos ticos ((ccruceruce))
cruce de dos puntos
+ padre 2
hijo 1 padre 1
hijo 2
![Page 12: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/12.jpg)
Operadores GenOperadores Genééticosticos((mutacimutacióónn))
mutación de varios puntos
mutación global
mutación de un punto
![Page 13: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/13.jpg)
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)
![Page 14: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/14.jpg)
• 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)
![Page 15: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/15.jpg)
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
![Page 16: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/16.jpg)
Selección por ruleta (3)
![Page 17: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/17.jpg)
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
![Page 18: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/18.jpg)
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
![Page 19: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/19.jpg)
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)
![Page 20: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/20.jpg)
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
![Page 21: Algoritmo Genético Simplefgonza/courses/2004-I/CompEvol/introGA.pdf · Algoritmo Genético Simple Fabio González, Ph.D. Departamento de Ingeniería de Sistemas e Industrial Universidad](https://reader034.fdocumento.com/reader034/viewer/2022042209/5ead4351f39be254692b807d/html5/thumbnails/21.jpg)
Linksn http://cs.felk.cvut.cz/~xobitko/ga/example_f.html
n http://alife.fusebox.com/morph_lab.html