Algoritmos Genéticos con Java y Python

Los Algoritmos Genéticos (Gas por sus siglas en inglés) intentan imitar los procesos por los cuales opera la selección natural, y aplicarlos para resolver problemas de negocios e investigación. Desarrollado por John Holland en la década de 1960 y 1970, proporcionan un marco para el estudio de los efectos de tales factores biológicamente inspirados como la selección de pareja, la reproducción, la mutación y el cruce de la información genética. En el mundo natural, las restricciones y tensiones de un medio ambiente particular obligan a las diferentes especies (y diferentes individuos dentro de las especies) a competir para producir la descendencia más apta. En el mundo de los algoritmos genéticos, las soluciones potenciales más aptas evolucionan para producir soluciones aún más óptimas.

No es sorprendente que el campo de los algoritmos genéticos haya tomado prestado mucho de la terminología genómica. Cada célula de nuestro cuerpo contiene el mismo conjunto de cromosomas, una cadena de ADN que funciona como un modelo para hacer uno de nosotros. Entonces, cada cromosoma se puede dividir en genes, que son bloque de ADN diseñado para codificar un rasgo particular como el color de ojos. Mutación, la alteración de un único gen en un cromosoma de la descendencia. La aptitud de la descendencia se evalúa, ya sea en términos de viabilidad (vivir lo suficiente como para reproducirse).

Ahora, un cromosoma se refiere a una de las soluciones potenciales al problema, un gen es un solo bit o dígito de la solución candidata. La mayoría funcionan actualizando iterativamente una colección de soluciones potenciales, llamada población. Cada miembro de la población se evalúa para la aptitud en cada ciclo. Una nueva población entonces reemplaza a la población vieja con los miembros más aptos.

La función más apta f (x) es una función de valor real que actúa sobre el cromosoma (solución potencial), no el gen, de modo que el x en f (x) se refiere al valor numérico tomado por el cromosoma en el momento de la evaluación de la aptitud.

Solución de problemas orientada a objetivos

Los algoritmos genéticos son una de las herramientas que podemos utilizar para aplicar machine learning y encontrar soluciones buenas, a veces incluso óptimas, a problemas que tienen miles de millones de soluciones potenciales. Utilizan procesos biológicos en el software para encontrar respuestas a problemas que tienen espacios de búsqueda realmente grandes generando continuamente soluciones candidatas, evaluando qué tan bien las soluciones se ajustan al resultado deseado y refinando las mejores soluciones.

Cuando se resuelve un problema con un algoritmo genético, en vez de pedir una solución específica, se proporcionan características que la solución debe tener o reglas que la solución debe pasar para ser aceptadas. Cuantas más restricciones agregue, más soluciones potenciales quedarán bloqueadas.

Los algoritmos genéticos se utilizan comúnmente para generar soluciones de alta calidad a la optimización y los problemas de búsqueda basándose en los operadores de mutación, crossover y selección.

Imagine que le dan 10 oportunidades para adivinar un número entre 1 y 1000 y la única información que recibe es si su conjetura es correcta o incorrecta. ¿Podría adivinar con certeza el número? Con sólo lo correcto o erróneo como retroalimentación, no tiene forma de mejorar sus conjeturas, por lo que tiene en el mejor de los casos una probabilidad de 1 en 100 de adivinar el número. Un aspecto fundamental de la solución de problemas utilizando algoritmos genéticos es que deben proporcionar retroalimentación que ayuda al motor a seleccionar el mejor de dos propuestas.

Usted puede ser capaz de adivinar al azar si tiene conocimiento específico del problema que le ayuda a eliminar ciertas combinaciones de números. El uso de conocimientos específicos de problemas para guiar la creación y modificación de soluciones potenciales del algoritmo genético puede ayudarles a encontrar una solución de órdenes de magnitud más rápida.

Los algoritmos genéticos y la programación genética son muy buenos para encontrar soluciones a problemas muy grandes. Lo hacen tomando millones de muestras del espacio de búsqueda, haciendo pequeños cambios, posiblemente recombinando partes de las mejores soluciones, comparando la aptitud resultante con la de la mejor solución actual y manteniendo la mejor de las dos. Este proceso se repite hasta que se produce una condición de parada como una de las siguientes: se encuentra la solución conocida, se encuentra una solución que cumple todos los requisitos, ha pasado un cierto número de generaciones o ha transcurrido una cantidad específica de tiempo, etc.

Adivine la contraseña

Imagine que le piden que adivine una contraseña; ¿Qué tipo de comentarios le gustaría? Estas decisiones son algunas de las que tiene que hacer al planificar la implementación de un algoritmo genético para encontrar una solución a su problema.

Los Algoritmos Genéticos usan la exploración aleatoria del espacio del problema combinado con procesos evolutivos como mutación y cruce (intercambio de información genética) para mejorar conjeturas. Pero también, porque no tienen experiencia en el dominio del problema, intentan cosas que un ser humano nunca pensaría intentar. Por lo tanto, una persona que utiliza un algoritmo genético puede aprender más sobre el problema de espacio y soluciones potenciales. Esto les da la capacidad de hacer mejoras al algoritmo.

Genes

Para empezar, el algoritmo genético necesita un conjunto de genes para usarlo y  construir una propuesta inicial. Para esta muestra será un conjunto genérico de letras. También necesita una contraseña de destino para adivinar:

Java:

/**

      Gene Set, we set a generic set of letters and target/desired result  

*/

private static final String geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!.,";

private static final String target = "This is a test for genetics aldorithms";

Python:

geneset = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!.,"

Generar una propuesta inicial

Luego el algoritmo necesita una manera de generar un texto aleatorio tomando como base en gene set.

Java:

private static final Random random = new Random();

/**

 * We need a way to generate random string (a guest) from the geneset.

 * @param length the number of random chars to be generated from a geneSet.

 */

private static String generate_parent(int length) {       

    StringBuilder genes = new StringBuilder();

    for (int i = 0; i < length; i++) {

        genes.append(geneSet.charAt(random.nextInt(geneSet.length())));

    }

    return genes.toString();

}

Python:

import random

     

def _generate_parent(length, geneSet, get_fitness):

    genes = []

    while len(genes) < length:

        sampleSize = min(length - len(genes), len(geneSet))

        genes.extend(random.sample(geneSet, sampleSize))

    return ''.join(genes)

Fitness

El valor de la aptitud o fitness que el algoritmo genético proporciona es la única retroalimentación que el motor obtiene para guiarla hacia una solución. En este ejemplo el valor de la aptitud es el número total de letras en la propuesta que puede emparejar la letra en la misma posición de la contraseña.

Java:

/**

 * We need to define a fitness

 * The fitness is the only feedback the engine get t o guide it towards a solution.

 * Fitness is the total number in the guess that match the letter in the same position of the password.

 */

private static int get_fitness(String guess){

    char[] guess_array = guess.toCharArray();

    char[] target_array = target.toCharArray();

   

    int contador = 0;

   

    for(int i = 0; i < target_array.length; i++) {

        if (guess_array[i] == target_array[i]) {

            contador++;

        }

    }

   

    return contador;       

   

}

Python:

def get_fitness(guess, target):

    return sum(1 for expected, actual in zip(target, guess)

           if expected == actual)

Mutate

Luego, el motor necesita una forma de producir una nueva conjetura mediante la mutación de la actual. La siguiente implementación convierte la cadena padre en una matriz, luego reemplaza 1 letra en la matriz con una seleccionada aleatoriamente de geneSet, y finalmente recombina el resultado en una nueva cadena.

Java:

/**

 * We need a new way to produce a new guess mutating the current one. Covnerts the parent string to an array

 * and replaces 1 letter in the array with a randomly selected from the geneSet.

 *

 * @return

 */

private static String mutate(String parent){       

    char[] guess_array = parent.toCharArray();

    char[] target_array = target.toCharArray();

           

    for(int i = 0; i < target_array.length; i++) {

        if (guess_array[i] != target_array[i]) {

            char gene = geneSet.charAt(random.nextInt(geneSet.length()));

            //is the new gene the same it was at that position?

            //replace the selected gene if it is the same as the one it is supposed to replace , which can prevent a significant number of wasted guesses.

            while (gene != guess_array[i]){

                guess_array[i] = gene;

            }               

        }

    }

   

    return String.valueOf(guess_array);

   

}

Python:

def _mutate(parent, geneSet, get_fitness):

    index = random.randrange(0, len(parent.Genes))

    childGenes = list(parent.Genes)

    newGene, alternate = random.sample(geneSet, 2)

    childGenes[index] = alternate \

        if newGene == childGenes[index] \

        else newGene

    return ''.join(childGenes)

Display

A continuación, es importante vigilar lo que está sucediendo para que el motor se puede detener si se atasca. Tener una representación visual de la secuencia génica, que puede no ser la secuencia del gen literal, es a menudo crítico para identificar qué funciona y qué no lo hace para que el algoritmo pueda ser mejorado.

Normalmente, la función de visualización también genera el valor de aptitud y el tiempo transcurrido.

Java:

/**

* It is important to monitor what is happening so that the engine can be stopped if      * gets stucked. Having a visual representatiion on the gene sequence , which may not be * the literal sequence, is often critical to identifying what works and what does not so * that the algorithms can be improved.

* Display function also show output the fitness value and how much time has elapsed.

*/

private static void display(String guess, Date startTime) {

    Date time = new Date();

    System.out.println(String.format("Guess: " + guess+ ", Fitness: " + get_fitness(guess) + ", Time: " + (time.getTime() - startTime.getTime()) + " milisegundos" ));       

}

Python:

      def display(candidate, startTime):

          timeDiff = datetime.datetime.now() - startTime

          print("{0}\t{1}\t{2}".format(

              candidate.Genes, candidate.Fitness, str(timeDiff)))

Main

El programa principal comienza inicializando bestParent a una secuencia aleatoria de letras y llamando a la función de visualización.

La pieza final es el corazón del motor genético. Es un bucle que:

• Generar una propuesta,
• Calcula la aptitud o fitness para esa propuesta, entonces,
• Compara la aptitud de modo que la mejor propuesta se mantiene.

public static void main(String[] args) {   

     

    GuessTheNumber guessTheNumber = new GuessTheNumber();

   

    //Generamos

    random.setSeed(12345);

    Date startTime = new Date();

    String best_parent = guessTheNumber.generate_parent(target.length());

    int best_fitness = guessTheNumber.get_fitness(best_parent);

    guessTheNumber.display(best_parent, startTime);

   

    while (true) {

        String child = guessTheNumber.mutate(best_parent);

        int child_fitness = guessTheNumber.get_fitness(child);

        if (best_fitness >= child_fitness) {

            display(child, startTime);

        }

       

        if (child_fitness >= best_parent.length()){

            display(child, startTime);

            break;

        }

       

        best_fitness = child_fitness;

        best_parent = child;

    }

   

}

Este ciclo se repite hasta que se produce una condición de stop, en este caso cuando todas las letras de la propuesta coinciden con el objetivo.

Ejecute el código y verá una salida similiar a lo siguiente:

Guess: spytwdwrmCCvnDBxIoBMGoVJlCiUMEaKmWEA w, Fitness: 0, Time: 0 milisegundos

.

.

.

.

Guess: IhX  is a GlKt fnV txnewiesvaNdorithms, Fitness: 24, Time: 5 milisegundos

Guess: Vhi  is a cAZt fu  gTnesiXsrasdorithms, Fitness: 26, Time: 5milisegundos

Guess: PhiI is a QKGt fhj gVneyi,sfafdorithms, Fitness: 26, Time: 5milisegundos

Guess: ghi. is a fjGt fD. gOneYissVaNdorithms, Fitness: 26, Time: 5 milisegundos

Guess: LhiV is a ZWEt fgK gUnexinsHaOdorithms, Fitness: 26, Time: 5 milisegundos

.

.

.

.

Guess: Thiv is a .yst fo! gtneIicspaldorithms, Fitness: 31, Time: 10 milisegundos

Guess: ThiR is a Dyst foa geneeicsDaldorithms, Fitness: 32, Time: 10 milisegundos

Guess: Thiu is a yJst fow geneeicsTaldorithms, Fitness: 32, Time: 10 milisegundos

Guess: ThiA is a oCst foY genexicsJaldorithms, Fitness: 32, Time: 10 milisegundos

Guess: Thil is a xEst fod geneWicsYaldorithms, Fitness: 32, Time: 10 milisegundos

.

.

.

.

Guess: This is a Zest for genetics aldorithms, Fitness: 37, Time: 15 milisegundos

Guess: This is a Vest for genetics aldorithms, Fitness: 37, Time: 15 milisegundos

Guess: This is a test for genetics aldorithms, Fitness: 38, Time: 15 milisegundos

Guess: This is a test for genetics algorithms, Fitness: 38, Time: 15 milisegundos

Cromosoma

A continuación, debemos introducir un objeto cromosómico que tenga genes y aptitud, esto hará que el motor genético sea más flexible haciendo posible pasar esos valores como una clase.

public class Chromosome {

   

    private int fitness;

    private String genes;

    public Chromosome(int fitness, String genes) {

        this.fitness = fitness;

        this.genes = genes;

    }

    public int getFitness() {

        return fitness;

    }

    public void setFitness(int fitness) {

        this.fitness = fitness;

    }

    public String getGenes() {

        return genes;

    }

    public void setGenes(String genes) {

        this.genes = genes;

    }

   

}

Ahora tenemos un motor, pero actualmente es una clase fuertemente acoplada, por lo que la próxima tarea depende de ti:

- Extraer el código del motor genético de forma que pueda ser reutilizado para otros proyectos.
- Crear un paquete llamado genetic e incluye la clase cromosoma allí.
- Trate de utilizar pruebas unitarias.
- Prueba el motor genético con una contraseña más larga.
- Añade soporte para benchmarking, es útil saber cuánto tiempo toma el motor para encontrar una solución en promedio y su desviación estándar.

Escríbame al correo electrónico miguelurbin@gmail.com para enviarle el proyecto en Python y Java para hacer sus propias pruebas o mejoras.