Los algoritmos genéticos explicados
La evolución ha producido ojos, alas y cerebros sin un diseñador, simplemente conservando lo que funciona y variándolo. Un algoritmo genético toma prestada esa idea para resolver problemas en un ordenador. No necesita entender el problema, solo distinguir una respuesta mejor de una peor, lo que lo convierte en una herramienta potente cuando el espacio de respuestas posibles es demasiado grande y demasiado extraño para explorarlo de otra manera.
La idea
En las décadas de 1960 y 1970, John Holland, de la Universidad de Míchigan, convirtió la teoría de Darwin en un algoritmo, descrito en su libro «Adaptation in Natural and Artificial Systems» de 1975. Más o menos en la misma época, Ingo Rechenberg y Hans-Paul Schwefel desarrollaron en Alemania las estrategias evolutivas para el diseño en ingeniería. La receta común: mantener una población de soluciones candidatas, puntuarlas, dejar que las mejores se reproduzcan con variación y repetir durante muchas generaciones.
Los genes y la población
Cada candidato se describe mediante un cromosoma, una lista de genes. En el laboratorio, los genes de un cohete son sus impulsos, uno por cada momento de su vuelo; en otros problemas podrían ser los bits de un número, el orden de las ciudades en una ruta o los tamaños de las piezas de un diseño. La primera generación es aleatoria, lo que significa que explora ampliamente el espacio de respuestas pero casi no tiene ninguna buena.
La función de aptitud
La aptitud es el único número que dice lo bueno que es un candidato, y es lo único que el algoritmo sabe del problema. Para los cohetes, premia sobre todo llegar pronto, después terminar cerca del objetivo, y castiga los choques. Una función de aptitud bien elegida guía la búsqueda suavemente hacia buenas respuestas; una descuidada premia lo que no debe, y el algoritmo aprovechará cualquier resquicio que deje abierto.
La selección
Los padres se eligen de modo que los candidatos más aptos tengan más hijos, pero los más débiles sigan teniendo una oportunidad, porque sus genes pueden contener piezas útiles. La selección por ruleta da a cada candidato una porción de una rueda proporcional a su aptitud; la selección por torneo toma unos cuantos al azar y se queda con el mejor. Una selección más fuerte acelera el progreso, pero también hace la población más uniforme, lo que puede terminar la búsqueda demasiado pronto.
Cruce y mutación
El cruce combina dos progenitores: aquí un hijo toma la primera parte de sus genes de uno y el resto del otro, de modo que las primeras maniobras de un cohete pueden unirse a las últimas de otro. La mutación sustituye algunos genes al azar. El cruce recombina lo que la población ya tiene; la mutación aporta lo que nunca ha tenido. El teorema de los esquemas de Holland describe cómo se extienden por la población bloques cortos de genes buenos bajo esta mezcla de selección y recombinación.
Elitismo, exploración y explotación
Copiar sin cambios los pocos mejores candidatos en la siguiente generación, el elitismo, garantiza que la mejor respuesta nunca se pierda. Todo algoritmo genético debe equilibrar la exploración, probar regiones nuevas del espacio de búsqueda, con la explotación, refinar lo que ya es bueno. Con muy poca variación, la población converge en una única respuesta mediocre; con demasiada, nunca se asienta. El tamaño de la población, la tasa de mutación y la presión de selección son los mandos que fijan ese equilibrio.
Óptimos locales
Un algoritmo genético solo sigue la aptitud, así que puede dejarse engañar. Cuando el camino hacia la mejor respuesta pasa primero por otras peores, la población sube a la colina más cercana y se queda allí: un óptimo local. Detrás de los muros escalonados del laboratorio, los cohetes que se estrellan bajo el objetivo puntúan mejor que los que se desvían para encontrar el hueco, así que la población se amontona contra el muro. Entre los remedios están las poblaciones más grandes, una mutación más alta, mantener la diversidad de la población y, sobre todo, una función de aptitud mejor.
Explóralo
Abre el laboratorio de algoritmos genéticos para hacer evolucionar cohetes alrededor de un muro, un hueco, pilares, muros escalonados o muros que dibujes tú. Cambia la población, la tasa de mutación, la duración de vida y el método de selección, activa y desactiva el elitismo y sigue en el gráfico lo rápido que crece la proporción de cohetes que alcanzan el objetivo, o por qué no crece.
Preguntas frecuentes
¿Es un algoritmo genético un tipo de inteligencia artificial?
Pertenece al campo más amplio de la IA y el aprendizaje automático, como método de búsqueda y optimización. No aprende de ejemplos como una red neuronal; mejora soluciones candidatas mediante ensayo y selección. Ambos se combinan a menudo, por ejemplo haciendo evolucionar la estructura o los pesos de redes neuronales, un enfoque llamado neuroevolución.
¿Encuentra siempre un algoritmo genético la mejor respuesta?
No. Es una heurística: suele encontrar buenas respuestas a problemas difíciles, pero no garantiza la mejor ni demuestra cuánto se acerca a ella. Para los problemas en los que un método exacto es lo bastante rápido, ese método es mejor.
¿Qué diferencia hay entre un algoritmo genético y las estrategias evolutivas?
Ambos son algoritmos evolutivos. Los algoritmos genéticos clásicos hacen hincapié en el cruce de cromosomas con forma de cadena; las estrategias evolutivas trabajan sobre todo con la mutación de números reales y a menudo adaptan por sí mismas el tamaño de sus mutaciones sobre la marcha. Los métodos modernos mezclan ideas de ambos.
¿Por qué los cohetes son tan torpes al principio?
Sus primeros genes son impulsos completamente aleatorios, que en promedio se anulan, así que los cohetes van a la deriva. Solo cuando la selección ha conservado los raros cohetes que por casualidad empujaban más o menos en la dirección correcta, y el cruce ha combinado sus buenos tramos, aparecen vuelos coordinados.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Abrir el laboratorio de algoritmos genéticos