Algoritmo genético para niños
Un algoritmo es como una receta o un conjunto de instrucciones paso a paso. Te dice exactamente qué hacer para resolver un problema específico.
En los años 1970, gracias a John Henry Holland, surgió una idea muy interesante en el campo de la inteligencia artificial: los algoritmos genéticos (AG). Se llaman así porque se inspiran en cómo funciona la evolución de los seres vivos y su información genética.
Estos algoritmos hacen que un grupo de "individuos" (que son posibles soluciones a un problema) cambie y mejore con el tiempo. Esto ocurre mediante acciones al azar, parecidas a las que vemos en la evolución biológica. Por ejemplo, hay "mutaciones" (pequeños cambios) y "recombinaciones genéticas" (mezcla de características). También hay una "selección", donde se eligen las mejores soluciones y se descartan las menos adecuadas.
Los algoritmos genéticos forman parte de un grupo más grande llamado algoritmos evolutivos. Este grupo también incluye otras técnicas como las estrategias evolutivas y la programación genética.
Contenido
¿Qué son los Algoritmos Genéticos y cómo funcionan?
¿Cómo trabajan los Algoritmos Genéticos?
Los algoritmos genéticos (AG) trabajan con las posibles soluciones de un problema. A cada solución se le da un "código" o "cromosoma", que suele ser una cadena de números (a menudo binarios, es decir, ceros y unos). Los pequeños pedazos de esta cadena se llaman "genes".
Estos "cromosomas" van cambiando a lo largo de muchas "generaciones" (como si fueran pasos o rondas). En cada generación, se evalúa qué tan buena es cada solución. Luego, se crean nuevas generaciones aplicando "operadores genéticos". Estos operadores son la selección, el cruzamiento (o mezcla), la mutación (cambios al azar) y el reemplazo (elegir los mejores para la siguiente ronda).
¿Cuándo usar estos algoritmos?
Los algoritmos genéticos son muy útiles para encontrar soluciones a problemas complejos. Especialmente, son buenos cuando las funciones matemáticas que describen el problema son difíciles de manejar.
Aquí hay algunas cosas a considerar:
- Si el problema tiene muchas soluciones "casi perfectas" pero no la mejor, el algoritmo podría necesitar más tiempo para encontrar la solución ideal.
- Si hay muchas soluciones muy parecidas a la mejor, el algoritmo podría encontrar una de ellas, pero no siempre la "mejor de todas".
Pasos de un Algoritmo Genético Básico
Un algoritmo genético puede tener algunas variaciones, pero en general sigue estos pasos:
- Paso 1: Inicialización: Se crea un grupo inicial de posibles soluciones de forma aleatoria. Es importante que este grupo sea diverso para que el algoritmo pueda explorar muchas opciones.
- Paso 2: Evaluación: Cada solución de este grupo se evalúa para ver qué tan buena es. Se usa una "función de aptitud" para medir su calidad.
- Paso 3: Condición de Parada: El algoritmo se detiene cuando encuentra una solución muy buena o después de un número determinado de generaciones. También puede detenerse si las soluciones ya no mejoran. Si no se cumple la condición de parada, se siguen los siguientes pasos:
- Selección: Se eligen las soluciones más aptas (las mejores) para que sean los "padres" de la siguiente generación. Las soluciones con mejor aptitud tienen más posibilidades de ser elegidas.
- Recombinación o Cruzamiento: Es como la reproducción. Se combinan las características de dos soluciones "padre" para crear nuevas soluciones "hijas".
- Mutación: Se hacen pequeños cambios al azar en las soluciones. Esto ayuda a explorar nuevas posibilidades y a evitar quedarse atascado en soluciones no tan buenas.
- Reemplazo: Las nuevas soluciones creadas (hijas) reemplazan a las soluciones menos aptas de la generación anterior. Así, la población mejora con el tiempo.
Desafíos y límites de los Algoritmos Genéticos
Aunque son muy útiles, los algoritmos genéticos tienen algunas limitaciones:
- Para problemas muy complejos, evaluar cada solución puede llevar mucho tiempo y usar muchos recursos de la computadora.
- A veces, el algoritmo puede encontrar una buena solución, pero no la mejor de todas. Esto puede pasar si los parámetros no se ajustan bien.
- No son muy buenos para problemas con muchísimas variables, porque el número de posibles soluciones crece muy rápido.
- Como la "mejor" solución se compara con otras, no siempre está claro cuándo detener el algoritmo, ya que no hay una respuesta única y perfecta.
- No son recomendables para problemas con respuestas simples de "sí" o "no", porque el algoritmo no tiene una "montaña" que escalar para mejorar.
- Diseñar la función de aptitud y elegir los parámetros correctos requiere experiencia y conocimiento del problema.
¿Para qué se usan los Algoritmos Genéticos?
Los algoritmos genéticos tienen muchas aplicaciones prácticas:
- Diseño automático de materiales y piezas para autos (más seguros, ligeros, aerodinámicos).
- Diseño de equipos industriales.
- Creación de sistemas de comercio en finanzas.
- Construcción de árboles genealógicos de especies.
- Optimización de cómo cargar contenedores.
- Diseño de redes de agua y circuitos electrónicos.
- En teoría de juegos, para encontrar equilibrios.
- Análisis de cómo se expresan los genes.
- Enseñar a los robots a comportarse.
- Aprender reglas de lógica difusa.
- Mejorar redes de comunicación móvil.
- Optimización de la forma de las moléculas.
- Predicción de eventos.
- Optimización de sistemas de compresión de datos.
- Predicción de cómo se pliegan las proteínas.
- Planificación de procesos industriales.
- Construcción de horarios en universidades para evitar conflictos.
- Resolver el Problema del viajante (encontrar la ruta más corta entre ciudades).
- Encontrar errores en programas de computadora.
- Optimización de la producción y distribución de energía eléctrica.
- Calibración y detección de daños en estructuras.
- Cálculo de poblaciones de estrellas.
¿Cómo funcionan en detalle?
Resolviendo problemas de optimización
En un algoritmo genético, un grupo de posibles soluciones (llamadas individuos o criaturas) a un problema de optimización mejora con el tiempo. Cada solución tiene características (sus cromosomas) que pueden cambiar. Tradicionalmente, las soluciones se representan con cadenas de ceros y unos, pero también pueden usarse otros códigos.
La evolución comienza con un grupo de soluciones creadas al azar. Este proceso se repite en "generaciones". En cada generación, se mide la "aptitud" de cada solución (qué tan buena es). Las soluciones más aptas se eligen para crear una nueva generación. Sus "genes" se modifican (se mezclan y a veces se mutan al azar) para formar nuevas soluciones. El algoritmo suele terminar cuando se alcanza un número máximo de generaciones o una solución suficientemente buena.
Un algoritmo genético necesita:
- Una forma de representar las soluciones (como un código genético).
- Una función para evaluar qué tan buena es cada solución.
Una forma común de representar una solución es como una lista de bits (ceros y unos). Esto facilita la mezcla de partes de las soluciones. También se pueden usar otras representaciones, como listas de números o estructuras más complejas.
Una vez que se define cómo se representan las soluciones y cómo se evalúan, el algoritmo genético crea una población inicial y la mejora aplicando repetidamente la mutación, el cruzamiento y la selección.
Creación de la población inicial
El tamaño del grupo inicial de soluciones depende del problema, pero suele ser de cientos o miles. A menudo, este grupo se genera completamente al azar para explorar todas las posibles soluciones. A veces, se pueden incluir algunas soluciones ya conocidas para ayudar al algoritmo a empezar.
Proceso de selección
En cada nueva generación, una parte de las soluciones existentes se elige para crear la siguiente. Las soluciones se seleccionan según su aptitud: las mejores tienen más posibilidades de ser elegidas. Algunos métodos evalúan todas las soluciones, mientras que otros solo evalúan una muestra para ahorrar tiempo.
La función de aptitud mide la calidad de la solución. Por ejemplo, en el problema de la mochila (cómo meter el mayor valor de objetos en una mochila con capacidad limitada), la aptitud sería la suma del valor de los objetos que caben.
A veces, es difícil definir la función de aptitud. En esos casos, se puede usar una simulación o incluso la evaluación humana para determinar qué tan buena es una solución.
Operadores genéticos
El siguiente paso es crear una segunda generación de soluciones usando el cruzamiento (o recombinación) y la mutación.
Para cada nueva solución, se eligen dos soluciones "padre" de la generación anterior. Al combinar sus características, se crea una nueva solución que suele tener rasgos de ambos padres. Se eligen nuevos padres para cada nueva solución hasta que se forma una nueva población completa. Aunque usar dos padres es lo más parecido a la biología, algunas investigaciones sugieren que más padres podrían generar mejores soluciones.
Estos procesos hacen que la nueva generación sea diferente de la inicial. En general, la calidad promedio de las soluciones mejora, porque solo las mejores se eligen para reproducirse, junto con una pequeña parte de las menos aptas. Estas soluciones menos aptas son importantes para mantener la diversidad en el grupo y asegurar que la siguiente generación tenga muchas opciones.
Hay diferentes opiniones sobre si el cruzamiento o la mutación son más importantes. Ambos son clave.
Es importante ajustar parámetros como la probabilidad de mutación, la probabilidad de cruzamiento y el tamaño de la población. Si la mutación es muy baja, el algoritmo puede quedarse atascado. Si es muy alta, puede perder buenas soluciones.
¿Cuándo termina el algoritmo?
Este proceso de generaciones se repite hasta que se cumple una condición de parada. Las condiciones comunes son:
- Se encuentra una solución que cumple con los requisitos mínimos.
- Se alcanza un número fijo de generaciones.
- Se agota el tiempo o los recursos asignados.
- La calidad de la mejor solución ya no mejora significativamente.
- Una persona decide detenerlo.
- Una combinación de las anteriores.
La hipótesis del bloque de construcción
Los algoritmos genéticos son fáciles de usar, pero entender por qué funcionan tan bien es complicado. La hipótesis del bloque de construcción (BBH) sugiere que estos algoritmos encuentran las mejores soluciones al identificar y combinar "bloques de construcción". Estos "bloques" son pequeñas partes de las soluciones que son muy buenas.
Imagina que un niño construye un castillo con bloques de madera. El algoritmo genético hace algo similar: construye soluciones cada vez mejores combinando las mejores "piezas" o "bloques de construcción" que ha encontrado.
Aunque no todos están de acuerdo con esta hipótesis, ha sido muy estudiada y usada como referencia para entender cómo funcionan estos algoritmos.
Limitaciones
Existen algunas limitaciones al usar algoritmos genéticos en comparación con otros métodos de optimización:
- Evaluar repetidamente la calidad de las soluciones en problemas complejos puede ser muy costoso en tiempo y recursos.
- Los algoritmos genéticos no manejan bien la complejidad extrema. Si hay muchísimos elementos que pueden cambiar, el número de posibles soluciones se vuelve gigantesco. Por eso, se suelen usar para partes más simples de un problema grande, como el diseño de una parte de un motor, no el motor completo.
- La "mejor" solución que encuentran es solo la mejor entre las que han explorado. No hay un criterio claro para saber cuándo detenerse, ya que no se conoce la solución perfecta de antemano.
- A veces, los AG pueden quedarse atascados en soluciones que son buenas, pero no las mejores de todas (óptimos locales). Esto se puede mejorar cambiando la función de aptitud o aumentando la mutación para explorar más.
- No son útiles para problemas donde la respuesta es simplemente "correcto" o "incorrecto", porque no hay una forma de "mejorar" gradualmente.
- Otros algoritmos de optimización pueden ser más rápidos para problemas específicos. La elección del algoritmo depende de cuánto se conozca el problema.
Variantes de los Algoritmos Genéticos
Representación del cromosoma
La forma más sencilla de representar un "cromosoma" es como una cadena de bits (0s y 1s). Los números también pueden representarse con números enteros o decimales. El algoritmo básico realiza el cruzamiento y la mutación a nivel de bits.
Otras variantes tratan el cromosoma como una lista de números, instrucciones o cualquier otra estructura de datos. Las operaciones de cruzamiento y mutación se adaptan a estas estructuras.
A veces se usa una "codificación Gray" para los números enteros. Esto ayuda a que pequeños cambios en el número se logren con pocas mutaciones, evitando que el algoritmo se quede atascado.
Elitismo
Una técnica útil es el "elitismo". Consiste en permitir que las mejores soluciones de una generación pasen directamente a la siguiente sin cambios. Esto asegura que la calidad de la solución no disminuya con el tiempo.
Implementaciones paralelas
Existen versiones de algoritmos genéticos que se ejecutan en varias computadoras al mismo tiempo. Algunas tienen una población en cada computadora y permiten que los individuos "migren" entre ellas. Otras asignan un individuo a cada procesador, que interactúa con sus vecinos.
Algoritmo genético adaptativo
Los algoritmos genéticos adaptativos (AGA) ajustan automáticamente sus parámetros (como la probabilidad de cruzamiento y mutación) durante el proceso. Esto les permite mantener la diversidad de la población y mejorar la velocidad de búsqueda de soluciones.
También es muy efectivo combinar los algoritmos genéticos con otros métodos de optimización. Los AG son buenos para encontrar soluciones generales, pero a veces no tan eficientes para encontrar la solución "perfecta". Combinarlos con otras técnicas puede mejorar su eficiencia.
Áreas de aplicación
Los algoritmos genéticos son especialmente adecuados para problemas de planificación y diseño. Se usan mucho en ingeniería y para encontrar las mejores soluciones en problemas de optimización global.
En general, los algoritmos genéticos son útiles en problemas donde el "paisaje" de soluciones es complejo. La combinación de mutación y cruzamiento ayuda a que el algoritmo no se quede atrapado en soluciones locales que no son las mejores.
Historia
En 1950, Alan Turing propuso una "máquina de aprendizaje" que funcionaría de forma similar a la evolución. Las simulaciones por computadora de la evolución comenzaron en 1954 con el trabajo de Nils Aall Barricelli. A partir de 1957, el genetista Alex Fraser publicó artículos sobre la simulación de la selección artificial.
Otros pioneros importantes fueron Hans-Joachim Bremermann, Richard Friedberg, George Friedman y Michael Conrad.
Aunque Barricelli ya había simulado la evolución de la capacidad de jugar un juego en 1963, la evolución artificial se hizo más conocida gracias al trabajo de Ingo Rechenberg y Hans-Paul Schwefel en los años 60 y 70. Ellos lograron resolver problemas complejos de ingeniería usando estrategias de evolución.
Los algoritmos genéticos se hicieron populares gracias a John Henry Holland a principios de los años 70, especialmente con su libro "Adaptation in Natural and Artificial Systems" (1975). Su trabajo se basó en estudios de autómatas celulares. La investigación en AGs fue principalmente teórica hasta mediados de los años 80, cuando se celebró la primera conferencia internacional sobre el tema.
Productos comerciales
A finales de los años 80, General Electric lanzó el primer producto de algoritmo genético comercial. En 1989, Axcelis, Inc. lanzó Evolver, el primer producto AG para computadoras de escritorio. Este software fue muy popular y sigue siendo usado hoy en día.
Ejemplo práctico
Imagina que quieres insertar signos de suma o resta entre los números 9 8 7 6 5 4 3 2 1 para que el resultado sea 100. No puedes cambiar el orden de los números. Una solución podría ser 98+7-6+5-4+3-2-1, que da exactamente 100.
Hay 9 lugares donde puedes poner un signo de más (+), un signo de menos (-) o nada (lo que une los números, como el 98). Esto significa que hay 3 elevado a la 9, o sea, 19683 combinaciones posibles. Aunque se podría probar cada una, este problema es un buen ejemplo para entender cómo funciona un algoritmo genético.
Codificación
Podemos representar cada combinación de signos con una cadena de 9 "trits" (dígitos ternarios: 0, 1, 2). Por ejemplo, si "0" significa "nada", "1" significa "menos" y "2" significa "más", entonces la cadena 002121211 corresponde a la solución 98+7-6+5-4+3-2-1.
Técnicas relacionadas
Campos de los padres
Los algoritmos genéticos son parte de:
- Algoritmos evolutivos
- Computación evolutiva
- Metaheurística
- Optimización estocástica
- Mejoramiento
Campos relacionados
Algoritmos evolutivos
Los algoritmos evolutivos son un campo más amplio que incluye:
- Las estrategias de evolución (ES) que cambian individuos por mutación y recombinación. Son buenas para problemas con números reales y ajustan sus propios parámetros.
- La programación evolutiva (EP) que usa poblaciones de soluciones con mutación y selección, y puede combinar información de varios padres.
- La estimación del algoritmo de distribución (EDA) que usa modelos para generar nuevas soluciones, aprendiendo de la población actual.
- La programación de expresión genética (GEP) que optimiza programas de computadora. Estos programas se codifican en "cromosomas" lineales que luego se convierten en árboles de expresión.
- La programación genética (GP) que también optimiza programas de computadora, pero a menudo usa estructuras de árbol.
- El algoritmo genético de agrupación (GGA) que se enfoca en grupos o subconjuntos de elementos, útil para problemas de empaquetamiento o partición.
- Los algoritmos evolutivos interactivos que usan la evaluación humana. Son útiles cuando es difícil crear una función de aptitud para la computadora, como en el diseño de arte o música.
Inteligencia de enjambre
- La optimización de la colonia de hormigas (ACO) usa muchos "agentes" (como hormigas) que exploran el espacio de soluciones, dejando "rastros" para encontrar las mejores áreas.
- La optimización de enjambre de partículas (PSO) usa un grupo de soluciones (partículas) que se mueven en el espacio de búsqueda. El movimiento de cada partícula es influenciado por su mejor posición conocida y la mejor posición conocida de todo el grupo.
Otros algoritmos evolutivos de computación
- El algoritmo memético (MA), también llamado algoritmo genético híbrido, mejora las soluciones con fases de optimización local.
- Los algoritmos bacteriológicos (BA) se inspiran en cómo las bacterias se adaptan a su entorno. Son útiles para problemas de posicionamiento o análisis de datos.
- El algoritmo cultural (CA) tiene un componente de población similar al AG y un componente de conocimiento.
- El algoritmo de búsqueda diferencial (DS) se inspira en la migración de superorganismos.
- La adaptación gaussiana (NA) busca maximizar el rendimiento de sistemas de procesamiento de señales y optimización.
Otros métodos metaheurísticos
- El recocido simulado (SA) es una técnica que explora el espacio de soluciones probando cambios aleatorios. Acepta siempre las mejoras y a veces acepta cambios que empeoran un poco, para evitar quedarse atascado.
- La búsqueda tabú (TS) es similar al recocido simulado, pero mantiene una lista de soluciones prohibidas para evitar repetir caminos y explorar más.
- La optimización extrema (EO) mejora una única solución modificando sus peores partes, en lugar de trabajar con una población.
Otros métodos de optimización estocástica
- El método de entropía cruzada (CE) genera soluciones candidatas usando una distribución de probabilidad que se actualiza para encontrar mejores muestras.
- La optimización de búsqueda reactiva (RSO) integra técnicas de aprendizaje para ajustar parámetros durante la búsqueda de soluciones.
Ver también
- Redes neuronales
- Lógica difusa
- Red bayesiana
- Mínimo/máximo local
- Inteligencia Artificial
- Robótica Evolutiva
- Emergencia
- Autómata celular
Véase también
En inglés: Genetic algorithm Facts for Kids
