Algoritmos geneticos explicados con pizza y horarios de tren

1. La palabra que asusta pero no deberia

Algoritmo genetico. Si nunca lo has oido, suena a tesis doctoral. Si lo has oido, probablemente te hayan contado que es algo complicadisimo con cruces, mutaciones y frentes de Pareto. La realidad es mucho mas simple: un algoritmo genetico es prueba y error con buena memoria.

Imagina que estas cocinando. Preparas un plato, lo pruebas, y esta soso. La proxima vez le echas mas sal. Si mejora, apuntas el cambio. Si empeora, vuelves a la version anterior. Eso es exactamente lo que hace un algoritmo genetico, pero en lugar de cocinar un plato, esta disenando el ala de un avion. Y en lugar de hacerlo una vez, lo hace 10.000 veces en una hora.

El termino "genetico" viene de la biologia. Darwin observo que los animales con caracteristicas favorables sobreviven y se reproducen, pasando esas caracteristicas a sus crias. Los algoritmos geneticos copian este mecanismo: crean una poblacion de soluciones, seleccionan las mejores, las cruzan para generar soluciones "hijas" y repiten. Generacion tras generacion, las soluciones mejoran.

No necesitas saber programar para entender como funcionan. Solo necesitas hambre. Vamos a disenar la pizza perfecta.

2. La pizza perfecta: un problema de optimizacion disfrazado de cena

Tienes tres variables para tu pizza: el grosor de la masa (del 1 al 10), la cantidad de queso (del 1 al 10) y la temperatura del horno (de 150 a 300 grados). Tu objetivo: la pizza mas deliciosa posible. Este es un problema de optimizacion con 3 variables.

Un enfoque de fuerza bruta seria probar TODAS las combinaciones. Eso son 10 × 10 × 151 = 15.100 pizzas distintas. Asumiendo que tardas 20 minutos en hacer cada una, necesitarias 210 dias sin dormir. Y eso con solo 3 variables. Si tuvieras 10 variables, el numero de combinaciones explotaria hasta hacerlo imposible. A esto se le llama maldicion de la dimensionalidad.

El algoritmo genetico adopta un enfoque mucho mas inteligente. En lugar de probar todas las combinaciones, empieza con un grupo pequeno de pizzas aleatorias, las prueba, aprende de los resultados y genera nuevas pizzas mezclando las mejores caracteristicas de las anteriores. Es como si en lugar de leer todos los libros de una biblioteca, hablaras con las personas que mas han leido y te quedaras con sus recomendaciones.

3. Poblacion y cromosomas: tus primeras 10 pizzas

El algoritmo arranca generando 10 pizzas al azar. Cada pizza es lo que llamamos un individuo, y el conjunto de 10 pizzas es la poblacion. Cada individuo tiene un cromosoma, que no es mas que una lista de numeros. Asi de simple:

• Pizza 1: [3, 8, 220] → masa fina, mucho queso, temperatura media
• Pizza 2: [9, 2, 300] → masa gorda, poco queso, horno a tope
• Pizza 3: [1, 10, 180] → masa finisima, queso a reventar, horno bajo
• Y asi hasta 10.

Esa lista de tres numeros es el cromosoma. En ingenieria real, el cromosoma podria tener 50 numeros representando la curvatura de un ala, el grosor de un material o el angulo de una turbina. Pero el principio es el mismo: una lista de valores que define una solucion candidata.

Las primeras 10 pizzas seran probablemente horribles. La mayoria estaran quemadas, crudas o con una combinacion de ingredientes incomible. Pero alguna, por puro azar, sera ligeramente menos mala que las demas. Y ahi empieza la magia.

4. Seleccion: que sobrevivan las mejores pizzas

Una vez que has horneado las 10 pizzas, las pruebas y les pones nota del 1 al 10. Las 4 con mejor puntuacion sobreviven. Las otras 6 van a la basura (o al comedor de la oficina). Este proceso se llama seleccion por torneo.

El nombre suena tecnico pero el concepto no lo es: organizas un "torneo" donde coges un grupo al azar (por ejemplo, 3 pizzas de entre las 10) y la que tiene mejor nota gana y pasa a la siguiente ronda. Repites esto hasta tener suficientes ganadores. Es como un concurso de talentos pero con mas pepperoni.

En terminos de ingenieria, la seleccion por torneo es preferida porque no requiere ordenar toda la poblacion y porque permite controlar la presion selectiva: si el torneo es grande (coges 5 en lugar de 3) los mejores ganan casi siempre y la busqueda se vuelve mas intensiva pero menos exploratoria. Si el torneo es pequeno (2), hay mas diversidad pero se tarda mas en converger.

Aqui tienes el pseudocodigo de una seleccion por torneo en Python, para que veas lo ridiculamente sencillo que es:

def torneo(poblacion, k=3):
    participantes = random.sample(poblacion, k)
    ganador = max(participantes, key=lambda p: p.puntuacion)
    return ganador

# Repetir hasta tener N ganadores para la siguiente generacion
padres = [torneo(poblacion, k=3) for _ in range(N)]

Y ya esta. Eso es la seleccion. Coge unos cuantos al azar, quedate con el mejor. Repite. Cero magia, cero inteligencia artificial, pura logica.

5. Cruce: cuando dos pizzas se quieren

Ya tienes a tus 4 supervivientes. Ahora tienes que crear la siguiente generacion. Para ello, tomas dos padres y los cruzas para generar un hijo. El mecanismo mas sencillo se llama cruce de un punto:

Pizza A: [3, 8, 220] (masa fina, mucho queso, 220°C)
Pizza B: [7, 5, 180] (masa gorda, queso medio, 180°C)

Elige un punto de corte al azar —por ejemplo, entre la primera y la segunda variable— y combina:

Hijo 1: [3, 5, 180] — masa fina de A, queso y temperatura de B
Hijo 2: [7, 8, 220] — masa gorda de B, queso y temperatura de A

Es como si cogieras la receta de tu abuela de la pasta y la receta de la salsa de un chef italiano y las juntaras. A veces sale un desastre. A veces sale algo que ninguno de los dos habria imaginado. Esa es la gracia.

En versiones mas sofisticadas, como el SBX (Simulated Binary Crossover) usado en NSGA-II, en lugar de copiar valores directamente, se calcula una media ponderada de los padres controlada por un parametro que determina cuanto se alejan los hijos de los padres:

def cruce(padre1, padre2, eta=20):
    hijo1, hijo2 = padre1[:], padre2[:]
    for i in range(len(padre1)):
        if random.random() < 0.5:
            if random.random() <= 0.5:
                beta = (2 * random.random()) ** (1 / (eta + 1))
            else:
                beta = (1 / (2 * (1 - random.random()))) ** (1 / (eta + 1))
            hijo1[i] = 0.5 * ((1 + beta) * padre1[i] + (1 - beta) * padre2[i])
            hijo2[i] = 0.5 * ((1 - beta) * padre1[i] + (1 + beta) * padre2[i])
    return hijo1, hijo2

Con eta alto, los hijos se parecen mucho a los padres (explotas lo que ya sabes). Con eta bajo, los hijos exploran zonas nuevas del espacio de busqueda. Como todo en ingenieria: un equilibrio.

6. Mutacion: el toque de locura necesario

Si solo cruzas a los mejores, corres el riesgo de estancarte. Imagina que por puro azar ninguna de tus pizzas iniciales lleva oregano. Por muchas generaciones que pasen, jamas descubriras el oregano porque nunca estuvo en el ADN de la poblacion inicial. Necesitas un mecanismo que introduzca variedad nueva.

Ahi entra la mutacion. De vez en cuando (tipicamente entre un 5% y un 10% de las veces), coges un valor de un hijo y lo cambias ligeramente al azar. El hijo [3, 5, 180] podria mutar a [3, 5, 185]. O a [3, 7, 180]. Son cambios pequenos, pero suficientes para explorar combinaciones que nadie habia probado.

La tasa de mutacion es un equilibrio delicado. Demasiado baja y no exploras suficiente. Demasiado alta y tu algoritmo se convierte en busqueda aleatoria pura, perdiendo todo lo aprendido en generaciones anteriores. Es como si en una receta cambiaras un ingrediente cada vez que cocinas. Si cambias poco, mejoras gradualmente. Si cambias todo de golpe, nunca sabras que funciono y que no.

En la practica, la probabilidad de mutacion se establece en 1/n, donde n es el numero de variables. Para nuestra pizza de 3 variables, cada variable tiene un 33% de posibilidades de mutar en cada nueva generacion. En un ala de avion con 50 variables de diseno, cada variable tiene un 2% de mutar. Muchas mutaciones pequenas, no pocas mutaciones grandes.

7. El problema de los horarios de tren: cuando el cerebro humano se rinde

Vale, la pizza esta muy bien. Pero a nadie le pagan por disenar pizzas con algoritmos geneticos. Veamos un problema real: planificar los horarios de una red de trenes.

Imagina 50 trenes que tienen que compartir 200 franjas horarias en un dia. Cada tren tiene una ruta, una velocidad, una prioridad y un tiempo minimo entre salidas. Quieres maximizar el numero de conexiones entre trenes (para que los pasajeros puedan hacer transbordos) y minimizar los retrasos acumulados. Este problema tiene mas combinaciones posibles que atomos en el universo.

Un planificador humano podria hacer un horario decente para 10 trenes en una semana. Pero para 50 trenes con 200 franjas, las interacciones son tan complejas que ningun humano —ni siquiera un equipo de humanos— puede encontrar la solucion optima. Simplemente hay demasiadas posibilidades.

El algoritmo genetico lo plantea asi: cada cromosoma es una lista de 50 numeros, donde cada numero representa la franja horaria asignada a cada tren. Por ejemplo, [14, 87, 3, 156, ...] significa: el tren 1 sale en la franja 14, el tren 2 en la 87, el 3 en la 3, etc. La funcion de evaluacion (la nota de la pizza) calcula cuantos transbordos se logran y cuanto retraso se genera.

Con 200 generaciones y una poblacion de 100 horarios, el algoritmo evalua 20.000 horarios distintos —cada uno probando combinaciones diferentes de asignaciones— y converge hacia soluciones que ningun humano habria encontrado. Y lo hace en minutos. No es la solucion perfecta (esa es practicamente imposible de encontrar), pero si una solucion "near-optimal": aproximadamente un 95-98% tan buena como la teorica optima.

8. Por que funciona: supervivencia de los bloques que funcionan

Hay una razon matematica por la que los algoritmos geneticos funcionan, y se llama el teorema de los esquemas. Pero no te preocupes, vamos a explicarlo sin una sola ecuacion.

Imagina que en el problema de los trenes, descubres que los trenes que salen en franjas impares tienden a conectar mejor con los trenes de larga distancia. Ese patron ("franja impar para trenes de cercanias") es lo que se llama un esquema: un trozo de solucion que funciona bien independientemente del resto de variables.

Los algoritmos geneticos son extremadamente buenos detectando estos esquemas. Cuando dos padres comparten un trozo bueno de solucion, el cruce tiende a preservarlo en los hijos. Y cuando ese trozo aparece en varios individuos con buena puntuacion, la seleccion tiende a multiplicarlo en la poblacion. Es un proceso de propagacion de buenas ideas parciales.

El teorema de los esquemas demuestra matematicamente que los esquemas cortos, de orden bajo y con rendimiento superior a la media reciben un numero exponencialmente creciente de copias en generaciones sucesivas. Traducido: las buenas ideas se vuelven virales dentro de la poblacion. Lo que funciona se copia. Lo que no, se extingue.

Es evolucion darwiniana dentro de un ordenador. Y funciona por la misma razon que la naturaleza ha producido ojos, alas y cerebros: porque acumular pequenas mejoras durante muchas generaciones produce resultados asombrosos.

9. Cuando NO usar algoritmos geneticos

Los algoritmos geneticos no son una herramienta universal. Hay situaciones donde usarlos es como matar moscas a canonazos. Aqui van las tres reglas para saber cuando buscar otra cosa:

Regla 1: Si puedes calcular la pendiente, usa descenso por gradiente. Si tu problema tiene una funcion diferenciable (puedes calcular hacia donde mejora mas rapido), metodos como el descenso por gradiente o L-BFGS son muchisimo mas rapidos. Un algoritmo genetico explora a ciegas; el descenso por gradiente sigue la pendiente mas pronunciada. Si estas en una colina con niebla, el algoritmo genetico da palos de ciego; el gradiente te dice "cuesta abajo es por ahi".

Regla 2: Si el problema es pequeno, usa fuerza bruta. Para problemas con 4 o 5 variables y pocos valores posibles, evaluar todas las combinaciones es mas rapido que montar todo el andamiaje de un algoritmo genetico. No uses un cohete para ir a la panaderia de la esquina.

Regla 3: Si las restricciones son muy estrictas, usa solvers MILP o SAT. Si todas tus variables son discretas y tienes restricciones del tipo "si A entonces no B", los solvers de programacion lineal entera (MILP) o de satisfacibilidad (SAT) son imbatibles. Los algoritmos geneticos pueden manejar restricciones, pero les cuesta. No les pidas a un corredor de maraton que juegue al ajedrez.

Los algoritmos geneticos brillan en el punto dulce: problemas con muchas variables, funciones de evaluacion costosas (como simulaciones CFD que tardan horas), multiples objetivos contrapuestos y espacios de busqueda con muchos optimos locales. Ahi es donde la evolucion le gana al calculo diferencial.

10. De la pizza al mundo real: lo que hemos aprendido

Hemos recorrido un camino que va desde la pizza hasta los horarios de tren. En el trayecto, has aprendido los cinco ingredientes de cualquier algoritmo genetico: poblacion (un grupo de soluciones), seleccion (quedarse con las mejores), cruce (combinar las buenas), mutacion (explorar cosas nuevas) y evaluacion (saber cual es mejor que cual).

Lo mas bonito de todo esto es que el algoritmo no sabe nada del problema que esta resolviendo. El mismo codigo que disena la pizza perfecta puede disenar el ala de un avion, organizar los horarios de tren o encontrar la mezcla optima de materiales compuestos. Solo cambia la funcion de evaluacion. El motor evolutivo es exactamente el mismo.

En MaterialTech Labs usamos algoritmos geneticos a diario. Optimizamos quillas de surf con NSGA-II (equilibrando velocidad, maniobrabilidad y peso), disenamos laminados de fibra de carbono minimizando peso y maximizando rigidez, y buscamos perfiles aerodinamicos que ningun ingeniero habria dibujado a mano. La evolucion, dentro de un ordenador, encuentra soluciones que la intuicion humana pasa por alto.

La proxima vez que oigas "algoritmo genetico", no pienses en formulas ni en tesis doctorales. Piensa en un cocinero paciente que prueba, descarta, mezcla y vuelve a probar hasta que el plato sale perfecto. Es prueba y error. Con esteroides.