35
Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores 7. Ejemplo

Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

  • Upload
    others

  • View
    6

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

Algoritmos genéticos

1. Introducción2. Esquema básico3. Codificación4. Evaluación5. Selección6. Operadores7. Ejemplo

Page 2: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

2

Introducción

Propuestos por Holland, mediados 70, computación evolutivaPopularizados por Goldberg, mediados 80, solución de problemas del mundo realInspirados en el modelo de evolución biológica sexualAplicables a problemas de búsqueda y optimización complejos

Page 3: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

3

Aproximación a la evolución biológica

Método de búsqueda y optimización inspirados en la evolución biológicaPosibles soluciones: poblaciónSelección de los individuos más aptosGeneración de nuevos candidatos: reproducción sexual

Recombinación (cruce) Mutación

Page 4: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

4

Esquema básico

función ALGORITMO-GENÉTICO(poblaciónInicial) returns una poblaciónentrada: poblaciónInicial, una poblaciónstatic: población(.), un array de población

begint 0población(t) poblaciónInicialEVALUAR(población(t))while (not condiciónTerminación) do

t t +1población1 SELECCIONAR(población(t-1))población2 CRUZAR(población1)población3 MUTAR(población2)población(t) REMPLAZAR(población3)

endreturn(población(t))end

Page 5: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

5

Codificación

Individuo: cromosomaCromosoma: cadena de caracteres

En principio, cualquier representación es válida

Codificación óptima: alfabeto binario (teorema de los esquemas)Codificación habitual: cadena de bits

Page 6: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

6

Ejemplos de codificaciónmaximización función

f(x)=1-x2, parábola invertida con máximo en x=0Único parámetro o atributo: variable xCodificamos el valor de la variable mediante un byte[0,255], ajustado al intervalo real [-1,1], donde queremos hallar el máximo de la función

65

41

145

148

Descodi-ficación

-0,49001000101

-0,67800101001

0,13710010001

0,16110010100

Valor real

Valor binario

2/255*x -1= y

Page 7: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

7

8-reinas

Atributo: posición de una dama en una columna (3 bits) Cromosoma: secuencia de atributos, 24 bits

100101111110011000001010

Col. 8Col. 7Col. 6 Col. 5Col. 4Col. 3Col. 2Col.1

Page 8: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

8

Regla de los bloques de construcción

La codificación es clave en la resolución del problemaHeurística: parámetros relacionados ente sí (genes) deben de estar cercanos en el cromosomaGran flexibilidad

Cromosomas bi, tridimensionalesLongitud variable

Page 9: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

9

Evaluación

En esta etapa hay que cuantificar la calidad de los individuos de la poblaciónGeneralmente

Decodificar el cromosomaCalidad de la soluciónEvaluación mediante función fitness o aptitud

Page 10: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

10

Ejemplos de funciones de aptitud

Para f(x)=1-x2, la función de aptitud es la misma

Para 8-reinas: número total de pares de damas no amenazadas

En cualquier solución: 7+6+5+4+3+2+1=28

-0,490

-0,678

0,137

0,161

Valor real

65

41

145

148

Descodi-ficación

.76001000101

.54000101001

.98110010001

0.97410010100

AptitudValor binario

Page 11: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

11

Selección

Selección de los elementos que se reproducenA partir de la función de aptitudVarios métodos

Rueda de ruleta Basado en el rangoSelección de torneo

Cambio de generaciónManteniendo el tamaño de la poblaciónAumentando el tamaño de la población

Page 12: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

12

Rueda de ruleta

Se asigna a cada individuo la probabilidad:

Si algún individuo domina la población, se escala o normaliza

Se elijen parejas aleatorias de individuos de acuerdo a su probabilidad

Inconveniente: los individuos con más aptitud tiende a dominar la población en pocas generaciones

∑ ∈

=poblacióny

yaptitudxaptitudx

)()()Pr(

1

23

4

Page 13: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

13

Rueda

0.233

0.166

0.301

0.299

Probabilidad

0.760

0.540

0.981

0.974

Aptitud

-0,490

-0,678

0,137

0,161

Valor real

65

41

145

148

Descodi-ficación

1.00001000101

0.76600101001

0.60010010001

0.29910010100

Probabilidad acumulada

Valor binario

1

23

4

Page 14: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

14

Basado en el rango

Se ordena la población por orden creciente de aptitudSe eliminan los M primeros (menor aptitud)Se eligen de forma aleatoria, con probabilidad dada por el rango, pares de individuos y sus descendientes se añaden a la población

Page 15: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

15

Torneo

Se seleccionan dos individuos aleatoriamenteSe elije el más apto con una probabilidad P y el menos apto con una probabilidad (1-P)Introduce más diversidad en la población

Page 16: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

16

Cambio de generación

Manteniendo el tamaño de la población intermedia

Reemplazar padres por hijosReemplazar un par de individuos elegidos aleatoriamente por los hijosOtros

Aumentando el tamaño de la población intermedia

Crear población temporal con padres e hijos, seleccionando los mejoresDados n padres generar m (m>n) hijos y de ellos seleccionar los n mejores

Page 17: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

17

Operador de cruce (crossover)

Principal operador genéticoSimula el intercambio de material genético o genesSe aplica con probabilidad pc a individuos seleccionadosCruce ideal: recombina buenos bloques de construcción de sus progenitoresOperadores

Cruce de n-puntosCruce multipuntoCruce especializado

Page 18: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

18

Cruce de un punto

Seleccionar aleatoriamente una posición en el cromosomaIntercambiar el final del cromosoma a partir de dicho punto

0

0

0

0

1

0

0

1

01011101hijo 2

00101001hijo 1

00101101madre

01011001padre

Page 19: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

19

Cruce de dos puntos

0

0

0

0

0

1

0

1

01011101hijo 2

00101001hijo 1

00101101madre

01011001padre

Page 20: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

20

Otros operadores de cruce

Multipunto o uniforme Cada bit se hereda de un padre aleatoriamente

Operadores especializadosEn aquellos problemas donde un cruce aleatorio puede generar individuos no válidos

Page 21: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

21

Ejemplo cruce 1 punto 8 reinas

La selección aleatoria del punto de cruce no es interesante

Genera individuos válidosLa mezcla de bloques –genes- no parece asimilable a un operador del problema real

Seleccionar aleatoriamente el gen a partir del que se hace el reemplazo

Seleccionar aleatoriamente un entero 1 y 7 (número de genes)Equivale a intercambiar columnas contiguas entre tableros padres

Page 22: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

22

Ejemplo cruce 1 punto 8 reinas

010000011110110001111101

Col. 8Col. 7Col. 6 Col. 5Col. 4Col. 3Col. 2Col.1

110100011010011101111011

Col. 8Col. 7Col. 6 Col. 5Col. 4Col. 3Col. 2Col.1

110100011010011001111101

Col. 8Col. 7Col. 6 Col. 5Col. 4Col. 3Col. 2Col.1

010000011110110101111011

Col. 8Col. 7Col. 6 Col. 5Col. 4Col. 3Col. 2Col.1

Page 23: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

23

Ejemplo cruce 1 punto 8 reinas

¤

¤

¤

¤

¤

¤

¤

¤

¤

¤

¤

¤¤

¤

¤

¤

¤

¤

¤

¤¤

¤

¤

¤

¤

¤

¤

¤

¤

¤

¤

¤

padres

hijos

Aptitud:20

Aptitud:25

Aptitud:26

Aptitud:27

Page 24: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

24

Operador de Mutación

En la evolución Las mutaciones son poco frecuentesEn la mayor parte de los casos letalesEn promedio, contribuyen a la diversidad genética

En los algoritmos genéticos:Se simula cambiando aleatoriamente el valor de un bitSe aplica con probabilidad baja (10-3 o menor) a cada bitde un nuevo individuo, habitualmente junto al cruceDependiendo del tamaño de la población y del número de bits por individuo, la mutación puede ser extremadamente rara en una generación

Page 25: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

25

Utilidad de la mutación

Genera diversidadPuede ser de utilidad cuando un algoritmo genético está estancadoSu abuso reduce al algoritmo genético a una búsqueda aleatoria

Otros mecanismos de generación de diversidad

Aumentar el tamaño de la poblaciónGarantizar la aleatoriedad de la población inicial

Page 26: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

26

Otros operadores

Cromosomas de longitud variableAñadir, eliminar

Operadores de nichoFuerzan a que cromosomas similares sólo reemplacen a cromosomas similaresIntentan mantener la diversidad

Distintas “especies” en la poblaciónCada una de ellas puede converger a un máximo diferente

Page 27: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

27

Ejemplo optimización: f(x)=x2

encontrar máximo entero en [1,32]

Codificación binaria: cadena de 5 bitsTamaño población inicial: 4 individuosPoblación inicial: aleatoria

Sortear cada bit de cada cadena con p=1/2

Función de aptitud f(x)=x2

Selección: ruletaCambio de generación: manteniendo el tamaño de la población intermedia

Reemplazar un par de individuos elegidos aleatoriamente por los hijos

Page 28: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

28

Población inicial

293Media

1170Suma

1.000.3136119100114

576mejor

0.690.06648010003

0.630.4957624110002

0.140.1416913011011

Probabilidad acumulada

Probabilidad selección

aptitudxPoblación inicial

Page 29: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

29

Selección: ruleta

Generar cuatro números aleatorios, distribución de probabilidad uniforme en intervalo (0,1)Un individuo i se selecciona si el número aleatorio obtenido está en el intervalo definido por la probabilidad acumulada del individuo i-1y la del individuo iSuponer que se obtienen: 0.58, 0.84, 0.11 y 0.43Individuos seleccionados: 2, 4, 1, 2

Page 30: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

30

Población seleccionada

420.5Media

1682Suma

57624110002

576mejor

16913011011

36119100114

57624110002

Probabilidad acumulada

Probabilidad selección

aptitudxPoblación inicial

Page 31: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

31

Cruce

Emparejamiento: emparejarlos según se han seleccionado -2 con 4, 1 con 2-Probabilidad de cruce: 0.8

Generar número aleatorio, distribución uniforme, (0, 1)Suponer se obtienen 0.7, 0.3: se produce el cruce en ambos emparejamientos

Generar puntos de cruce: numero aleatorio, distribución uniforme en [1, 2… ,L] con L longitud del cromosoma

Suponer se obtienen 2,3

Page 32: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

32

Creación descendientes

00001h2

11011h1

110014

000112

10011h4

00110h3

000112

101101

Page 33: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

33

Mutación

Probabilidad mutación: 10-3

Suponer no se produce ninguna mutación

Page 34: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

34

Nueva población:reemplazar padres por hijos

418,5Media

1674Suma

1.000.376252511001h4

729mejor

0.630.0464801100h3

0.590.152561610000h2

0.440.447292711011h1

Probabilidad acumulada

Probabilidad selección

aptitudxPoblación 1ªiteración

Page 35: Algoritmos genéticos - UVacalonso/IAI/Tema5-AlgoritmosGeneticos/...Algoritmos genéticos 1. Introducción 2. Esquema básico 3. Codificación 4. Evaluación 5. Selección 6. Operadores

35

Ejercicio

Considerar el problema de encontrar el máximo de la función f(x)=1-x2, en el intervalo [-1, 1]Utilizar la codificación y función de aptitud propuestas como ejemploMétodo de selección: torneoProbabilidad de cruce: 0,8Probabilidad de mutación:0,001Cambio de generación: cambiar padres por hijosObtener la población tras dos iteraciones