introduction genetic algorithms machine learning
cómo abrir archivos bin en la pc
Este tutorial de algoritmos genéticos explica en detalle qué son los algoritmos genéticos y su función en el aprendizaje automático :
En el Tutorial anterior , aprendimos sobre los modelos de redes neuronales artificiales: perceptrón multicapa, retropropagación, sesgo radial y mapas autoorganizados de Kohonen, incluida su arquitectura.
Nos centraremos en los algoritmos genéticos que surgieron mucho antes que las redes neuronales, pero ahora GA se ha hecho cargo de NN. Aunque GA todavía tiene aplicaciones en la vida real, como problemas de optimización como programación, juegos, robótica, diseño de hardware, problemas de vendedores ambulantes, etc.
Los algoritmos genéticos son algoritmos que se basan en la idea evolutiva de la selección natural y la genética. Los GA son algoritmos de búsqueda heurística adaptativa, es decir, los algoritmos siguen un patrón iterativo que cambia con el tiempo. Es un tipo de aprendizaje por refuerzo donde la retroalimentación es necesaria sin indicar el camino correcto a seguir. La retroalimentación puede ser positiva o negativa.
=> Lea la serie completa de capacitación sobre aprendizaje automático
Lo que vas a aprender:
- Por qué utilizar algoritmos genéticos
- ¿Qué son los algoritmos genéticos?
- Ventajas y desventajas del algoritmo genético
- Aplicaciones de los algoritmos genéticos
- Conclusión
Por qué utilizar algoritmos genéticos
Los GA son algoritmos más robustos que se pueden utilizar para varios problemas de optimización. Estos algoritmos no se desvían fácilmente en presencia de ruido, a diferencia de otros algoritmos de IA. Los GA se pueden utilizar en la búsqueda de espacios grandes o multimodales.
Antecedentes biológicos de los algoritmos genéticos
La genética se deriva de la palabra griega 'génesis' que significa crecer. La genética decide los factores de herencia, semejanzas y diferencias entre los descendientes en el proceso de evolución. Los algoritmos genéticos también se derivan de la evolución natural.
Algunas terminologías en un cromosoma biológico
- Cromosomas: Toda la información genética de una especie se almacena en cromosomas.
- Genes: Los cromosomas se dividen en varias partes llamadas genes.
- Alelos: Los genes identifican la característica de un individuo. La posibilidad de que una combinación de genes forme propiedades se denomina alelos. Un gen puede tener diferentes alelos.
- Reserva genética: Todas las posibles combinaciones de genes que son todos alelos en un grupo de población se llama grupo de genes.
- Genoma: El conjunto de genes de una especie se llama genoma.
- Lugar: Cada gen tiene una posición en un genoma que se llama locus.
- Genotipo: Una combinación completa de genes en un individuo se llama genotipo.
- Fenotipo: Un conjunto de genotipos en una forma decodificada se llama fenotipo.
¿Qué son los algoritmos genéticos?
Los Algoritmos Genéticos estimulan el proceso como en los sistemas naturales de evolución. Charles Darwin afirmó la teoría de la evolución de que en la evolución natural, los seres biológicos evolucionan de acuerdo con el principio de 'supervivencia del más apto'. La búsqueda de GA está diseñada para fomentar la teoría de la 'supervivencia del más apto'.
Los GA realizan una búsqueda aleatoria para resolver problemas de optimización. El GA utiliza técnicas que utilizan la información histórica anterior para dirigir su búsqueda hacia la optimización en el nuevo espacio de búsqueda.
Correlación de un cromosoma con GA
El cuerpo humano tiene cromosomas que están formados por genes. Un conjunto de todos los genes de una especie específica se llama genoma. En los seres vivos, los genomas se almacenan en varios cromosomas, mientras que en GA todos los genes se almacenan en el mismo cromosoma.
Comparación entre evolución natural y terminología de algoritmos genéticos
Evolución natural | Algoritmo genético |
---|---|
Cromosoma | Cuerda |
Gene | Característica |
Alelo | Valor de característica |
Genotipo | Cadena codificada |
Fenotipo | Estructura decodificada |
Terminología importante en GA
- Población: Es un grupo de individuos. La población incluye el número de individuos que se están probando, la información del espacio de búsqueda y los parámetros del fenotipo. Generalmente, la población se inicializa aleatoriamente.
- Individuos: Los individuos son una única solución en la población. Un individuo tiene un conjunto de parámetros llamados genes. Los genes se combinaron para formar cromosomas.
- Genes: Los genes son bloques de construcción de algoritmos genéticos. Un cromosoma está formado por genes. Los genes pueden determinar la solución al problema. Están representados por una cadena de bits (0 o 1) de longitud aleatoria.
- Aptitud física: La aptitud indica el valor del fenotipo del problema. La función de aptitud indica qué tan cerca está la solución de la solución óptima. La función de aptitud se determina de muchas formas, como la suma de todos los parámetros relacionados con el problema: distancia euclidiana, etc. No existe una regla para evaluar la función de aptitud.
Un algoritmo genético simple
Un GA simple tiene una población de cromosomas individuales. Estos cromosomas representan posibles soluciones. Los operadores de reproducción se aplican sobre estos conjuntos de cromosomas para realizar mutaciones y recombinación. Por lo tanto, es importante encontrar operadores de reproducción apropiados, ya que el comportamiento de GA depende de ellos.
Un algoritmo genético simple es el siguiente:
#1) Comience con la población creada al azar.
#2) Calcula la función de aptitud de cada cromosoma.
#3) Repita los pasos hasta que se creen n descendientes. Las crías se crean como se muestra a continuación.
- Seleccione un par de cromosomas de la población.
- Cruce el par con probabilidad pcpara formar descendientes.
- Mute el cruce con probabilidad pmetro.
#4) Reemplace la población original con la nueva población y vaya al paso 2.
Veamos los pasos seguidos en este proceso de iteración. Se genera la población inicial de cromosomas. La población inicial debe contener suficientes genes para que se pueda generar cualquier solución. El primer grupo de población se genera aleatoriamente.
- Selección: El mejor conjunto de genes se selecciona según la función de aptitud. Se elige la cuerda con la mejor función de fitness.
- Reproducción: Las nuevas crías se generan por recombinación y mutación.
- Evaluación: Los nuevos cromosomas generados se evalúan para determinar su aptitud.
- Reemplazo: En este paso, la población vieja se reemplaza con la población recién generada.
Método de selección de la rueda de la ruleta
La selección de la rueda de la ruleta es el método de selección más utilizado.
El proceso de selección es breve como se muestra a continuación:
En este método, se realiza una búsqueda lineal a través de la rueda de la ruleta. Las ranuras de la rueda se pesan de acuerdo con el valor de aptitud individual. El valor objetivo se establece aleatoriamente según la proporción de la suma de la aptitud en la población.
Luego se busca en la población hasta que se alcanza el valor objetivo. Este método no garantiza el más apto de los individuos, pero tiene la probabilidad de ser el más apto.
Veamos los pasos involucrados en la selección de la ruleta.
El valor esperado de un individuo = Aptitud individual / aptitud de la población. Las ranuras de las ruedas se asignan a las personas en función de su estado físico. La rueda gira N veces donde N es el número total de individuos de la población. Cuando termina una rotación, la persona seleccionada se coloca en un grupo de padres.
- Sea el valor total esperado de un número de individuos de la población S.
- Repita los pasos 3-5 n veces.
- Seleccione un entero s entre 0 y S.
- Recorra los individuos de la población, sume los valores esperados hasta que la suma sea mayor que s.
- Se selecciona el individuo cuyo valor esperado coloca la suma por encima del límite s.
Inconvenientes de la selección de la rueda de la ruleta:
- Si la aptitud difiere mucho, la circunferencia de la rueda de la ruleta será tomada al máximo por el cromosoma de función de aptitud más alta, por lo que los demás tienen muy pocas posibilidades de ser seleccionados.
- Es ruidosa.
- La evolución depende de la variación en la aptitud de la población.
Otros métodos de selección
Hay muchos otros métodos de selección utilizados en la 'Selección' paso del algoritmo genético.
Discutiremos los otros 2 métodos ampliamente utilizados:
# 1) Selección de rango: En este método, cada cromosoma recibe un valor de aptitud de la clasificación. La peor aptitud es 1 y la mejor aptitud es N. Es un método de convergencia lenta. En este método, la diversidad se conserva y conduce a una búsqueda exitosa.
Se seleccionan los padres potenciales y luego se lleva a cabo un torneo para decidir cuál de los individuos será un padre.
# 2) Selección del torneo: En este método, se aplica una estrategia de presión selectiva a la población. El mejor individuo es el que tiene la mayor aptitud. Este individuo es el ganador de la competencia del torneo entre los individuos Nu de la población.
La población del torneo junto con el ganador se agrega nuevamente al grupo para generar nuevas crías. La diferencia en los valores de aptitud del ganador y de los individuos en el grupo de apareamiento proporciona una presión selectiva para obtener resultados óptimos.
Transversal
Es un proceso de tomar 2 individuos y producir un hijo de ellos. El proceso de reproducción después de la selección produce clones de las picaduras buenas. El operador de cruce se aplica sobre las cuerdas para producir una mejor descendencia.
La implementación del operador de cruce es la siguiente:
- Se seleccionan al azar dos individuos de la población para producir crías.
- Se selecciona un sitio cruzado al azar a lo largo de la cadena.
- Los valores en el sitio se intercambian.
El cruce realizado puede ser un cruce de un solo punto, un cruce de dos puntos, un cruce multipunto, etc. El cruce de un solo punto tiene un sitio de cruce mientras que un sitio de cruce de dos puntos tiene 2 sitios donde los valores se intercambian.
Podemos ver esto en el siguiente ejemplo:
Crossover de un solo punto
Crossover de dos puntos
Probabilidad de cruce
PAGc, la probabilidad de cruce es el término que describe la frecuencia con la que se realizará el cruce. 0% de probabilidad significa que los nuevos cromosomas serán una copia exacta de los cromosomas antiguos, mientras que 100% de probabilidad significa que todos los nuevos cromosomas se forman por cruzamiento.
Mutación
La mutación se realiza después del Crossover. Mientras que el cruce se centra solo en la solución actual, la operación de mutación busca en todo el espacio de búsqueda. Este método consiste en recuperar la información genética perdida y distribuir la información genética.
Este operador ayuda a mantener la diversidad genética en la población. Ayuda a prevenir mínimos locales y evita generar soluciones inútiles por parte de cualquier población.
La mutación se realiza de muchas formas, como invertir el valor de cada gen con una pequeña probabilidad o realizar la mutación solo si mejora la calidad de la solución.
Algunas de las formas de mutación son:
- Voltear: Cambio de 0 a 1 o de 1 a 0.
- Intercambiando: Se eligen dos posiciones aleatorias y los valores se intercambian.
- Marcha atrás: Se elige una posición aleatoria y los bits próximos a ella se invierten.
Veamos algunos ejemplos de cada uno:
Voltear
Intercambiando
Marcha atrás
Probabilidad de mutación
PAGmetro, la probabilidad de mutación es un término que decide con qué frecuencia se mutarán los cromosomas. Si la probabilidad de mutación es del 100%, significa que todo el cromosoma ha cambiado. Si no se realiza una mutación, la nueva descendencia se genera directamente después del cruce.
Un ejemplo de un algoritmo genético general Probabilidad de mutación: PAGmetro, la probabilidad de mutación es un término que decide con qué frecuencia se mutarán los cromosomas. Si la probabilidad de mutación es del 100%, significa que todo el cromosoma ha cambiado.
Si no se realiza una mutación, la nueva descendencia se genera directamente después del cruce. La población inicial de cromosomas se da como A, B, C, D. El tamaño de la población es 4.
La función de aptitud se toma como un número de unos en la cadena.
Cromosoma | Aptitud física |
---|---|
A: 00000110 | 2 |
B: 11101110 | 6 |
C: 00100000 | 1 |
D: 00110100 | 3 |
La suma de la aptitud es 12, lo que implica que la función de aptitud promedio sería ~ 12/4 = 3
Probabilidad de cruce = 0,7
Probabilidad de mutación = 0,001
#1) Si se seleccionan B y C, el cruce no se realiza porque el valor de aptitud de C está por debajo de la aptitud promedio.
#2) B está mutado => B: 11101110 -> B’: 01101110 para preservar la diversidad de la población
#3) Se seleccionan B y D, se realiza el cruce.
B: 11101110 E: 10110100 -> D: 00110100 F: 01101110
#4) Si E está mutado, entonces
E: 10110100 -> E’: 10110000
Los cromosomas correspondientes se muestran en la siguiente tabla. El orden se pone al azar.
Cromosoma | Aptitud física |
---|---|
A: 01101110 | 5 |
B: 00100000 | 1 |
C: 10110000 | 3 |
D: 01101110 | 5 |
Aunque el individuo más apto con un valor de aptitud física de 6 se pierde, la aptitud física promedio general de la población aumenta y sería: 14/4 = 3.5
Cuándo detener el algoritmo genético
Un algoritmo genético se detiene cuando se cumplen algunas de las condiciones que se enumeran a continuación:
# 1) Mejor convergencia individual: Cuando el nivel mínimo de condición física cae por debajo del valor de convergencia, el algoritmo se detiene. Conduce a una convergencia más rápida.
# 2) Peor convergencia individual: Cuando los individuos menos aptos de la población alcanzan un valor mínimo de aptitud por debajo de la convergencia, el algoritmo se detiene. En este método, el estándar mínimo de aptitud se mantiene en la población. Significa que el mejor individuo no está garantizado, pero estarán presentes individuos con un valor mínimo de aptitud física.
# 3) Suma de aptitud: En este método, si la suma de la aptitud es menor o igual que el valor de convergencia, la búsqueda se detiene. Garantiza que toda la población se encuentre dentro del rango de aptitud.
# 4) Aptitud media: En este método, al menos la mitad de los individuos de la población serán mejores o iguales al valor de convergencia.
Algún criterio de convergencia o condición de parada puede ser:
- Cuando ha evolucionado un número específico de generaciones.
- Cuando se cumple el tiempo especificado para ejecutar el algoritmo.
- Cuando el valor de aptitud de la población no cambia más con las iteraciones.
Ventajas y desventajas del algoritmo genético
Las ventajas de un algoritmo genético son:
- Tiene un espacio de solución más amplio.
- Es más fácil descubrir el óptimo global.
- Paralelismo: Varias GA pueden ejecutarse juntas usando la misma CPU sin interferir entre sí. Funcionan paralelamente de forma aislada.
Limitaciones de GA:
- La identificación de la función de aptitud es una limitación.
- La convergencia de los algoritmos puede ser demasiado rápida o demasiado lenta.
- Existe una limitación en la selección de parámetros como el cruce, la probabilidad de mutación, el tamaño de la población, etc.
Aplicaciones de los algoritmos genéticos
GA es eficaz para resolver problemas de gran dimensión. Una GA se usa de manera efectiva cuando el espacio de búsqueda es muy grande, no hay técnicas matemáticas de resolución de problemas disponibles y otros algoritmos de búsqueda tradicionales no funcionan.
Algunas aplicaciones donde se usa GA:
- Problema de optimizacion: Uno de los mejores ejemplos de los problemas de optimización es el problema del vendedor de viajes que utiliza GA. Otros problemas de optimización, como la programación de trabajos y los GA de optimización de la calidad del sonido, se utilizan ampliamente.
- Modelo del sistema inmunológico: Los GA se utilizan para modelar varios aspectos del sistema inmunológico para familias de genes individuales y de múltiples genes durante el tiempo evolutivo.
- Aprendizaje automático: Los GA se han utilizado para resolver problemas relacionados con la clasificación, la predicción, crear reglas para el aprendizaje y la clasificación. .
Conclusión
Los algoritmos genéticos se basan en el método de evolución natural. Estos algoritmos son diferentes de los otros algoritmos de clasificación ya que usan parámetros codificados (0 o 1), hay múltiples números de individuos en una población y usan el método probabilístico para la convergencia.
Con el proceso de cruce y mutación, los AG convergen en generaciones sucesivas. La ejecución de un algoritmo GA no garantiza siempre una solución exitosa. Los algoritmos genéticos son altamente eficientes en la optimización: problemas de programación de trabajos.
¡Espero que este tutorial haya enriquecido sus conocimientos sobre el concepto de algoritmos genéticos!
=> Visite aquí para ver la serie exclusiva de aprendizaje automático
Lectura recomendada
- Pruebas basadas en modelos utilizando algoritmos genéticos
- Minería de datos Vs Aprendizaje automático Vs Inteligencia artificial Vs Aprendizaje profundo
- Tutorial de aprendizaje automático: introducción al aprendizaje automático y sus aplicaciones
- Tipos de aprendizaje automático: aprendizaje supervisado frente a aprendizaje no supervisado
- Una guía completa para la red neuronal artificial en el aprendizaje automático
- Las 11 herramientas de software de aprendizaje automático más populares en 2021
- Las 13 MEJORES empresas de aprendizaje automático [Lista actualizada en 2021]
- ¿Qué es la máquina de vectores de soporte (SVM) en el aprendizaje automático?