Introducción a los Algoritmos Genéticos en Java

Los algoritmos genéticos son parte de una familia de algoritmos para la optimización global llamada Computación Evolutiva, que se compone de inteligencia artificial...

Introducción

Los algoritmos genéticos forman parte de una familia de algoritmos para la optimización global denominada Computación evolutiva, que se compone de metaheurísticas de inteligencia artificial con aleatorización inspiradas en la biología. ¡Guau, las palabras realmente se pueden organizar en cualquier orden! Pero aguanta, lo desglosaremos:

  • Optimización global es una rama de las matemáticas aplicadas que se utiliza para encontrar mínimos o máximos globales de funciones. Para encontrar estos valores en una eficiencia de tiempo razonable, utilizamos optimizaciones de inteligencia artificial. Muchas cosas se pueden expresar como funciones, lo que nos permite resolver una variedad de problemas con optimizaciones.
  • Computación Evolutiva es una familia de algoritmos para la optimización, que están específicamente inspirados en la biología. Los algoritmos genéticos están diseñados para simular la mutación y la selección natural, pero otros tipos de algoritmos simulan comportamientos de hormigas, abejas, lobos y similares, así como muchas variaciones e implementaciones diferentes de cada uno de ellos.
  • Inteligencia artificial es, más comúnmente, una rama de la informática y una designación para algoritmos que se ocupan de problemas en los que hay una explosión combinatoria. Esos problemas no se pueden resolver en un tiempo razonable con algoritmos clásicos, por lo que la inteligencia artificial consiste en idear soluciones correctas basadas en algunas propiedades inusuales demostrables matemáticamente de nuestros algoritmos, o aproximar soluciones utilizando metaheurísticas.
  • Una metaheurística es una [heurística] de orden superior (https://en.wikipedia.org/wiki/Heuristic), diseñada para ser un patrón para la creación de heurísticas. Las heurísticas son técnicas para aproximar la solución de un problema con una mucho mejor complejidad del tiempo que si tuviera que resolver por el solución exacta. Así que usamos una metaheurística para crear heurísticas para todo tipo de problemas diferentes.

Sheesh, ¡eso es mucho para asimilar! La buena noticia es que en realidad no la necesitará para comprender la esencia del artículo, pero se incluyó para brindarle una imagen más amplia del contexto en el que existen este tipo de algoritmos y para que pueda apreciar la inmensidad de el campo de la inteligencia artificial.

Conceptos básicos

Los algoritmos genéticos, como se mencionó, se inspiraron en la evolución y la selección natural, y pretenden emularla. La idea básica es representar el dominio de las posibles soluciones como un genoma discreto, una matriz finita de genes, y luego averiguar cuál de esas posibles soluciones es la correcta.

Usted resuelve esto creando una población aleatoria de soluciones y 'calificando' esas soluciones de alguna manera, y luego combinando las mejores soluciones en una nueva para crear una generación de soluciones aún mejor, hasta que la 'calificación' sea satisfactorio. Dicha calificación se denomina fitness, mientras que la combinación de soluciones se denomina reproducción o crossover.

Debido a que el algoritmo se basa en la aleatoriedad, es posible que converja accidentalmente en una solución incorrecta. Para evitar eso, realizamos una mutación al azar en un pequeño porcentaje de nuestros genomas para aumentar la probabilidad de que encontremos la solución adecuada.

Los algoritmos genéticos se pueden aplicar prácticamente a cualquier problema de búsqueda, pero a menudo se dice que los algoritmos genéticos son la segunda mejor solución para todos los problemas. A lo que se refiere este adagio es que los algoritmos genéticos son bastante fáciles de implementar, pero pueden no ser tan eficientes como un algoritmo hecho a mano para un problema en particular.

Sin embargo, cuando se trata de problemas difíciles, puede llevar bastante tiempo crear una solución perfecta. A veces preferimos hacer un algoritmo genético en una hora o dos y dejar que funcione durante media hora, que pasar días o semanas analizando las propiedades matemáticas de un problema en particular para diseñar un algoritmo eficiente, para luego tenerlo todavía diez minutos o algo de tiempo de ejecución.

Por supuesto, si un problema en particular tiene una solución ya conocida, o si el tiempo de ejecución del algoritmo es de vital importancia, los algoritmos genéticos pueden no ser su solución ideal. Se usan principalmente en problemas con grandes necesidades computacionales donde la solución puede ser lo suficientemente buena y no necesita ser perfecta.

Como ejemplo de dónde puede aplicar un algoritmo genético, observe el siguiente gráfico que representa un mapa de altura 2D de la cima de un acantilado:

{.img-responsive}

Digamos que queremos encontrar el máximo de la función f en el segmento dado. Sin embargo, verificar cada punto en el segmento es imposible porque hay incontablemente infinito números reales entre dos números reales diferentes. Incluso si decimos que estaremos contentos con una respuesta aproximada, y podemos verificar el valor de f(x) para un millón de valores de x y tomar el máximo, en algunos escenarios podría ser muy operación costosa.

Por ejemplo, si cada punto de la montaña tuviera que ser escalado y su altura medida a mano, digamos que su asistente se cansaría de usted por unas pocas medidas menos de un millón. Entonces, ¿cuál sería una buena manera de adivinar algunos buenos valores de x para medir, de modo que no tengamos que escalar tantas veces, pero aún podamos llegar a una solución bastante buena?

Representación genética

Para poder usar el algoritmo genético, necesitamos representarlo de alguna manera. Las diferentes especies tienen un número diferente de cromosomas, cada uno de los cuales contiene información vital sobre la construcción del espécimen. En nuestro caso, normalmente no necesitaremos más que un solo cromosoma para codificar nuestra solución candidata. Otro término utilizado para la solución candidata es genoma.

El genoma debe representarse de una manera que nos permita generar fácilmente un genoma válido al azar, calcular su aptitud rápidamente y reproducir y mutar genes específicos. Por supuesto, técnicamente podría permitir que su algoritmo se ejecute con soluciones no válidas en la población y esperar que se eliminen, pero es simplemente ineficiente y, por lo general, innecesario.

Una forma común de representar un genoma es una matriz de dígitos binarios. Esta representación es excelente porque podemos usar operaciones binarias rápidas para trabajar con ella, y es muy intuitivo imaginar cómo evoluciona. Por ejemplo, dado un segmento [a,b] y una función f(x) definida en ese segmento, podríamos definir el punto más a la izquierda de la función, que es a, para que se represente como 0000000000 (diez ceros), y podríamos decir que el punto b más a la derecha es 1111111111 (diez unos).

Hay 2^10=1024 puntos que podemos denotar con estas matrices de longitud 10. Digamos longitud ([a,b])/1024 = l. Entonces podríamos representar a+l como 0000000001, a+2l como 0000000010, y así sucesivamente.

Si p es el valor de un número binario, podemos calcular el valor real correspondiente de x con la siguiente fórmula:

$$
x=a+\frac{p}{2^n-1}(b-a)
$$

Por otro lado, para asignar una representación binaria a un número del intervalo [a,b], usaríamos la siguiente ecuación:

$$
p=\Bigg[\frac{x-a}{b-a}(2^n-1)\Bigg]
$$

Hay muchas formas posibles de representar un genoma, y ​​la conveniente para usar dependerá del problema específico al que se enfrente. Es importante recordar que un algoritmo genético no es solo un algoritmo, sino una metaheurística, lo que significa que el objetivo de este artículo es que comprenda la forma de pensar detrás de él, no los ejemplos particulares.

Por ejemplo, supongamos que su algoritmo debe adivinar una palabra de 5 letras y puede saber cuántas letras acertó. Sería bastante natural usar una cadena como su genoma en ese caso. Si estuviera tratando de enseñarle a saltar sobre agujeros en un juego, puede usar una serie de valores booleanos, donde “verdadero” significa saltar y “falso” significa correr, aunque nuevamente, podría mapearlo para que “1” signifique saltar y 0 significa ejecutar.

Población

Cada generación es una colección de generalmente un número igual de genomas. Esta colección normalmente se denomina población de soluciones candidatas, o población e individuos. La generación inicial está poblada con individuos generados completamente al azar y distribuidos uniformemente en el espacio de búsqueda. A veces podemos adivinar con mayor precisión dónde estará la solución, por lo que podemos crear genomas más adecuados desde el principio. A veces, tenemos condiciones adicionales que debe cumplir un espécimen válido.

Es preferible generar el genoma para que necesariamente cumpla con esas condiciones, a realizar verificaciones y correcciones después de generarlo, porque eso desperdicia mucho tiempo y los tamaños de generación suelen ser enormes.

Función de fitness y función objetiva

Para evaluar cuál de nuestros genomas debe pasar a la siguiente generación a través de la reproducción u otros medios, necesitamos una función para calcular su valor de una manera que nos permita comparar los valores de dos genomas diferentes. Esta función se llama función de aptitud y podemos denotarla como f(x). Aunque no es exactamente nuestra f(x) de la imagen del acantilado, está destinada a aproximarla.

Por lo general, siempre es positivo, y cuanto mayor sea el número, mejor será el genoma. Cuando usamos una función de fitness de este tipo, estamos maximizando el espacio de búsqueda, buscando el valor máximo de fitness.

La función objetivo es bastante similar a la función de aptitud, y en muchos casos son lo mismo, pero a veces la distinción es importante. La función objetivo se utiliza para calcular la aptitud del mejor genoma en cada generación (el que tiene el valor máximo de la función de aptitud) para comprobar si cumple unas condiciones predeterminadas.

¿Por qué usar dos funciones diferentes? Bueno, debido a que la función de aptitud se realiza en cada genoma en cada generación, es muy importante que sea rápido. No tiene que ser muy preciso, siempre y cuando clasifique razonablemente bien los genomas por calidad.

Por otro lado, la función objetivo se llama solo una vez por generación, por lo que podemos darnos el lujo de usar una función más costosa y más precisa, para saber con seguridad qué tan bueno es nuestro resultado. La función objetivo sería nuestra f(x) en la imagen del acantilado, mientras que la función de aptitud sería su aproximación más cercana.

Selección

La selección es un método utilizado para determinar y transferir los buenos atributos de una generación a la siguiente. No todos los individuos de una población pueden reproducirse, y debemos tener en cuenta varias cosas al elegir cuáles transmitirán sus genes a la próxima generación.

La primera idea sería, por supuesto, simplemente tomar la parte superior, digamos el 25%, y hacer que se reproduzcan. El problema con este método es que muy a menudo causa lo que se llama convergencia temprana. Por ejemplo, mira la imagen de abajo:

{.img-responsive}

Si todas las soluciones en la generación actual están en el área azul y solo elegimos las de mayor aptitud, terminaremos eligiendo las del máximo local. Los de la izquierda, que son un poco peores en lo que respecta a la forma física, pero se acercan a la solución real, se quedarán fuera de la próxima generación.

Con cada generación, el área azul se volverá más y más estrecha porque combinaremos las soluciones que están dentro de ella, hasta que finalmente nos detengamos en el máximo local. Estamos tratando de encontrar el máximo global (etiquetado como 'solución real'), por lo que esto no es deseable.

Para evitar esto, utilizamos métodos de selección especiales.

Selección de ruleta

{.img-responsive}

Una buena forma de seleccionar los genomas más aptos sería seleccionarlos con la probabilidad proporcional a su aptitud. De esta manera, incluso los genomas menos aptos tendrán la oportunidad de ser seleccionados, pero será una oportunidad menor. Esto es similar a una ruleta donde las porciones del pastel no son iguales. En la imagen de arriba, el genoma etiquetado como ‘c’ tiene la mayor aptitud y, por lo tanto, ocupa la mayor parte de la ruleta. La probabilidad de que cada genoma i participe en la reproducción (que gane la ruleta) es:

$$
p=\frac{f(i)}{\sum_j^N f(j)}
$$

En otras palabras, es la aptitud de dicho genoma, dividida por la aptitud resumida de toda la generación. Debido a que la función de fitness siempre es positiva, este número estará entre 0 y 1.

La forma en que logramos esto en el código es generar un número positivo aleatorio n, más pequeño que la suma total de aptitud de la generación. Luego pasamos a través de nuestra generación y sumamos su estado físico uno por uno a otra suma. Cuando esa suma alcanza o supera n, tomamos el genoma actual como el ganador.

Selección de torneos {#selección de torneos}

En la selección de torneos, elegimos “k” genomas aleatorios para participar en un torneo y seleccionamos al ganador. Cuanto mayor sea la aptitud de un genoma, más probable es que gane (o menos probable, si estamos minimizando). Hay diferentes tipos de torneos:

  • El torneo determinista siempre selecciona el mejor genoma en un torneo. Esto es esencialmente solo buscar un genoma con una aptitud máxima o mínima.
  • El torneo de 1 vía es un torneo con un solo competidor y es equivalente a la selección estohastica (aleatoria).
  • El torneo proporcional de aptitud clasifica los genomas de acuerdo con la aptitud y los indexa. El i`ésimo genoma se elige entonces con la probabilidad:

$$
p(1-p)^{i-1}
$$

Al decidir el tamaño del torneo, se debe tener en cuenta que cuanto menor sea el número, más probable es que el algoritmo se comporte como un torneo de 1 vía y sea casi aleatorio, pero cuanto mayor sea el tamaño, más determinista será, en ese sentido. los genomas con una aptitud pequeña tendrán cada vez menos posibilidades de ser elegidos (dependiendo del método).

La selección de torneos es muy utilizada y tiene muchas ventajas sobre otros tipos de selección. Es fácil de implementar, funciona igualmente bien para la minimización y la maximización, es fácil de paralelizar y, si necesita ajustar la presión de selección, puede hacerlo fácilmente cambiando el tamaño del torneo.

Transversal

El objetivo de crear una nueva generación es transmitir los buenos atributos de la última generación, pero crear nuevas variaciones para intentar mejorar aún más la forma física. Para ello, realizamos una operación de cruce.

En esencia, el cruce toma dos genomas principales elegidos por selección y crea una serie de genomas secundarios (uno o más). La forma en que mezcla los dos genomas puede variar ligeramente (como veremos en la implementación más adelante), pero la esencia es que tomamos una parte de los genes de un padre y una parte del otro.

Hay varios tipos de cruces:

  • cruce de un solo punto

{.img-responsive}

  • cruce de dos puntos

{.img-responsive}

  • cruce de punto k
  • cruce uniforme - hay una cierta probabilidad de que el gen en un lugar determinado se herede del padre 1, de lo contrario se hereda del padre 2
  • cruce especial diseñado para satisfacer las restricciones de un problema particular

Mutación

Probablemente recuerde el problema de la convergencia temprana mencionado anteriormente. Si bien el uso de buenos métodos de selección ayuda a mitigarlo, la convergencia temprana todavía ocurre a veces debido a la naturaleza aleatoria de los algoritmos genéticos. Para reducir aún más la probabilidad de que suceda, podemos mutar genomas dentro de una nueva generación con cierta probabilidad. El número de genomas mutados normalmente será inferior al 1%. Si la tasa de mutación es demasiado alta, nuestra búsqueda comenzará a parecerse a una búsqueda aleatoria, porque virtualmente estamos generando nuevos genomas para cada generación. Pero si es extremadamente bajo, podemos obtener una convergencia temprana.

La mutación puede limitarse a un gen, ocurrir en cada gen con una pequeña probabilidad o en una subsecuencia completa de genes. Para la mayoría de los problemas, tiene más sentido mutar un gen por genoma, pero si cree que su problema puede beneficiarse de algunas formas específicas de mutación, no tenga miedo de probarlo, siempre que tenga un buen razonamiento detrás.

Políticas de reemplazo de generación

Las pólizas de reemplazo de generación son reglas que usamos para decidir quién pasa a la siguiente generación. Hay dos tipos principales de algoritmos genéticos basados ​​en las reglas que utilizan:

  • Los algoritmos genéticos generacionales seleccionan genomas para el cruce de la generación actual y reemplazan toda la próxima generación con niños creados a partir del cruce y la mutación.
  • Los algoritmos genéticos de estado estable reemplazan a los miembros de la población tan pronto como los niños se crean de acuerdo con alguna política. Eso significa que los niños pueden ser elegidos para participar en una mayor reproducción dentro de la generación de sus padres. Hay muchas políticas diferentes para el reemplazo:
    • Replacement of the worst replaces the genomes with the lowest fitness with the new children.
    • Random replacement replaces random genomes with the new children.
    • Intergenerational competition replaces the parents with their children if the children's fitness is higher than their parents'.
    • Tournament replacement works like tournament selection, except instead of the best we choose the worst genome.

Elitismo es una estrategia opcional que se puede combinar con otras políticas. Elitismo significa que una selección de genomas de alta aptitud están protegidos contra el reemplazo, lo que significa que se transmiten completos a la siguiente generación. Esta es una buena estrategia para evitar una regresión accidental.

Si hay mejores niños en la nueva generación, se desempeñarán mejor y eliminarán los genomas protegidos por el elitismo. Pero si todos los niños resultan ser peores, notaremos que nuestro mejor estado físico ya no mejora, lo que significa que hemos convergido (para bien o para mal).

Terminación

Seguimos construyendo nuevas generaciones hasta llegar a una condición de terminación. Algunas de las condiciones comunes son:

  • El mejor genoma ha satisfecho los criterios mínimos de terminación evaluados por la función objetivo
  • Hemos alcanzado un número máximo preestablecido de generaciones
  • El algoritmo excedió el tiempo máximo de ejecución o gastó otros recursos limitados
  • El mejor genoma se está estancando - las iteraciones sucesivas ya no producen mejores resultados
  • Una combinación de varios de los anteriores.

Tenemos que tener cuidado de establecer buenas condiciones de terminación para que nuestro programa no termine en un bucle infinito. Por lo general, se recomienda limitar el número de generaciones o el tiempo de ejecución, como mínimo.

Implementación

Dicho esto, un bucle de algoritmo genético típico podría parecerse a esto. No hay necesidad de entender esto completamente en este momento, pero debería servir como una buena idea de cómo puede verse:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// Create genetic algorithm with parameters such as population size
// mutation rate, crossover rate, elitism count, tournament size 
GeneticAlgorithm ga = new GeneticAlgorithm(200, 0.05, 0.9, 2, 10);

// Initializing the population with chromosome length of 128, this
// number depends on the number of genes needed to encode the
// solution
Population population = ga.initPopulation(128);

// Evaluate the population for global fittness
ga.evalPopulation(population, maze);
       
int generation = 1;
       
// Start evolution loop
while (!ga.isTerminationConditionMet(generation, maxGenerations)) {
    Individual fittest = population.getFittest(0);

    // Print fittest individual from population to track progress
    System.out.println("G" + generation + " Best solution (" + fittest.getFitness() + "): " + fittest);

    // Crossover population
    population = ga.crossoverPopulation(population);
    // Mutate population
    population = ga.mutatePopulation(population);
    // Evaluate population
    ga.evalPopulation(population, maze);
           
    // Increment generation counter
    generation++;
}

En el próximo artículo repasaremos la implementación de un algoritmo genético resolviendo un problema clásico en informática: el problema del viajante de comercio:

Problema del viajante de comercio con algoritmos genéticos en Java

Si está interesado en aprender más sobre algoritmos genéticos, un gran libro para comenzar es [Algoritmos genéticos en conceptos básicos de Java] (https://stackabu.se/genetic-algorithms-in-java-basics-book) !

Conclusión

Los algoritmos genéticos son una herramienta poderosa y conveniente. Es posible que no sean tan rápidos como las soluciones diseñadas específicamente para el problema en cuestión, y es posible que no tengamos muchas pruebas matemáticas de su eficacia, pero pueden resolver cualquier problema de búsqueda de cualquier dificultad y no son demasiado difíciles de dominar. y aplicar

Y como guinda del pastel, son infinitamente fascinantes de implementar cuando piensas en los procesos evolutivos en los que se basan y cómo eres el autor intelectual detrás de una minievolución propia.