Introducción a los Algoritmos Genéticos

Tomás Arredondo Vidal17/4/09

Esta charla trata de lo siguiente:• Introducción a algunos aspectos de los

algoritmos genéticos.• Introducción a algunas aplicaciones de los

algoritmos genéticos.

Modelo Evolutivo

• Considerando los sistemas evolutivos Holland propuso un modelo de la evolución artificial basados en la evolución y la genética natural.

Modelo Evolutivo

De acuerdo a Holland un sistema evolutivo contiene los siguientes elementos:• E : el ambiente en el cual el sistema se esta

adaptando• τ : un plan evolutivo que determina

modificaciones estructurales en los organismos artificiales

• μ : una medida de la capacidad de diferentes estructuras en el medio ambiente

• En este formalismo el plan evolutivo actúa en tiempos discretos t = 1,2,3,...

Modelo Evolutivo

• La acción del plan evolutivo τ es progresar dentro de un set de posibles estructuras A (genomas) hacia la que tenga la mejor capacidad de sobrevivencia

• A esta conformado por numero de genes en el cual cada gen Ai tiene k alelos

• Ej: = 3, A =A1A2A3k = 2, Ai = 0 o 1

• Numero combinaciones = k = 23 = 8

E

τ

A(1)

A(2)

A(3)Ω(1) Ω(2)

A(t)Ω(t)

• El plan τ va a producir una trayectoria a través de las posibles estructuras A(t) en el tiempo t (t=1, 2,...) a través de la selección de sucesivos operadores Ω(t).

• Cada estructura A(t) tiene asociada una capacidad μ(A(t))

¿Que es un algoritmo genético (GA)?• Los algoritmos genéticos (GA) son algoritmos de

búsqueda y optimización basados en los mecanismos de selección natural y genética.

• Los GA usan los siguientes mecanismos:1. la sobrevivencia de los organismos con mejor capacidad dentro

de una población2. uso de secuencias de caracteres (generalmente 1s y 0s) en

strings como representación del ADN de estos organismos3. el uso de métodos aleatorios (random) para la generación de la

población y para su reproducción

Poblacióngeneración = n

Mecanismo aleatorio de reproducción

Poblacióngeneración = n+1

¿Cómo se reproducen los algoritmos genético (GA)?• Los GA se reproducen usando el siguiente algoritmo:

1. Esquema de codificación de la información de los miembros en strings (ADN de 1s y 0s)

2. Evaluación de capacidad (fitness) de cada miembro3. Selección aleatoria de los miembros que se van a

reproducir 4. Cruce de la información de los miembros

(Crossover) 5. Mutación de la información

¿Condiciones necesarias para la evolución de losalgoritmos genético (GA)?

• Las condiciones necesarias para la evolución son las siguientes:1. Una entidad capaz de reproducirse2. Una población de estas entidades3. Una variedad en la reproducción4. Alguna diferencia en la habilidad para sobrevivir de

los miembros de la población (los mas capaces sobreviven) basada en el medio ambiente

Ejemplo de una máxima local y global

• f(x) = (x^3)*(sin(x))+x+2

-2.78 3.0

máxima local (-2.22,3.58)

máxima global(2.27, 8.11)

Usando métodos basados en derivados (hill climbing) (df/dx)=0 podría resultar que nos quedáramos en la máxima local

Ejemplo de una función mas compleja

222222 )1(53)1(2

31)

5(10)1(3),( yxyxyx eeyxxexyxfz −+−−−+−− −−−−−==

-6-4

-2 0

2 4

6 -6 -4 -2 0 2 4 6

-10

-5

0

5

10

Resumen:• Los algoritmos genéticos (GA) funcionan con una

codificación de parámetros no los parámetros mismos• Los GA son paralelos y evalúan múltiples posibles

soluciones a las vez no en una dirección como los algoritmos basados en derivados (búsqueda lineal)

• Cada miembro de la población es una posible solución,los GA so algoritmos de búsqueda global no local

• Los GA usan funciones de costo no derivadas• Los GA usan métodos estocásticos no determinísticos• Al contrario de los métodos basados en derivados los

GA no tiene un punto singular de búsqueda inicial• Los métodos basados en derivados son mas rápidos ya

que evalúan y buscan en una sola dirección a la vez

Ejemplo: Maximizar una función• Encontrar el máximo de la siguiente función:

f(x) = x2 • Dado que x es representada por 5 bits [1]parte 1: generar población inicial (generación = 1) (tamaño

entre 50 a 100 miembros)(A1) → 01101

(B1) → 11000

(C1) → 01000

(D1) → 10011

Ejemplo (cont):

parte 2: hacer reproducción para obtener nueva población (usando una ruleta)

String Capacidad % Capacidad(A1) → 01101 169 14.4

(B1) → 11000 576 49.2

(C1) → 01000 64 5.5

(D1) → 10011 361 30.9Total 1170 100

B1

A1

D1

C1

Ruleta: Se corre cuatro veces y da:A1, B1, B1, D1

Ejemplo (cont):

parte 3: hacer cruce para obtener nueva generación (se eligen sitios de cruce aleatoriamente)

Strings iniciales: (A1) → 01101 (B1) → 11000 (B1) → 11000 (D1) → 10011 Nuevos Strings (generación = 2) (A2) → 01100

(B2) → 11001

(C2) → 11011

(D2) → 10000

Ejemplo (cont):

parte 4: se introducen mutaciones en la nueva población usando una probabilidad de mutación de cada gen (Ej. pm=.001)

Nuevos Strings (generación = 2) (A2) → 01100

(B2) → 11001

(C2) → 11011

(D2) → 10000 → 11000

Se vuelve a la parte 1 para las siguientes generaciones = 3,4,…

Ejemplo2: Optimización con variables reales.• Max f(x ,y) = 21.5 + x sin(4π x) + sin(20π y)• -3.0 ≤ x ≤ 12.1• 4.1 ≤ y ≤ 5.8

-2 0 2 4 6 8 10 12

4.2 4.4

4.6 4.8

5 5.2

5.4 5.6

5.8

5 10 15 20 25 30 35

Ejemplo2 (cont):

Representación: • si el dominio de la variable xj es [aj, bj] y la precisión

requerida es 5 dígitos después del punto decimal • el rango del dominio debe ser dividido en al menos

(bj- aj)*105 rangos de igual tamaño. Los bits requeridos (mj) serán:

1210*)(2 51 −≤−<− jj mjj

m ab

Ejemplo2 (cont):

Bits necesarios para las variables:

x: (12.1-(-3.0))*10.000=151.000 => 217 <151000 ≤ 218=> m1=18

y: (5.8 - 4.1)*10.000=17.000 => 214 < 17.000 ≤ 215=> m2=15

Longitud Total del cromosoma : m1 + m2 = 33 bits.

000001010100101001 101111011111110 18 15

Ejemplo2 (cont):

Conversión de string a un número real:

Número Binario Número Decimalx 000001010100101001 5417y 101111011111110 24318

x = -3.0 + 5417 * [12.1 – (-3.0)] / [218 – 1] = -2.687969y = 4.1 + 24318 * [5.8 – 4.1] / [215 – 1] = 5.361653

12*)(

−

−+=

jm

jjjj

absubstringdecimalax

Ejemplo2 (cont):

Algoritmo

Parte 1: Crear Población Inicial Aleatoria• generacion = 1

V1= [000001010100101001101111011111110]V2= [001110101110011000000010101001000]...V50= [111000111000001000010101001000110]

Corresponde a:V1= [x1,x2]= [-2.687969, 5.361653]V2= [x1,x2]= [0.474101, 4.170144]...V50= [x1,x2]= [10.419457, 4.661461]

Ejemplo2 (cont):

Parte 2: Evaluación de capacidadf(x ,y) = 21.5+ xsin(4π x) + sin(20π y)

Eval(v1) = f(-2.687969, 5.361653) = 19.805119Eval(v2) = f(0.474101, 4.170144) = 17.370896...Eval(v50) = f(10.419457, 4.661461) = 9.590546

Ejemplo2 (cont): Parte 3: Selección de Cruces basado en Evaluación de capacidad y

RuletaParte 4: Mutación• Iterar para generaciones = 2, 3, ...

Cuando parar iteraciones: Hay varias condiciones posibles para parar iteraciones, algunas de ellas son: cuando generaciones sean un valor determinado cuando evaluación da un porcentaje del máximo valor deseado cuando capacidad máxima no cambia mucho en porcentaje muchas otras posibilidades!

Ejemplo3: Optimización de rutas en redes WDM.• Definir conjunto de rutas que permite la comunicación

entre todos los nodos deseados en una red• Hay muchas posibles opciones por ejemplo entre (0,3):

0-1-3, 0-2-3, 0-4-2-3• La idea es optimizar las rutas entre los nodos para

minimizar el costo total de conexión de la red

0 1 3

24

Ejemplo3 (cont):

Representación: • cada individuo de la población codifica todas la rutas

usadas por los m nodos de la red • se utiliza un arreglo de 2 dimensiones, la primera

dimensión indica el numero de la ruta• la segunda indica todos los nodos usados en esta ruta• el arreglo completo denominado padres contiene todos

los individuos de la población

Ejemplo3 (cont):

• los pares de nodos de inicio y termino en una ruta (nodo1 y nodo2) se generan de acuerdo al código:

for(j = 0 ; j < (m*m) - m ; j++) nodo1 = j/(m - 1); nodo2 = (j/(m - 1) > j%(m - 1)) ? j%(m - 1) : (j%(m - 1) + 1);• para m=5 los pares de nodos generados son: (0,1),

(0,2), (0,3), (0,4), (1,0), (1,2), (1,3), (1,4), (2,0), (2,1), (2,3), (2,4), ..., (4,0), (4,1), (4,2), (4,3)

Ejemplo3 (cont):

• Por ejemplo, una población de 6 individuos (con m = 5) y las rutas para el primer individuo

padres [ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ]

[0 1 2 3 4 5 ... 19]

[ 0 ][ 4 ][ 1 ][-1 ][ ][ ]

[ 0 ][ 2 ][-1 ][ ][ ][ ]

[ 0 ][ 4 ][ 1 ][ 3 ][-1 ][ ]

[...] [...] [...] [ 4 ][ 1 ][ 3 ][-1 ][ ][ ]

Fin de la rutas indicada por un -1

(0,1) (0,2) (0,3) (0,4) (1,0) (1,2) (4,3)

Max población

Para el primer individuola ruta (0,1) es 0-4-1

Ejemplo3 (cont):

Algoritmo:1- Crear población de padres inicial aleatoria, utiliza:

elegir_ruta(m , nodo1, nodo2, matriz, padres[i][j], tipo_nodo, file_results);

2- Evaluar fitness de cada miembro de la población:fit[i].val = fitness(padres[i] , m , beta, Nl, Ll);

3- Imprimir promedio, mejor y peor fitness4- Generar ruleta usando metodo Fitness Proportionate: ruleta[0] = fit[0].val / fit_total; for (i = 1 ; i < tamPobla ; i++) ruleta[i] = ruleta[i - 1] + (fit[i].val / fit_total);

Ejemplo3 (cont):

5- Elegir pares a cruzar (i1 e i2) usando ruleta: for(i = 0 ; i < tamPobla/2 ; i++) indiv1 = aleatorio(); indiv2 = aleatorio(); for(i1 = 0 ; indiv1 >= ruleta[i1] ; i1++); for(i2 = 0 ; indiv2 >= ruleta[i2] ; i2++);

6

34

5

...

i1=3

18

1516

17

...

i2=15

Ejemplo3 (cont):

5(cont)- Cruzar pares seleccionados (i1 e i2) si aleatorio( ) es menor que probCruce (0 < probCruce ≤ 1):

for(i = 0 ; i < tamPobla/2 ; i++)

... for(j = 0 ; j < (m*m - m) ; j++) copiar_ruta(padres[i1][j] , hijos[2*i][j] , m); for(j = 0 ; j < (m*m - m) ; j++) copiar_ruta(padres[i2][j] , hijos[2*i + 1][j] , m); if(aleatorio() < probCruce) cruce(hijos[2*i] , hijos[2*i + 1] , m);

Nota: cruce( ) intercambia todas las rutas entre los pares

Ejemplo3 (cont):

6- Hacer mutación:for(i = 0 ; i < tamPobla ; i++) if(aleatorio() < probMut) mutacion(hijos[i] , matriz , m, tipo_nodo, ...);Nota: mutación llama elegir_ruta(...) para mutar cada rutasi aleatorio() < P_MUTAC

7- Si quedan iteraciones por ejecutar volver al paso 28- Determinar el fitness del mejor individuo9- Imprimir rutas del mejor individuo

Schema (o Esquema o Molde):• Para analizar las características de los AG se introducen don’t care

bits usando el simbolo * para crear esquemas (schemata) usando el alfabeto 0, 1, *

• Un esquema explícitamente reconoce las similitudes en una población de strings y eso ayuda en el análisis de los AG.

• Entonces, un esquema es un aparato para reconocer patrones:

*0000 → 10000, 00000*111* → 01110, 11110, 01111, 11111

Con estos bits se seleccionan todos los strings quecorresponden a don’t care bits

Teorema Fundamental:

Let A = string binario (A=a1a2a3a4a5a6a7) an = 0 o 1 (alelos)

then A’=a5a4a1a2a3a6a7 (nuevo orden)

Definicionesan → un genAi → un string en una poblaciónA → una poblaciónA(t) → una población en una generación especifica

Teorema Fundamental (cont):

Orden del esquema o(H): El orden de la esquema H es el numero de posiciones fijas presentes en una esquema.

O(011*1**) = 4

Distancia definitoria del esquema δ(H): La distancia entre la primera y ultima posición definitivaδ(011*1**) = 5 – 1 = 4

Teorema Fundamental (cont):

Asumamos que los strings son copiados a la nueva generación con una probabilidad basada en su valor de capacidad (fitness fi) dividida por la total capacidad en la generación (fitness proportional reproduction):

∑=i

iip if/f

Teorema Fundamental (cont):

Asumamos que m es el numero de copias de un esquema en una población de tamaño n en particular en la generación t → m(H,t)

Nota: f(H) es la capacidad promedio de todos los strings que corresponden al esquema H en la generación t

Entonces en promedio,

ff(H)nt)m(H, 1)tm(H,

i∑××=+

i

Teorema Fundamental (cont):

Si es la capacidad promedio de la población completa,

Entonces,

f

ii n/f∑=i

f

f / f(H))t)(m(H, 1)tm(H, ×=+

Teorema Fundamental (cont):Para ver cuales esquemas son afectados por un cruce y cuales no los son, consideren un string y dos esquemas asociados que lo representan ( = 7).A = 0 1 1 1 0 0 0H1 = * 1 * * * * 0H2 = * * * 1 0 * *Si ocurre un cruce en la posición 3 y el material genético a la izquierda del cruce es intercambiado se ve que el esquema no sobrevive el cruce…

Teorema Fundamental (cont):B = 0 0 0 1 0 0 0A = 0 1 1 1 0 0 0H1 = * 11 * * * * 0H2 = * * * 1 0 * *

Si ocurre un cruce en la posición 3 (entre A y B por ejemplo)el material genético a la izquierda del cruce es intercambiado se ve que el esquema H1 no sobrevive elcruce porque tiene un elemento fijo (el 1) que va a ser intercambiado por un 0 en el string B

Teorema Fundamental (cont):

Basado en el ejemplo previo se ve que no es muy difícil generalizar esta situación ya que mientras mas largo es el esquema (el valor de δ(H) vs ) mas pequeñas son las probabilidades de sobrevivencia.pd = δ(Hx)/(-1) y ps = 1- pd = 1 - δ(Hx)/(-1)

mas generalmente (incluyendo la probabilidad de cruce pc

que es siempre de 0 a 1)ps = 1 - pd ≥ 1 - δ(Hx)/(-1) pc

Teorema Fundamental (cont):

Entonces:

Llegamos a la conclusión del teorema fundamental que es una versión analítica de algo que ya sabíamos intuitivamente y que combina los efectos de reproducción y cruce en el numero de un esquema en la próxima generación considerando su estado en la generación actual.

1-(H)p - 1 p - 1 p c

ds

δ≥=

−≥+

1)(p-1 f(H) t)m(H, 1)tm(H, c

Hf

δ

Teorema Fundamental (cont):

Finalmente incluyendo la probabilidad de mutación pm y considerando que mientras mas posiciones fijas tiene el esquema (o(H)) mayor es la probabilidad de que sea destruido. Para que sobreviva un esquema todas las posiciones fijas tienen que sobrevivir, dado que la mutaciones son estadísticamente independientes obtenemos la probabilidad de sobrevivir una mutación de (1 – pm)o(H) .Para valores pequeños (pm << 1) se aproxima con 1 – o(H) pm

El resultado final [1] se denomina Teorema Fundamental de los AG:

−

−≥+ mc p)(

1)(p-1 f(H) t)m(H, 1)tm(H, HoH

f

δ

Teorema Fundamental (cont):

• En el siguiente ejemplo se ve como de acuerdo a mf(H1)/ del esquema H1 se espera que sobrevivan 3.2 esquemas después del cruce. • El promedio de la capacidad del esquema es:

f(H1) = (576 + 361)/2 = 468.5• El promedio de fitness de la población es:• Multiplicando por el numero de esquemas H1 en el

tiempo t (m(H1,t) = 2) obtenemos • m(H1,t+1) = m(H1,t)f(H1)/ = (2*468.5)/293 = 3.2

f

293=f

f

Teorema Fundamental (cont):

• También basado en δ(H1) = 0 se ve que el cruce no afecta ni un bit.

• Por ultimo con un Pm = 0.001 se que deberíamos tener m * Pm = 3 * 0.001 = 0.003 bits afectados (o sea probablemente ninguno en este caso).

Paralelismo en la búsqueda:

El siguiente grafico ilustra el paralelismo en los esquemas en la búsqueda de soluciones de los algoritmos genéticos.

B = 1 0 0 A = 1 0 1 H1 = 11 * *

010

001100

Algunos ejemplos de aplicaciones:

• Diseño de controlador PID usando GA [3]• Diseño de controlador difuso usando GA [3]• Navegación robótica usando GA [3], [4]• Calibración de imágenes usando GA [4]• Diseño de controlador H2 usando GA [4]• Generación de datos de prueba para programas usando GA [4]• Minería de datos usando GA [4]• Optimización de red neural usando GA [4]

Referencias:[1] Goldberg, D., Genetic Algorithms in Search, Optimization and

Machine Learning, Addison Wesley, NY, 1989[2] Holland, J., Adaptation in Natural and Artificial Systems, MIT

Press, 1995[3] Jamshidi, M., et al., Robust Control Systems with Genetic

Algorithms, CRC Press, Boca Raton, 2001[4] Karr, C., Freeman. L, Industrial Aplications of Genetic

Algorithms, CRC Press, Boca Raton, 2001