Introducción a los algoritmos genéticos
-
Upload
leonardo-hernandez-rodriguez -
Category
Documents
-
view
235 -
download
4
description
Transcript of Introducción a los algoritmos genéticos
1
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
Algoritmos genéticos
L. A. Hernández
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
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.
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.
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.
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.
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.
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.
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
34
Cruce
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
0101 0011Padres
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
51
Prog. de Ing. de Sistemas y Comp.Algoritmos Genéticos
Leonardo A. Hernández R.
… y el proceso continúa