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



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



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



5



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



6



Valor $ 40 50 45 30

Peso K 50 55 35 15

Ejemplo de una solución:


Valor de estos objetos: $50 + $45 = $95

Peso: 55 kilos + 35 kilos = 90 kilos

Representación: 0 1 1 0



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



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



9

Generación de la población inicial



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



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



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




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


13




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


14

Penalización



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



Poblacióninicial


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



Poblacióninicial


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


Penalización: 40 kilos * 2 pesos / kilo = $80

Nota: 2 pesos / kilo es el máximo valor/peso

17

Penalización



Poblacióninicial


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


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



Poblacióninicial


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


Valor: $80

Peso: 70 kilos

19

Selección ( Ruleta)



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





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





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





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





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




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




a

b

c

d

e

0 ,14

0 ,6 2 0 ,3 7

0 ,78

10


26




a

b

c

d

e

0 ,14

0 ,6 2 0 ,3 7

0 ,78

10


27




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





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





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





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






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


selecciónc 0 1 0 1b 0 0 1 1a 0 0 1 0e 1 0 0 1c 0 1 0 1

32






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


selecciónc 0 1 0 1b 0 0 1 1a 0 0 1 0e 1 0 0 1c 0 1 0 1

33

Cruce



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



0101 0011Padres

35

Cruce



0101 0011Padres

Punto de cruce=random{1,2,3} = 2

36

Cruce



01 00Padres


01 11

37

Cruce



01 00Padres


01 11

01 000111

38

Cruce



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



Poblaciónantes del

cruce

Random(0,1)<=0.25

Random{1,2,3}


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



Poblaciónantes del

cruce

Random(0,1)<=0.25

Random{1,2,3}


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



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




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





Poblacióndespués

de lasmutaciones


44

Mutación





Poblacióndespués

de lasmutaciones


45

Segunda generación



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



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


Valor: $95 ($80 pesos en la primera generación)

Peso: 90 kilos

47





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



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



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



Objetos seleccionados: 1, 3, 4

Valor: $115 (Antes $95 y $80)

Peso: 100 kilos

Población actual


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



… y el proceso continúa

Documents

Introducción a los algoritmos genéticos