3.- Habrá diferentes posibles soluciones (cadenas de bits que representan la información codificada de los parámetros). ¿Cómo se realizan? (Gp:) 000100011 (Gp:) 000111011 (Gp:) 000101111 (Gp:) 110100011 (Gp:) 000100000
4.- Debemos asociar una función de idoneidad o "fitness" a cada una de estas posibles soluciones. ¿Cómo se realizan? "Fitness" = 0.0 Solución x ¿sobrevive?
4.- Debemos asociar una función de idoneidad o "fitness" a cada una de estas posibles soluciones. ¿Cómo se realizan? "Fitness" = 0.0 No sobrevive
ESTRUCTURA DEL SGA 1.- Generar al azar N "individuos". 2.- Calcular la eficacia de cada individuo de la población. 3.- Elegir 2 progenitores de modo que la probabilidad de ser elegido (dejar hijos) sea directamente proporcional a la eficacia ("fitness proportionate selection"). 4.- De cada par de padres obtener 2 hijos mediante recombinación. 5.- Repetir el paso 3 hasta alcanzar el tamaño poblacional N. 6.- La nueva población sustituye a la antigua. 7.- Mutar e iterar desde el paso 2 usando esta nueva población. Algoritmo Genético Simple (SGA)
1.- En cada generación los individuos dejan descendencia en función del valor medio de la población.
2.- El tamaño poblacional N permanece constante. Características del SGA
Para usar algoritmos genéticos debemos codificar las distintas soluciones de modo que sea posible hacer que evolucionen (recombinen y muten). Características del SGA
Poner en pseudocódigo (independiente del lenguaje de programación) el SGA para un problema de 8 bits (longitud del cromosoma) Ejercicio 1
0.- Declarar e inicializar variables. Ejercicio 1
1.- Generar al azar N individuos (N < < 28)
Para i= 1 hasta N individuo[i]=parte entera de[uniform()× 28] Ejercicio 1
2.- Calcular la eficacia de cada individuo de la población y la media poblacional
Para i= 1 hasta N eficacia[i] = ObtenEficacia(individuo[i]) sumEficacia += eficacia[i] Ejercicio 1
3, 4 y 5.- Elegir padres y obtener N hijos
Repetir hasta obtener N hijos padre1 = ObtenPadre() padre2 = ObtenPadre() //obtener 2 hijos mediante recombinación: recombina(padre1,padre2,hijo1,hijo2) Ejercicio 1
6.- La nueva población sustituye a la vieja
Para i= 1 hasta N individuo[i] = hijo[i] Ejercicio 1
7.- Mutar y volver al paso 2 hasta terminar las generaciones o alcanzar un valor especificado (p. ej. eficacia promedio = 1) muta(poblacion) // poblacion es un vector de N individuos Ejercicio 1
1.- Binaria: Cada alelo de un cromosoma consta de 0/1. 2.- Real: Cada alelo es un nº real. 3.- Longitud fija: Cromosomas de n bits 4.- Longitud variable: Reales o binarios Métodos de representación
1.- Selección proporcional (a la eficacia): A mayor eficacia probabilidad de más hijos (no es determinista).
2.- Selección por torneo: Se seleccionan q soluciones y gana la mejor. Se repite el proceso hasta generar N nuevos hijos.
3.- Selección por rango: Se ordenan las soluciones según su valor de fitness.
4.- Estrategia evolutiva (? + ?)ES: Se seleccionan determinísticamente ? soluciones de un total de ? paternas + ? hijos. Métodos de selección
Existen distintos métodos para realizar la recombinación:
1.- Entrecruzamiento de 1 punto: Sólo un punto de cruce.
2.- Entrecruzamiento de n puntos: Se usa bastante con n = 2
3.- Entrecruzamiento uniforme: El nº de puntos no está fijado. La decisión de insertar un punto de ruptura es independiente para cada bit del cromosoma. Métodos de recombinación
Para cada individuo i se calcula el valor de la función de idoneidad o función objetivo (la que queremos maximizar) f(i)
Sea fprom(t) la media de las funciones de idoneidad de la población en la generación t
La fitness del individuo i será w(i) = f(i) / fprom(t)
Cálculo de la eficacia de un individuo
¿Por qué funcionan los AGs? Esquema: Subconjunto de cadenas con similitudes en ciertas posiciones (1 # # 0). Orden de un esquema: El nº de alelos definidos en él. Longitud de un esquema: La distancia entre el primero y último de los alelos especificados.
¿Por qué funcionan los AGs? Teorema Fundamental de los AGs (de los esquemas): Esquemas cortos, de orden bajo y con eficacia por encima de la media, incrementan el nº de representantes en las generaciones sucesivas de un AG.
Problemas de los AGs Decepción: Algunos esquemas cortos y de bajo orden pueden engañar al algoritmo y hacerle converger en soluciones subóptimas.
Problemas de los AGs Función decepcionante: Cuando existen esquemas cortos de bajo orden y alta eficacia que no proporcionan la solución óptima.
Problemas de los AGs Epistasis: No independencia en el efecto de los distintos genes (bits) sobre el valor de eficacia del individuo. Existen diferentes modos de medir la epistasis de una codificación (ej: varianza de la epistasis, Davidor 1991).
Escribir en C o en otro lenguaje de programación una función que cuente el nº de 1's en una cadena de 8 bits Ejercicio 2
double d_obtenUnos(int cromosoma, int nbits) {/* Devuelve un valor mayor cuantos más 1's tenga el cromosoma */ /*variables*/ int pos, sumUnos=0,control=1; for(pos=0;pos< nbits;pos++){ // para todas las posiciones // identifica si hay un 1 en la posición pos y lo cuenta if(control&cromosoma) sumUnos++; control =control< < 1; // sucesivas potencias de 2 } return ((double)sumUnos); } Código : Valor del individuo
Escribir en C una subrutina que realice la recombinación uniforme y libre (misma probabilidad en todas las posiciones) entre 2 cadenas de n bits Ejercicio 3
void v_Rec(int padre1,int padre2,int *hijo1, int *hijo2, int nbits) { /* Entrecruzmiento Uniforme: Recombinación libre (pr = 0.5) entre padre1 y 2 para producir hijos 1 y 2 */ long int EE, FF, maxval= (1< < nbits)-1; EE = i_getbin(nbits); // obtiene un nº al azar entre 0 y 2nbits FF = ~EE; // obtiene los bits complementarios de EE FF = FF&maxval; // pone a 0 todos los bits a la izq de maxval *hijo1 = (EE&padre1|FF&padre2); *hijo2 = (EE&padre2|FF&padre1); } Código: Recombinación
Escribir en C una rutina que, dada una tasa de mutación por individuo y locus, genere los mutantes de la población. Ejercicio 4
void muta(int *indiv,int N,int nbits, double mu) {/* Genera el nº de mutantes de la población para una tasa de mutación mu dada */ /*variables*/ int NumMut, mut, mutante, locus=1; double tasa; tasa=(double)N*(double)nbits*mu; NumMut =poison(tasa); // opcionalmente: NumMut = (int)tasa if(NumMut){ // si hay al menos un mutante. for(mut=0;mut< NumMut;mut++){ mutante=(int)(N*uniform());//elige 1 individuo posicion=(int)(nbits*uniform()); //elige 1 locus /* ponemos un 1 en la posición :*/ locus=1< < posicion /* con el OR exclusivo ^ mutamos */ indiv[mutante]=indiv[mutante]^locus; } } } Código: Mutación
SELECCIÓN La ruleta de la selección "roulette wheel selection": Las ranuras de la ruleta tendrán un tamaño porporcional a la eficacia de cada individuo.
SELECCIÓN w1 w2 w3 w4 w5 w6 w7 w8 T = ?wi 0 T w1
SELECCIÓN Elegir un nº j al azar entre 0 y T
SELECCIÓN w1 w2 j
SELECCIÓN Recorremos los valores de fitness wi de cada individuo desde 0 hasta N
SELECCIÓN Si la probabilidad acumulada de wi es mayor que j elegimos a i como padre sino pasamos a i+1
SELECCIÓN w1 w2 w1 + w2 j
Escribir en C una rutina que, obtenga hijos en proporción a la fitness de los padres (selección porporcional). Ejercicio 5
// Código para elegir un padre (recordar que un padre es un nº entero): j=(int)(cT*uniform()); // cT es la suma de todas las fitness for(cSum=0.0, ci=0; ci< Nini; ci++){ cSum+=Cw[ci]; // seleccionar el individuo cuyo valor incrementa la suma más allá del límite j: if(cSum>=j){ padre=individuo[ci]; break; // salimos del bucle for } }
Código: Selección proporcional
Obtener, a partir de 4 cadenas obtenidas al azar, la cadena de 8 bits con mayor nº de unos (función objetivo) Problema 1
1.- Generar al azar una pob de 4 individuos (4 números enteros) 2.- Calcular la fitness de cada uno y la fitness total de la población 3.- Elegir 2 padres usando el método de selección proporcional 4.- Obtener 2 hijos mediante recombinación (libre) 5.- Volver al punto 3 hasta alcanzar el tamaño de población N 6.- La nueva población sustituye a la antigua 7.- Mutar y volver a 2 hasta alcanzar Max generaciones o una solución con fitness 1 (8 unos, la solución buscada) Problema 1 Pistas:
Paso de binario a decimal:
b2b1b0,b-1 = (22 × b2)+ (21 × b1)+ (20 × b0)+ (2-1 × b-1)
Ej: Pasar a decimal el nº binario 1010,01 Sistemas de numeración
Paso de decimal a binario: Para obtener la parte entera dividimos entre 2 sucesivamente hasta que el resultado sea 1 o 0. El nº binario buscado es el último resultado obtenido seguido de todos los restos de las sucesivas divisiones. Sistemas de numeración
Paso de decimal a binario: Para obtener la parte decimal multiplicamos por 2 sucesivamente, si el resultado es menor que 1 ponemos un 0 sino ponemos un 1. En este último caso restamos 1 y continuamos. El nº binario buscado es la ristra de 0's y 1's. Ej: Pasar 10,25 a binario Sistemas de numeración
Codificar reales con enteros binarios
Pasos para obtener desde un nº binario un nº real con una precisión y rango dados:
1.- Pasar la cadena binaria a un nº en base 10 2.- Hallar el nº real correspondiente al dominio [-1..2] y con la precisión pedida (ej. 6 dígitos tras el punto decimal)
Codificar reales con enteros binarios ¿Cuántos bits necesitamos?
Longitud del dominio [-1..2] = 3. Para obtener una precisión de 6 dígitos debemos dividir el rango en 3 ×106 rangos de igual tamaño. 221 < 3 ×106 < 222 nbits = ceil(log2(rango × 10precision)) =22
Codificar reales con enteros binarios Sea la cadena bn.b2b1b0
Obtenemos el entero positivo x' en base 10 Obtenemos el real x en el dom [-1..2] tal que
x = inf + x' long / (2nbits -1 ) = -1 + x' 3 / (222 -1 )
Problema 2 Dada la función f(x) = xsen(10?x) + 1.0 encontrar el valor de x perteneciente a [-1..2] que maximice la función. Se pide una precisión de 6 decimales tras el punto.
Problema 2 El valor f(x) será el valor de eficacia. A mayor f(x) mayor nº de hijos dejará un individuo x. La mutación y recombinación son las ya vistas para una cadena de bits.
Problema 2 Escribir la función que obtiene la fitness para este problema: La función de obtención de la fitness será simplemente la función que pase una cadena binaria al correspondiente nº real x y calcule f(x).
Problema 2 Lo que resta es muy similar a lo hecho para el problema 1.
1.- Generar al azar una pob de 4 individuos (4 números enteros) 2.- Calcular la fitness de cada uno y la fitness total de la población 3.- Elegir 2 padres usando el método de selección proporcional 4.- Obtener 2 hijos mediante recombinación (libre) 5.- Volver a 3 hasta alcanzar el tamaño de población N 6.- La nueva población sustituye a la antigua 7.- Mutar y volver a 2 hasta alcanzar Max generaciones o una solución con fitness media mayor que una dada (conviene ir guardando la mejor solución encontrada). Problema 2 Pistas:
APLICACIONES EN BIOLOGÍA Diseño de cebadores usando algoritmos genéticos.
El diseño de primers es una tarea tediosa en la que hay que tener en cuenta diversas restricciones APLICACIONES EN BIOLOGÍA
Reglas generales para el diseño de primers APLICACIONES EN BIOLOGÍA
APLICACIONES EN BIOLOGÍA PARÁMETROS A CONSIDERAR
Tamaño del oligonucleótido: 20-25 nt
Temperatura de fusión (Tm): Tm = 2(A+T) + 4(G+C) Fórmula de Wallace. Tm = 59.9 + 0.41 (%G+C) – 675/tamaño
Especificidad: En general, una temperatura de fusión de 55°C -72°C es la más adecuada (Corresponde a un tamaño de oligonucleótido de 18-24 bases según la regla de Wallace).
Bibliografía Davidor, Y. 1991. Epistasis variance: a viewpoint on GA-hardness. In Rawlins, G. (ed.), Foundations on Genetics Algorithms, Morgan Kauffman, Berlin, 23-25.
Michalewicz, Z. 1996. Genetic Algorithms + Data Structures = Evolution Programs, Springer Verlag.
Mitchell, M. 1996. An Introduction to Genetic Algorithms, MIT Press, Massachusetts.
Whitley, D. 2000. An overview of evolutionary algorithms: practical issues and common pitfalls.
| Página siguiente |