1

1. ALGORITMOS GENÉTICOS. INTRODUCCIÓN2. ¿CÓMO SE CONSTRUYE? 3. SOBRE SU UTILIZACIÓN4. ALGUNAS CUESTIONES: DIVERSIDAD, EXPLORACIÓN vs

EXPLOTACIÓN 5. MODELOS: GENERACIONAL vs ESTACIONARIO6. DOMINIOS DE APLICACIÓN7. EJEMPLO: VIAJANTE DE COMERCIO8. APLICACIONES

ALGORITMOS GENÉTICOS

2

BIBLIOGRAFÍA

D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, 1989.

Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. Springer Verlag, 1996.

T. Bäck, D.B. Fogel, Z. Michalewicz, Handbook of Evolutionary Computation, Oxford Univ. Press, 1997.

3

EVOLUCIÓN NATURAL. EVOLUCIÓN ARTIFICIAL

¿QUÉ ES UN ALGORITMO GENÉTICO?

LOS INGREDIENTES

El CICLO DE LA EVOLUCIÓN

ESTRUCTURA DE UN ALGORITMO GENÉTICO

1. INTRODUCCIÓN A LOS ALGORITMOS GENÉTICOS

4

Evolución Natural (1)

En la naturaleza, los procesos evolutivos ocurrencuando se satisfacen las siguientes condiciones:

Una entidad o individuo tiene la habilidad de reproducirse

Hay una población de tales individuos que son capaces dereproducirse

Existe alguna variedad, diferencia, entre los individuos quese reproducen

Algunas diferencias en la habilidad para sobrevivir en elentorno están asociadas con esa variedad

5

Evolución Natural (2)

Los mecanismos que conducen esta evolución no sontotalmente conocidos, pero sí algunas de suscaracterísticas, que son ampliamente aceptadas:

La evolución es un proceso que opera sobre loscromosomas más que sobre las estructuras de la vida queestán codificadas en ellos

6

La selección natural es el enlace entre los cromosomas y laactuación de sus estructuras decodificadas.

El proceso de reproducción es el punto en el cual laevolución toma parte, actúa

La evolución biológica no tiene memoria

Referencia: Darwin, C. (1859). On the Origin ofSpecies by Means of Natural Selection or thePreservations of Favoured Races in the Struggle forLife. London: John Murray

Evolución Natural (3)

7

COMPUTACIÓN EVOLUTIVA

Está compuesta por modelos de evolución basados enpoblaciones cuyos elementos representan soluciones aproblemas

La simulación de este proceso en un ordenador resulta seruna técnica de optimización probabilística, que confrecuencia mejora a otros métodos clásicos en problemasdifíciles

Evolución Artificial (1)

8

Existen cuatro paradigmas básicos:

Algoritmos Genéticos que utilizan operadores genéticossobre cromosomas

Estrategias de Evolución que enfatizan los cambios decomportamiento al nivel de los individuos

Programación Evolutiva que enfatizan los cambios decomportamiento al nivel de las especies

Programación Genética que evoluciona expresionesrepresentadas como árboles

Existen otros múltiples Modelos de Evolución dePoblaciones

Evolución Artificial (2)

9

¿Qué es un Algoritmo Genético?

Los Algoritmos Genéticos

son algoritmos de optimización,búsqueday aprendizajeinspirados en los procesos de

Evolución Natural y

Evolución Genética

10

t t + 1

mutación

reproducción

selección

Los Ingredientes

Cruce(o recombinación)

11

Cruce

Mutación

Selección

Reemplazamiento

El ciclo de la Evolución

PADRES

POBLACIÓN

DESCENDIENTES

12

Estructura de un Algoritmo Genético

Algoritmo Genético BásicoInicio (1)

t = 0inicializar P(t)evaluar P(t)

Mientras (no se cumpla la condición de parada) hacerInicio(2)

t = t + 1seleccionar P’(t) desde P(t-1)P’’(t) ← cruce P’(t)P’’’(t) ← mutación P’’(t)P(t) ← reemplazamiento (P(t-1),P’’’(t))evaluar P(t)

Final(2)

Final(1)

13

Pasos para construir un Algoritmo Genético:

Diseñar una representaciónDecidir cómo inicializar una poblaciónDiseñar una correspondencia entre genotipo y fenotipoDiseñar una forma de evaluar un individuoDiseñar un operador de mutación adecuadoDiseñar un operador de cruce adecuadoDecidir cómo seleccionar los individuos para ser padresDecidir cómo reemplazar a los individuosDecidir la condición de parada

2. ¿CÓMO SE CONSTRUYE?

14

Representación

Debemos disponer de un mecanismo para codificar un individuo como un genotipo

Existen muchas maneras de hacer esto y se debe elegir la más relevante para el problema en cuestión

Una vez elegida una representación, tenemos que tener en mente cómo se evaluarán los genotipos (codificación) y qué operadores genéticos habrá que utilizar

15

Ejemplo: Representación binaria

CROMOSOMA

GEN

La representación de un individuo se puede hacer mediante una codificación discreta, en particular binaria

16

Ejemplo: Representación binaria

8 bits Genotipo

Fenotipo• Entero• Número real• Secuencia• ...• ¿Cualquier otra?

17

Ejemplo: Representación binaria

El fenotipo puede ser uno o varios números enteros

Genotipo:

1·27 + 0·26 + 1·25 + 0·24 + 0·23 + 0·22 + 1·21 + 1·20 =128 + 32 + 2 + 1 = 163

= 163Fenotipo:

18

Ejemplo: Representación binaria

También puede corresponder a números realesEjemplo: un número entre 2.5 y 20.5 utilizando 8 dígitos binarios

( ) 9609,135,25,202561635,2 =−+=x

= 13,9609Genotipo: Fenotipo:

19

Ejemplo: Representación Real

Una forma natural de codificar una solución es utilizando valores reales como genes

Muchas aplicaciones tienen esta forma natural de codificación

20

Ejemplo: Representación Real

Los individuos se representan como vectores de valores reales:

La función de evaluación asocia a un vector un valor real de evaluación:

Rx

x

xx

X i

n

∈

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

= ,2

1

M

RRf n →:

21

Ejemplo: Representación de orden

Los individuos se representan como permutaciones

Se utilizan para problemas de secuenciación

Ejemplo famoso: Viajante de Comercio, donde cada ciudad tiene asignado un único número entre 1 y n

Necesita operadores especiales para garantizar que el resultado de aplicar un operador sigue siendo una permutación

22

Inicialización

Uniforme sobre el espacio de búsqueda … (si es posible)

Cadena binaria: 0 ó 1 con probabilidad 0.5

Representación real: uniforme sobre un intervalo dado (para valores acotados)

Elegir la población a partir de los resultados de una heurística previa

23

Correspondencia entre Genotipo y Fenotipo

Algunas veces la obtención del fenotipo a partir del genotipo es un proceso obvio

En otras ocasiones, el genotipo puede ser un conjunto de parámetros para algún algoritmo, el cual trabaja sobre los datos de un problema para obtener un fenotipo

Datos de un Problema

Fenotipo

Algoritmode obtención

Genotipo(Codificación)

24

Evaluación de un individuo: fitness o valor de adecuación

Este es el paso más costoso para una aplicación real

Puede ser una subrutina, un simulador, o cualquier proceso externo (ej. Experimentos en un robot, ....)

Se pueden utilizar funciones aproximadas para reducir el costo de evaluación

Cuando hay restricciones, éstas se pueden introducir en la función de fitness como penalización del costo

Con múltiples objetivos se busca una solución de compromiso

25

Operador de mutación

Podemos tener uno o más operadores de mutación para nuestra representación

Algunos aspectos importantes a tener en cuenta son:

Debe permitir alcanzar cualquier parte del espacio de búsqueda

El tamaño de la mutación debe ser controlado

Debe producir cromosomas válidos

26

Ejemplo: Mutación para representación discreta binaria

La mutación ocurre con una probabilidad pmpara cada gen

1 1 1 1 1 1 1antes

1 1 1 0 1 1 1después

gen mutado

27

Ejemplo: Mutación para representación real

Perturbación de los valores mediante un valor aleatorio

Frecuentemente, mediante una distribución Gaussiana/normal N(0,σ), donde

• 0 es la media• σ es la desviación típica

x’i ← xi + N(0,σi)

para cada parámetro

28

Ejemplo: Mutación para representación de orden

7 83 41 2 6 5

7 83 46 2 1 5

Se seleccionan aleatoriamente dos genes y se intercambian

29

Operador de Cruce

Podríamos tener uno o más operadores de cruce para nuestra representación

Algunos aspectos importantes a tener en cuenta son:

Los hijos deberían heredar algunas características de cada padre. Si éste no es el caso, entonces estamos ante un operador de mutación

Se debe diseñar de acuerdo a la representación

La recombinación debe producir cromosomas válidos

30

Ejemplo: Operador de cruce para representación binaria

Población: . . .

Cada cromosoma se corta en n partes que son recombinadas. (Ejemplo para n = 1)

1 1 1 1 1 1 1 0 0 0 0 0 0 0 padrescorte corte

1 1 1 0 0 0 0 0 0 0 1 1 1 1descendientes

31

Ejemplo: Operador de cruce para representación real

Recombinación discreta (cruce uniforme): dados 2 padres se crea un descendiente escogiendo aleatoriamente cada gen de un padre o del otro:

a db fc e g h

FD GE HCBA

a b C Ed Hgf

32

Ejemplo: Operador de cruce para representación real

Existen muchos operadores específicos para la codificación real. Por ejemplo, la recombinación aritmética (cruce aritmético):

a db fc e

FD ECBA

(a+A)/2 (b+B)/2 (c+C)/2 (e+E)/2(d+D)/2 (f+F)/2↓

33

Ejemplo: Operador de cruce para representación de orden (Cruce OX)

7 83 41 2 6 5 78 16 5234

81 2

7, 3, 4, 6, 5

4, 3, 6, 7, 5

ordenar

7 85 41 2 3 6

Padre 1 Padre 2

Hijo 1 insertar a partir del2º punto de cruce

34

Estrategia de Selección

Debemos garantizar que los mejores individuos tengan una mayor posibilidad de ser padres (reproducirse) frente a los individuos menos buenos

Debemos ser cuidadosos para dar una posibilidad de reproducirse a los individuos menos buenos. Éstos pueden incluir material genético útil en el proceso de reproducción

Esta idea nos define la presión selectiva que conducirá la reproducción como la selección fuerte de los mejores

35

Ejemplo: Selección proporcional

El número de veces que un individuo se debe reproducir es:

∑=

jj

ii f

fSP )(

Mejor

Peor

Los mejores individuos tienen:

Más espacio en la ruletaMás probabilidad de ser seleccionados

36

Ejemplo: Selección proporcional

Desventajas:

Peligro de convergencia prematura porque los mejores individuos dominan la población muy rápidamente

Baja presión selectiva cuando los valores de la función objetivo están muy cercanos

Comportamientos diferentes cuando se realizan traslaciones sobre la función de evaluación

37

Ejemplo: Selección proporcional

Una solución: Escalado del fitness:

Ajustar el fitness a un rango:Ej. Rangos de 0 a 1

Normalizar:La suma de los fitness igual a 1

38

Ejemplo: Selección por torneo

Para cada individuo a seleccionar, se escogen k individuos aleatoriamente, sin reposición

Se elige el mejor de ellosk se llama el tamaño del torneo

39

Ejemplo: Selección basada en orden

Los individuos se ordenan por su valor de función objetivo de mejor a peor. El lugar ocupado en la lista se llama el orden del cromosoma

En lugar del valor de la función objetivo, se utiliza el orden del cromosoma, para ordenar entre un máximo y un mínimo

40

Ejemplo: Selección basada en orden

Función objetivo: f(A) = 5, f(B) = 2, f(C) = 19Orden (minimización): r(A) = 1, r(B) = 0, r(C) = 2

Función: h(A) = 1, h(B) = 1.25, h(C) = 0.75Proporción en la ruleta:

p(A) = 33.3%, p(B) = 41.7%, p(C) = 25%

25.1min2]1,0[75.0

1)()()(

max

min

minmaxmax

=−=∈=

−−−=

rankrank

nxrrankrankrankxh

41

Estrategia de Reemplazamiento

La presión selectiva se ve también afectada por la forma en que los cromosomas de la población son reemplazados por los nuevos descendientes

Podemos utilizar métodos de reemplazamiento aleatorios o determinísticos

Se puede reemplazar toda la población actual con la de descendientes (esquema generacional) o sólo una parte de ella (esquema estacionario)

Podemos decidir no reemplazar al mejor(es) cromosoma(s) de la población: Elitismo

42

Criterio de parada

¡Cuando se alcanza el óptimo!

Recursos limitados de CPU:Fijar el máximo número de evaluaciones

Límite sobre la paciencia del usuario: Después de algunas iteraciones sin mejora

43

Cruce

Mutación

Componentes

PADRES

POBLACIÓN

DESCENDIENTES

Representación

Inicialización Población

Función Evaluación

Reemplazamiento

Selección

44

3. SOBRE SU UTILIZACIÓN

Nunca sacar conclusiones de una única ejecuciónutilizar medidas estadísticas (medias, medianas, ...)con un número suficiente de ejecuciones independientes

“Se puede obtener lo que se desea en una experimentación de acuerdo a la dificultad de los casos utilizados” – No se debe ajustar/chequear la actuación de un algoritmo sobre ejemplos simples si se desea trabajar con casos reales

Desde el punto de vista de las aplicaciones:

doble enfoque y diferente diseñoEncontrar una solución muy buena al menos una vez

Encontrar al menos una solución muy buena en cada ejecución

45

4. ALGUNAS CUESTIONES: DIVERSIDAD, EXPLORACIÓN vs EXPLOTACIÓN

Diversidad genética

Asociada a las diferencias entre los cromosomas en la población

Falta de diversidad genética = todos los individuos en la población son parecidos

Falta de diversidad convergencia al vecino más cercano

Alta presión selectiva falta de diversidad

En la práctica es irreversible. Soluciones:• Inclusión de mecanismos de diversidad en la evolución• Reinicialización cuando se produce convergencia

prematura

46

ALGUNAS CUESTIONES: DIVERSIDAD, EXPLORACIÓN vs EXPLOTACIÓN

Exploración vs Explotación

Exploración = muestrear regiones desconocidas

Excesiva exploración = búsqueda aleatoria, no convergencia

Explotación = trata de mejorar el mejor individuo

Excesiva explotación = solo búsqueda local … convergencia a un óptimo local

47

5. MODELOS: GENERACIONAL vs ESTACIONARIO

Modelo generacional: Durante cada iteración se crea una población completa con nuevos individuosLa nueva población reemplaza directamente a la antigua

Modelo estacionario: Durante cada iteración se escogen dos padres de la población (diferentes mecanismos de muestreo) y se les aplican los operadores genéticos

El/los descendiente/s reemplaza/n a uno/dos cromosoma/s de la población inicialEl modelo estacionario es elitista. Además, produce una presión selectiva alta (convergencia rápida) cuando se reemplazan los peores cromosomas de la población

48

MUTACIÓNcon prob. Pm

Modelo Generacional

Pactual(t)C1

C2

…CM

REEMPLAZAMIENTO

con elitismo (semantiene el mejor de P(t))

SELECCIÓN

(los C’ soncopias de los C)

Ppadres

C’1C’2…

C’M

CRUCE

con prob Pc

Pintermedia

C’’1C’2…

C’’M

Phijos

H1= C’’m1

H2=C’m2

…HM=C’’M

Pactual(t+1)H1H2…

HM-1Cmejor

t ← t+1

49

MUTACIÓNcon prob. Pm

Modelo Estacionario

Pactual(t)C1

C2

…CM

REEMPLAZAMIENTO

(los dos hijos compitenpara entrar en P(t))

SELECCIÓN

(dos cromo-somas de C)

Ppadres

C’1C’2

CRUCE

con prob 1

Pintermedia

C’’1C’’2

Phijos

H1= C’’1H2=C’’m2

Pactual(t+1)C1C2…H1CM

t ← t+1

50

Optimización estructural

Generación de trayectorias

1 2 m1n

Planificación de sistemas de Producción

Diseño de circuitos VLSI

AprendizajeClasificación

Control de procesos químicos

6. DOMINIOS DE APLICACIÓN

51

DOMINIOS DE APLICACIÓN

Optimización combinatoria y en dominios reales

Modelado e identificación de sistemas

Planificación y control

Ingeniería

Vida artificial

Aprendizaje y minería de datos

Visión por Computador e Informática Gráfica

Internet y Sistemas de Recuperación de Información

...

T. Bäck, D.B. Fogel, Z. Michalewicz, Handbook of Evolutionary Computation. Oxford Univ. Press, 1997

52

7. EJEMPLO: VIAJANTE DE COMERCIO

Representación de orden

(3 5 1 13 6 15 8 2 17 11 14 4 7 9 10 12 16)

17 ciudadesObjetivo: Suma de la distancia entre las ciudades.Población: 61 cromosomas - ElitismoCruce: OX (Pc = 0,6)Mutación: Inversión de una lista (Pm = 0,01 – cromosoma)

53

Viajante de Comercio

17! = 3.5568743 e14 recorridos posibles Solución óptima: 226.64

54

Viajante de Comercio

Iteración: 0 Costo: 403.7Solución óptima: 226.64

Iteración: 25 Costo: 303.86

55

Viajante de Comercio

Iteración: 50 Costo: 293,6Solución óptima: 226,64

Iteración: 100 Costo: 256,55

56

Viajante de Comercio

Iteración: 250 Solución óptima: 226,64Iteración: 200 Costo: 231,4

57

Viajante de Comercio

Visualización de la evolución de una población de 50 cromosomas y 70 iteraciones

58

Viajante de Comercio

Visualización de la evolución de una población de 50 cromosomas y 70 iteraciones

59

Viajante de Comercio

Visualización de la evolución de una población de 50 cromosomas y 70 iteraciones

60

Viajante de Comercio

Visualización de la evolución de una población de 50 cromosomas y 70 iteraciones

61

Viajante de Comercio

Visualización de la evolución de una población de 50 cromosomas y 70 iteraciones

62

Viajante de Comercio

Visualización de la evolución de una población de 50 cromosomas y 70 iteraciones

63

RESUMEN

Algoritmos Genéticos

basados en una metáfora biológica: evolución gran potencialidad de aplicaciónmuy populares en muchos camposmuy potentes en diversas aplicacionesaltas prestaciones a bajo costo

64

BIBLIOGRAFÍA

D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, 1989.

Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. Springer Verlag, 1996.

T. Bäck, D.B. Fogel, Z. Michalewicz, Handbook of Evolutionary Computation, Oxford Univ. Press, 1997.