1
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Inteligencia Artificial
Algoritmos Genticos
Prof. Dra. Silvia Schiaffino
ISISTAN
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Agenda
Concepto
Ciclo
Poblacin
Reproduccin
Recombinacin
Mutacin
Evaluacin
Algoritmo
Ejemplos
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Algoritmos Genticos
Algoritmo de bsqueda en espacio de soluciones.
Inspirados en mecanismos de evolucin biolgica
Se basan en el mecanismo de supervivencia del ms apto
Desarrollados por Holland en la Universidad de Michigan en los 70
Para entender el proceso adaptativo de los sistemas naturales
Para disear sistemas artificiales con la robustez de los sistemas naturales
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Algoritmos Genticos
Procedimiento iterativo
Produce una serie de generaciones de poblaciones, una poblacin por cada iteracin
Cada miembro de la poblacin representa una solucin al problema y se denomina cromosoma
Nuevas soluciones se generan por crossover (recombinacin) y mutacin
Requiere el clculo de una funcin de fitness
2
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Similitud con sistemas biolgicos
Sistemas Biolgicos
Los miembros de una poblacin compiten por
sobrevivir y reproducirse
Las especies que mejor se adapten a su ambiente
son las que tienen ms
posibilidades de
reproducirse
Los hijos son un hbrido de sus padres
Algoritmos Genticos
Muchas soluciones compiten por resolver el
problema y reproducirse
Las soluciones que mejor resuelven el problema son
las que tienen ms
posibilidades de
reproducirse
A partir de 2 soluciones se obtienen otras mediante el
operador crossover
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Similitud con sistemas biolgicos
Sistemas Biolgicos
Los hijos tienen un cdigo gentico independiente del de sus padres
Los padres son gradualmente reemplazados por sus hijos
La poblacin es cada vez ms apta y se adapta al ambiente con el paso del tiempo
Algoritmos Genticos
Los hijos reciben un cdigo independiente del
de sus padres a travs del
operador mutacin
Los padres mueren inmediatamente una vez
que nacen sus hijos
La poblacin de soluciones es cada vez
mejor para resolver el
problema
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Algoritmos Genticos: Componentes
Tcnica de codificacin gen, cromosoma
Procedimiento de inicializacin creacin
Funcin de fitness ambiente
Seleccin de padres reproduccin
Operadores Genticos mutacin, crossover (recombinacin)
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Algoritmos Genticos: Ciclo
3
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Poblacin
Inicializacin de la poblacin: aleatoria o soluciones conocidas
Los cromosomas pueden ser:
String de bits (0101...1100)
Nmeros reales (43.6 78.2....)
Permutaciones de elementos (E11 E3...E15)
Lista de reglas (R1 R2...R10)
...
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Reproduccin
Los padres son seleccionados aleatoriamente, pero sus chances de
seleccin estn en relacin a la evaluacin
de los cromosomas
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Reproduccin: Seleccin por rueda de la ruleta
Cuando la rueda se detiene, la probabilidad de detenerse en un cromosoma i es:
Pi = fi / k fk
La ruleta gira una cantidad aleatoria y devuelve el cromosoma apuntado por la
flecha
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Reproduccin
Seleccin por torneo: Selecciona un par de individuos aleatoriamente. Generar un nmero aleatorio R entre 0 y 1. Si R=r, usa el segundo individuo como padre. El valor de r es un parmetro de este mtodo. Se hace lo mismo para encontrar el segundo padre.
Elitismo: Primero se copian los N mejores cromosomas a la nueva poblacin, y el resto se determinan con otros mtodos. Esto incrementa rpidamente la performance del algoritmo ya que previene la prdida de buenas soluciones.
4
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Modificacin de cromosomas
Operadores
Mutacin
Crossover (Recombinacin)
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Mutacin
Causa un movimiento en el espacio de bsqueda
Altera los genes aleatoriamente
Mantiene la diversidad gentica
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Crossover o Recombinacin
Crossover es una caracterstica crtica de los algoritmos genticos
Combina 2 padres en nuevos hijos, genera variantes combinando material gentico existente
Acelera la bsqueda tempranamente en la evolucin de la poblacin
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Crossover
5
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Evaluacin
El evaluador decodifica un cromosoma y le asigna un valor de fitness
El evaluador es el nico nexo entre el algoritmo gentico y el problema que se est
solucionando
Se necesita un modelo de evaluacin distinto para cada problema
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Tcnicas de fitness
La evaluacin es directamente el valor de fitness
Windowing: toma el valor ms bajo y asigna a cada cromosoma un valor de fitness igual a la cantidad
que excede del mnimo
Normalizacin lineal: los cromosomas se ordenan por orden decreciente de valor de evaluacin, y se le
asigna un valor de fitness que comienza con una
constante y decrece linealmente. El valor individual y
el decremento son parmetros de esta tcnica.
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Eliminacin
Eliminar todos: elimina todos los miembros de la poblacin actual y los reemplaza con el mismo
nmero de cromosomas que fueron creados
Steady-State: Elimina n de los viejos miembros, y los reemplaza con n nuevos miembros
Steady-State-No duplicates: igual al anterior pero chequea no incluir cromosomas duplicados en la
poblacin. Tiene un costo adicional pero se explora
ms cantidad del espacio de bsqueda.
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Algoritmo Bsico
6
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Algoritmo
Inicializar una poblacin de cromosomas
Coleccin de puntos iniciales, soluciones
Transformar cada solucin en un string de bits
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Algoritmo
Seleccionar padres para la reproduccin
Crear nuevos cromosomas por crossover y mutacin
Identificar puntos de crossover
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Algoritmo
Seleccionar padres para la reproduccin
Crear nuevos cromosomas por crossover y mutacin
Identificar puntos de crossover
En cada punto de crossover, intercambiar las partes sealadas y crear nuevos hijos
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Algoritmo
Ocasionalmente mutar los hijos
Puntos de mutacin
Seleccionar un bit aleatorio en el string y
cambiarlo
Mutaciones complejas
Mutar un patrn o secuencias de bits
7
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Algoritmo bsico
Seleccionar cuestiones de implementacin bsicas
Representacin
Tamao de la poblacin, razn de mutacin
Seleccin, polticas de eliminacin
Operadores de mutacin y crossover
Criterio de terminacin
La solucin va a ser tan buena como lo sea la funcin de evaluacin
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Ejemplo 1: Problema del viajante
Problema del viajante: encontrar un camino entre un conjunto de ciudades de manera
que:
Cada ciudad se visita solo una vez
Minimizar la distancia total
Solucin: lista ordenada de ciudades
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Ejemplo 1: Problema del viajero
Posibles soluciones
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Ejemplo 1: Problema del viajante
Puede generar soluciones ilegales:
Elige una parte del primer padre y la copia al primer hijo
Copia los restantes genes que no estn en la parte copiada
Usa el orden de los genes del 2 padre
Repite el proceso con el rol de los padres invertidos para generar el 2 hijo
8
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Ejemplo: Problema del viajante
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Ejemplo 1: Problema del viajante
Mutacin: consiste en reordenar la lista
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
El algoritmo determina que hacer para resolver el problema.
Operan de forma simultnea con varias soluciones, en lugar de trabajar de forma secuencial como las tcnicas tradicionales.
En cualquier momento se puede obtener una solucin al problema. Las soluciones mejoran a travs del tiempo.
Se puede aumentar la velocidad de la evolucin con conocimiento acerca del problema.
Facilita la exploracin de soluciones alternativas.
Utilizan operadores probabilsticos.
El algoritmo puede ser diseado como un mdulo separado de la aplicacin.
Ventajas de la tcnica
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Pueden tardar mucho en converger, dependiendo en cierta medida de los parmetros que se utilicen (tamao
de la poblacin, nmero de generaciones, etc).
Como el mtodo es bsicamente numrico, no siempre es posible representar el conocimiento del dominio en la
forma requerida por el algoritmo gentico
Desventajas de la tcnica
9
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
The Origin of Species. Charles Darwin. 1859. http://www.darwin-literature.com/The_Origin_of_Species/index.html
Adaptation in Natural and Artificial Systems. John Holland. University of Michigan Press, Ann Arbor, 1975
Genetic Algorithm in Search, Optimization and Machine Learning. Goldberg, D. E. Addison-Wesley Publishing Company, Massachusetts, 1989.
Machine Learning. Tom Mitchell. Ed. McGraw Hill, 1997.
Representations for Genetic and Evolutionary Algorithms. Franz Rothlauf. Ed. Springer, 2006.
Referencias
Inteligencia Artificial 2014
Prof.Dra. Silvia Schiaffino
Herramientas
Algoritmos genticos
JGAP
http://jgap.sourceforge.net/
JavaEva
http://www-ra.informatik.uni-tuebingen.de/software/JavaEvA/
Jaga
http://www.jaga.org/
Top Related