Login Form

En la vida cotidiana nos enfrentamos de manera continua con la tarea de encontrar soluciones a problemas complejos, de los cuáles no podemos determinar de manera absoluta e inequívoca la solución perfecta e ideal que es superior a cualquier otra posible opción; ejemplo de esto es "¿Qué carrera debo estudiar?"  o "¿Qué debo corregir y qué no en el comportamiento de mis hijos?". En mi opinión, son dos aspectos diametralmente opuestos y a la vez complementarios, como caras de una moneda, los que nos lo impiden. Por un lado, la falta de información e incertidumbre y por otro, el exceso de información y/o variabilidad. Enfocándonos en el último aspecto (el exceso de información y variabilidad), en los ejemplos que expuse, son demasiadas variables en juego como para poder tomar un enfoque completamente determinístico. A lo único que podemos aspirar, en muchos de los casos, es a tomar la información que tenemos en ese momento dada por nuestra experiencia, juicio, educación, creencias y demás factores y tomar lo que nos parezca ser una solución aceptable dadas las restricciones que nos imponen dichos factores, esto es, una solución lo suficientemente buena que satisfaga ciertos criterios. Lo mismo sucede de manera frecuente en problemas encontrados en ingeniería, ciencias, matemáticas y demás áreas donde a menudo se tienen demasiadas variables que tomar en cuenta como para poder llegar a la mejor solución en un tiempo aceptable evaluándolas completamente.

Como resultado de este tipo de problemas, se desarrollan métodos que intentan encontrarles soluciones y a menudo se utilizan problemas clásicos para probarlos. En este artículo utilizaremos el problema de las 8 reinas para mostrar el funcionamiento de un algoritmo genético el cual consiste en colocar 8 reinas en un tablero de ajedrez cumpliendo la restricción de que no se puedan "comer" entre ellas como se muestra en la siguiente figura:

 

queens

  

 

Optimización y Espacios de Búsqueda

Como resultado de la aparición frecuente de dicho tipo de problemas han surgido disciplinas enteras dedicadas exclusivamente a encontrar métodos eficientes para encontrar soluciones tales como Optimización ó Investigación de Operaciones.  En Ciencias de la Computación, han surgido también métodos que comparten dicho fin y en su expresión más simple, de lo que se trata es de minimizar o maximizar una función en la cual reside el conocimiento del problema. Esta función tiene un dominio, el cuál es conocido como espacio de búsqueda y en términos simples, se refiere al conjunto de todas las posibles soluciones candidatas al problema. La función en sí impone restricciones que se deben cumplir y lo que queremos encontrar es aquella solución, o entrada de la función, que produce un valor de salida aceptable. A medida que el número de variables de entrada crece, el número de combinaciones también crece hasta que llega el momento que resulta simplemente impráctico pensar en probar todas y cada una de ellas para encontrar la mejor y por ello surgen aquellos métodos que intentan utilizar heurísticas o técnicas sofisticadas que nos permitan explorar de manera eficiente el espacio de búsqueda sin necesidad de recorrerlo en su totalidad y aun así, encontrar soluciones suficientemente buenas en tiempos aceptables y uno de dichos métodos, del cual trata el artículo, es el de Algoritmos Genéticos.

 

Algoritmos Genéticos

Los algoritmos genéticos surgieron en la década de los 70 propuestos por Holland y se llaman así porque se inspiran en el proceso de selección natural y de evolución genética encontrado en la naturaleza permitiendo producir una búsqueda eficiente, aleatoria y a la vez dirigida, a través del espacio de soluciones permitiendo encontrar resultados de excelente calidad.

La idea básica es comenzar con una población inicial aleatoria de soluciones potenciales y hacer que evolucione a través de generaciones utilizando los siguientes mecanismos:

  1. Cruce
  2. Selección
  3. Mutación

 Cada vez que se produce una nueva generación (offspring por el término utilizado en la literatura en inglés), se evalua cada uno de los individuos para determinar si se obtuvo una solución aceptable o bien, se alcanzó un número máximo de generaciones y el proceso debe detenerse.

En java, el esqueleto de un algoritmo genético se podría ver así:

 

        // We get an initial random population.
        Population population = ga.initPopulation();
        
        // We evaluate the population.
        ga.evaluatePopulation(population);        
        
        // We evolve the population until we get a solution or a max generation is reached.
        int generation = 1;
        while(!ga.isTerminationConditionMet(generation, population)){
            logger.info("Best Individual found so far: " + population.getIndividual(0));
           
            // We evolve the next generation.
            population = ga.evolvePopulation(population);

            // We evaluate the next generation.
            ga.evaluatePopulation(population);
            
            generation++;
        }
        
        // Print the best solution found.
        logger.info("Solution: " + population.getIndividual(0));

 

 Se comienza creando de manera aleatoria una población de individuos representando potenciales soluciones e inmediatamente se evalua ya que, por su naturaleza aleatoria, podría ser que encontraramos  en ese conjunto inicial una solución aceptable al problema. Cabe aclarar que es muy probable que la mayoría de las soluciones ni siquiera sean soluciones válidas, es decir, es muy probable que no satisfagan las restricciones impuestas por la función de evaluación pero para eso están los mecanimos de selección, cruce y mutación, para de manera iterativa, ir refinando las soluciones y encontrar soluciones válidas.

 

Cruce y Selección

 El objetivo de trabajar con una generación dada es hacer que evolucione, y para ello, los individuos deben cruzarse de manera que se produzca un hijo que contenga información genetica de ambos padres. El mecanismo de cruce garantiza que se van a explorar nuevas soluciones candidatas en el espacio de búsqueda ya que es el que permite que se combine información de dos distintas soluciones. El mecanismo de selección se utiliza para, dado un individuo, seleccionar de entre la población la pareja con la que debe de cruzarse. Existen variaciones a través de distintas implementaciones pero en este ejemplo la estrategia es recorrer la población entera y, para cada individuo, seleccionar una pareja con la cuál se cruce para obtener un individuo que lo reemplace en la siguiente generación.

Existen muchos métodos de selección y en este proyecto utilizamos el método de selección por torneo el cuál simplemente consiste en poner a competir a un pequeño grupo de soluciones candidatas entre sí y tomar la mejor. Para ello se debe definir un tamaño de torneo N ,el número de soluciones candidatas que van a competir, y de manera aleatoria se obtienen N individuos utilizándose el mejor de ellos como pareja.

Como mecanismo de cruce, de igual manera, se puede elegir entre una gran variedad de métodos disponibles dependiendo la naturaleza del problema a tratar; existen métodos que hacen caso omiso de la información contenida en las soluciones y simplemente toman de manera aleatoria partes de ambos padres y los mezclan sin mayor consideración mientras que existen otros más sofisticados que de alguna manera preservan el orden de la información original de los padres. El método a seleccionar depende del problema a tratar y en nuestro caso utilizamos el método de Order crossover descrito en este artículo.

 

Mutación

Si nos quedáramos únicamente con los mecanismo de selección y cruce, al inicio efectivamente estaríamos explorando en cada generación hija soluciones nuevas pero llegaría forzosamente el momento en que no podríamos generar más soluciones nuevas ya que cada generación hija contiene únicamente alguna combinación de la información contenida en su generación padre y es aquí donde entra en juego el mecanismo de mutación que introduce de manera controlada el elemento aleatorio que permite disparar la búsqueda en direcciones completamente nuevas haciendo que las generaciones evolucionen de manera sorprendente y se recorran áreas del espacio de soluciones a las que de otra manera no se podría acceder. El mecanismo funciona definiendo un umbral de mutación y para cada individuo hijo obtenido del proceso de selección y cruce, decidir si se debe mutar o no en base al umbral definido. Para este ejemplo, la implementación del mecanismo de cruce es simplemente especificar un umbral en el intervalo [0,1] y para cada individuo hijo, recorrer cada uno de sus genes y generar un número aleatorio, si el número aleatorio es superior al umbral, el gen se muta, si no, se mantiene tal cual.

  

    @Override
    public void mutateIndividual(Individual individual, double mutationRate) {
        for (int geneIndex = 0; geneIndex < individual.getChromosomeLength(); geneIndex++) {

            // Mutate this gene only if it happens to be selected to be mutated by the mutationRate.
            if (mutationRate > randomGenerator.nextDouble()) {
                
                // Flip the gene to a valid random position.
                PositionCreatorHelper.addPosition(individual.getChromosome(), geneIndex);
            }
        }
    }

 

Representación y Función de evaluación

Lo que se ha descrito hasta este momento es hasta cierto punto algo general y mecánico que se aplica a cualquier problema, de hecho, existen frameworks para algoritmos genéticos que de alguna manera ofrecen implementaciones específicas de los diferentes mecanismos. Lo que en mi opinión considero los puntos cruciales y más difíciles a la hora de diseñar un algoritmo genético para un problema dado son:

  1. La representación de las soluciones
  2. La función de evaluación

El primer aspecto es la representación de la solución. Una solución candidata debe ser representada de manera tal que pueda ser manipulada como material genético permitiendo la aplicación de los operadores de cruce y mutación y a la vez, que permita ser codificada y decodificada para ser evaluada y en última instancia, utilizada y esto es totalmente específico del problema y no hay representación absoluta.

En nuestro ejemplo, una solución candidata se puede ver como la posición de cada una de las 8 reinas dentro del tablero, es decir, un arreglo de 8 posiciones por lo que se creó una clase "Posición" y cada solución estaría representada por una clase "Individual" conteniendo un arreglo de 8 posiciones. Cada posición sería un cromosoma del individuo y así podríamos aplicarles los operadores genéticos:

 

public class Individual {

    // The chromosome representing the solution.
    private Position[] chromosome;
    
    // The fitness of this solution
    private double fitness;
    
....

 

Se podría haber utilizado cualquier otro tipo de representación; por ejemplo, en vez de crear la clase Posición, se pudo haber representado el tablero de ajedrez como un arreglo de 64 bits y asignar 1 a las posiciones de las casillas con reinas y 0 a las posiciones de casillas vacías pero crear la clase Posicion y enfocarse únicamente en las posiciones ocupadas, permitió simplificar la codificación/decodificación y evaluación de una solución. 

El segundo aspecto es la evaluación de la solución, es decir, la creación de la función que asigna una calificación a cada solución candidata. Esta es realmente la parte más difícil del diseño ya que en la función es donde reside el conocimiento del problema y se tiene que garantizar que la función tome en cuenta las restricciones inherentes a una solución aceptable a la vez que debe ser capaz de discernir entre una solución de baja calidad y una buena solución.

En nuestro caso, la función asigna una calificación inicial de 8 a la solución que está evaluando lo cuál representa 8 reinas colocadas correctamente, es decir, la calificación máxima y a continuación comienza a verificar que cada una de las reinas no esté en la mira de alguna otra. Por cada error que encuentre, castiga a la solución decrementando en un punto su calificación por lo que el algoritmo termina cuando encontramos una solución con calificación de 8 ya que cualquier otra calificación representa una solución incorrecta.

 

    private void calculateFitness(Individual individual){
        
        int fitness = Constants.N;
        for(int i=0; i < individual.getChromosome().length; i++) {
            Position evaluatedPosition = individual.getGene(i);
            for (int j=0; j < individual.getChromosome().length; j++) {
                if (i!=j) {
                    Position position = individual.getGene(j);                    
                    int x = Math.abs(position.getX() - evaluatedPosition.getX());
                    int y = Math.abs(position.getY() - evaluatedPosition.getY());
                    // If they are in the same vertical, horizontal or diagonal line, we lower the score in one point.
                    if (x== y || evaluatedPosition.getX()==position.getX() || position.getY() == evaluatedPosition.getY()){
                        fitness--;
                    }
                }
            }
        }
        individual.setFitness(fitness);        
    }

 

Por último, cabe mencionar que, debido a la naturaleza aleatoria del algoritmo en sí y probablemente también a los detalles de la implementación, el algoritmo no siempre converge a la primera por lo que quizá haya que correrlo dos o tres veces antes de que arroje una solución válida.

 El código JAVA puede ser encontrado aquí

 For the English speakers, you may have to run the application twice or thrice before it converges to a valid solution and the JAVA code can be found here.

 

Add comment


Security code
Refresh

contacts Contactanos

 

bugs Reportar bugs

about Acerca de www.tecnohobby.net

Go to top