algoritmos genÉticos...algoritmos genéticos • algoritmos basados en los principios de la...
TRANSCRIPT
![Page 1: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/1.jpg)
ALGORITMOS GENÉTICOS “En lugar de envidiar la naturaleza
debemos emularla” Holland
![Page 2: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/2.jpg)
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
![Page 3: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/3.jpg)
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
![Page 4: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/4.jpg)
Esquema básicoProcedimiento AGInicio
t:=0;inicializar P(t);evaluar P(t);mientras (no condición de terminación) hacer
t:=t+1;reproducir P(t1) en P(t);recombinar P(t);evaluar P(t);
Fin_mientras;Fin.
![Page 6: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/6.jpg)
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• Los cromosomas están compuestos por genes; el valor de
un gen se denomina alelo y a su posición locus
1 0 1 0
![Page 7: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/7.jpg)
Representación
• Cada iteración será una generación; cit = (bi1
t...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:Xi
t=(cit,xi
t,fit)
• xit es la decodificación del cromosoma (fenotipo) y fi
t es la adecuación de la solución
![Page 8: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/8.jpg)
Obtención de la población inicial• Conjunto de individuos de número m, (m parámetro)
P(t)= {Xit,....Xi
t}
• 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 fi
0 lo obtendremos a través de la función de evaluación.
0 1 1 0 1
1 1 0 0 0
0 1 0 0 0
1 0 0 1 1
m = 4
![Page 9: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/9.jpg)
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 xi
t podemos obtener su adecuación fi
t como:
• fit=eval(ci
t)=f(xit)
![Page 10: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/10.jpg)
Función de evaluación
117036119100116480100057624110001691301101
Fitnessfi
Decodificaciónxi
Codificaciónci
fit=eval(ci
t)=f(xit) en este caso f(x) =x2
![Page 11: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/11.jpg)
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 t1 a la generación tLos 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.
![Page 12: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/12.jpg)
Operadores Genéticos: selección y muestreo
1001170
30.93611910011
5.564801000
49.25762411000
14.41691301101
% del totalFitnesscici
1 copia
0 copias
2 copias
1 copia
![Page 13: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/13.jpg)
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
![Page 15: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/15.jpg)
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
1 1 0 0 0
1 0 0 1 11 0 0 0 0
1 1 0 1 1
![Page 16: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/16.jpg)
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
![Page 17: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/17.jpg)
Operadores Genéticos: cruce
![Page 18: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/18.jpg)
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
![Page 19: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/19.jpg)
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: 50100– Probabilidad de cruce: 0.60– Probabilidad de mutación: 0.001
![Page 20: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/20.jpg)
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∑≤≤ ni
ii xb1
Cxpni
ii ≤∑≤≤1
{ } 0,0,1,0 >>∈ iii pbx
![Page 21: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/21.jpg)
El problema de la mochila• RepresentaciónX=(x1, x2,...xn) xi pertenece a (0,1)
!! Pueden haber individuos que no cumplen las restriciones!!• Función de evaluación:
si
en otro caso
∑≤≤
−ni
ii xbC1
Cxbni
ii >∑≤≤1
∑≤≤ ni
ii xb1
![Page 22: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/22.jpg)
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
![Page 23: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/23.jpg)
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
![Page 24: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/24.jpg)
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
![Page 25: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/25.jpg)
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 Een la generación t
![Page 26: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/26.jpg)
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/m1• Si la longitud del esquema es dos la
probabilidad es 2/m1. En general L(E)/m1
• Teniendo en cuenta la probabilidad de aplicar el cruce Pc L(E)/m1
![Page 27: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/27.jpg)
Fundamentos de AG
• Aplicación del operador mutación: • Pm probabilidad de mutación, 1Pm 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
![Page 28: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/28.jpg)
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 ). [1PcL(e)/(m1)
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
![Page 30: ALGORITMOS GENÉTICOS...Algoritmos genéticos • Algoritmos basados en los principios de la evolución natural • Se utilizan en problemas donde no se pueden encontrar soluciones](https://reader035.vdocumento.com/reader035/viewer/2022071114/5feb399aef21305390157183/html5/thumbnails/30.jpg)
Tutoriales
http://geneura.ugr.es/~jmerelo/iehttp://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