Algoritmos Genéticos

1

Inteligencia Artificial 2014

Prof.Dra. Silvia Schiaffino

Inteligencia Artificial

Algoritmos Genticos

Prof. Dra. Silvia Schiaffino

ISISTAN



Agenda

Concepto

Ciclo

Poblacin

Reproduccin

Recombinacin

Mutacin

Evaluacin

Algoritmo

Ejemplos



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



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



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



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



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)



Algoritmos Genticos: Ciclo

3



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)

...



Reproduccin

Los padres son seleccionados aleatoriamente, pero sus chances de

seleccin estn en relacin a la evaluacin

de los cromosomas



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



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



Modificacin de cromosomas

Operadores

Mutacin

Crossover (Recombinacin)



Mutacin

Causa un movimiento en el espacio de bsqueda

Altera los genes aleatoriamente

Mantiene la diversidad gentica



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



Crossover

5



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



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.



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.



Algoritmo Bsico

6



Algoritmo

Inicializar una poblacin de cromosomas

Coleccin de puntos iniciales, soluciones

Transformar cada solucin en un string de bits



Algoritmo

Seleccionar padres para la reproduccin

Crear nuevos cromosomas por crossover y mutacin

Identificar puntos de crossover



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



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



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



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



Ejemplo 1: Problema del viajero

Posibles soluciones




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



Ejemplo: Problema del viajante




Mutacin: consiste en reordenar la lista



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



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



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



Herramientas

Algoritmos genticos

JGAP

http://jgap.sourceforge.net/

JavaEva

http://www-ra.informatik.uni-tuebingen.de/software/JavaEvA/

Jaga

http://www.jaga.org/

Documents

Algoritmos Genéticos