Download Algoritmos Genéticos 1
Document related concepts
no text concepts found
Transcript
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