Download Algoritmos Genéticos 1

Algoritmos Genéticos
Ramón Garduño Juárez
Diseño de Fármacos
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Introducción
“Los Algoritmos Genéticos
son buenos al tomar
grandes, potencialmente
enormes espacios de
búsqueda y navegar por
entre ellos, buscando por
combinaciones óptimas de
cosas, soluciones que de
otra manera se tomarían
toda una vida para
encontrar.”
- Salvatore Mangano
Computer Design, Mayo 1995
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Clases de técnicas de búsqueda
Search techniques
Calculus-based techniques
Direct methods
Finonacci
Guided random search techniques
Indirect methods
Newton
Evolutionary algorithms
Evolutionary strategies
Genetic algorithms
Parallel
Centralized
Simulated annealing
Distributed
Sequential
Steady-state Generational
Enumerative techniques
Dynamic programming
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Una revisión rápida de los AG



Desarrollados: en los EUA en los 1970’s
Pioneros: J. Holland, K. DeJong, D. Goldberg
Típicamente aplicados a:
–

Características Atribuidas :
–
–

La optimización discreta
no son muy rápidos
Una buena heurística para problemas combinatorios
Características Especiales:
–
–
tradicionalmente enfatiza el combinar la información de
padres saludables (cruzamiento)
muchas variantes, e.g., modelos de reproducción, operadores
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Algoritmos Genéticos


El AG original de Holland se conoce ahora
como el genético algoritmo simple (AGS)
Otros AGs usan diferentes:
–
–
–
–
Representaciones
Mutaciones
Cruzamientos
Mecanismos de selección
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Resumen técnico de los AGS
Representación
Cadenas binarias
Recombinación
N-puntos o uniforme
Mutación
Dar la vuelta a pares de bits
con probabilidad fija
Aptitud-Proporcionado
Selección de padres
Selección de sobrevivientes Todos los hijos remplazan a
los padres
Especialidad
Énfasis en el cruzamiento
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Representación de los cromosomas
población

Los cromosomas pueden ser:
–
–
–
–
–
–
Cadenas de Bits
(0101 ... 1100)
Números Reales
(43.2 -33.1 ... 0.0 89.2)
Permutaciones de elementos (E11 E3 E7 ... E1 E15)
Listas de reglas
(R1 R2 R3 ... R22 R23)
Elementos del programa
(programación genética)
... cualquier estructura de datos ...
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Representación
Espacio Fenotipo
Espacio Genotipo = {0,1}L
Codificado
(representación)
10010001
10010010
010001001
011101001
Decodificado
(representación inversa)
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Tipos de AGS
población
miembros descartados
desechos


AG Generacional:
poblaciones enteras son reemplazadas en cada
iteración
AG Estado-estable:
unos cuantos miembros son reemplazados en
cada generación
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Ciclo de reproducción en AGS
1. Seleccionar a los padres del pozo de apareamiento
(tamaño del pozo = tamaño de la población)
2. Mezclar el pozo de apareamiento
3. Para cada par consecutivo aplicar el cruzamiento con
probabilidad pc , de lo contrario copiar los padres
4. Para cada prole aplicar la mutación (cambiar el bit
con probabilidad pm independientemente del bit)
5. Remplazar la población entera con la prole resultante
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Operadores AGS: cruzamiento de 1-punto




Escoja un punto al azar en los dos padres
Separe a los padres en este punto de cruce
Dé origen a nueva prole al intercambiar sus extremos
Pc típicamente en el intervalo (0.6, 0.9)
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Operadores AGS: mutación


Altere cada gen independientemente con una
probabilidad pm
pm es conocida como el índice de mutación
–
Típicamente entre 1/tamaño_pobl y 1/ longitud_cromosoma
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Operadores AGS: Selección

Idea Principal: mejores individuos tienen mayor probabilidad
– Probabilidad proporcional a la aptitud
– Implementación: técnica de la ruleta
 Asignar a cada individuo una parte de la
ruleta
 Gire la ruleta n veces para seleccionar n
individuos
1/6 = 17%
A
3/6 = 50%
B
C
aptitud (A) = 3
aptitud (B) = 1
2/6 = 33%
aptitud (C) = 2
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Un ejemplo [Goldberg 1989]


Problema simple : max x2 sobre {0,1,…,31}
Enfoque AG:
–
–
–
–
–

Representación: código binario, e.g. 01101  13
Tamaño de la población: 4
X-amiento de 1-punto, mutación por bit
Selección de ruleta
Inicialización azarosa
Se muestra un ciclo generacional hecho a mano
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Ejemplo x2: selección
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Ejemplo X2: cruzamiento
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Ejemplo X2: mutación
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
El AG simple

Ha sido sujeto de muchos estudios
–

aún se usa como referencia para AGs nuevos
Muestra muchos defectos, e.g.
–
–
–
–
Representación es muy restrictiva
Mutación & cruzamiento solo se aplica a cadenas de
bits & representaciones de enteros
Mecanismo de selección es sensitivo en la
convergencia de poblaciones con valores de aptitud
muy cercanos
Modelo de población generacional (paso 5 en AGS
ciclo reproductivo) puede ser mejorado con la
selección explicita del sobreviviente
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Operadores Alternativos de Cruzamiento

El desempeño con cruzamiento de 1 punto depende
del orden en el que las variables ocurren en la
representación
–
más probablemente mantendrá juntos a los genes
que están cercanos
–
nunca podrá mantener juntos a genes de los
extremos opuestos de la cadena
–
esto es conocido como la tendencia posicional
–
Puede ser explotado si conocemos la estructura del
problema, pero generalmente éste no es el caso
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Cruzamiento de n-puntos




Escójanse n puntos azarosos de cruce
Sepárense los genes en estos puntos
Pegue las partes, alternándose entre los padres
Generalización de 1 punto (todavía con tendencia
posicional)
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Cruzamiento uniforme




Asignar ‘cabezas’ a un padre, y ‘colas’ a el otro
Eche una moneda al aíre para cada gen del primer hijo
Haga una copia inversa del gen para el segundo hijo
La herencia es independiente de la posición
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
¿Cruzamiento O mutación?

Debate con más de una década: cual es mejor /
necesario / principales-antecedentes

Respuesta (al menos, más de común acuerdo):
–
–
–
–
depende del problema, pero
en general, es mejor tener a ambos
ambos tienen un papel diferente
es posible tener AE-solo-mutación, AE-solo-Xamiento no
trabajan
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
¿Cruzamiento O mutación? (cont)
Exploración: Descubriendo áreas prometedoras en el espacio
de búsqueda, i.e. ganando información del problema
Explotación: Optimizando dentro de un área prometedora, i.e.
usando información
Existe la cooperación Y competición entre ellos

El cruzamiento es exploratorio, realiza un gran brinco a un
área en algún lugar “entre” dos (padres) áreas

La mutación es explotadora, esta crea al azar pequeñas
desviaciones, por lo cual permanece cerca (en el área de) del
padre
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
¿Cruzamiento O mutación? (cont)

Solo el cruzamiento puede combinar la información
de dos padres

Solo la mutación puede introducir nueva información
(alelos)

El cruzamiento no cambia las frecuencias de los
alelos en la población (por medio de experimentos:
50% 0’s en el primer bit en la población, ?% después
de llevar a cabo n cruzamientos)

Para pegarle al óptimo a menudo se necesita una
mutación ‘suertuda’
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Otras representaciones

Codificación Gray de enteros (aún cromosomas
binarios)
–
la codificación Gray es un mapeo que significa que pequeños
cambios en el genotipo causan pequeños cambios en el
fenotipo (a diferencia del código binario). Un mapeo genotipofenotipo “más suave” hace la vida más fácil para el AG
Hoy en día es más aceptado que es mejor codificar las
variables numéricas directamente como

Enteros

Variables de punto flotante
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
Un ejemplo abstracto
Distribución de Individuos en la Generación 0
Distribución de Individuos en la Generación N
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms
En resumen
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Genetic Algorithms