Algoritmos genéticos: cómo un auto aprende a estacionar solo

⏱️ Lectura: 17 min

Un auto virtual sin una sola línea de código que le diga cómo manejar aprendió a estacionarse en el simulador de trekhleb.dev alrededor de la generación 40 de prueba y error automatizado: nadie programó su comportamiento, un algoritmo genético lo evolucionó desde movimientos aleatorios. El experimento reduce un problema que suena complicado (coordinar motor, volante y ocho sensores de distancia para encajar en un espacio) a un problema de optimización de 180 bits.

📑 En este artículo

1. TL;DR
2. ¿Qué es un algoritmo genético?
3. Por qué importa entender esto
4. Cómo funciona la evolución artificial del auto
   1. El genoma: el auto como una cadena de bits
   2. Sensores y motor: qué recibe y qué produce el cerebro
   3. La función de fitness: qué premia y qué castiga
   4. Selección: quién se reproduce
   5. Cruce (crossover): combinar dos genomas en uno
   6. Mutación: la fuente de novedad
   7. Elitismo: no perder al mejor
5. Ejemplos prácticos: del genoma al movimiento
   1. 1. Decodificar el genoma en movimientos
   2. 2. Calcular el fitness de un intento
   3. 3. Cruzar dos genomas
6. Cómo empezar: correr el simulador real
7. Casos de uso reales de la evolución artificial
8. Errores comunes y buenas prácticas
9. Comparativa con alternativas
10. Profundizando: detalles avanzados
11. Preguntas frecuentes
    1. ¿Un algoritmo genético garantiza encontrar la mejor solución posible?
    2. ¿Cuántas generaciones necesita la evolución artificial para estacionar un auto?
    3. ¿En qué se diferencia la evolución artificial del aprendizaje por refuerzo?
    4. ¿Hace falta saber cálculo o redes neuronales para aplicar optimización evolutiva?
    5. ¿Qué pasa si la tasa de mutación en una búsqueda evolutiva es demasiado alta?
    6. ¿Sirve la computación evolutiva para problemas fuera de simulaciones y videojuegos?
12. Referencias
    1. 📚 Artículos relacionados

Este artículo explica paso a paso cómo funciona esa evolución artificial, con ejemplos de código propios, salidas calculadas a mano y los conceptos necesarios para replicarla en cualquier lenguaje, no solo en TypeScript.

TL;DR

• Un algoritmo genético evoluciona genomas de manejo al azar hasta que uno logra estacionar sin chocar.
• Cada auto traduce ocho sensores de distancia en giros y aceleración mediante movimientos = f(sensores).
• La aptitud, o fitness, castiga los choques y premia terminar cerca y alineado con el espacio.
• Selección, cruce y mutación combinan a los padres más aptos para crear la siguiente generación.
• 180 bits de genoma bastan para que el comportamiento de manejo emerja sin reglas escritas a mano.

¿Qué es un algoritmo genético?

Un algoritmo genético es una técnica de optimización inspirada en la selección natural: genera una población de soluciones candidatas codificadas como cadenas de bits o números, mide qué tan buena es cada una con una función de fitness, y combina y muta a las mejores para producir generaciones que se acercan a la mejor solución.

En el caso del auto que se estaciona, cada solución candidata es un genoma binario que, decodificado, se convierte en una tabla de decisiones: dado lo que ven los sensores, qué hacer con el motor y con el volante. No hay red neuronal entrenada con gradientes ni reglas if/else escritas por un humano. Solo bits que sobreviven o desaparecen según qué tan bien maniobran.

Por qué importa entender esto

Los algoritmos genéticos resuelven problemas donde no existe una fórmula matemática limpia para llegar al óptimo, o donde calcular un gradiente es imposible porque la función de éxito tiene saltos discontinuos (un auto chocó o no chocó, no hay «medio choque» derivable). Eso los vuelve útiles para optimizar rutas, diseñar antenas o afinar hiperparámetros de otros modelos, tareas donde probar y comparar variantes completas es más práctico que derivar una fórmula.

A diferencia del aprendizaje por refuerzo, que ajusta una política paso a paso con una señal de recompensa en cada instante, un algoritmo genético solo necesita un puntaje final por intento completo. Eso simplifica la implementación: no hace falta diseñar una recompensa por cada instante de la simulación, alcanza con juzgar el resultado cuando el auto se detiene, choca o se queda sin tiempo.

Como pedagogía, el caso del auto que estaciona es ideal: expone en código legible cada pieza (genoma, fitness, selección, cruce, mutación) que después reaparece, con otros nombres, en el entrenamiento de redes neuronales evolutivas y en optimizadores que no dependen de backpropagation.

Cómo funciona la evolución artificial del auto

Todo el ciclo de búsqueda evolutiva que usa un algoritmo genético se repite generación tras generación con seis pasos:

flowchart TD
    A["Generar población inicial de genomas aleatorios"] --> B["Simular cada auto, sensores cada 100ms"]
    B --> C["Calcular fitness: choques, distancia y ángulo final"]
    C --> D["Seleccionar los autos más aptos"]
    D --> E["Cruzar genomas de los padres seleccionados"]
    E --> F["Mutar una fracción pequeña de los bits"]
    F --> G["Nueva generación de autos"]
    G --> B

El genoma: el auto como una cadena de bits

Cada auto de la población arranca con un genoma generado al azar: una cadena de bits que, en el proyecto original de trekhleb, mide 180 bits de longitud. Ese genoma no se interpreta directamente como «gira a la izquierda»; se decodifica en una tabla que asocia combinaciones de sensores con señales de motor y volante. Cambiar un solo bit puede cambiar por completo cómo reacciona el auto ante el mismo obstáculo.

Sensores y motor: qué recibe y qué produce el cerebro

El auto percibe el mundo con ocho sensores de distancia, cada uno capaz de medir obstáculos entre 0 y 4 metros. Cuando no hay nada cerca, el sensor reporta 0; cuanto más chico el número distinto de cero, más cerca está el obstáculo. Esos ocho valores se recalculan cada 100 milisegundos y son la única información que el auto tiene del entorno.

La salida es igual de simple: dos señales, una para el motor y otra para el volante, cada una con solo tres valores posibles: -1, 0 o +1. El motor interpreta -1 como reversa, 0 como punto muerto y +1 como avanzar; el volante interpreta -1 como girar a la izquierda, 0 como ir recto y +1 como girar a la derecha. Toda la «inteligencia» del auto se reduce a la función movimientos = f(sensores) que el genoma codifica.

flowchart LR
    S["8 sensores de distancia (0 a 4 metros)"] --> B["Genoma decodificado: movimientos = f(sensores)"]
    B --> M["Señal de motor: -1, 0 o +1"]
    B --> W["Señal de volante: -1, 0 o +1"]
    M --> C["El auto se mueve"]
    W --> C

La función de fitness: qué premia y qué castiga

La función de fitness convierte el desempeño de un auto en un número comparable. En este problema tiene que castigar los choques con dureza (un auto que se estampa contra otro carro no debería competir con uno que casi lo logra) y premiar dos cosas al final del intento: qué tan cerca terminó del espacio de estacionamiento y qué tan alineado quedó su ángulo respecto a ese espacio. Sin la segunda condición, un auto podría «ganar» quedando pegado al espacio pero de costado, sin haber estacionado en ningún sentido útil.

⚠️ Ojo: una función de fitness que solo premia velocidad y cercanía, sin castigar choques, entrena autos que se estampan contra el espacio a toda velocidad porque, técnicamente, terminan cerca.

Selección: quién se reproduce

Terminada la simulación de toda la generación, cada auto queda con un puntaje de fitness. La selección decide qué genomas pasan a la siguiente ronda como «padres»: los métodos más comunes son la selección por torneo (se sortean pares o grupos pequeños y gana el de mejor fitness) y la selección por ruleta (la probabilidad de ser elegido es proporcional al fitness). El objetivo es sesgar la reproducción hacia los mejores sin eliminar por completo la diversidad, porque una población demasiado uniforme deja de explorar soluciones nuevas.

Cruce (crossover): combinar dos genomas en uno

El cruce toma dos genomas padres y produce un hijo combinando fragmentos de ambos, normalmente cortando cada cadena en un punto y pegando la primera mitad de un padre con la segunda del otro. La apuesta es que si un padre aprendió a frenar a tiempo y el otro aprendió a girar en el momento justo, el hijo puede heredar ambas ventajas.

Mutación: la fuente de novedad

La mutación invierte al azar una fracción pequeña de los bits del hijo, típicamente entre el 1% y el 5% del genoma. Sin mutación, la población solo puede recombinar variaciones que ya existían en la generación inicial, y si esa generación inicial no incluía ningún genoma razonable, el algoritmo se estanca. La mutación es la única fuente de comportamiento genuinamente nuevo.

Elitismo: no perder al mejor

Como el cruce y la mutación son procesos con azar, es posible que una generación entera termine peor que la anterior por pura mala suerte en las combinaciones. El elitismo copia sin cambios al mejor genoma (o a los mejores N) directamente a la siguiente generación, garantizando que el progreso nunca retroceda por completo.

sequenceDiagram
    participant E as Entorno
    participant Se as Sensores
    participant Ce as Cerebro
    participant Mu as Musculos
    E->>Se: distancias a obstáculos cada 100ms
    Se->>Ce: 8 números entre 0 y 4 metros
    Ce->>Mu: señal de motor y volante
    Mu->>E: nueva posición del auto
    Note over E,Mu: se repite cada 100ms hasta chocar o estacionar

Ejemplos prácticos: del genoma al movimiento

Los siguientes ejemplos son versiones simplificadas, escritas en TypeScript, de las piezas que describimos arriba. Cada uno puede ejecutarse de forma aislada con Node.js, y su salida es la que aparece debajo, calculada exactamente sobre los valores del ejemplo.

1. Decodificar el genoma en movimientos

Este primer ejemplo muestra cómo un fragmento de bits se traduce en señales de motor o volante usando una tabla de codificación fija:

type MuscleSignal = -1 | 0 | 1;

const CODE: Record<string, MuscleSignal> = { '00': 0, '01': 1, '10': -1, '11': 0 };

function decodeMove(bits: string): MuscleSignal {
  return CODE[bits] ?? 0;
}

const genomeFragment = '011000'; // 3 movimientos codificados en 2 bits cada uno
const moves = [
  decodeMove(genomeFragment.slice(0, 2)),
  decodeMove(genomeFragment.slice(2, 4)),
  decodeMove(genomeFragment.slice(4, 6)),
];

console.log(moves);

La salida es literal: [ 1, -1, 0 ]. El primer par de bits (01) decodifica a avanzar, el segundo (10) a reversa y el tercero (00) a punto muerto.

2. Calcular el fitness de un intento

function fitness(distanciaAlEspacio: number, diferenciaAngulo: number, choco: boolean): number {
  if (choco) return 0;
  const puntajeDistancia = Math.max(0, 100 - distanciaAlEspacio * 10);
  const puntajeAngulo = Math.max(0, 50 - diferenciaAngulo);
  return puntajeDistancia + puntajeAngulo;
}

console.log(fitness(2.5, 12, false));

Con una distancia final de 2.5 metros y una diferencia de ángulo de 12 grados, sin choque, la salida es 113: 75 puntos por la distancia (100 – 2.5×10) más 38 por el ángulo (50 – 12).

3. Cruzar dos genomas

function crossover(padreA: string, padreB: string, puntoCorte: number): string {
  return padreA.slice(0, puntoCorte) + padreB.slice(puntoCorte);
}

console.log(crossover('11110000', '00001111', 4));

La salida es 11111111: los primeros 4 bits vienen del padre A (1111) y los últimos 4, del padre B (1111). Un punto de corte distinto habría producido un hijo distinto, incluso con los mismos dos padres.

Cómo empezar: correr el simulador real

El proyecto que inspira este artículo es de código abierto y corre en el navegador. Para probarlo localmente en Linux o macOS con Node.js ya instalado:

git clone https://github.com/trekhleb/self-parking-car-evolution.git
cd self-parking-car-evolution
npm install

En Windows, los mismos tres comandos funcionan igual desde PowerShell o desde una terminal de Node.js. El script exacto para levantar el simulador (según la versión del repo puede ser npm start o un script equivalente) está documentado en el README del proyecto; conviene revisarlo antes de ejecutar nada, porque puede cambiar entre versiones.

💡 Tip: si vas a experimentar con tus propios parámetros, empezá con una población chica (20-30 genomas) y una función de fitness simple. Si el auto no mejora en 20 generaciones, el problema casi siempre está en el fitness, no en el algoritmo.

Casos de uso reales de la evolución artificial

El auto que estaciona es un caso didáctico, pero la misma receta (genoma, fitness, selección, cruce, mutación) resuelve problemas de ingeniería reales. La NASA usó algoritmos evolutivos para diseñar antenas con formas que ningún ingeniero humano habría dibujado a mano, optimizando directamente el patrón de radiación en vez de partir de una geometría conocida.

Fuera del hardware, la optimización evolutiva se usa para programar horarios y turnos con restricciones difíciles de modelar analíticamente, para ajustar hiperparámetros de otros modelos de machine learning cuando la búsqueda en grilla es demasiado costosa, y para generar contenido procedural en videojuegos (niveles, mapas, criaturas) donde «bueno» se define con una función de fitness y no con una fórmula cerrada.

También es la puerta de entrada a la neuroevolución: en vez de decodificar el genoma en una tabla fija como en el ejemplo del auto, se lo puede decodificar directamente en los pesos de una red neuronal, y dejar que la evolución (no el descenso de gradiente) ajuste esos pesos. Algoritmos como NEAT llevan esa idea un paso más allá y evolucionan también la estructura de la red, no solo sus pesos.

Errores comunes y buenas prácticas

• Fitness mal diseñada: si el puntaje no captura exactamente lo que querés (estacionar bien, no solo «estar cerca»), el algoritmo va a optimizar hacia el resultado que sí mide, aunque sea el equivocado.
• Población demasiado chica: con pocos genomas, la diversidad inicial se agota rápido y la población converge de forma prematura a una solución mediocre de la que ya no puede escapar.
• Mutación mal calibrada: demasiado baja y el algoritmo se estanca sin explorar nada nuevo; demasiado alta y cada generación se parece cada vez menos a sus padres, perdiendo el progreso acumulado.
• Sin elitismo: si no protegés al mejor genoma de una generación, el azar del cruce y la mutación puede hacer que la siguiente generación sea, en promedio, peor que la anterior.
• Sobreajuste al escenario de prueba: un auto entrenado siempre con el mismo obstáculo en la misma posición puede aprender ese caso particular de memoria y fallar apenas cambia el punto de partida.

Comparativa con alternativas

Profundizando: detalles avanzados

La decisión de codificar el genoma en bits, dentro de la computación evolutiva, no es arbitraria: facilita el cruce, porque cortar una cadena de bits en un punto siempre produce dos mitades válidas, mientras que cortar una lista de números reales puede requerir más cuidado según cómo se interprete cada gen. La contrapartida es que decodificar bits a valores útiles (como los -1, 0, +1 de motor y volante) exige una tabla de mapeo, y esa tabla es, en sí misma, una decisión de diseño que afecta qué tan fácil es que la evolución encuentre soluciones buenas.

La selección por torneo y la selección por ruleta no son las únicas opciones: la selección por rango ordena a toda la población por fitness y asigna probabilidades según la posición, no según el valor absoluto del puntaje, lo que evita que un solo individuo con fitness desproporcionado domine toda la reproducción. Cuando el problema tiene más de un objetivo en tensión (por ejemplo, estacionar rápido y estacionar con precisión), algoritmos multiobjetivo como NSGA-II mantienen un frente de soluciones no dominadas en vez de reducir todo a un solo número de fitness.

El costo computacional también importa: cada generación exige simular a todos los autos de la población durante todo el intento antes de poder calcular un solo fitness. Con poblaciones grandes y simulaciones largas, ese costo crece rápido, y es una de las razones por las que, para problemas donde sí existe una señal de recompensa por paso, el aprendizaje por refuerzo suele ser más eficiente en cómputo que una evolución artificial equivalente.

📖 Resumen en Telegram: Ver resumen.

Tu próximo paso: tomá los tres ejemplos de código de este artículo, pegalos en un archivo .ts y modificá los valores de fitness() para ver cómo cambia el puntaje antes de tocar el simulador completo.

Preguntas frecuentes

¿Un algoritmo genético garantiza encontrar la mejor solución posible?

No. Un algoritmo genético converge hacia una buena solución, pero no hay garantía matemática de que sea la óptima global; puede quedar atrapado en un óptimo local si la población pierde diversidad demasiado rápido.

¿Cuántas generaciones necesita la evolución artificial para estacionar un auto?

Depende de la función de fitness, el tamaño de la población y la tasa de mutación. En el experimento de trekhleb.dev, los autos empiezan a mostrar comportamiento de estacionamiento reconocible alrededor de la generación 40, sin garantía de que ese número se repita con otros parámetros.

¿En qué se diferencia la evolución artificial del aprendizaje por refuerzo?

La evolución artificial evalúa el resultado completo de un intento con una sola función de fitness al final, mientras que el aprendizaje por refuerzo ajusta una política usando una señal de recompensa en cada paso de la simulación.

¿Hace falta saber cálculo o redes neuronales para aplicar optimización evolutiva?

No. La versión básica solo necesita cadenas de bits, una función de fitness y operaciones de selección, cruce y mutación; no hay derivadas ni matrices de pesos involucradas, a menos que se decida decodificar el genoma en una red neuronal.

¿Qué pasa si la tasa de mutación en una búsqueda evolutiva es demasiado alta?

Cada hijo se parece cada vez menos a sus padres, así que el algoritmo deja de acumular progreso entre generaciones y se comporta más como una búsqueda aleatoria que como una evolución dirigida.

¿Sirve la computación evolutiva para problemas fuera de simulaciones y videojuegos?

Sí: se usa en diseño de antenas, ajuste de hiperparámetros de modelos de machine learning y programación de horarios con restricciones complejas, entre otros problemas donde no hay una fórmula cerrada para el óptimo.

Referencias

• Self-Parking Car in 500 Lines of Code (trekhleb.dev): el artículo y simulador original en los que se inspira este ejemplo.
• Repositorio self-parking-car-evolution en GitHub: código fuente completo en TypeScript del simulador.
• Genetic algorithm (Wikipedia): definición formal y variantes del algoritmo genético.
• Evolved antenna (Wikipedia): caso real de la NASA usando algoritmos evolutivos para diseño de hardware.

📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @programacion donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.

Imagen destacada: Foto de Arron Choi en Unsplash