Algoritmos Genéticos en Java utilizando JGAP (teoría y ejemplo)

Salandrews · 11 Dic 2010

Que tal compañeros, desde hace rato cargo la idea de compartir con ustedes algunos temas, pero hasta hoy me decidí.

Vamos a tratar el tema de los algoritmos genéticos.

Teoría

Los algoritmos genéticos se basan en la teoría de la evolución de Darwin, en pocas palabras: "solo los individuos más fuertes sobreviven".

Recordemos que un algoritmo es una serie de pasos que nos lleva a resolver un problema o a alcanzar un objetivo.

Entonces, ¿qué es un algoritmo genético (AG de ahora en adelante)?

Un AG es un algoritmo que "produce" una serie de individuos que representan una solución a nuestro problema u objetivo por alcanzar. Dichos individuos no siempre serán la mejor solución, por lo que a través de iteraciones, el algoritmo hace que dichos individuos "evolucionen", con la idea de que cada "generación" de individuos sea mejor que su predecesora, y cuando el algoritmo termine o converja, tengamos un individuo que tal vez no sea la solución óptima, pero si una solución muy aceptable.

Técnicamente, el AG es un problema para resolver búsquedas. Es utilizado principalmente en problemas que no tienen un procedimiento definido para resolverlos.

¿Como se producen las nuevas generaciones?

El AG comienza con una primera generación compuesta de individuos generados al azar.

Estos individuos son evaluados por una función de aptitud, que determina que tan bien un individuo resuelve el problema. Luego, dicha función asigna un valor real a cada individuo.

Ahora, en base a su valor de aptitud los individuos tendrán una probabilidad de ser seleccionados como padres de la siguiente generación. Como ya mencionamos que el AG esta basado en la teoría de la evolución de Darwin, los individuos con mejor valor de aptitud tendrán una probabilidad mayor de ser seleccionados que los individuos con menor valor de aptitud.

Cuando tengamos a los individuos seleccionados, los podemos "cruzar" o "mutar" para obtener nuevos individuos que conformarán nuestra siguiente generación. Si al cruzar a los padres obtenemos hijos con mejor valor de aptitud que ellos, los hijos pasan a formar parte de la nueva generación, en caso contrario, pasamos los padres a la siguiente generación. Luego de muchas generaciones, posiblemente obtengamos a un "superindividuo" que será la mejor solución a nuestro problema.

Ejemplo
Cuadrado mágico de 3x3

Vamos a programar un AG para que resuelva un cuadrado mágico de 3x3. Aunque podemos programar el AG a mano, vamos a utilizar una librería JGAP que se toma la molestia de realizar todo lo anterior por nosotros.

Codificación

Lo primero que debemos hacer, es codificar nuestro problema. Veamos ejemplos de individuos que resuelven el cuadrado mágico:

1 4 5
3 3 8
3 4 9

Este es un individuo realizado al azar. Un cuadrado mágico es aquel cuya suma de casillas es el mismo (15, para un cuadrado de 3x3), para todas las direcciones (horizontales, verticales y diagonales), y además, los valores de sus casillas no pueden repetirse. Para el caso del cuadrado de 3x3, tenemos valores entre 1 y 9.

Veamos mas individuos:

1 4 5
7 3 8
2 4 9

1 1 2
2 3 8
3 4 2

Nos podemos dar cuenta que estos individuos están compuestos por 9 casillas, en cada una de ellas puede ir un valor entre 1 y 9.

En un AG, a la cadena de casillas se le llama cromosoma (y representa al individuo), y a los valores que pueden ir en cada casilla se les llaman genes (los valores entre 1 y 9).

Por ejemplo, para este individuo:

1 1 2
2 3 8
3 4 2

Su cromosoma sería:

c1 c2 c3 c4 c5 c6 c7 c8 c9
3 4 2 2 3 8 1 1 2

Suponiendo que vemos las casillas así:

c7 c8 c9
c4 c5 c6
c1 c2 c3

Entonces, ya tenemos la codificación de nuestro cromosoma.

Función de aptitud

Para la función de aptitud, tendremos una variable llamada fitness que será el valor de aptitud que se le otorgue a cada individuo.

La función de aptitud depende completamente de nosotros, y el éxito de un AG depende de dicha función. JGAP lo hace casi todo por nosotros, excepto esta parte, que es donde debemos aplicar nuestra imaginación.

Vemos que tenemos ciertas restricciones:
1. Solo pueden haber valores entre 1 y 9
2. No se pueden repetir casillas
3. La suma de las horizontales debe ser 15
4. La suma de las verticales debe ser 15
5. La suma de las diagonales debe ser 15

Si todas las restricciones anteriores se cumplen para un individuo, entonces posiblemente tengamos al individuo solución.
En este caso vamos a crear funciones que sumen las horizontales, verticales y diagonales, y si dan un valor de 15, sume 15 a la variable fitness. Además, vamos a crear una función que busque valores repetidos. Por cada valor que no se encuentre repetido, vamos a sumar 5 a la variable fitness. Estos valores que sumamos a la variable fitness dependen de nosotros, en mi caso los decidí al azar.

Programación

Este programa lo hice en Nebteans. Creamos un proyecto nuevo (AG_CuadradoMagico en mi caso).

Primero, debemos importar el jar de JGAP. Lo podemos descargar de acá, para este ejemplo utilicé la versión 3.4.4. Una vez descargado, descomprimimos e importamos el jar de JGAP a nuestro proyecto.

Ahora, creamos una clase llamada funcionAptitud. Así:

Código:

package ag_cuadradomagico;

/**
 *
 * @author Salandrews
 */

import org.jgap.FitnessFunction;
import org.jgap.IChromosome;

public class funcionAptitud extends FitnessFunction {

    private double fitness; //La variable que llevará el valor de aptitud

    public funcionAptitud()
    {
        fitness=0;
    }

     @Override
    public double evaluate(IChromosome cromosoma){


        evaluarHorizontal1(cromosoma);
        evaluarHorizontal2(cromosoma);
        evaluarHorizontal3(cromosoma);

        evaluarVertical1(cromosoma);
        evaluarVertical2(cromosoma);
        evaluarVertical3(cromosoma);

        evaluarDiagonal1(cromosoma);
        evaluarDiagonal2(cromosoma);

        verificarRepetidos(cromosoma);

        return fitness;
    }

     //Funciones

    public void verificarRepetidos(IChromosome cromosoma)
    {
        //Verificamos que el valor de una casilla no se encuentre repetido, si es asi sumamos 5, sino no se suma nada

        Integer c1= (Integer)cromosoma.getGene(0).getAllele();
        Integer c2 = (Integer) cromosoma.getGene(1).getAllele();
        Integer c3 = (Integer) cromosoma.getGene(2).getAllele();
        Integer c4= (Integer)cromosoma.getGene(3).getAllele();
        Integer c5 = (Integer) cromosoma.getGene(4).getAllele();
        Integer c6 = (Integer) cromosoma.getGene(5).getAllele();
        Integer c7= (Integer)cromosoma.getGene(6).getAllele();
        Integer c8 = (Integer) cromosoma.getGene(7).getAllele();
        Integer c9 = (Integer) cromosoma.getGene(8).getAllele();


        if ((((c1.compareTo(c2)!=0) && (c1.compareTo(c3)!=0)) && ((c1.compareTo(c4)!=0) && (c1.compareTo(c5)!=0))) && (((c1.compareTo(c6)!=0) && (c1.compareTo(c7)!=0)) && ((c1.compareTo(c8)!=0) && (c1.compareTo(c9)!=0))))
        {
            fitness=fitness+5;
        }

        if ((((c2.compareTo(c1)!=0) && (c2.compareTo(c3)!=0)) && ((c2.compareTo(c4)!=0) && (c2.compareTo(c5)!=0))) && (((c2.compareTo(c6)!=0) && (c2.compareTo(c7)!=0)) && ((c2.compareTo(c8)!=0) && (c2.compareTo(c9)!=0))))
        {
            fitness=fitness+5;
        }
        if ((((c3.compareTo(c2)!=0) && (c3.compareTo(c1)!=0)) && ((c3.compareTo(c4)!=0) && (c3.compareTo(c5)!=0))) && (((c3.compareTo(c6)!=0) && (c3.compareTo(c7)!=0)) && ((c3.compareTo(c8)!=0) && (c3.compareTo(c9)!=0))))
        {
            fitness=fitness+5;
        }
        if ((((c4.compareTo(c2)!=0) && (c4.compareTo(c3)!=0)) && ((c4.compareTo(c1)!=0) && (c4.compareTo(c5)!=0))) && (((c4.compareTo(c6)!=0) && (c4.compareTo(c7)!=0)) && ((c4.compareTo(c8)!=0) && (c4.compareTo(c9)!=0))))
        {
            fitness=fitness+5;
        }
        if ((((c5.compareTo(c2)!=0) && (c5.compareTo(c3)!=0)) && ((c5.compareTo(c4)!=0) && (c5.compareTo(c1)!=0))) && (((c5.compareTo(c6)!=0) && (c5.compareTo(c7)!=0)) && ((c5.compareTo(c8)!=0) && (c5.compareTo(c9)!=0))))
        {
            fitness=fitness+5;
        }
        if ((((c6.compareTo(c2)!=0) && (c6.compareTo(c3)!=0)) && ((c6.compareTo(c4)!=0) && (c6.compareTo(c5)!=0))) && (((c6.compareTo(c1)!=0) && (c6.compareTo(c7)!=0)) && ((c6.compareTo(c8)!=0) && (c6.compareTo(c9)!=0))))
        {
            fitness=fitness+5;
        }
        if ((((c7.compareTo(c2)!=0) && (c7.compareTo(c3)!=0)) && ((c7.compareTo(c4)!=0) && (c7.compareTo(c5)!=0))) && (((c7.compareTo(c6)!=0) && (c7.compareTo(c1)!=0)) && ((c7.compareTo(c8)!=0) && (c7.compareTo(c9)!=0))))
        {
            fitness=fitness+5;
        }

        if ((((c8.compareTo(c2)!=0) && (c8.compareTo(c3)!=0)) && ((c8.compareTo(c4)!=0) && (c8.compareTo(c5)!=0))) && (((c8.compareTo(c6)!=0) && (c8.compareTo(c7)!=0)) && ((c8.compareTo(c1)!=0) && (c8.compareTo(c9)!=0))))
        {
            fitness=fitness+5;
        }

        if ((((c9.compareTo(c2)!=0) && (c9.compareTo(c3)!=0)) && ((c9.compareTo(c4)!=0) && (c9.compareTo(c5)!=0))) && (((c9.compareTo(c6)!=0) && (c9.compareTo(c7)!=0)) && ((c9.compareTo(c8)!=0) && (c9.compareTo(c1)!=0))))
        {
            fitness=fitness+5;
        }


    }

    public void evaluarHorizontal1(IChromosome cromosoma)
    {
        //Casillas 1,2 y 3
        Integer c1= (Integer)cromosoma.getGene(0).getAllele();
        Integer c2 = (Integer) cromosoma.getGene(1).getAllele();
        Integer c3 = (Integer) cromosoma.getGene(2).getAllele();

        if (c1+c2+c3==15)//Si la suma de la horizontal es 15, sumamos 15
            fitness=fitness+15;
    }


    public void evaluarHorizontal2(IChromosome cromosoma)
    {
        //Casillas 4,5 y 6
        Integer c4= (Integer)cromosoma.getGene(3).getAllele();
        Integer c5 = (Integer) cromosoma.getGene(4).getAllele();
        Integer c6 = (Integer) cromosoma.getGene(5).getAllele();

        if (c4+c5+c6==15)//Si la suma de la horizontal es 15, sumamos 15
            fitness=fitness+15;
    }


    public void evaluarHorizontal3(IChromosome cromosoma)
    {
        //Casillas 7,8 y 9
        Integer c7= (Integer)cromosoma.getGene(6).getAllele();
        Integer c8 = (Integer) cromosoma.getGene(7).getAllele();
        Integer c9 = (Integer) cromosoma.getGene(8).getAllele();

        if (c7+c8+c9==15) //Si la suma de la horizontal es 15, sumamos 15
            fitness=fitness+15; 
    }


    public void evaluarVertical1(IChromosome cromosoma)
    {
        //Casillas 7,4 y 1
        Integer c7= (Integer)cromosoma.getGene(6).getAllele();
        Integer c4 = (Integer) cromosoma.getGene(3).getAllele();
        Integer c1 = (Integer) cromosoma.getGene(0).getAllele();

        if (c7+c4+c1==15) //Si la suma de la vertical es 15, sumamos 15
            fitness=fitness+15;
    }

    public void evaluarVertical2(IChromosome cromosoma)
    {
        //Casillas 7,4 y 1
        Integer c8= (Integer)cromosoma.getGene(7).getAllele();
        Integer c5 = (Integer) cromosoma.getGene(4).getAllele();
        Integer c2 = (Integer) cromosoma.getGene(1).getAllele();

        if (c8+c5+c2==15) //Si la suma de la vertical es 15, sumamos 15
            fitness=fitness+15;
    }

    public void evaluarVertical3(IChromosome cromosoma)
    {
        //Casillas 7,4 y 1
        Integer c9= (Integer)cromosoma.getGene(8).getAllele();
        Integer c6 = (Integer) cromosoma.getGene(5).getAllele();
        Integer c3 = (Integer) cromosoma.getGene(2).getAllele();

        if (c9+c6+c3==15) //Si la suma de la vertical es 15, sumamos 15
            fitness=fitness+15;
    }


    public void evaluarDiagonal1(IChromosome cromosoma)
    {
        //Casillas 7,5 y 3
        Integer c7= (Integer)cromosoma.getGene(6).getAllele();
        Integer c5 = (Integer) cromosoma.getGene(4).getAllele();
        Integer c3 = (Integer) cromosoma.getGene(2).getAllele();

        if (c7+c5+c3==15) //Si la suma de la diagonal es 15, sumamos 15
            fitness=fitness+15;
    }

    public void evaluarDiagonal2(IChromosome cromosoma)
    {
        //Casillas 1,5 y 9
        Integer c1= (Integer)cromosoma.getGene(0).getAllele();
        Integer c5 = (Integer) cromosoma.getGene(4).getAllele();
        Integer c9 = (Integer) cromosoma.getGene(8).getAllele();

        if (c1+c5+c9==15) //Si la suma de la diagonal es 15, sumamos 15
            fitness=fitness+15;
    }

}

Con esto ya tenemos nuestra función de aptitud. Ahora, debemos configurar JGAP indicandole cual es nuestra función de aptitud, como son los individuos (dandole de ejemplo un cromosoma), el tamaño de la población inicial, y finalmente, poniendo a iterar el algoritmo. Vamos a la clase main y programamos:

Código:

package ag_cuadradomagico;

/**
 *
 * @author Salandrews
 */

//Libreria JGAP
import org.jgap.Chromosome;
import org.jgap.Configuration;
import org.jgap.FitnessFunction;
import org.jgap.Gene;
import org.jgap.Genotype;
import org.jgap.IChromosome;
import org.jgap.InvalidConfigurationException;
import org.jgap.impl.DefaultConfiguration;
import org.jgap.impl.IntegerGene;



public class Main {

    /**
     * @param args the command line arguments
     */

   public static void mostrarCuadrado(IChromosome cuadradoSolucion)
   {
        Integer c1 = (Integer) cuadradoSolucion.getGene(0).getAllele();
        Integer c2 = (Integer) cuadradoSolucion.getGene(1).getAllele();
        Integer c3 = (Integer) cuadradoSolucion.getGene(2).getAllele();

        Integer c4 = (Integer) cuadradoSolucion.getGene(3).getAllele();
        Integer c5 = (Integer) cuadradoSolucion.getGene(4).getAllele();
        Integer c6 = (Integer) cuadradoSolucion.getGene(5).getAllele();

        Integer c7 = (Integer) cuadradoSolucion.getGene(6).getAllele();
        Integer c8 = (Integer) cuadradoSolucion.getGene(7).getAllele();
        Integer c9 = (Integer) cuadradoSolucion.getGene(8).getAllele();

        System.out.println(c7+"   "+c8+"   "+c9);
        System.out.println(c4+"   "+c5+"   "+c6);
        System.out.println(c1+"   "+c2+"   "+c3);

   }


    public static void main(String[] args) {
        // TODO code application logic here

        //Algoritmo genético
         try{
            // Start with a DefaultConfiguration, which comes setup with the
            // most common settings.
            // -------------------------------------------------------------

            //Configuramos JGAP
            Configuration configuracion = new DefaultConfiguration();

            FitnessFunction myFunc = new funcionAptitud();
            configuracion.setFitnessFunction(myFunc); //Le indicamos a JGAP cual sera nuestra funcion de aptitud

            Gene[] genEjemplo = new Gene[9];
            //Creamos una codificacion de 9 genes que nos servira para nuestros individuos (fenotipo)
            //Los genes seran valores entre 1 y 9 (por el cuadrado magico de 3x3)
            genEjemplo[0] = new IntegerGene(configuracion, 1, 9);
            genEjemplo[1] = new IntegerGene(configuracion, 1, 9);
            genEjemplo[2] = new IntegerGene(configuracion, 1, 9);
            genEjemplo[3] = new IntegerGene(configuracion, 1, 9);
            genEjemplo[4] = new IntegerGene(configuracion, 1, 9);
            genEjemplo[5] = new IntegerGene(configuracion, 1, 9);
            genEjemplo[6] = new IntegerGene(configuracion, 1, 9);
            genEjemplo[7] = new IntegerGene(configuracion, 1, 9);
            genEjemplo[8] = new IntegerGene(configuracion, 1, 9);
            

            //Recordemos que los cromosomas son el correspondiente a los individuos
            Chromosome cromosomaCuadradoMagico = new Chromosome(configuracion, genEjemplo); //Creamos un individuo a partir de la configuracion de los genes anterior
            configuracion.setSampleChromosome(cromosomaCuadradoMagico); //Le indicamos a JGAP un ejemplo de como seran los individuos, a partir del individuo de ejemplo que creamos

            configuracion.setPopulationSize(5000); //Creamos nuestra poblacion inicial

            //Creamos el genotipo de la poblacion
            //Recordemos que el genotipo se determina del fenotipo = la configuracion de los genes para un cromosoma particular
            Genotype population = Genotype.randomInitialGenotype(configuracion);


            //Comienza a iterar el algoritmo
            for (int m = 0 ; m < 50 ; m++) //50 iteraciones, cada iteracion sera una generacion
            {
                population.evolve();

                System.out.println("Iteracion #"+m);
                IChromosome mejor_individuo = population.getFittestChromosome(); //Obtenemos el mejor individuo para esta generacion
                System.out.println("Mejor Individuo de la generacion "+m+" :");
                mostrarCuadrado(mejor_individuo);
                System.out.println("Valor de aptitud obtenido:"+mejor_individuo.getFitnessValue());
            }

            /*Al final de las iteraciones, obtenemos el mejor individuo,
             * para nuestro ejemplo, es el cuadrado que no repite valores
             * en sus casillas, y cuya suma de lineas verticales, horizontales y
             * diagonales es 15
             */
            IChromosome bestSolutionSoFar = population.getFittestChromosome(); //mejor individuo obtenido

            System.out.println("Este es el mejor individuo encontrado para el cuadrado magico de 3x3 despues de 50 generaciones:");
            mostrarCuadrado(bestSolutionSoFar);//Mostramos al individuo
            System.out.println("Valor de aptitud obtenido:"+bestSolutionSoFar.getFitnessValue()); //Mostramos el valor obtenido en la función de aptitud para el mejor individuo

        }
        catch (InvalidConfigurationException ex) {
            System.out.println("No se pudo ejecutar el AG");

        }

    }

}

Ahora, ejecutamos el programa y obtendremos un individuos que representa la solución al cuadrado mágico de 3x3. La idea aquí no es explicar JGAP, sino el AG, utilizando JGAP. Si ustedes quieren programa el AG a mano, este sería el pseudocódigo:

Código:

BEGIN /* Algoritmo Genetico Simple */
Generar una poblacion inicial.
Computar la funcion de evaluacion de cada individuo.
WHILE NOT Terminado DO
BEGIN /* Producir nueva generacion */
FOR Tama~no poblacion/2 DO
BEGIN /*Ciclo Reproductivo */
Seleccionar dos individuos de la anterior generacion, para el cruce (probabilidad de seleccion proporcional
a la funcion de evaluacion del individuo).
Cruzar con cierta probabilidad los dos
individuos obteniendo dos descendientes.
Mutar los dos descendientes con cierta probabilidad.
Computar la funcion de evaluacion de los dos
descendientes mutados.
Insertar los dos descendientes mutados en la nueva generacion.
END
IF la poblacion ha convergido THEN
Terminado := TRUE
END
END

¿Cuando termina un AG? Puede terminar dándole un número finito de iteraciones, como en el ejemplo (50 iteraciones), o bien cuando el algoritmo converja. ¿Cuando converje? Cuando los individuos de las generaciones ya no cambian.

¿Hay algún problema que se pueda dar con el AG? Si, como el AG es un método de búsqueda, existe el problema de que podamos encontrar máximos o mínimos locales, y no el global, es que el que nos interesa.

Bien, espero que les sea útil, copien y prueben el ejemplo, modifiquenlo, hagan sus pruebas y saquen sus propias conclusiones. Pruebenlo para resolver problemas de la ruta mas corta, problemas de las N reinas o caballos sobre un tablero sin que se puedan atacar entre si, obtener configuraciones óptimas de dietas, resolución de rompecabezas, etc. Quizá se me olvido explicar algunas cosas, o no me di a entender, así que si tienen dudas, no duden en compartirlas y vemos si les podemos dar solución.

Saludos

cremoso · 11 Dic 2010

Interesante la teoría, gracias por el aporte.

rivererchi · 11 Dic 2010

buen aporte..¡¡¡

El_hada_69 · 13 Dic 2010

interesante aunque entendí la mitad haha XD

Aztek53 · 15 Dic 2010

Hey amigo hice correr el programa pero no me resuelve el problema veo repeticion de numeros y no todos los lados me da 15, que puede ser ?? ya le he aumentado el numero de iteraciones y naada. o en que debo modificarle para que solo me muestre el resultado.

Salandrews · 15 Dic 2010

Aztek53 dijo:

Seguramente estas viendo las primeras iteraciones, en ellas los individuos aún muestran repetición de numeros y sus lados no suman 15, debes esperar a que el algoritmo termine y ver el último individuo que representa la solución.

De cualquier manera, si solo quieres ver la solución, el siguiente código:

Código:

//Comienza a iterar el algoritmo
            for (int m = 0 ; m < 50 ; m++) //50 iteraciones, cada iteracion sera una generacion
            {
                population.evolve();

                System.out.println("Iteracion #"+m);
                IChromosome mejor_individuo = population.getFittestChromosome(); //Obtenemos el mejor individuo para esta generacion
                System.out.println("Mejor Individuo de la generacion "+m+" :");
                mostrarCuadrado(mejor_individuo);
                System.out.println("Valor de aptitud obtenido:"+mejor_individuo.getFitnessValue());
            }

Modificalo así:

Código:

//Comienza a iterar el algoritmo
            for (int m = 0 ; m < 50 ; m++) //50 iteraciones, cada iteracion sera una generacion
            {
                population.evolve();
            }

Así el algoritmo evolucionara a los individuos y tu solo verás al final al mejor individuo que será la solución.

tochoromero · 16 Dic 2010

Interesante amigo, en un chanza le doy una leida, yo actualmente estoy trabajando con Minería de Datos y el ciclo CBR y un poquito de Agentes, y esto anda por el mismo rumbo que el mio. Saludos y ahí luego intercambiamos conocimientos

kalsidon · 17 Dic 2010

buenisimo empezare a adelantar este proyecto, mas adelante comparto uno de agentes inteligentes

lenin arce · 2013-08-13T21:51:20-0500

LA ÚLTIMA ITERACIÓN NO SUMA 15

SI DESEAS TE ENVÍO EL CÓDIGO, GRACIAS POR TU RESPUESTA

Algoritmos Genéticos en Java utilizando JGAP (teoría y ejemplo)

Salandrews

Bovino maduro

cremoso

Bovino de la familia

rivererchi

Bovino Milenario

El_hada_69

Bovino maduro

Aztek53

Becerro

Salandrews

Bovino maduro

tochoromero

Bovino adicto

kalsidon

Bovino maduro

lenin arce

Becerro