Introducción a los algoritmos genéticos en Java

I

Introducción

Los algoritmos genéticos son parte de una familia de algoritmos para la optimización global llamada Computación Evolutiva , que se compone de metaheurísticas de inteligencia artificial con aleatorización inspirada en la biología. ¡Vaya, las palabras se pueden organizar en cualquier orden! Pero aguanta, analizaremos esto:

  • La 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.
  • La Computación Evolutiva es una familia de algoritmos de optimización, que se inspiran específicamente 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 el comportamiento de hormigas, abejas, lobos y similares, así como muchas variaciones e implementaciones diferentes de cada uno de ellos.
  • La inteligencia artificial es, más comúnmente, una rama de la informática y una designación para los 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 se trata de idear soluciones correctas basadas en algunas propiedades inusuales de nuestros algoritmos que se pueden demostrar matemáticamente, o de soluciones aproximadas utilizando metaheurísticas.
  • Una metaheurística es una heurística de orden superior , 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 complejidad de tiempo mucho mayor que si tuviera que resolver la solución exacta. Entonces usamos una metaheurística para crear heurísticas para todo tipo de problemas diferentes.

¡Joder, eso es mucho para asimilar! La buena noticia es que realmente no lo 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 darle una apreciación de la inmensidad del 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 apuntan a emularlos. La idea básica es representar el dominio de posibles soluciones como un genoma discreto, una matriz finita de genes, y luego averiguar cuál de esas posibles soluciones es la correcta.

Esto se resuelve 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 satisfactoria. Dicha clasificación se denomina aptitud, mientras que la combinación de soluciones se denomina reproducción o cruzamiento.

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 aleatoria en un pequeño porcentaje de nuestros genomas para aumentar la probabilidad de que encontremos la solución correcta.

Los algoritmos genéticos se pueden aplicar en prácticamente cualquier problema de búsqueda, pero a menudo se dice que los algoritmos genéticos son la segunda mejor solución para cada problema. 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 diseñado 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 dejarlo funcionar 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 que luego todavía tome diez minutos o más. 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 utilizan 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 en 2D de un acantilado:

Digamos que queremos encontrar el máximo de la función fen el segmento dado. Sin embargo, verificar todos los puntos del segmento es imposible porque hay incontables números reales infinitos entre dos números reales diferentes. Incluso si decimos que estaremos contentos con una respuesta aproximada, y podemos simplemente verificar el valor de f(x)un millón de valores de xy tomar el máximo, eso podría en algunos escenarios ser una operación muy 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 con unas pocas medidas menos que un millón. Entonces, ¿cuál sería una buena manera de adivinar algunos valores agradables de xmedir para que no tengamos que escalar tantas veces, pero aún así podamos llegar a una solución bastante buena?

Representación genética

Para poder utilizar 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 de un cromosoma para codificar nuestra solución candidata. Otro término utilizado para la solución candidata es el genoma.

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

Una forma común de representar un genoma es una matriz de dígitos binarios. Esta representación es excelente porque entonces 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)definidos en ese segmento, podríamos definir el punto más a la izquierda de la función, que es a, para ser representado como 0000000000(diez ceros), y podríamos decir que el punto b más a la derecha es 1111111111(diez unos).

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

Si pes el valor de un número binario, podemos calcular el valor real correspondiente de xcon la siguiente fórmula:

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

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 {xa} {ba} (2 ^ n-1) Bigg]
$$

Hay muchas formas posibles de representar un genoma, y ​​la más conveniente 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 usted comprenda la forma de pensar detrás de él, no los ejemplos particulares.

Por ejemplo, digamos que se suponía que su algoritmo debía adivinar una palabra de 5 letras y puede saber cuántas letras acertó. Sería bastante natural usar una cadena como genoma en ese caso. Si estabas tratando de enseñarle a saltar sobre los agujeros en un juego, puedes usar una serie de valores booleanos, donde truesignifica saltar y falsesignifica correr, aunque nuevamente, podrías mapearlo para que 1significa saltar y 0significa correr.

Población

Cada generación es una colección de generalmente un número igual de genomas. Esta colección generalmente 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, de modo que podamos crear genomas más adecuados desde el principio. A veces, tenemos condiciones adicionales que debe cumplir una muestra válida.

Se prefiere generar el genoma para que necesariamente cumpla esas condiciones, sobre realizar comprobaciones y arreglos después de generarlo, porque eso desperdicia mucho tiempo y los tamaños de generación suelen ser enormes.

Función fitness y función objetiva

Para evaluar cuál de nuestros genomas debería pasar a la siguiente generación a través de la reproducción u otro medio, 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 del todo nuestro f(x)desde la imagen del acantilado, está destinado a aproximarse.

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

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

¿Por qué utilizar dos funciones diferentes? Bueno, debido a que la función de acondicionamiento físico se realiza en cada genoma en cada generación, es muy importante que sea rápido. No tiene que ser muy preciso, siempre que clasifique más o menos los genomas por calidad razonablemente bien.

Por otro lado, la función objetivo se llama solo una vez por generación, por lo que podemos permitirnos el uso de una función más costosa y más precisa, para saber con certeza qué tan bueno es nuestro resultado. La función objetivo sería nuestra f(x)en la imagen de la cima del acantilado, mientras que la función de aptitud sería su aproximación 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 a todos los individuos de una población se les permite reproducirse, y debemos tener en cuenta varias cosas al elegir cuáles llevarán sus genes a la próxima generación.

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

Si todas las soluciones de 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 cuanto a fitness, pero que 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

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

$$
p = frac {f (i)} {suma_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 aptitud 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, menor que la suma total de aptitud de la generación. Luego repasamos nuestra generación y sumamos su aptitud una por una a otra suma. Cuando esa suma alcanza o supera n, tomamos el genoma actual como ganador.

Selección del torneo

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

  • El torneo determinista siempre selecciona el mejor genoma en un torneo. Básicamente, se trata de buscar un genoma con una aptitud máxima o mínima.
  • El torneo unidireccional es un torneo con un solo competidor y es equivalente a una selección estocástica (aleatoria).
  • El torneo de aptitud proporcional clasifica los genomas de acuerdo con la aptitud y los indexa. A icontinuación, se elige el genoma 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 será 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 el sentido de que los genomas con una aptitud pequeña tendrán cada vez menos posibilidades de ser recogidos (según el método).

La selección de torneos se usa ampliamente y tiene muchas ventajas sobre otros tipos de selección. Es fácil de implementar, funciona igualmente bien para la minimización y 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 aptitud. Para ello, realizamos una operación de cruce.

En esencia, el cruce toma dos genomas progenitores elegidos por selección y crea varios genomas secundarios (uno o más). La forma en que se mezclan 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 uno de los padres y una parte del otro.

Hay varios tipos de cruces:

  • crossover de un solo punto
  • cruce de dos puntos
  • cruce de puntos k
  • cruce uniforme: existe una cierta probabilidad de que el gen en un lugar determinado se herede del padre 1, de lo contrario, se hereda del padre 2
  • crossover especial diseñado para satisfacer las limitaciones 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 suele 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 estamos generando virtualmente nuevos genomas para cada generación. Pero si es extremadamente bajo, podemos lograr una convergencia temprana.

La mutación puede limitarse a un gen, ocurrirle a cada gen con una ligera probabilidad, oa 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 y cuando tenga un buen razonamiento detrás.

Políticas de reemplazo de generación

Las políticas 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 a 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:
    • El reemplazo de los peores reemplaza los genomas con menor aptitud con los nuevos hijos.
    • El reemplazo aleatorio reemplaza los genomas aleatorios con los nuevos hijos.
    • La competencia intergeneracional reemplaza a los padres con sus hijos si la aptitud de los niños es superior a la de sus padres.
    • El reemplazo de torneos funciona como la selección de torneos, excepto que en lugar del mejor, elegimos el peor genoma.

El elitismo es una estrategia opcional que se puede combinar con otras políticas. El elitismo significa que una selección de genomas de alta aptitud está protegida contra el reemplazo, lo que significa que se llevan completos a la próxima generación. Ésta es una buena estrategia para evitar regresiones accidentales.

Si hay mejores niños en la nueva generación, superarán y eliminarán los genomas protegidos por el elitismo. Pero si todos los niños empeoran, 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 para la 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 de generaciones preestablecido
  • El algoritmo ha superado el tiempo máximo de ejecución o ha gastado otros recursos limitados
  • El mejor genoma está estancado: 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. Generalmente 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 verse algo así. No es necesario comprender esto completamente en este momento, pero debería servir como una buena idea de cómo puede verse:

// 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 la ciencia de la computación: el problema del viajante:

Problema de vendedor ambulante con algoritmos genéticos en Java

Si está interesado en aprender más acerca de los algoritmos genéticos, ¡un gran libro para comenzar es Algoritmos genéticos en conceptos básicos de Java !

Conclusión

Los algoritmos genéticos son una herramienta poderosa y conveniente. Puede que no sean tan rápidas 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 una cereza en la parte superior, son infinitamente fascinantes de implementar cuando piensas en los procesos evolutivos en los que se basan y en cómo eres el cerebro detrás de una mini-evolución propia.

 

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad