AI::EA (OPEAL) Version 0.3


Copyright (c) 2001 J.J. Merelo and J.G. Castellano
Todos los derechos reservados.
Este programa es software libre; puede redistribuirlo y/o modificarlo bajo los términos de la licencia GPL.

EJEMPLO MAREA


Ejemplo Marea: Ejemplo de un Algoritmo Genético sencillo con un vector de valores binarios

El problema a resolver

El comienzo siempre es igual:Tenemos un problema, además ese problema lo queremos resolver usando algoritmos evolutivos. Supongamos que tenemos la función marea cuya expresión matemática es la siguiente:

y cuya gráfica se muestra en la Figura 1. El problema al que nos enfretamos es encontrar las coordenadas (x,y), que maximicen la función f(x,y).


Figura 1:Gráfica de la función "marea".

Si observamos la gráfica de la función (ver Figura 1) la forma de la función va haciendo ondulaciones conforme se acerca a la coordenado (0,0), alcanzando el máximo en dicha coordenada, de forma que f(x,y)=1 para x=y=0.

Elección del tipo de individuo

Una vez conocido el problema a resolver, deberemos decidir es los tipos de datos que usaremos para codificar la solución, en este ejemplo usaremos un vector de 128 bits, donde los primeros 64bits, serán el valor binario de la x y los restantes 64bits, serán la codificación en binario del valor y. Por tanto, de entre los tipos de individuos de OPEAL escogemos VectorIndi que sirve pare representar un vector de valores binarios.

Creación de la función de adecuamiento o fitness

Ya sabemos el tipo de individuo a usar y el problema a resolver, por lo que ahora debemos construir nuestra función de fitness (función de adecuamiento) que mide lo buena que es el individuo, en nuestro ejemplo calculará f(x,y) a partir del individuo de 64bits, cuyos primeros 32bits son para la x y lo restantes 32bits para la y. Vamos a construir nuestra función de fitness en Perl, para nuestro problema y nuestra representación:

 
my $rr = sub {
  #Cogemos el individuo a evaluar
  my $chrom = shift;

  #Pasamos el individuo a una cadena
  my $str = $chrom->Chrom();

  #El fitness (adecuamiento), incialmente, es uno (caso de división por cero)
  my $fitness = 1;

  #extraemos los dos números binarios
  my $l2=length($str)/2;
  my $x=eval("0b".substr ($str, 0, $l2));
  my $y=eval("0b".substr ($str,    $l2));

  #Los normalizamos y los pasamos al rango [0,1]
  my $max=(2 ** ($l2) )-1;
  $x=$x/$max;
  $y=$y/$max;

  #Calculamos la función marea
  my $sqrt=sqrt( ($x*$x) + ($y*$y) );
  $fitness= sin( $sqrt ) / $sqrt  if ($sqrt !=0 );

  #Y devolvemos el fitness calculado
  return $fitness;
};

Si nos fijamos un poco las dos primeras instrucciones que hemos ejecutado en nuestra función de fitness se utilizarán en todas las funciones de fitness que programemos. Con la primera cogemos el individuo a evaluar y con la segunda cogemos el cromosoma del individuo.

Creación de la población inicial

Una vez elegidos el tipo de individuo y construida la función de adecuamiento (fitness). Vamos a contruir la población inicial de individuos que evolucionarán:

#Definimos la población inicial
$numBits=64; #Número de bits a usar 32bits->x 32bits->y
$popSize=100; #Tamaño de la población que será evolucionado, usaremos 100 individuos
my @pop;      #Población de individuos

#Creamos $popSize individuos
for ( 0..$popSize ) {
  my $indi = new BinaryIndi $numBits ; #Creamos individuos aleatorios
  push( @pop, $indi ); #Los añadimos a la población
}

Elección del algoritmo evolutivo y operadores genéticos

Ahora tenemos que decidir el algoritmo evolutivo de OPEAL a usar, escogeremos EZFullAlgo, que es un algoritmo evolutivo simple. Para usar dicho algoritmo tendremos que definir como se realiza una sóla generación de dicho algoritmo, esto lo haremos con EasyAlgorithm.

Para describir una generación del algoritmo, nos hace falta la función de adecuamiento (que ya la tenemos hecha) y especificarle los operadores a usar. Como operadores usaremos la mutación de un sólo bit (MutationOne) y el cruce clásico de dos puntos (Crossover). Entonces quedaría:

  
  #Definimos los operadores de variación
  my $m = new MutationOne; #Cambia a un sólo bit
  my $c = new Crossover; #Cruce en 2 puntos clásico

  #Usamos estos operadores para definir una generación del algoritmo. Lo cual
  # no es realmente necesario ya que este algoritmo define ambos operadores por
  # defecto. Los parámetros son la función de fitness, la tasa de selección y los
  # operadores de variación.
  my $generation = new EasyAlgorithm( $rr, 0.2, [$m, $c] );

Ahora tenemos que especificar el terminador del algoritmo evolutivo, es decir, el objeto que se encarga de decidir cuando termina el algoritmo evolutivo. En nuestro ejemplo vamos a parar cuando lleguemos a 200 generaciones.

  my $term; #Terminador
  my $numGens=200; #Número de generaciones

  $term = new GenerationalTerm  $numGens ; #Utilizamos un terminador generacional

Después de definir el terminador y una vez que tenemos definida una sóla generación, creamos el algoritmo evolutivo (habíamos escogido EZFullAlgo) y lo ejecutamos sobre la población inicial que habíamos construido:

  #Definimos el algoritmo
  my $fullAlgo = new EZFullAlgo  $generation, $term, 1 ;

  #Ejecutamos el algoritmo
  $fullAlgo->apply( \@pop );

Terminando

Y finalmente, en nuestro script, mostramos los resultados:

 #Mostramos los resultados
 print "La mejor solución encontrada es ", $pop[0]->asString(), "\n";

Además necesitamos incluir, al principio, los módulos a usar:

  #Incluimos las librerías de OPEAL que nso van a hacer falta
  use EasyAlgorithm;
  use EZFullAlgo;
  use BinaryIndi;
  use GenerationalTerm;

Finalmente hemos obtenido el fichero marea-tutorial.pl (en este fichero se ha añadido un terminador delta, se permite que ciertos valores se pasen como parámetros y se ha mejorado la presentación de resultados). Y ya lo tenemos. Un Algoritmo Evolutivo que encuentra el máximo de una función matemática, realizado rápidamente. Sólo hemos tenido que programar la función de fitness y elegir el tipo de datos, los operadores y el algoritmo a usar. ¿Puede ser más fácil?