Introducci贸n a los algoritmos gen茅ticos en Java

    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 鈥嬧媗a 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 鈥嬧媏n 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.

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *