introducción a los algoritmos genéticos
DESCRIPTION
Visualización de un algoritmo genético aplicado al problema de la mochila 0/1TRANSCRIPT
![Page 1: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/1.jpg)
1
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Algoritmos genéticos
L. A. Hernández
![Page 2: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/2.jpg)
2
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Inspirados en la teoría de la evolución
Selección
Cruce
Mutación
![Page 3: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/3.jpg)
3
Usos
Ponencias de CIIC2007:• Diseño de circuitos lógicos secuenciales• Herramienta para la ubicación de publicidad exterior
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
![Page 4: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/4.jpg)
4
Problema de la mochila 0/1
Capacidad de la mochila: 100 kilosObjeto 1 2 3 4
Valor $ 40 50 45 30
Peso K 50 55 35 15
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
![Page 5: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/5.jpg)
5
Problema de la mochila 0/1
Capacidad de la mochila: 100 kilosObjeto 1 2 3 4
Valor $ 40 50 45 30
Peso K 50 55 35 15
Ejemplo de una solución:
Objetos seleccionados: 2 y 3
Valor de estos objetos: $50 + $45 = $95
Peso: 55 kilos + 35 kilos = 90 kilos
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
![Page 6: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/6.jpg)
6
Problema de la mochila 0/1
Capacidad de la mochila: 100 kilosObjeto 1 2 3 4
Valor $ 40 50 45 30
Peso K 50 55 35 15
Ejemplo de una solución:
Objetos seleccionados: 2 y 3
Valor de estos objetos: $50 + $45 = $95
Peso: 55 kilos + 35 kilos = 90 kilos
Representación: 0 1 1 0
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
![Page 7: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/7.jpg)
7
Valor / peso
Objeto 1 2 3 4Valor $ 40 50 45 30Peso K 50 55 35 15Valor/Peso 0.80 0.91 1.29 2.00
50 / 55 = 0.91
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
![Page 8: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/8.jpg)
8
Valor / peso
Objeto 1 2 3 4Valor $ 40 50 45 30Peso K 50 55 35 15Valor/Peso 0.80 0.91 1.29 2.00
Máximo valor / peso: 2
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
![Page 9: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/9.jpg)
9
Generación de la población inicial
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
a 0 0 1 0b 0 0 1 1c 0 1 0 1d 1 1 1 0e 1 0 0 1
![Page 10: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/10.jpg)
10
Generación de la población inicial
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
a 0 0 1 0b 0 0 1 1c 0 1 0 1d 1 1 1 0e 1 0 0 1
Cromosoma
Gen
![Page 11: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/11.jpg)
11
Evaluación de la población inicial
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblacióninicial
Valor
a 0 0 1 0 45b 0 0 1 1 75c 0 1 0 1 80d 1 1 1 0 135e 1 0 0 1 70
Objeto 1 2 3 4
Valor $ 40 50 45 30
Peso K 50 55 35 15
Capacidad de la mochila: 100 kilos
![Page 12: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/12.jpg)
12
Evaluación de la población inicial
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblacióninicial
Valor Peso
a 0 0 1 0 45 35b 0 0 1 1 75 50c 0 1 0 1 80 70d 1 1 1 0 135 140e 1 0 0 1 70 65
Objeto 1 2 3 4
Valor $ 40 50 45 30
Peso K 50 55 35 15
Capacidad de la mochila: 100 kilos
![Page 13: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/13.jpg)
13
Evaluación de la población inicial
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblacióninicial
Valor Peso Factible
a 0 0 1 0 45 35 Sb 0 0 1 1 75 50 Sc 0 1 0 1 80 70 Sd 1 1 1 0 135 140 Ne 1 0 0 1 70 65 S
Objeto 1 2 3 4
Valor $ 40 50 45 30
Peso K 50 55 35 15
Capacidad de la mochila: 100 kilos
![Page 14: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/14.jpg)
14
Penalización
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblacióninicial
Valor Peso Factible Eval
a 0 0 1 0 45 35 S 45b 0 0 1 1 75 50 S 75c 0 1 0 1 80 70 S 80d 1 1 1 0 135 140 N 55e 1 0 0 1 70 65 S 70
![Page 15: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/15.jpg)
15
Penalización
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblacióninicial
Valor Peso Factible Eval
a 0 0 1 0 45 35 S 45b 0 0 1 1 75 50 S 75c 0 1 0 1 80 70 S 80d 1 1 1 0 135 140 N 55e 1 0 0 1 70 65 S 70
Exceso de peso: 140 kilos – 100 kilos = 40 kilos
![Page 16: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/16.jpg)
16
Penalización
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblacióninicial
Valor Peso Factible Eval
a 0 0 1 0 45 35 S 45b 0 0 1 1 75 50 S 75c 0 1 0 1 80 70 S 80d 1 1 1 0 135 140 N 55e 1 0 0 1 70 65 S 70
Exceso de peso: 140 kilos – 100 kilos = 40 kilos
Penalización: 40 kilos * 2 pesos / kilo = $80
Nota: 2 pesos / kilo es el máximo valor/peso
![Page 17: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/17.jpg)
17
Penalización
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblacióninicial
Valor Peso Factible Eval
a 0 0 1 0 45 35 S 45b 0 0 1 1 75 50 S 75c 0 1 0 1 80 70 S 80d 1 1 1 0 135 140 N 55e 1 0 0 1 70 65 S 70
Exceso de peso: 140 kilos – 100 kilos = 40 kilos
Penalización: 40 kilos * 2 pesos / kilo = $80
Evaluación: $135 - $80 = $55
Nota: 2 pesos / kilo es el máximo valor/peso
![Page 18: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/18.jpg)
18
Mejor cromosoma en la población inicial
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblacióninicial
Valor Peso Factible Eval
a 0 0 1 0 45 35 S 45b 0 0 1 1 75 50 S 75c 0 1 0 1 80 70 S 80d 1 1 1 0 135 140 N 55e 1 0 0 1 70 65 S 70
Objetos seleccionados: 2 y 4
Valor: $80
Peso: 70 kilos
![Page 19: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/19.jpg)
19
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes de laselección
Eval p
a 0 0 1 0 45 0.14b 0 0 1 1 75 0.23c 0 1 0 1 80 0.25d 1 1 1 0 55 0.16e 1 0 0 1 70 0.22
Total: 325 1.00
0.25 = 80 / 325
![Page 20: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/20.jpg)
20
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes de laselección
Eval p
a 0 0 1 0 45 0.14b 0 0 1 1 75 0.23c 0 1 0 1 80 0.25d 1 1 1 0 55 0.16e 1 0 0 1 70 0.22
Total: 325 1.00
0.16 = 55 / 325
![Page 21: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/21.jpg)
21
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes de laselección
Eval p q
a 0 0 1 0 45 0.14 0.14b 0 0 1 1 75 0.23c 0 1 0 1 80 0.25
d 1 1 1 0 55 0.16e 1 0 0 1 70 0.22
Total: 325 1.00
![Page 22: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/22.jpg)
22
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes de laselección
Eval p q
a 0 0 1 0 45 0.14 0.14b 0 0 1 1 75 0.23 0.37c 0 1 0 1 80 0.25
d 1 1 1 0 55 0.16e 1 0 0 1 70 0.22
Total: 325 1.00
0.37 = 0.14 + 0.23
![Page 23: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/23.jpg)
23
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes de laselección
Eval p q
a 0 0 1 0 45 0.14 0.14b 0 0 1 1 75 0.23 0.37c 0 1 0 1 80 0.25 0.62d 1 1 1 0 55 0.16 0.78e 1 0 0 1 70 0.22 1.00
Total: 325 1.00
0.62 = 0.37 + 0.25
![Page 24: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/24.jpg)
24
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
a
b
c
d
e
0 ,14
0 ,6 20 ,3 7
0 ,7 8
10
Población Eval qa 0 0 1 0 45 0.14b 0 0 1 1 75 0.37c 0 1 0 1 80 0.62d 1 1 1 0 55 0.78e 1 0 0 1 70 1.00
![Page 25: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/25.jpg)
25
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
a
b
c
d
e
0 ,14
0 ,6 2 0 ,3 7
0 ,78
10
Población Eval qa 0 0 1 0 45 0.14b 0 0 1 1 75 0.37c 0 1 0 1 80 0.62d 1 1 1 0 55 0.78e 1 0 0 1 70 1.00
![Page 26: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/26.jpg)
26
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
a
b
c
d
e
0 ,14
0 ,6 2 0 ,3 7
0 ,78
10
Población Eval qa 0 0 1 0 45 0.14b 0 0 1 1 75 0.37c 0 1 0 1 80 0.62d 1 1 1 0 55 0.78e 1 0 0 1 70 1.00
![Page 27: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/27.jpg)
27
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Población q Random(0,1)
a 0 0 1 0 0.14 0.41b 0 0 1 1 0.37c 0 1 0 1 0.62d 1 1 1 0 0.78e 1 0 0 1 1.00
Seleccionadosc 0 1 0 1
a
b
c
d
e
0 ,1 4
0 ,6 20 ,3 7
0 ,7 8
10
0 ,4 1
![Page 28: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/28.jpg)
28
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Población q Random(0,1)
a 0 0 1 0 0.14 0.41b 0 0 1 1 0.37 0.24c 0 1 0 1 0.62d 1 1 1 0 0.78e 1 0 0 1 1.00
Seleccionadosc 0 1 0 1b 0 0 1 1
a
b
c
d
e
0 ,1 4
0 ,6 20 ,3 7
0 ,78
10
0 ,2 4
![Page 29: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/29.jpg)
29
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Población q Random(0,1)
a 0 0 1 0 0.14 0.41b 0 0 1 1 0.37 0.24c 0 1 0 1 0.62 0.12d 1 1 1 0 0.78 0.90e 1 0 0 1 1.00 0.45
Seleccionadosc 0 1 0 1b 0 0 1 1a 0 0 1 0e 1 0 0 1c 0 1 0 1
a
b
c
d
e
0 ,1 4
0 ,6 20 ,3 7
0 ,7 8
10
![Page 30: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/30.jpg)
30
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes de laselección
Eval p q Random(0,1)
a 0 0 1 0 45 0.14 0.14 0.41b 0 0 1 1 75 0.23 0.37 0.24c 0 1 0 1 80 0.25 0.62 0.12d 1 1 1 0 55 0.16 0.78 0.90e 1 0 0 1 70 0.22 1.00 0.45
Poblacióndespués de la
selecciónc 0 1 0 1b 0 0 1 1a 0 0 1 0e 1 0 0 1c 0 1 0 1
![Page 31: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/31.jpg)
31
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes de laselección
Eval p q Random(0,1)
a 0 0 1 0 45 0.14 0.14 0.41b 0 0 1 1 75 0.23 0.37 0.24c 0 1 0 1 80 0.25 0.62 0.12d 1 1 1 0 55 0.16 0.78 0.90e 1 0 0 1 70 0.22 1.00 0.45
Poblacióndespués de la
selecciónc 0 1 0 1b 0 0 1 1a 0 0 1 0e 1 0 0 1c 0 1 0 1
![Page 32: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/32.jpg)
32
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes de laselección
Eval p q Random(0,1)
a 0 0 1 0 45 0.14 0.14 0.41b 0 0 1 1 75 0.23 0.37 0.24c 0 1 0 1 80 0.25 0.62 0.12d 1 1 1 0 55 0.16 0.78 0.90e 1 0 0 1 70 0.22 1.00 0.45
Poblacióndespués de la
selecciónc 0 1 0 1b 0 0 1 1a 0 0 1 0e 1 0 0 1c 0 1 0 1
![Page 33: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/33.jpg)
33
Cruce
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes del
cruce
Random(0,1)<=0.25
0 1 0 1 S0 0 1 1 S0 0 1 0 S1 0 0 1 N0 1 0 1 S
10
S e c ru za
N o s e c ru za
![Page 34: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/34.jpg)
34
Cruce
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
0101 0011Padres
![Page 35: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/35.jpg)
35
Cruce
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
0101 0011Padres
Punto de cruce=random{1,2,3} = 2
![Page 36: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/36.jpg)
36
Cruce
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
01 00Padres
Punto de cruce=random{1,2,3} = 2
01 11
![Page 37: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/37.jpg)
37
Cruce
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
01 00Padres
Punto de cruce=random{1,2,3} = 2
01 11
01 000111
![Page 38: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/38.jpg)
38
Cruce
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes del
cruce
Random(0,1)<=0.25
Random{1,2,3}
Poblacióndespuésdel cruce
0 1 0 1 S 2 0 1 1 10 0 1 1 S 0 0 0 10 0 1 0 S 3 0 0 1 11 0 0 1 N 1 0 0 10 1 0 1 S 0 1 0 0
![Page 39: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/39.jpg)
39
Cruce
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes del
cruce
Random(0,1)<=0.25
Random{1,2,3}
Poblacióndespuésdel cruce
0 1 0 1 S 2 0 1 1 10 0 1 1 S 0 0 0 10 0 1 0 S 3 0 0 1 11 0 0 1 N 1 0 0 10 1 0 1 S 0 1 0 0
![Page 40: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/40.jpg)
40
Cruce
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes del
cruce
Random(0,1)<=0.25
Random{1,2,3}
Poblacióndespuésdel cruce
0 1 0 1 S 2 0 1 1 10 0 1 1 S 0 0 0 10 0 1 0 S 3 0 0 1 11 0 0 1 N 1 0 0 10 1 0 1 S 0 1 0 0
![Page 41: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/41.jpg)
41
Mutación
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes de lasmutaciones
Random(0,1)<=0.01
0 1 1 1 S N S N0 0 0 1 N N N N0 0 1 1 N S S N1 0 0 1 N N N N0 1 0 0 N N S N
M u ta
N o m u ta
![Page 42: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/42.jpg)
42
Mutación
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes de lasmutaciones
Random(0,1)<=0.01(para cada gen)
Poblacióndespués
de lasmutaciones
0 1 1 1 S N S N 1 1 0 10 0 0 1 N N N N 0 0 0 10 0 1 1 N S S N 0 1 0 11 0 0 1 N N N N 1 0 0 10 1 0 0 N N S N 0 1 1 0
![Page 43: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/43.jpg)
43
Mutación
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes de lasmutaciones
Random(0,1)<=0.01(para cada gen)
Poblacióndespués
de lasmutaciones
0 1 1 1 S N S N 1 1 0 10 0 0 1 N N N N 0 0 0 10 0 1 1 N S S N 0 1 0 11 0 0 1 N N N N 1 0 0 10 1 0 0 N N S N 0 1 1 0
![Page 44: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/44.jpg)
44
Mutación
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes de lasmutaciones
Random(0,1)<=0.01(para cada gen)
Poblacióndespués
de lasmutaciones
0 1 1 1 S N S N 1 1 0 10 0 0 1 N N N N 0 0 0 10 0 1 1 N S S N 0 1 0 11 0 0 1 N N N N 1 0 0 10 1 0 0 N N S N 0 1 1 0
![Page 45: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/45.jpg)
45
Segunda generación
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
1 1 0 1
0 0 0 1
0 1 0 1
1 0 0 1
0 1 1 0
![Page 46: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/46.jpg)
46
Evaluación de la segunda generación
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Población Valor Peso Factible Eval1 1 0 1 120 120 N 800 0 0 1 30 15 S 300 1 0 1 80 70 S 801 0 0 1 70 65 S 700 1 1 0 95 90 S 95
Objetos seleccionados: 2 y 3
Valor: $95 ($80 pesos en la primera generación)
Peso: 90 kilos
![Page 47: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/47.jpg)
47
Selección ( Ruleta)
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes de laselección
Eval p q Random
(0,1)a 1 1 0 1 80 0.23 0.23 0.04b 0 0 0 1 30 0.08 0.31 0.70c 0 1 0 1 80 0.23 0.54 0.16d 1 0 0 1 70 0.19 0.73 0.28e 0 1 1 0 95 0.27 1.00 0.75
355 1.00
Poblacióndespués de la selección
a 1 1 0 1d 1 0 0 1a 1 1 0 1b 0 0 0 1e 0 1 1 0
![Page 48: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/48.jpg)
48
Cruce
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes del
cruce
Random(0,1)<=0.25
Random(1,3)
Poblacióndespués
del crucea 1 1 0 1 S 1 1 0 0 1d 1 0 0 1 S 1 1 0 1a 1 1 0 1 N 1 1 0 1b 0 0 0 1 S 2 0 0 1 0e 0 1 1 0 S 0 1 0 1
![Page 49: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/49.jpg)
49
Mutación
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Poblaciónantes de lamutación
Random(0,1)<=0.01 Población con
mutaciones
1 0 0 1 N N S N 1 0 1 1
1 1 0 1 N N N N 1 1 0 1
1 1 0 1 N N N N 1 1 0 1
0 0 1 0 S N N N 1 0 1 0
0 1 0 1 N N N N 0 1 0 1
![Page 50: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/50.jpg)
50
Tercera generación
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Objetos seleccionados: 1, 3, 4
Valor: $115 (Antes $95 y $80)
Peso: 100 kilos
Población actual
Valor Peso Factible Eval
1 0 1 1 115 100 S 1151 1 0 1 120 120 N 801 1 0 1 120 120 N 801 0 1 0 85 85 S 850 1 0 1 80 70 S 80
![Page 51: Introducción a los algoritmos genéticos](https://reader030.vdocumento.com/reader030/viewer/2022020200/568c0f051a28ab955a929fec/html5/thumbnails/51.jpg)
51
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
… y el proceso continúa