Download ALGORITMOS GENÉTICOS

ALGORITMOS GENÉTICOS
“En lugar de envidiar la naturaleza
debemos emularla” Holland
Algoritmos genéticos
•
•
•
Algoritmos basados en los principios de la evolución
natural
Se utilizan en problemas donde no se pueden encontrar
soluciones o estas no son satisfactorias
Funcionamiento básico:Se genera de forma aleatoria
una población inicial de soluciones potenciales, se entra
en un proceso iterativo que trasforma la población a
través de:
– una evaluación de las soluciones que forman la
población
– selección de las “mejores” y reproducción
– recombinación de estas formando una nueva
población
Componentes de un algoritmo
genético
• Una representación genética de las soluciones del
problema
• Una forma de crear una población inicial de soluciones
• Una función de evaluación capaz de medir la bondad de
cualquier solución
• Un conjunto de operadores genéticos como reglas de
transición probabilísticas para guiar la búsqueda
• El valor de unos parámetros de entrada que el algoritmo
genético utilizará para guiar su evolución
Esquema básico
Procedimiento AG
Inicio
t:=0;
inicializar P(t);
evaluar P(t);
mientras (no condición de terminación) hacer
t:=t+1;
reproducir P(t-1) en P(t);
recombinar P(t);
evaluar P(t);
Fin_mientras;
Fin.
Esquema básico
Representación
• Cadenas binarias (generalmente) de longitud determinada
por el número de variables existentes en una solución y el
número de bits necesarios para representarlas;
cromosomas o estructuras
• Ejemplo: maximizar f(x)=x2 (0- 31)
• Representación en binario
1010
• Los cromosomas están compuestos por genes; el valor de
un gen se denomina alelo y a su posición locus
Representación
• Cada iteración será una generación; cit = (bi1t...bilt)
representa el cromosoma ci de la generación t, b será un
gen o un elemento del vocabulario elegido.
• Podemos representar un individuo Xit en una generación
determinada t, como la terna:
Xit=(cit,xit,fit)
• xit es la decodificación del cromosoma (fenotipo) y fit es
la adecuación de la solución
Obtención de la población inicial
• Conjunto de individuos de número m, (m parámetro)
P(t)= {Xit,....Xit}
• Inicialización de un individuo Xi0 consiste en asignar un
valor aleatorio a cada uno de los genes bij0, con la
decodificación obtenemos su fenotipo xi0 y fi0 lo
obtendremos a través de la función de evaluación.
01101
m=4
11000
01000
10011
Función de evaluación
• Objetivo: medir la adecuación de una solución en una
generación t
• La función de evaluación se corresponde con la función
objetivo del problema
• Dado un cromosoma cit, y su fenotipo xit podemos
obtener su adecuación fit como:
• fit=eval(cit)=f(xit)
Función de evaluación
fit=eval(cit)=f(xit) en este caso f(x) =x2
Codificación Decodificación Fitness
ci
xi
fi
01101
13
169
11000
24
576
01000
8
64
10011
19
361
1170
Operadores Genéticos
Reproducción: Incluye un algoritmo de selección y un
algoritmo de muestreo
  El algoritmo de selección asigna una probabilidad de
selección a cada cromosoma
  El algoritmo de muestreo produce copias de los
cromosomas de la generación t-1 a la generación t
Los cromosomas con mayor probabilidad de selección se
reproducirán un número de veces mayor y tendrán mayor
repercusión en las siguientes generaciones.
Operadores Genéticos: selección y
muestreo
ci
ci
Fitness % del total
01101 13
169
14.4
1 copia
11000 24
576
49.2
2 copias
01000 8
64
5.5
10011 19
361
30.9
1170
100
0 copias
1 copia
Operadores Genéticos: esquemas
de selección y muestreo
• Basado en el rango:
– Se mantiene el porcentaje de la población.
– Los M peores se substituyen por la descendencia de los mejores.
– Diferentes variantes
• Rueda de ruleta:
– Los cromosomas de la generación actual en una cantidad
proporcional a su “bondad”
• Selección de torneo:
– Se escoge aleatoriamente un número T de individuos, gana el que
mejor se adapta, se repite hasta obtener el número de individuos
deseados
Operadores genéticos: rueda de
ruleta
Operadores Genéticos: cruce
• Cruce:
– Dependiendo de una probabilidad inicial, probabilidad
de cruce seleccionamos de forma aleatoria los
cromosomas que van a participar en el apareamiento
– A continuación aplicamos alguna técnica de cruce, por
ejemplo el cruce simple
11000
10000
10011
11011
Operadores Genéticos: cruce
• Cruce de n puntos:
– los cromosomas se cortan por n puntos
aleatorios y se intercambia el material genético
• Cruce uniforme:
– cada gen se obtiene de la madre o del padre de
forma aleatoria
Operadores Genéticos: cruce
Operadores Genéticos: mutación
• Mutación:
– Su objetivo es producir diversidad en la población
– Teniendo en cuenta una probabilidad, probabilidad de
mutación, y de forma aleatoria se altera un bit o gen de
un cromosoma
• Una vez aplicados los operadores, se evalúa de nuevo la
población
Operadores Genéticos
• Parámetros:
– Tamaño de la población
– Número de generaciones
– Probabilidad de cruce
– Probabilidad de mutación
• Ejemplo: valores aceptados para funciones de
optimización
– Tamaño de la población: 50-100
– Probabilidad de cruce: 0.60
– Probabilidad de mutación: 0.001
EL problema de la mochila
• N objetos para meter en una mochila
• Cada objeto i, tiene un pero pi, y si se mete en la
mochila produce un beneficio bi
• Objetivo: Llenar la mochila obteniendo el
máximo beneficio:
• Maximizar
sujeto a  p x  C
bx

1i  n
i i
xi  0,1, bi  0, pi  0
1i  n
i i
El problema de la mochila
• Representación
X=(x1, x2,...xn) xi pertenece a (0,1)
!! Pueden haber individuos que no cumplen las restriciones!!
• Función de evaluación:
C
b x
1i  n
b x
1i  n
i i
i i
si
b x
1i  n
en otro caso
i i
C
Problema de la mochila
• Con la función de evaluación eliminamos
las soluciones no factibles
• Se generan individuos de forma aleatoria
• El operador de cruce, se puede usar el
cruce simple
• Se puede seguir el esquema general
Fundamentos de AG
• Esquema: patrón de similitud que describe un
subconjunto de cadenas con similitudes en ciertas
posiciones
• Aumentamos el vocabulario con el símbolo *, en
las posiciones en las que aparece este símbolo
puede haber cualquier elemento del alfabeto
inicial.
• Orden de un esquema O(E): número de
posiciones fijas en él
Fundamentos de AG
• Longitud de un esquema L(E): distancia entre la
primera y la última posición definida en el
esquema
• Cada ristra pertenece a todas las regiones
(esquemas) en las cuales aparece cualquiera de
sus bits
• El número de esquemas procesados útilmente por
un algoritmo genético que maneje una población
de n individuos es del orden de m3. Paralelismo
implícito
Fundamentos de AG
• Aplicación del operador selección: La
probabilidad de seleccionar un cromosoma
perteneciente a un esquema E, viene dada por el
cociente entre la adecuación media de los
representantes de un esquema y la adecuación
media de la población en un instante t.
• m(E,t+1)= m(E,t) . fpro(E)/fpro
• m(E,t) número de representantes del esquema E
en la generación t
Fundamentos de AG
• Aplicación del operador cruce:
• Si A=B No se destruye ningún esquema
• Si el orden del esquema es cero, no será destruido
nunca
• Si la longitud del esquema es uno la probabilidad
de que sea destruido es 1/m-1
• Si la longitud
del esquema es dos
la
probabilidad es 2/m-1. En general L(E)/m-1
• Teniendo en cuenta la probabilidad de aplicar el
cruce Pc L(E)/m-1
Fundamentos de AG
• Aplicación del operador mutación:
• Pm probabilidad de mutación, 1-Pm probabilidad
de que un gen sobreviva
• O(E) . Pm probabilidad de que sobrevivan todos
los de un cromosoma
• Si consideramos un esquema por encima de la
media e%, el efecto del operador reproducción,
en cada generación los esquemas por encima de
la media reciben un incremento exponencial de
sus representantes
• m(E,t+1) = m(E,0)(1+e)t
Fundamentos de AG
• Si consideramos también el efecto del operador cruce y
mutación:
• m(E,t+1) >= m(E,t) . (fpro(E)/fpro ). [1-PcL(e)/(m-1)O(E)Pm
Teorema del esquema:
Los esquemas de longitud corta, orden bajo y adecuación
por encima de la media reciben un incremento
exponencial en subsiguientes generaciones de un
algoritmo genético
Fundamentos de AG
Tutoriales
http://geneura.ugr.es/~jmerelo/ie
http://www.cs.qub.ac.uk/~/M.Sullivan/ga/ga_index.html
http://polaris.lcc.uma.es/~ccottap/semEC/
http://cs.felk.cvut.cz/~xobitko/ga/
http://lisisu02.fis.usal.es/~curdoc7/
Se encuentran un tutoriales sobre algoritmos genéticos, y
direcciones donde se pueden encontrar algoritmos
simples, con los que se puede “jugar” cambiando
parámetros del algoritmo