Algoritmos Genéticos: Búsqueda y Optimización por Selección Natural

¿Qué son los algoritmos genéticos?

En los últimos años, ha habido un gran revuelo en torno a la Inteligencia Artificial (IA). Las principales empresas como Google, Apple y Microsoft están trabajando activamente en el tema. De hecho, la IA es un paraguas que cubre muchos objetivos, enfoques, herramientas y aplicaciones. Los algoritmos genéticos (GA) son solo una de las herramientas para la búsqueda inteligente a través de muchas soluciones posibles.

GA es una técnica de búsqueda y optimización metaheurística basada en 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 posibles soluciones para el problema. La idea es que la "evolución" encontrará una solución óptima para el problema después de varias 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 GA es la aptitud. Los cromosomas que son más aptos tienen una mejor oportunidad de supervivencia. La aptitud es una función que mide la calidad de la solución representada por el cromosoma. En esencia, cada cromosoma dentro de la población representa los parámetros de entrada. Por ejemplo, si su problema contiene dos parámetros de entrada, como el precio y el volumen de negociación, 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 pares de progenitores para la reproducción . Cada niño toma características de sus padres. Básicamente, el niño representa una recombinación de características de sus padres: algunas de las características se toman de un padre 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 subsiguiente tendrá una mejor condición física. En algún momento, una generación contendrá un cromosoma que representará una solución suficientemente buena para nuestro problema.

GA es poderoso y ampliamente aplicable para problemas complejos. Existe 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 programación, transporte, enrutamiento, tecnologías de grupo, diseño de diseño, entrenamiento de redes neuronales y muchas otras.

Poner las cosas en práctica

El ejemplo que veremos se puede considerar el "Hola Mundo" de GA. 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 emparejamiento de palabras trata de desarrollar 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.

Dado que hay 26 letras posibles para cada una de las 13 ubicaciones [excluyendo los espacios en blanco] en la lista, la probabilidad de obtener la frase correcta de forma puramente aleatoria es (1/26)^13=4.03038×10-19, que es aproximadamente dos posibilidades de un [quintillón] (Gen & Chong, 1997).

Definiremos el problema un poco más ampliamente aquí, haciendo que la solución sea aún más difícil. Supongamos que no estamos limitados al idioma inglés o una frase específica. Podemos terminar tratando con cualquier alfabeto, o incluso con cualquier conjunto de símbolos. No tenemos conocimiento del idioma. Ni siquiera sabemos si hay algún idioma en absoluto.

Digamos que nuestro oponente pensó en una frase arbitraria, incluidos los espacios en blanco. Sabemos la longitud de la frase y la cantidad de símbolos en el alfabeto. Ese es el único conocimiento que tenemos. Después de cada intento, nuestro oponente nos dice cuántas letras hay en su lugar.

Cada cromosoma es una secuencia de índices de los símbolos en el alfabeto. Si estamos hablando del alfabeto inglés, entonces 'a' se representará con 0, 'b' con 1, 'c' con 2, y así sucesivamente. Entonces, por ejemplo, la palabra "ser" se representará como [4, 1] .

Demostraremos todos los pasos a través de fragmentos de código Java, pero no se requiere conocimiento de Java para comprender cada paso.

Núcleo de algoritmo genético

Podemos comenzar 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 conjunto simple de pasos en los que consiste más o menos cada GA. En el paso de inicialización, generamos una población inicial de frases. El tamaño de la población está determinado por el tamaño de la populationSize . La forma en que se genera la frase depende de la implementación del supplier .

Dentro del paso de iteración, hacemos evolucionar 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 en la población. La termination encapsula una implementación exacta.

Dentro de cada iteración, realizamos los pasos típicos de GA:

1. Realice una selección sobre la población basada en la aptitud cromosómica.
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 e independiente del dominio. Será lo mismo para todos los problemas. Lo que necesitará ajustar es la implementación de operadores genéticos. A continuación, analizaremos de cerca cada uno de los operadores de GA mencionados anteriormente.

Selección

Como ya sabemos, la selección es un proceso de encontrar sucesores de los cromosomas actuales, los cromosomas que se adaptan mejor a nuestro problema. Durante la selección, debemos asegurarnos de que los cromosomas con mejor aptitud física tengan más posibilidades de supervivencia.

 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[fitnesses.length]; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses[i] / totalFitness; probabilities[i] = sum; } probabilities[probabilities.length - 1] = 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.

La parte del rango que toma un cromosoma es proporcional a su aptitud. Esto da como resultado que un cromosoma más en forma obtenga una porción más grande. Luego echamos un vistazo al azar a un número entre 0 y 1 y encontramos un rango que incluye el número. Obviamente, los rangos más grandes tienen mayores posibilidades de ser seleccionados y, por lo tanto, los cromosomas más aptos tienen más posibilidades de supervivencia.

Debido a que no conocemos los detalles sobre 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 tasas 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 reducidas 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, por lo que lo establecemos en 1 solo para estar seguros.

Finalmente, 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 notar, el mismo cromosoma puede seleccionarse varias veces.

Transversal

Ahora necesitamos los cromosomas para "reproducir".

 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[2 * i]; final int index2 = indexes[2 * i + 1]; 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, lo que permite que ocurra cualquier combinación. Tomamos pares de padres y aplicamos el operador de crossover . Aplicamos el operador dos veces para cada par porque necesitamos mantener el mismo tamaño de la población. Los niños reemplazan a sus padres en la población.

Mutación

Finalmente, 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 probabilidad predefinida de probabilidad de mutationProbability , realizamos una "mutación" en los cromosomas. La mutación en sí misma se define por mutation .

Configuración de algoritmos específicos del problema

Ahora echemos un vistazo a 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 fitness
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í está 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 cruzado 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 de 0,25, por lo que esperamos que, en promedio, el 25 por ciento de los cromosomas se seleccionen para el cruce. Realizamos un procedimiento simple para el cruce de un par de cromosomas. Generamos un número aleatorio n del rango [0..length] , donde la length es la longitud de un cromosoma. Ahora emparejamos el par seleccionado tomando los primeros n caracteres de un cromosoma y los caracteres restantes del segundo.

Función de acondicionamiento físico

 private double fitness(char[] value) { return range(0, value.length) .filter(i -> value[i] == expected[i]) .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[location] = ALPHABET[letter]; } return result; }

La operación de mutación se realiza de forma independiente en cada cromosoma. La probabilidad de mutación es 0,05, por lo que esperamos que, en promedio, el cinco por ciento de la población mute. Mutamos eligiendo una posición de letra aleatoria y reemplazando su valor con una letra aleatoria 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[i] = ALPHABET[letter]; } return result; }

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

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 3000.

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. Puedes jugar con probabilidades de cruce y mutación.

Reducir el número conducirá a una solución estable pero lenta. Los operadores genéticos afectarán a un número menor de cromosomas 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 solo 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 le dará al algoritmo más oportunidades de encontrar una solución pero, por otro lado, llevará más tiempo. También puede 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.

¿Qué sigue?

Hemos cubierto solo la punta del iceberg aquí. Tomamos un ejemplo que tiene solo una entrada, y la entrada se puede presentar fácilmente como un cromosoma. Los operadores genéticos son claros y simples.

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

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 GA que podemos usar para resolverlo.

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