Branch and bound nos llevó al óptimo del TSP de Rutalia expandiendo mil nodos en lugar de un millón — pero cerramos la lección admitiendo que la explosión combinatoria solo estaba retrasada: con las 60-120 paradas de una furgoneta real, ningún método exacto termina a tiempo. Esta lección cruza la frontera de forma deliberada: los algoritmos genéticos (AG) renuncian a la garantía de optimalidad y, a cambio, producen soluciones muy buenas en tiempo controlado, para casi cualquier problema que sepas evaluar. Veremos el esquema evolutivo completo — codificación, población, fitness, selección, cruce, mutación, elitismo — y lo implementaremos entero en Python sobre la misma instancia de 10 puntos de 02-02/02-03, para poder comparar contra el óptimo conocido de 35,22 km. Terminaremos con una guía de hiperparámetros y un vistazo breve a las metaheurísticas "primas" (recocido simulado, búsqueda tabú).

1. Exactos vs heurísticos: qué sacrificamos y qué ganamos
2. La metáfora evolutiva
3. Representación: cromosomas binarios y permutaciones
4. Función de fitness
5. Selección: torneo y ruleta
6. Cruce: un punto y order crossover (OX)
7. Mutación, elitismo y criterios de parada
8. Implementación completa: AG para el TSP de Rutalia
9. Hiperparámetros: qué tocar y qué esperar
10. Las primas de vecindad: recocido simulado y búsqueda tabú

La palabra clave es certificado. Un AG puede darte la ruta óptima — de hecho, en nuestra instancia pequeña lo hará — pero no puede decírtelo: no produce cotas que demuestren que no existe nada mejor. Para Rutalia el trato suele compensar: entre "la ruta óptima dentro de tres semanas" y "una ruta un 2 % peor dentro de un minuto", operaciones elige lo segundo todos los días. La disciplina profesional consiste en saber cuándo estás haciendo ese trato y en medir la calidad contra cotas o instancias con óptimo conocido — exactamente lo que haremos aquí.

Un AG mantiene una población de soluciones candidatas y la hace evolucionar imitando la selección natural:

La intuición de por qué funciona: la selección concentra a la población en zonas buenas del espacio de soluciones (explotación), el cruce combina fragmentos buenos de padres distintos — quizá una madre resuelve bien el norte de la ciudad y un padre el sur —, y la mutación inyecta variedad para no quedarse atascado (exploración). Nada de esto garantiza el óptimo; lo que produce es una presión estadística sostenida hacia soluciones mejores.

Vocabulario que usaremos: individuo/cromosoma (una solución codificada), gen (una posición del cromosoma), fitness (calidad del individuo), generación (una iteración del bucle).

La primera decisión de diseño — y la más importante — es cómo codificar una solución:

• Codificación binaria: una lista de 0/1. Natural para problemas de subconjunto, como la mochila de 02-02: [0, 1, 0, 1, 0] significa "cargar E2 y E4". Los operadores clásicos (cruce por punto, mutación bit a bit) funcionan directamente.
• Codificación de permutación: un orden de elementos. Natural para problemas de secuencia como el TSP: [3, 1, 5, ...] es el orden de visita de las paradas. Cuidado: los operadores binarios clásicos aquí rompen la solución — cruzar dos permutaciones por un punto suele duplicar unas paradas y omitir otras, es decir, produce hijos que ni siquiera son rutas. Las permutaciones exigen operadores especializados (OX, que veremos enseguida).

El fitness traduce "calidad" a un número que la selección pueda comparar. Para el TSP, menor distancia = mejor individuo. Dos opciones habituales: usar directamente la longitud de la ruta (y seleccionar los menores), o convertir a "mayor es mejor" con fitness = 1 / longitud. Usaremos la primera por claridad, con una precaución de ingeniería: la evaluación de fitness es el 90 % del coste de un AG típico (se ejecuta población × generaciones veces), así que debe ser barata — y con nuestra matriz D precalculada en 02-02, lo es.

Para problemas con restricciones (mochila con sobrepeso), el fitness además debe decidir qué hacer con los infactibles: penalizar (restar mucho valor por kilo de exceso) o reparar (descargar objetos hasta que quepa). Las penalizaciones mal calibradas son una fuente clásica de AGs que "funcionan" llenos de soluciones inservibles.

La selección elige qué individuos se reproducen. Debe favorecer a los buenos sin eliminar la diversidad (si solo se reproduce el mejor, en tres generaciones la población son clones y el AG degenera en un voraz caro).

• Torneo (k participantes): elige k individuos al azar y gana el mejor. Simple, robusto y con presión regulable: k = 2 es suave, k = 7 es agresivo. Es la opción por defecto en la práctica.
• Ruleta: cada individuo recibe una probabilidad proporcional a su fitness (una "ruleta" con sectores de tamaño desigual). Elegante en teoría, delicada en la práctica: exige fitness positivo y "mayor = mejor", y si un individuo domina mucho, monopoliza la ruleta (convergencia prematura); si todos son parecidos, la selección se vuelve casi aleatoria.

Cruce de un punto (codificación binaria): corta ambos padres por la misma posición aleatoria e intercambia las mitades. Para la mochila: [1,0|0,1,1] × [0,1|1,0,0] → hijos [1,0,1,0,0] y [0,1,0,1,1]. Barato y efectivo cuando genes contiguos forman "bloques" con sentido.

Order crossover (OX) (permutaciones): el operador estrella para rutas. Copia un segmento del padre 1 tal cual, y rellena los huecos con las paradas restantes en el orden en que aparecen en el padre 2. El hijo hereda una subruta literal de un padre y el orden relativo del otro — y siempre es una permutación válida:

• Mutación: con probabilidad pequeña, alterar el individuo. Binaria: voltear un bit. Permutaciones: intercambiar dos posiciones (swap) o invertir un tramo. Sin mutación, la población solo recombina material genético inicial: si ninguna permutación inicial pone a H al final, el cruce jamás lo inventará; la mutación sí.
• Elitismo: copiar intactos los 1-2 mejores individuos a la siguiente generación. Garantiza que el mejor resultado nunca empeora entre generaciones (monotonía que la selección estocástica por sí sola no da). Con demasiada élite, la población se uniformiza.
• Criterios de parada: número fijo de generaciones (predecible, nuestro default), estancamiento (X generaciones sin mejora — el más usado en producción), presupuesto de tiempo, o alcanzar una cota conocida.

Todo junto, sobre la instancia de 02-02 (requiere NOMBRES, D y longitud_ruta de esa lección). El depósito (índice 0) queda fuera del cromosoma: siempre es inicio y fin, así que el individuo es una permutación de [1..9]:

Puntos que merecen lupa:

• Evaluaciones totales: 100 individuos × 200 generaciones = 20.000 evaluaciones de ruta — del mismo orden de trabajo útil que los ~1.200 nodos de B&B multiplicados por su coste de cota, y muy por debajo de las 362.880 rutas de la fuerza bruta. En nuestra ejecución, el AG alcanza el óptimo conocido de 35,22 km (la misma ruta que B&B), normalmente en las primeras decenas de generaciones. Que esto ocurra casi siempre en una instancia de 10 nodos es esperable: el espacio es pequeño para la potencia del método. La diferencia aparece al escalar: con 100 paradas, B&B no termina y el AG sigue entregando buenas rutas con el mismo código.
• La élite se copia (ind[:]), no se referencia: si la mutación tocara una referencia compartida, corrompería al mejor individuo silenciosamente. Errores así son la pesadilla de depurar AGs, porque el algoritmo sigue funcionando, solo que peor.
• El historial es tu instrumento de diagnóstico: una curva que cae rápido y se aplana pronto sugiere convergencia (¿prematura?); una que baja a trompicones hasta el final pide más generaciones.
• La semilla fija la secuencia aleatoria. En producción se ejecutan varias semillas y se reporta media y mejor caso — una sola ejecución de un algoritmo estocástico es una anécdota, no una medida.

Los AG no se programan una vez: se ajustan. Guía de efectos:

La tensión de fondo es siempre la misma: explotación (refinar lo bueno: más presión de selección, más élite) contra exploración (buscar lo nuevo: más mutación, más población). No existe configuración universal; existe el hábito de medir con el historial y ajustar un parámetro cada vez.

Los AG no son la única forma de buscar sin garantías. Dos familias que conviene conocer de nombre — trabajan con un solo individuo que se mueve por su vecindario (soluciones a un pequeño cambio de distancia), en lugar de con una población:

• Recocido simulado (simulated annealing): acepta a veces movimientos que empeoran, con una probabilidad que decae con el tiempo (la "temperatura" baja). Al principio explora con libertad; al final solo refina. Inspiración: el enfriamiento lento de los metales.
• Búsqueda tabú: búsqueda local que mantiene una lista tabú de movimientos recientes prohibidos, para no deshacer lo andado ni ciclar alrededor de un óptimo local.

En la práctica compiten de tú a tú con los AG (y a menudo se hibridan: un AG cuyo mejor individuo se refina con búsqueda local). No las desarrollaremos más: nos basta con saber que existen y qué las distingue, porque la próxima lección presenta una metaheurística de espíritu muy distinto — basada en cooperación mediante rastros compartidos — y cerraremos comparando las tres aproximaciones del módulo sobre el mismo TSP.

• Cruce clásico sobre permutaciones. El cruce de un punto aplicado a rutas produce hijos con paradas duplicadas y omitidas — ni siquiera son soluciones. Con permutaciones, usa OX (o PMX/CX, sus parientes). Es el error número uno al adaptar código de mochila a TSP.
• Olvidar copiar la élite. nueva = poblacion[:2] guarda referencias; una mutación posterior corrompe a los mejores. Copia con ind[:] o list(ind).
• Fitness caro. Si evaluar un individuo cuesta 10 ms, 100 × 200 evaluaciones son 3,3 minutos solo de fitness. Precalcula (nuestra matriz D), cachea, vectoriza. El análisis de costes de 01-02 se aplica dentro de la metaheurística.
• Convergencia prematura no diagnosticada. Si en la generación 20 todos los individuos son casi idénticos, el resto del presupuesto se tira. Vigila la diversidad (p. ej., longitudes distintas en la población) además del mejor fitness.
• Concluir a partir de una ejecución. Estocástico significa que la semilla 42 puede ser afortunada. Ejecuta 10-30 semillas y mira distribución, no anécdota.
• Usar un AG donde hay método exacto viable. Para la mochila de 5 envíos o el TSP de 10 puntos, PD y B&B dan el óptimo certificado en menos tiempo del que cuesta ajustar hiperparámetros. Las metaheurísticas son la herramienta de frontera, no la primera opción.
• Consejo: guarda siempre el mejor individuo global de la ejecución (no solo el de la última generación) y, si existe, compáralo con una cota o un óptimo conocido. Sin referencia, "el AG mejoró" no significa nada.

1. OX a mano. Con padres P1 = [2, 5, 1, 4, 3, 6] y P2 = [4, 1, 6, 2, 5, 3] y segmento en las posiciones 1–3 (0-indexado, ambas incluidas), calcula el hijo del cruce_ox paso a paso. Verifica que es una permutación válida.

2. AG para la mochila. Adapta el esquema completo a la mochila 0/1 de 02-02 (capacidad 15, pesos [12, 7, 11, 8, 9], valores [40, 24, 35, 26, 30]): codificación binaria, cruce de un punto, mutación de volteo de bit, y fitness con penalización por sobrepeso (valor − 10 × exceso). ¿Alcanza el óptimo de 50 €? ¿Qué pasa si la penalización es 1 por unidad de exceso en vez de 10?

3. Estudio de mutación. Ejecuta algoritmo_genetico con prob_mutacion en {0.0, 0.05, 0.2, 0.8} y 10 semillas cada una (deja el resto de parámetros por defecto). Para cada valor anota cuántas semillas alcanzan 35,22 km y la media del mejor resultado. Interpreta los extremos.

Ejercicio 1. Segmento de P1, posiciones 1–3: 5, 1, 4 → hijo parcial [_, 5, 1, 4, _, _]. Restantes de P2 en su orden, saltando 5, 1, 4: P2 = [4, 1, 6, 2, 5, 3] → quedan 6, 2, 3. Huecos: posiciones 0, 4, 5 → hijo = [6, 5, 1, 4, 2, 3]. Contiene cada gen 1..6 exactamente una vez: permutación válida. Observa la herencia: el bloque 5-1-4 viene literal de P1; el orden relativo 6 → 2 → 3 viene de P2.

Ejercicio 2. Esqueleto de los cambios:

Con penalización 10, el sobrepeso sale carísimo y la población converge a individuos factibles; el óptimo [0,1,0,1,0] (50 €) aparece en pocas generaciones — el espacio solo tiene 2⁵ = 32 puntos, así que más que un reto es un banco de pruebas. Con penalización 1 el AG descubre un "truco" indeseado: [1,1,1,1,1] pesa 47 (exceso 32) y puntúa 155 − 32 = 123 > 50 — el mejor individuo es infactible y el AG optimiza con entusiasmo el problema equivocado. Es la lección importante del ejercicio: la penalización debe hacer que ningún infactible supere a un factible, o el fitness miente.

Ejercicio 3. Resultados típicos (los tuyos variarán, de eso trata el ejercicio): con 0.0, varias semillas se quedan clavadas por encima del óptimo — sin mutación, la población agota su material genético inicial y no puede fabricar orderings nuevos; con 0.05 y 0.2, la gran mayoría de semillas alcanzan 35,22 km, con 0.2 algo más robusto en esta instancia; con 0.8, los hijos se destruyen casi siempre nada más nacer y la media empeora — la búsqueda se acerca a un muestreo aleatorio con élite. La curva calidad-vs-mutación tiene forma de U invertida: el punto dulce está donde hay variedad suficiente sin destruir la herencia.

Hemos hecho el trato heurístico con los ojos abiertos: a cambio del certificado de optimalidad que daban PD y B&B, los algoritmos genéticos nos dan escala y generalidad — solo piden una codificación sensata (binaria para subconjuntos, permutaciones con OX para rutas), un fitness barato y honesto con las restricciones, y el equilibrio eterno entre presión de selección y mutación. Sobre el TSP de Rutalia, nuestro AG de 100 individuos y 200 generaciones alcanzó los mismos 35,22 km que B&B certificó en 02-03 — sin poder certificarlos, pero con un código que seguiría funcionando igual con 100 paradas, donde B&B ya no juega. En la próxima lección conoceremos una metaheurística con otra inspiración biológica: en lugar de herencia y selección, cooperación indirecta — hormigas que se dejan señales químicas sobre las buenas rutas. Implementaremos la optimización por colonia de hormigas sobre esta misma instancia y cerraremos el módulo con la comparación experimental de las tres aproximaciones: exacta, evolutiva y estigmérgica.