¿Qué son los algoritmos genéticos?

Durante los últimos años, ha habido un gran revuelo en torno a la Inteligencia Artificial (IA). Grandes empresas como Google, Apple y Microsoft están trabajando activamente en el tema. De hecho, la IA es un paraguas que abarca muchos objetivos, enfoques, herramientas y aplicaciones. Los Algoritmos Genéticos (AG) son sólo una de las herramientas para la búsqueda inteligente a través de muchas soluciones posibles.

GA es una técnica metaheurística de búsqueda y optimización basada en los principios presentes en la evolución natural. Pertenece a una clase más amplia de algoritmos evolutivos.

GA mantiene una población de cromosomas-un conjunto de soluciones potenciales para el problema. La idea es que la “evolución” encontrará una solución óptima para el problema después de un número de generaciones sucesivas -similar a la selección natural.

GA imita tres procesos evolutivos: selección, cruce de genes y mutación.

Similar a la selección natural, el concepto central de la selección de GA es la aptitud. Los cromosomas que son más aptos tienen más posibilidades de sobrevivir. La aptitud es una función que mide la calidad de la solución representada por el cromosoma. En esencia, cada cromosoma de la población representa los parámetros de entrada. Por ejemplo, si el problema contiene dos parámetros de entrada, como el precio y el volumen en el comercio, cada cromosoma constará lógicamente de dos elementos. Cómo se codifican los elementos dentro del cromosoma es un tema diferente.

Durante la selección, los cromosomas forman parejas de padres para la reproducción. Cada hijo toma características de sus padres. Básicamente, el hijo representa una recombinación de características de sus padres: Algunas de las características se toman de un progenitor y otras de otro. Además de la recombinación, algunas de las características pueden mutar.

Debido a que los cromosomas más aptos producen más hijos, cada generación posterior tendrá una mejor aptitud. En algún momento, una generación contendrá un cromosoma que representará una solución suficientemente buena para nuestro problema.

GA es potente y ampliamente aplicable para problemas complejos. Hay una gran clase de problemas de optimización que son bastante difíciles de resolver mediante técnicas de optimización convencionales. Los algoritmos genéticos son algoritmos eficientes cuya solución es aproximadamente óptima. Las aplicaciones conocidas incluyen la programación, el transporte, el enrutamiento, las tecnologías de grupo, el diseño de la disposición, el entrenamiento de redes neuronales, y muchos otros.

Poniendo las cosas en práctica

El ejemplo que veremos puede considerarse el “Hola Mundo” de los AG. Este ejemplo fue dado inicialmente por J. Freeman en Simulating Neural Networks with Mathematica. Lo tomé de Genetic Algorithms and Engineering Design de Mitsuo Gen y Runwei Cheng.

El Problema de Coincidencia de Palabras trata de evolucionar una expresión con un algoritmo genético. Inicialmente, se supone que el algoritmo “adivina” la frase “ser o no ser” a partir de listas de letras generadas aleatoriamente.

Como hay 26 letras posibles para cada una de las 13 posiciones de la lista, la probabilidad de que obtengamos la frase correcta de forma puramente aleatoria es (1/26)^13=4.03038×10-19, lo que equivale a unas dos posibilidades de un (Gen & Chong, 1997).

Aquí definiremos el problema de forma un poco más amplia, lo que dificulta aún más la solución. Supongamos que no estamos limitados al idioma inglés o a una frase específica. Podemos acabar tratando con cualquier alfabeto, o incluso con cualquier conjunto de símbolos. No tenemos ningún conocimiento del idioma. Ni siquiera sabemos si hay algún idioma en absoluto.

Digamos que nuestro oponente pensó en una frase arbitraria, incluyendo espacios en blanco. Sabemos la longitud de la frase y el número de símbolos del alfabeto. Ese es el único conocimiento que tenemos. Después de cada conjetura, nuestro oponente nos dice cuántas letras hay.

Cada cromosoma es una secuencia de índices de los símbolos del alfabeto. Si hablamos del alfabeto inglés, entonces la “a” estará representada por el 0, la “b” por el 1, la “c” por el 2, y así sucesivamente. Así, por ejemplo, la palabra “be” se representará como .

Demostraremos todos los pasos a través de fragmentos de código Java, pero no es necesario tener conocimientos de Java para entender cada paso.

Núcleo del Algoritmo Genético

Podemos empezar con una implementación general del algoritmo genético:

public void find() { // Initialization List<T> population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); }}

Este es el simple conjunto de pasos en que consiste más o menos todo AG. En el paso de inicialización, generamos una población inicial de frases. El tamaño de la población se determina por populationSize. Cómo se genera la frase depende de la implementación de la supplier.

En el paso de iteración, evolucionamos la población hasta que se cumplan las condiciones de terminación dentro de la prueba del bucle while. Las condiciones de terminación pueden incluir tanto el número de generaciones como la coincidencia exacta de una de las frases de la población. El termination encapsula una implementación exacta.

En cada iteración, realizamos los pasos típicos del AG:

1. Realizar una selección sobre la población basada en la aptitud del cromosoma.
2. Producir una nueva “generación” a través de la operación de cruce.
3. Realizar una recombinación de algunas letras en algunas frases.

El núcleo del algoritmo es muy simple y agnóstico del dominio. Será el mismo para todos los problemas. Lo que habrá que afinar es la implementación de los operadores genéticos. A continuación, echaremos un vistazo a cada uno de los operadores de AG mencionados anteriormente.

Selección

Como ya sabemos, la selección es un proceso de búsqueda de sucesores de los cromosomas actuales-los cromosomas que son más adecuados para nuestro problema. Durante la selección, tenemos que asegurarnos de que los cromosomas con mejor aptitud tienen más posibilidades de sobrevivir.

private List<T> selection(List<T> population) { final double fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double probabilities = new double; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses / totalFitness; probabilities = sum; } probabilities = 1; return range(0, probabilities.length).mapToObj(i -> { int index = binarySearch(probabilities, random()); if (index < 0) { index = -(index + 1); } return population.get(index); }).collect(toList());}

La idea detrás de esta implementación es la siguiente: La población se representa como rangos consecuentes en el eje numérico. Toda la población está entre 0 y 1.

El trozo del rango que toma un cromosoma es proporcional a su fitness. Esto hace que un cromosoma más apto obtenga un trozo mayor. Entonces miramos al azar un número entre 0 y 1 y encontramos un rango que incluya el número. Obviamente, los rangos más grandes tienen más posibilidades de ser seleccionados y, por tanto, los cromosomas más aptos tienen más posibilidades de sobrevivir.

Debido a que no conocemos los detalles de la función de aptitud, necesitamos normalizar los valores de aptitud. La función de aptitud está representada por fitness, que convierte un cromosoma en un doble arbitrario que representa la aptitud del cromosoma.

En el código, encontramos los índices de aptitud para todos los cromosomas de la población, y también encontramos la aptitud total. Dentro del bucle for, realizamos una suma acumulativa sobre las probabilidades escaladas por la aptitud total. Matemáticamente, esto debería dar como resultado que la variable final tenga el valor de 1. Debido a la imprecisión del punto flotante, no podemos garantizarlo, así que lo ponemos a 1 sólo para estar seguros.

Por último, para un número de veces igual al número de cromosomas de entrada, generamos un número aleatorio, encontramos un rango que incluye el número, y luego seleccionamos el cromosoma correspondiente. Como puede observar, el mismo cromosoma puede ser seleccionado varias veces.

Cruzamiento

Ahora necesitamos que los cromosomas se “reproduzcan”.

private void crossover(List<T> population) { final int indexes = range(0, population.size()) .filter(i-> random() < crossoverProbability) .toArray(); shuffle(Arrays.asList(indexes)); for (int i = 0; i < indexes.length / 2; i++) { final int index1 = indexes; final int index2 = indexes; final T value1 = population.get(index1); final T value2 = population.get(index2); population.set(index1, crossover.apply(value1, value2)); population.set(index2, crossover.apply(value2, value1)); }}

Con la probabilidad predefinida crossoverProbability, seleccionamos los padres para la reproducción. Los padres seleccionados se barajan, permitiendo cualquier combinación. Tomamos pares de padres y aplicamos el operador crossover. Aplicamos el operador dos veces para cada pareja porque necesitamos mantener el mismo tamaño de la población. Los hijos sustituyen a sus padres en la población.

Mutación

Por último, realizamos la recombinación de las características.

private void mutation(List<T> population) { for (int i = 0; i < population.size(); i++) { if (random() < mutationProbability) { population.set(i, mutation.apply(population.get(i))); } }}

Con una probabilidad predefinida mutationProbability, realizamos la “mutación” en los cromosomas. La mutación en sí está definida por mutation.

Configuración del Algoritmo Específico del Problema

Ahora veamos qué tipo de parámetros específicos del problema debemos proporcionar a nuestra implementación genérica.

private BiFunction<T, T, T> crossover;private double crossoverProbability;private ToDoubleFunction<T> fitness;private Function<T, T> mutation;private double mutationProbability;private int populationSize = 100;private Supplier<T> supplier;private Predicate<Collection<T>> termination;

Los parámetros, respectivamente, son:

1. Operador de cruce
2. Probabilidad de cruce
3. Función de ajuste
4. Operador de mutación
5. Probabilidad de mutación
6. Tamaño de la población
7. Proveedor de cromosomas para la población inicial
8. Función de terminación

Aquí tenemos la configuración para nuestro problema:

new GeneticAlgorithm<char>() .setCrossover(this::crossover) .setCrossoverProbability(0.25) .setFitness(this::fitness) .setMutation(this::mutation) .setMutationProbability(0.05) .setPopulationSize(100) .setSupplier(() -> supplier(expected.length)) .setTermination(this::termination) .find()

Operador de cruce y probabilidad

private char crossover(char value1, char value2) { final int i = (int) round(random() * value1.length); final char result = new char(value1.length); System.arraycopy(value1, 0, result, 0, i); System.arraycopy(value2, i, result, i, value2.length - i); return result;}

La probabilidad de cruce es 0.25, por lo que esperamos que en promedio el 25 por ciento de los cromosomas sean seleccionados para el cruce. Realizamos un procedimiento sencillo para el cruce de un par de cromosomas. Generamos un número aleatorio n del rango , donde length es la longitud de un cromosoma. Ahora emparejamos el par seleccionado tomando los primeros caracteres n de un cromosoma y los caracteres restantes después del segundo.

Función de aptitud

private double fitness(char value) { return range(0, value.length) .filter(i -> value == expected) .count();}

La función de aptitud simplemente cuenta el número de coincidencias entre la frase objetivo y el cromosoma dado.

Operador de mutación y probabilidad

private char mutation(char value) { final char result = Arrays.copyOf(value, value.length); for (int i = 0; i < 2; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); int location = (int) round(random() * (value.length - 1)); result = ALPHABET; } return result;}

La operación de mutación se realiza independientemente en cada cromosoma. La probabilidad de mutación es de 0,05, por lo que esperamos que, de media, el cinco por ciento de la población mute. Mutamos eligiendo una posición de letra al azar y sustituyendo su valor por una letra al azar del alfabeto. Lo hacemos dos veces por cada cromosoma mutado.

Proveedor

private char supplier(int length) { final char result = new char(length); for (int i = 0; i < length; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); result = ALPHABET; } return result;}

El proveedor genera frases aleatorias tomando letras al azar del alfabeto. Cada frase tiene una longitud constante predefinida.

Función de terminación

private boolean termination(Collection<char> chars) { count++; final Optional<char> result = chars.stream() .filter(value -> round(fitness(value)) == expected.length) .findAny(); if (result.isPresent()) { System.out.println("Count: " + count); System.out.println(result.get()); return true; } final boolean terminated = count == 3000; if (terminated) { chars.forEach(System.out::println); } return terminated;}

La función de terminación cuenta el número de llamadas y devuelve true si hay una coincidencia exacta, o si el recuento de generación llega a 3.000.

Ejecución

Ahora estamos listos para probar nuestro algoritmo. Si lo ejecuta varias veces, notará que no todas las ejecuciones son exitosas. Cada vez, el número de iteraciones será diferente. Esto se debe a la naturaleza probabilística del algoritmo. El algoritmo tiene varios puntos en los que se puede mejorar. Se puede jugar con las probabilidades de cruce y mutación.

Bajar el número llevará a una solución estable pero lenta. Un menor número de cromosomas se verá afectado por los operadores genéticos y, por lo tanto, se requerirán más iteraciones para la solución.

Aumentar los números acelerará el algoritmo, pero también hará que la solución sea inestable. Los cromosomas aptos no sólo se conservarán, sino que también se verán afectados por los operadores genéticos. Por lo tanto, perderán sus genes “buenos”.

Es importante encontrar un buen equilibrio. Aumentar el número de iteraciones dará al algoritmo más oportunidades de encontrar una solución pero, por otro lado, llevará más tiempo. También puedes aplicar diferentes métodos de cruce y mutación. Una buena selección de estos operadores mejorará drásticamente la calidad de la solución.

Hemos cubierto sólo la punta del iceberg aquí. Tomamos un ejemplo que tiene sólo una entrada, y la entrada puede ser fácilmente presentada como un cromosoma. Los operadores genéticos son simples y sencillos.

Es muy interesante tomar un problema del mundo real y aplicarle el algoritmo genético. Descubrirá diferentes enfoques en la codificación de los datos de entrada reales, así como diferentes implementaciones de cruces y mutaciones.

Si un problema se puede expresar a través de un conjunto de parámetros que tenemos que adivinar para optimizar una métrica, podemos configurar rápidamente un AG que podemos utilizar para resolverlo.

Uno de los problemas más interesantes es la enseñanza de las redes neuronales artificiales. Podemos establecer que los parámetros optimizables sean las fuerzas de las sinapsis, y que la métrica de aptitud sea el porcentaje de entradas para las que nuestra red neuronal dio la respuesta correcta. Después, podemos sentarnos y dejar que nuestra red neuronal evolucione hacia la solución ideal que deseamos. O al menos hasta que consigamos algo lo suficientemente bueno, porque la evolución lleva su tiempo.