Un ejemplo de optimización con GA

Así como los genetistas tienen individuos de pruebas, los problemas de optimización (tanto para algoritmos genéticos como para otras técnicas) poseen problemas de prueba. Es decir, problemas ya estudiados que sirven para estudiar el rendimiento de las técnicas a utilizar.

Aquí vamos a tratar de encontrar el máximo global de una función de dos variables que determina una superficie en el espacio. No lo vamos a hacer para un espacio infinito, sino acotado.

La función que vamos a seleccionar es una variante de la función conocida como el Valle de Rosenbock1. Se define como f(x,y)=100(y-x^2)^2+(1-x)^2 y vamos a estudiarla en el intervalo [-2;2] tanto para la dimensión x, como para la dimensión y. A continuación se ve la representación gráfica de la superficie que la función describe en el intervalo estudiado:
vallederosenbrockEl esquema básico de funcionamiento de los algoritmos genéticos se puede resumir en el siguiente diagrama:

esquemabasico

Un algoritmo genético debe poseer los siguientes componentes:

  • Una representación genética para soluciones potenciales.
  • Una forma de crear una población inicial de soluciones potenciales.
  • Una función de evaluación que tome el rol del entorno biológico, calificando los individuos (potenciales soluciones) en términos de su fitness.
  • Operadores genéticos que alteren la composición de la descendencia.
  • Valores para parámetros, como son los siguientes:
    • Tamaño de la población
    • Probabilidad de aplicación de cada operador genético
    • Otros

Paso a paso vamos a ir definiendo nuestro algoritmo genético.

Representación

Tomando el enfoque clásico de algoritmos genéticos, vamos a buscar una forma de representar una posible solución como una riestra de bits. Y aquí nos encontramos con el primer problema: la función está definida en el conjunto de los reales, es decir que x,y \in \mathbb{R}. Y nosotros podemos expresar soluciones en términos de matemática discreta, es decir, enteros (\mathbb{Z}). Entonces conviene cómo vamos a representar esos números reales a partir de riestras de binarios, fijando qué precisión vamos a considerar válida. Tomemos una precisión arbitraria, como por ejemplo 10 decimales. Es decir, discretizamos un contínuo en 1010 slots para ambas dimensiones (x e y). Vale decir, entonces, que para cada dimensión vamos a tener 4 x 1010 valores posibles. Necesitaremos 36 bits de precisión para especificar las variables, ya que:

235 = 3,4359738368 1010 < 4 x 1010 < 236 = 6,8719476736 x 1010

Por tanto necesitaremos 72 bits para representar las variables x e y. Para convertir nuestra representación a decimal, bastaría con aplicar las siguiente fórmulas:

  • x = -2 + x' \dfrac{4}{2^{36}-1}
  • y = -2 + y' \dfrac{4}{2^{36}-1}

Vamos, entonces a definir nuestro cromosoma como un arreglo de bits de logitud 72, portador de dos genes, uno representando a la variable x y otro representando a la variable y. Con la siguiente estructura:

  • Gen x o 1: ubicado en el loci 0, longitud 36 bits.
  • Gen y o 2: ubicado en el loci 36, longitud 36 bits.

Un ejemplo de nuestro cromosoma podría ser la siguiente tira de bits:

010100001101001001101010011010010101010111010000001010100101000101111101

Que representaría una solución que indica que

  • gen x=010100001101001001101010011010010101 (2,1695473301 x 1010 en base 10, es decir que la variable x valdría 0,1695473301)
  • gen y=010111010000001010100101000101111101 (2,4967270781 x 1010 en base 10, es decir que la variable y valdría 0,4967270781)
  • Por tanto la solución (z) tomaría el valor 11,394310437 que surge de aplicar la definición de la función a optimizar.

Población inicial

Hay varias maneras de generar una población inicial. En el enfoque clásico, se utiliza la generación pseudoaleatoria. En enfoques más híbridos, se pueden utilizar salidas de otros algoritmos, como por ejemplo, soluciones que estén en el plano de lo factible. En este caso utilizaremos una población aleatoria.

Función de evaluación

Para evaluar a cada individuo según su fitness utilizaremos una función que tome el cromosoma o arreglo de bits a estudiar y produzca un número real, de tal modo que la función de evaluación sea eval(v) = f(x,y) .

Operadores genéticos

La población de individuos evolucionará en función de dos de los operadores básicos de los GA, a saber, mutación y crossover.

Aquí utilizaremos la versión más simple del operador de mutación, que alterará un gen particular, en una posición particular según una probabilidad de mutación (que es un parámetro de la corrida de los GA). La mutación en si, consiste en la inversión del bit a mutar, es decir, si en la posición concreta hay un 0, se mutará a un 1 y vice versa.

Dentro del operador de crossover hay más posibilidades, todo una gama de operaciones posibles. Aquí utilizaremos la más sencilla, el crossover en un punto. Se toman los dos individuos a cruzar, a saber I1 e I2, siendo, por ejemplo:

I1 = 001011001010000110101010111111111111010101010101010001110101000101101010
I2 =010100001101001001101010011010010101010111010000001010100101000101111101

Suponiendo que el punto de cruce fue la posición 10 (seleccionada al azar, marcada en negrita en los individuos), la descendencia quedaría configurada de la siguiente manera:

I12‘ = 001011001001001001101010011010010101010111010000001010100101000101111101

I12” =010100001110000110101010111111111111010101010101010001110101000101101010

Mecanismo de Selección

Para ser seleccionados para cruzarse, los individuos son sometidos a un mecanismo de selección (en el que intenta analogarse la selección natural), que puede tener muchas variantes. Aquí utilizaremos el enfoque clásico de Ruleta o Selección proporcional. Con este método la probabilidad que tiene un individuo de reproducirse es proporcional a su valor de función de evaluación. Como primer paso es necesario calcular la sumatoria del valor de la función de fitness aplicada a cada uno de los elementos del conjunto que están aptos para ser elegidos. Este será el rango máximo. Luego se calculan los rangos individuales de cada uno de los individuos de la siguiente manera:

  • R0=0
  • R1=eval(v1)
  • R2=R1+eval(v2)
  • ………………..
  • Rn=Rn-1+eval(vn)

De este modo, los rangos se encuentran en el intervalo [0;\sum\limits_{i=1}^n eval(v_{i})], el individuo con más fitness tendrá una amplitud mayor de intervalo, cada individuo tendrá una probabilidad p_{i}=\dfrac{eval(v_{i})}{\sum\limits_{j=1}^n eval(v_{j})} de ser elegido, y obviamente, para la selección se utiliza un numero pseudoaleatorio en el rango [0;\sum\limits_{i=1}^n eval(v_{i})].

Otros Parámetros

El tamaño de la población es fijo a lo largo de la evolución y se ha decidido (arbitrariamente en este caso) establecerlo en 50.

La probabilidad de mutación es de 0,035.

La distribución de probabilidades es uniforme para seleccionar el punto de cruce en la operación de crossover.

La condición de corte no la establecimos, sino que evolucionamos 100 generaciones y nos quedamos con el mejor individuo.

Resultados

La salida del programa ha sido la siguiente:

Solución encontrada en 0.291 segundos.
La mejor solución tiene un fitness de 3609.0
El individuo resultó ser:
x=-2.0
y=-2.0

Es decir, que f(x,y)=3609 siendo (-2,-2) uno de los puntos que estábamos buscando. Sin paralelismo y sin mucha optimización, pudimos resolver el problema en menos de 3 décimas de segundo.

Ahora, veamos cómo fue evolucionando la población: ResumenGeneracionesRosenbockValley

Podemos ver que no hizo falta llegar a las 100 generaciones, ya que en la 66 se encontró el óptimo global que estábamos buscando (al menos uno de los varios que puede haber en la función).

También es posible graficar la evolución del fitness en función del tiempo (generaciones) de la siguiente manera:

analisisvallerosenbrock

En donde podemos observar que hay un incremento importante inicial en el fitness que se ameseta hasta llegar al máximo.

La implementación fue realizada en Java con el framework jgap y maven que ayuda mucho a evitar el infierno de las dependencias, por lo que dejo disponible el código fuente (realmente programé muy pocas líneas… Es casi una vergüenza…)  aquí:

La función de Fitness, en este archivo java: FitnessRosenbockValley

La Aplicación que se ejecuta, en este archivo java: App

El archivo pom.xml de Maven: pom


Notas
1 La idea de utilizar esta función fue tomada del trabajo de Marcin Molga y Czeslaw Smutnicki “Test functions for optimization needs” en el que se analiza un gran catálogo de funciones modelo para analizar desde las técnicas de optimización.

Anuncios

Deje un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s