Algoritmo Genético

Este elemento es una ampliación de los cursos y guías de Lawi. Ofrece hechos, comentarios y análisis sobre este tema. [aioseo_breadcrumbs] En inglés: Genetic Algorithm.

Algoritmo Genético en el Aprendizaje Automatizado

La esencia del aprendizaje automático es la búsqueda de la mejor solución a nuestro problema: encontrar un clasificador que clasifique de la forma más correcta posible no solo los ejemplos de formación, sino también los ejemplos futuros.Entre las Líneas En otro lugar se explicó el principio de una de las técnicas de búsqueda basadas en la IA más populares, la llamada “escalada”, y se mostró cómo puede utilizarse en la inducción del clasificador.

Existe otro enfoque de búsqueda: el Algoritmo Genético, inspirado en los principios de la evolución darwiniana. El lector debe familiarizarse con él porque la técnica puede ser muy útil para tratar diversos problemas de aprendizaje de las máquinas. Este texto presenta el algoritmo genético de base.

Observaciones históricas

La idea de fundamentar el principio de la evolución biológica en la forma del algoritmo genético se debe a Holland, aunque algunos otros autores sugirieron algo similar un poco antes. Entre ellos, quizás Rechenberg merece ser mencionado, mientras que a Fogel y otros se les debe atribuir el mérito de haber sido pioneros en la idea de la programación genética. La forma concreta de aplicar el algoritmo genético a las selecciones del clasificador k es de Rozsypal y Kubat.

Visión General

El algoritmo genético, inspirado en la evolución darwiniana, es una alternativa popular a las técnicas clásicas de búsqueda de inteligencia artificial. La implementación más simple funciona con cadenas binarias.

El algoritmo somete a una población de individuos a tres operaciones esenciales: supervivencia basada en la función de aptitud, recombinaciones de pares de cromosomas y mutación. (Tal vez sea de interés más investigación sobre el concepto). También se utiliza a veces la inversión de una subcadena.

Uno de los problemas más frecuentes en las aplicaciones prácticas del algoritmo genético es la degeneración prematura de una población. (Tal vez sea de interés más investigación sobre el concepto). Una forma de detectarla es considerar la diversidad de los cromosomas de la población. (Tal vez sea de interés más investigación sobre el concepto). Una solución añadirá a la población cromosomas creados artificialmente. También el operador de inversión es útil, aquí.

Las implementaciones alternativas del algoritmo genético utilizan cadenas de números, símbolos, cadenas mixtas, o incluso estructuras de árboles.

El algoritmo genético de base

Describamos primero brevemente el principio general del algoritmo genético, relegando los detalles de la implementación a la siguiente sección.
La filosofía básica En esta sección, el clasificador codificará en forma de cromosoma, que la mayoría de las veces será una cadena de bits que a veces se denominan “genes”. El algoritmo genético opera con una población de cromosomas, cada uno de los cuales describe a un individuo (un clasificador). A cada uno de esos individuos se le asigna un valor mediante una función de aptitud; este valor dependerá normalmente del rendimiento (véase una definición en el diccionario y más detalles, en la plataforma general, sobre rendimientos) del clasificador. La función de aptitud desempeña un papel análogo al de la función de evaluación en la búsqueda heurística.

El bucle del algoritmo genético El algoritmo genético funciona en un bucle sin fin.Entre las Líneas En cada momento, hay una población de individuos, cada uno con un cierto valor de la función de aptitud. Este valor determina entonces el tamaño del segmento perteneciente al individuo en una “rueda de la fortuna” que determina las posibilidades de supervivencia del individuo. Es importante entender la naturaleza probabilística del proceso. Mientras que un individuo con un segmento más grande disfruta de una mayor probabilidad de supervivencia, no hay garantía de ello porque el juego de supervivencia no es determinante.Entre las Líneas En el mundo real, también, un espécimen con excelentes genes puede perecer en un tonto accidente, mientras que un débil puede lograrlo por simple buena suerte.Si, Pero: Pero a largo plazo, y en grandes poblaciones, las leyes de la probabilidad favorecerán a los genes que contribuyen a la alta aptitud.

Los especímenes supervivientes elegirán entonces “parejas de apareamiento”.Entre las Líneas En el proceso de apareamiento, los cromosomas de los individuos participantes se recombinan (véase más abajo), lo que da lugar a un par de nuevos cromosomas. Estos nuevos cromosomas pueden ser sometidos posteriormente a una mutación, que esencialmente añade ruido a las cadenas de genes.

Cómo funciona el Bucle sin fin

Una vez que se ha creado una nueva población, el proceso entra en un nuevo ciclo en el que los individuos se someten a la misma rueda de la fortuna, seguido de apareamiento, recombinación y mutación, y la historia sigue y sigue hasta que se detiene por un criterio de terminación apropiado. Obsérvese cómo los ocasionales giros equivocados son eliminados por la naturaleza probabilística del proceso. Un cromosoma de baja calidad puede sobrevivir a la rueda de la fortuna por casualidad; pero si los valores de aptitud de sus hijos permanecen bajos, los genes perecerán en las generaciones siguientes de todos modos. Por otra parte, algunos de los genes de un individuo poco prometedor pueden resultar útiles cuando están incrustados en diferentes cromosomas a los que pueden entrar por recombinación. (Tal vez sea de interés más investigación sobre el concepto). Al darles una segunda oportunidad ocasional, el proceso ofrece una flexibilidad que sería imposible en un entorno más determinista.

Implementación de los módulos individuales

Veamos más de cerca cómo implementar en un programa de ordenador los aspectos básicos del algoritmo genético: el juego de supervivencia, el proceso de apareamiento (selección de pareja), la recombinación de cromosomas y la mutación. (Tal vez sea de interés más investigación sobre el concepto). Para empezar, discutiremos solo soluciones muy simples, relegando las técnicas más avanzadas a secciones posteriores.

Población inicial

El enfoque más común para crear la población inicial empleará un generador de números aleatorios. A veces, el ingeniero puede confiar en algunos conocimientos que pueden ayudarle a crear cromosomas iniciales que se sabe que superan a los individuos generados al azar.Entre las Líneas En el ámbito de los “pasteles”, este papel puede ser desempeñado por las descripciones de los ejemplos positivos.

Puntualización

Sin embargo, hay que asegurarse de que la población inicial sea suficientemente grande y tenga suficiente diversidad.

El juego de la supervivencia

El algoritmo genético supone que hay una forma de calcular para cada espécimen sus posibilidades de supervivencia.Entre las Líneas En algunas aplicaciones, estas posibilidades pueden establecerse mediante un experimento práctico que permite a los especímenes individuales luchar contra ello.Entre las Líneas En otros ámbitos, la aptitud se calcula mediante una función de evaluación especificada por el usuario cuyo valor depende de las propiedades del cromosoma. Y si el cromosoma representa un clasificador, la función de aptitud puede basarse en el porcentaje de los ejemplos de entrenamiento correctamente etiquetados por el clasificador. La supervivencia de un individuo se determina de manera probabilística.

Mientras que los especímenes con poca aptitud física es probable que sean eliminados, aquellos con valores más altos pueden aparecer en el grupo de supervivientes más de una vez. Un biólogo se estremecerá ante esta idea de “clonación”, pero en el pragmático mundo de los programadores informáticos, el mismo individuo puede “sobrevivir” dos, tres o incluso muchas veces.

El operador de emparejamiento

El juego de supervivencia es seguido por el emparejamiento.Entre las Líneas En la naturaleza, un individuo juzga la idoneidad de un compañero por su fuerza, velocidad o dientes afilados. Algo similar se logra en una implementación de la computadora por medio de la función de aptitud.

Puntualización

Sin embargo, hay una diferencia: la noción de sexo es usualmente ignorada – cualquier cromosoma puede aparearse con cualquier otro cromosoma.

Otra estrategia más lo hace probabilísticamente. Toma al individuo de mayor rango, y luego elige a su pareja usando el mecanismo empleado en el juego de supervivencia. Lo mismo se hace para el segundo individuo de mayor rango, luego para el tercero, y así sucesivamente, hasta que la nueva población haya alcanzado el tamaño requerido. Así pues, es probable (aunque no está garantizado) que los individuos “mejores” se aparejen con otros individuos fuertes. A veces, la pareja tendrá un valor bajo (debido a la selección probabilística), pero esto da lugar a una diversidad que da al sistema la oportunidad de preservar valiosos trozos de cromosomas que solo tienen la mala suerte de estar actualmente incorporados en especímenes de baja calidad.

Individuos longevos e inmortales

Uno de los defectos de este algoritmo es que un organismo muy bueno puede ser reemplazado por niños de menor valor y los genes útiles pueden desaparecer. Para evitar que esto suceda, algunos programas informáticos copian los mejores especímenes en la nueva generación junto con sus hijos. Por ejemplo, el programa puede insertar directamente en la nueva generación el 20% de los mejores supervivientes, y luego crear el 80% restante aplicando los operadores de recombinación y mutación al 95% de los mejores individuos, ignorando totalmente el 5% inferior. De esta manera, no solo los mejores especímenes vivirán más tiempo (incluso se convertirán en “inmortales”), sino que el programa también se deshará de algunos especímenes muy débiles que han sobrevivido por mera casualidad.

Recombinación de cromosomas: Cruce de un punto

La forma más simple de implementar la recombinación cromosómica es mediante el cruce de un punto, un operador que intercambia partes de la información en los cromosomas padres.

El operador de la mutación

La tarea de la mutación es corromper la información genética heredada.Entre las Líneas En la práctica, esto se hace cambiando un pequeño porcentaje de los bits en el sentido de que el valor 0 de un bit se cambia a 1 o al revés. El porcentaje concreto (la frecuencia de las mutaciones) es un parámetro establecido por el usuario. Supongamos que este parámetro requiere que p = 0. 001 de los bits se vean afectados de esta manera en promedio. El módulo de programa correspondiente generará entonces para cada bit un entero aleatorio a partir del intervalo [1, 1000]. Si el número entero es igual a 1, entonces el valor del bit se modifica, de lo contrario se deja solo.

Pensemos en la frecuencia de las mutaciones que necesitamos.Entre las Líneas En un extremo, mutaciones muy raras apenas tendrán efecto alguno.Entre las Líneas En el otro extremo, una frecuencia de mutación muy alta interrumpiría la búsqueda genética al dañar demasiados cromosomas. Si la frecuencia se acerca al 50%, entonces cada nuevo cromosoma se comportará como una cadena de bits generada aleatoriamente; el algoritmo genético degenerará entonces en un generador de números aleatorios.
El operador de la mutación tiene un propósito diferente al del operador de cruce.Entre las Líneas En el cruce de un punto, no se crea ninguna información nueva, solo se intercambian las subcadenas existentes. La mutación introduce algún nuevo giro, antes ausente en la población.

El peligro de la degeneración prematura

El hecho de que el algoritmo genético haya alcanzado un valor que no parece mejorar a lo largo de una serie de generaciones no significa todavía que la búsqueda haya tenido éxito. La meseta puede explicarse por otras circunstancias.

Degeneración prematura

Una simple implementación del algoritmo genético se detendrá después de un número predefinido de generaciones. Una versión más sofisticada llevará la cuenta del valor de aptitud más alto logrado hasta ahora, y luego terminará la búsqueda cuando este valor ya no mejore.

Sin embargo, hay una trampa. El hecho de que el valor de aptitud haya alcanzado una meseta puede no garantizar que se haya encontrado una solución. (Tal vez sea de interés más investigación sobre el concepto). Más bien, la búsqueda podría haber alcanzado la etapa llamada degeneración prematura.

La única manera de causar un cambio es usar una mutación. (Tal vez sea de interés más investigación sobre el concepto). Cambiando los bits apropiados, la mutación puede reavivar la búsqueda. Por ejemplo, esto ocurrirá después de la mutación del tercer bit en el primer cromosoma y el cuarto bit (desde la izquierda) del último cromosoma. Desafortunadamente, las mutaciones son raras, y esperar a que esto suceda puede ser poco práctico. A efectos prácticos, la degeneración prematura significa que la búsqueda se atascó.

Prevención de la degeneración prematura

La degeneración prematura tiene mucho que ver con la diversidad de la población. (Tal vez sea de interés más investigación sobre el concepto). La peor población es aquella en la que todos los cromosomas tienen exactamente la misma cadena de bits, algo que el ingeniero quiere evitar.

Una Conclusión

Por lo tanto, cualquier implementación informática se beneficiará de un módulo que monitorice la diversidad y tome medidas cuando ésta descienda por debajo de un cierto nivel. Una forma sencilla de identificar esta situación es calcular la similitud media entre los pares de cromosomas, quizás contando el número de bits que tienen el mismo valor en ambas cadenas.

Basado en la experiencia de varios autores, mis opiniones, perspectivas y recomendaciones se expresarán a continuación (o en otros lugares de esta plataforma, respecto a las características en 2026 o antes, y el futuro de esta cuestión):

Una vez que se detecta una caída en la similitud promedio entre cromosomas, el sistema tiene que reaccionar. Esto no es todavía una causa de alarma. Así, en el ejemplo de la maximización de funciones, las generaciones avanzadas estarán marcadas por poblaciones en las que la mayoría de los especímenes ya están cerca del máximo. Este tipo de “degeneración” no se considerará ciertamente “prematura”.

Puntualización

Sin embargo, la situación es diferente si se puede demostrar que el mejor cromosoma es muy diferente de la solución. (Tal vez sea de interés más investigación sobre el concepto).Entre las Líneas En este caso, tenemos que aumentar la diversidad.

Aumentar la diversidad

Se pueden utilizar varias estrategias. La más simple es insertar en la población actual uno o más individuos aleatorios recién creados. Un enfoque más sofisticado ejecutará el algoritmo genético en dos o más poblaciones en paralelo, aisladas unas de otras. Entonces, ya sea a intervalos aleatorios, o cuando se sospeche una degeneración prematura, se permitirá a un espécimen de una población elegir su pareja de apareamiento en una población diferente. Al implementar esta técnica, el programador tiene que decidir en qué población colocar a los niños.

El impacto del tamaño de la población

Se debe prestar especial atención al tamaño de la población. (Tal vez sea de interés más investigación sobre el concepto). Normalmente, aunque no siempre, el tamaño se mantiene constante a lo largo de toda la búsqueda genética. El número de individuos en la población será dictado por la aplicación concreta. Como regla general, las poblaciones más pequeñas necesitarán muchas generaciones para alcanzar una buena solución, a menos que se degeneren prematuramente. Las poblaciones muy grandes pueden ser robustas frente a la degeneración, pero pueden incurrir en costos (o costes, como se emplea mayoritariamente en España) de computación poco prácticos.

Datos verificados por: LI

Recursos

Véase También

Algoritmos genéticos en el procesamiento de señales (también conocidos como filtros de partículas)
Propagación del esquema
Darwinismo universal
Metaheurística
Sistema de clasificación del aprendizaje
Aprendizaje automático basado en reglas
Clasificadores bayesianos, teoría de aprendizaje computacional, árboles de decisión, algoritmos genéticos, clasificadores lineales y polinómicos, clasificador del vecino más cercano, redes neuronales, evaluación del rendimiento, Algoritmos evolutivos, Algoritmos de búsqueda, Cibernética,
aprendizaje de refuerzo, aprendizaje estadístico, clases variables en el tiempo, representación desequilibrada, inteligencia artificial, datos de aprendizaje automático, minería de aprendizaje profundo, aprendizaje no supervisado

Aprendizaje profundo
Dinámica de sistemas
Inteligencia artificial
Inteligencia computacional
Redes neuronales
Lógica difusa
Red bayesiana
Mínimo/máximo local
Inteligencia Artificial
Robótica Evolutiva
Emergencia
Autómata celular
Codigo Santillan
Internet de las cosas
Sistema dinámico
Minería de datos
Reconocimiento de patrones
Reglas de asociación
Robot autónomo
Sistema complejo
Representación del conocimiento
Equidad (aprendizaje automático)
Análisis predictivo – Técnicas estadísticas que analizan los hechos para hacer predicciones sobre eventos desconocidos
El aprendizaje de las máquinas cuánticas
Aplicaciones del aprendizaje a máquina en bioinformática
Seq2seq
Equidad (aprendizaje automático)

Ciencias de la computación, minería de datos, Descubrimiento de conocimientos, Grandes datos, Computación evolutiva, Algoritmos, Vida artificial, Organismos digitales

Análisis de datos, inteligencia computacional, Inteligencia artificial, Visión por computadora, Cibernética, Aprendizaje, Aprendizaje Profundo, Algoritmos de clasificación, Estadística computacional, Neurociencia computacional, Investigación de mercado, Segmentación de mercado, Psicología matemática, Métodos económicos matemáticos, Métodos económicos cuantitativos

▷ Esperamos que haya sido de utilidad. Si conoces a alguien que pueda estar interesado en este tema, por favor comparte con él/ella este contenido. Es la mejor forma de ayudar al Proyecto Lawi.