Los algoritmos genéticos de la lección anterior buscaban mediante herencia: los buenos individuos se reproducen y sus rasgos se propagan. La optimización por colonia de hormigas (ACO, Ant Colony Optimization) busca mediante algo más extraño y más elegante: cooperación indirecta. Ningún agente hereda nada de otro; simplemente, cada uno deja marcas en el entorno que sesgan las decisiones de los siguientes. Es una idea copiada literalmente de las hormigas reales, y resulta especialmente natural para los problemas de rutas que obsesionan a Rutalia: las marcas viven exactamente donde vive el problema, en los tramos entre paradas. En esta lección formalizaremos el mecanismo (feromonas, probabilidades de transición, evaporación), lo implementaremos completo en Python sobre la misma instancia de 10 puntos de las tres lecciones anteriores, y cerraremos el módulo con lo prometido: la comparación experimental de las tres aproximaciones al TSP — branch and bound, genético y colonia de hormigas — y una guía de cuándo elegir cada una.

1. La inspiración: hormigas, feromonas y estigmergia
2. Anatomía de ACO: qué mantiene y cómo decide
3. La probabilidad de transición: α y β
4. Evaporación y depósito de feromonas
5. Implementación completa: ACO para el TSP de Rutalia
6. Ajuste de parámetros
7. Comparación experimental: B&B vs genético vs ACO
8. Cuándo elegir cada aproximación

El experimento clásico (Deneubourg, años 80, con hormigas argentinas reales): se conecta un hormiguero a una fuente de comida mediante dos puentes, uno corto y uno largo. Al principio las hormigas eligen al azar, mitad y mitad. Al cabo de un rato, casi todas usan el puente corto. Ninguna hormiga ha comparado los puentes; ninguna sabe siquiera que hay dos. El mecanismo:

1. Cada hormiga deposita feromona (una señal química) al caminar.
2. Las hormigas prefieren, probabilísticamente, los caminos con más feromona.
3. Las que toman el puente corto van y vuelven antes, así que el puente corto acumula feromona más deprisa.
4. Más feromona atrae más hormigas, que depositan más feromona: retroalimentación positiva.
5. La feromona se evapora, borrando poco a poco los rastros que no se refuerzan.

A esta coordinación a través de modificaciones del entorno — sin comunicación directa, sin jefe, sin mapa — se la llama estigmergia. Lo que la convierte en algoritmo es una observación: la feromona funciona como una memoria colectiva de calidad distribuida sobre las aristas del problema, y la evaporación como un olvido controlado que evita fijarse en la primera solución mediocre. Marco Dorigo formalizó esto en 1992 como método de optimización, con el TSP como primer campo de pruebas — el mismo problema, casi la misma escala, que nuestra ruta de Rutalia.

Traducción a ingredientes computacionales, en paralelo con el AG para fijar ideas:

La diferencia filosófica: el AG recombina soluciones enteras; ACO aprende, arista por arista, qué decisiones locales suelen aparecer en las buenas soluciones. Por eso ACO brilla en problemas donde la solución es una secuencia de decisiones sobre un mapa de opciones — rutas, planificación, asignaciones encadenadas.

Una hormiga situada en el punto i decide su siguiente parada j entre las no visitadas, al azar pero con sesgo. La probabilidad de elegir j es proporcional a:

donde:

• τ(i,j) es la feromona de la arista — la memoria colectiva: "por aquí pasaron buenas rutas".
• η(i,j) es la información heurística local, para el TSP η = 1 / distancia(i,j) — la miopía útil: "esta parada está cerca".
• α y β son exponentes que gradúan cuánto pesa cada fuente.

Los dos extremos aclaran el papel de cada exponente:

• Con α = 0, la feromona se ignora: cada hormiga es un vecino más cercano probabilístico, sin aprendizaje colectivo. Recordemos de 02-02 que el vecino más cercano puro daba 43,1 km (+22 %): esa es más o menos la calidad de la primera iteración de ACO, antes de que exista rastro.
• Con β = 0, la distancia se ignora: las primeras rutas (aleatorias) marcan feromona, las siguientes las imitan, y la colonia se autoconfirma sobre rutas malas — convergencia prematura de libro.

El arte está en el medio: típicamente α = 1 y β entre 2 y 5 (la heurística manda al principio, cuando la feromona es uniforme; el rastro va tomando el control a medida que acumula evidencia).

Tras construir todas las hormigas sus rutas, la matriz τ se actualiza en dos pasos:

1. Evaporación — toda arista pierde una fracción ρ de su feromona:

   τ(i,j) ← (1 − ρ) · τ(i,j)

   Sin evaporación, los errores del pasado nunca se borran y la primera ruta razonable se fosiliza. Con ρ típico de 0,3–0,5, un rastro no reforzado se extingue en pocas iteraciones.

2. Depósito — cada hormiga añade feromona a las aristas de su ruta, en cantidad inversamente proporcional a la longitud:

   τ(i,j) ← τ(i,j) + Q / L para cada arista (i,j) de una ruta de longitud L

   Las rutas cortas depositan más por arista: la retroalimentación positiva del puente de Deneubourg, en una línea de código. Q es solo una constante de escala.

Este es el esquema original (Ant System). Las variantes que dominan la literatura afinan justo aquí: elitista (la mejor ruta histórica deposita extra), MAX-MIN (τ acotada entre un mínimo y un máximo para forzar exploración), ACS (evaporación local durante la construcción). Nos quedamos con el esquema clásico, que ya exhibe todo el comportamiento interesante.

Sobre la instancia canónica del módulo (requiere NOMBRES, D y longitud_ruta de 02-02; óptimo conocido: 35,22 km):

Lectura guiada:

• random.choices(..., weights=pesos) implementa la ruleta de transición: no elegimos la mejor candidata (eso sería un voraz) sino una al azar con probabilidades sesgadas. Ese resto de azar es lo que mantiene viva la exploración.
• El coste por iteración es n_hormigas × N decisiones, cada una con O(N) candidatas: Θ(hormigas · N²). Con 20 hormigas y 100 iteraciones son 20 × 100 = 2.000 rutas construidas — presupuesto similar al del AG (20.000 evaluaciones, pero las suyas eran más baratas: solo medir, no construir).
• Guardamos el mejor global (mejor_km) aparte de la matriz τ: la colonia puede alejarse temporalmente de la mejor ruta encontrada (y está bien que explore), pero el resultado que entregamos nunca empeora.
• En nuestra ejecución, ACO alcanza los 35,22 km óptimos, típicamente en las primeras decenas de iteraciones: el historial muestra la mecánica esperada — primeras iteraciones alrededor de 40-44 km (hormigas casi voraces sobre feromona uniforme) y caída rápida según el rastro acumula evidencia.

El diagnóstico se hace igual que en el AG: con el historial y con varias semillas. Si todas las hormigas construyen rutas casi idénticas en la iteración 15, hay convergencia prematura (sube ρ o baja α); si el mejor global sigue bajando en la última iteración, faltan iteraciones.

Es la hora de cerrar lo que abrimos en 02-02. Misma instancia (10 puntos, depósito incluido), mismo hardware, ejecuciones con las configuraciones de cada lección:

Lecturas honestas de esta tabla:

• En esta instancia todos empatan a 35,22 km. No es casualidad ni mérito de las metaheurísticas: 10 nodos es territorio cómodo para cualquiera. La elegimos precisamente para tener la respuesta correcta y poder verificar que cada método la alcanza. La tabla interesante es la fila "con 100 paradas": ahí los exactos desaparecen y solo queda comparar metaheurísticas entre sí — contra cotas inferiores, ya que el óptimo es incognoscible.
• La diferencia entre AG y ACO no es la calidad aquí, sino el carácter. El AG es agnóstico: solo necesita evaluar soluciones, sirve igual para mochila que para rutas que para calendarios. ACO incorpora estructura del problema (heurística local η, rastro sobre aristas): suele converger más rápido en problemas de rutas, y peor —o requiere rediseño— fuera de ellos.
• B&B es imbatible mientras llegue. Certificado, sin semillas, sin hiperparámetros que calibrar. La frontera práctica del TSP exacto con técnicas serias está en cientos-miles de nodos; nuestra cota casera llega mucho menos lejos, pero el principio es el mismo.

Reglas de decisión que resumen el módulo entero, en versión "lunes por la mañana en Rutalia":

• ¿La instancia es pequeña o el problema tiene estructura exacta explotable (PD pseudopolinómica como la mochila, relajaciones fuertes como en PLE)? → Método exacto (PD, B&B, solver de PLE). Es la única opción con certificado, y el certificado tiene valor de negocio: nadie renegocia una ruta que se demostró óptima.
• ¿Instancia grande, función objetivo "sucia" (penalizaciones raras, reglas de negocio, ventanas horarias) o el modelo cambia cada semana? → Metaheurística. El AG si el problema es heterogéneo o no tiene estructura de ruta; ACO si es construcción secuencial de caminos sobre un mapa de opciones. En ambos casos: varias semillas, historial, y una cota inferior aunque sea burda para saber cuánto dejas sobre la mesa.
• ¿Necesitas lo mejor de ambos? Híbridos: metaheurística para el incumbente inicial de un B&B (lo vimos en 02-03), o búsqueda local refinando al mejor individuo/hormiga. En la práctica industrial casi nada compite con un buen híbrido.
• Y siempre: primero un voraz. Cuesta minutos, da la línea base y a veces (mochila fraccionaria, sistemas canónicos) resulta que era óptimo. Las herramientas sofisticadas se justifican contra esa línea base, no contra el vacío.

• Olvidar la evaporación (o ponerla casi a cero). La feromona solo crece, la primera ruta decente se fosiliza y la colonia entera la repite. Es el fallo más común en implementaciones caseras: el algoritmo "converge" sospechosamente rápido y siempre a lo mismo.
• η al revés. La heurística debe premiar las aristas cortas: η = 1/distancia. Si usas la distancia directamente, las hormigas prefieren los tramos largos y el algoritmo funciona activamente mal. Si hay distancias 0 (dos paradas en el mismo portal), añade un épsilon.
• Elegir el máximo en vez de sortear. Sustituir la ruleta por max(candidatas) convierte la colonia en N copias del mismo voraz determinista: sin variedad no hay rastro que aprender. (Las variantes serias como ACS mezclan ambas cosas, pero con una probabilidad explícita.)
• Actualizar feromona a mitad de construcción cuando el esquema es de actualización global: mezcla las fases y hace el comportamiento irreproducible. Construyen todas, luego evapora, luego deposita.
• Comparar metaheurísticas con una sola semilla. Con dos métodos estocásticos, una ejecución de cada uno ordena monedas al aire. Distribuciones sobre 10-30 semillas, mismas instancias, mismo presupuesto de evaluaciones.
• Consejo: imprime la matriz τ (o un mapa de calor) cada 20 iteraciones. Ver cómo el rastro se concentra sobre las aristas de la ruta óptima — y detectar cuándo se concentra sobre las equivocadas — enseña más que cualquier descripción.

1. La regla de transición a mano. Una hormiga está en el depósito; quedan tres paradas: P (distancia 2, τ = 4), Q (distancia 4, τ = 1) y R (distancia 1, τ = 1). Con α = 1 y β = 1, calcula la probabilidad de elegir cada parada. Repite con α = 0 y con β = 0. Comenta qué "personalidad" muestra la hormiga en cada caso.

2. El papel de la evaporación. Ejecuta colonia_de_hormigas con ρ ∈ {0.0, 0.1, 0.5, 0.9} (10 semillas cada uno). Anota cuántas semillas alcanzan 35,22 km y en qué iteración media se alcanza el mejor resultado. Explica los dos extremos con el vocabulario de la lección.

3. Torneo a tres. Monta un banco de pruebas que ejecute sobre la instancia de Rutalia el AG de 02-04 y el ACO de esta lección con un presupuesto igualado (p. ej., 20.000 evaluaciones de ruta cada uno) y 20 semillas, y compare: mejor resultado, media y desviación. Añade la fila de B&B (determinista, de 02-03). ¿Reproduce tu experimento las conclusiones de la tabla de la lección?

Ejercicio 1. Con α = β = 1, el peso de cada candidata es τ · (1/d): P → 4 · (1/2) = 2; Q → 1 · (1/4) = 0,25; R → 1 · (1/1) = 1. Suma 3,25 → p(P) ≈ 0,615, p(Q) ≈ 0,077, p(R) ≈ 0,308. Con α = 0 (solo heurística): pesos 0,5 / 0,25 / 1 → p ≈ 0,286 / 0,143 / 0,571 — la hormiga es un vecino-más-cercano probabilístico y prefiere R, la más próxima. Con β = 0 (solo feromona): pesos 4 / 1 / 1 → p ≈ 0,667 / 0,167 / 0,167 — la hormiga es puro rebaño y sigue el rastro hacia P aunque haya opciones más cercanas. La regla completa negocia entre ambas personalidades.

Ejercicio 2. Patrón esperado: con ρ = 0.0 la feromona nunca se borra; los refuerzos de las primeras iteraciones (construidos casi al azar) dominan para siempre y varias semillas se estancan por encima del óptimo — fosilización. Con ρ = 0.1 mejora pero aún consolida lento los cambios de opinión. Con ρ = 0.5 (nuestro default), equilibrio: casi todas las semillas alcanzan 35,22 km en pocas decenas de iteraciones. Con ρ = 0.9 la colonia es amnésica: cada iteración casi borra lo aprendido, el rastro no acumula evidencia y el comportamiento se queda cerca del vecino-más-cercano aleatorio de la primera iteración; alcanzar el óptimo pasa a depender de la suerte. La evaporación es el mando exploración/explotación de ACO, igual que la mutación lo era en el AG.

Ejercicio 3. Esqueleto: fija evaluaciones = 20_000; para el AG eso es tam_poblacion × generaciones = 100 × 200; para ACO, n_hormigas × iteraciones × 1 construcción por hormiga → p. ej. 20 hormigas × 100 iteraciones = 2.000 construcciones (si quieres igualar más fino, cuenta cada construcción como N elecciones y ajusta). Ejecuta cada método con semilla = 0..19, guarda el mejor km de cada ejecución y calcula mínimo, media y desviación con statistics. Resultado esperado en esta instancia: ambos métodos alcanzan 35,22 km en la mayoría de semillas (la media de ACO suele ser igual o levemente mejor por su heurística local; el AG muestra algo más de varianza), y B&B aporta la única fila con la palabra "certificado". Si tus números difieren, no es un error: es la naturaleza estocástica que esta lección te ha enseñado a medir en lugar de a ignorar.

Cerramos el módulo de optimización con las tres familias frente a frente sobre el mismo problema. La colonia de hormigas añadió la última pieza: búsqueda por cooperación estigmérgica, donde la memoria colectiva vive en las aristas (feromona τ), la miopía útil la aporta la heurística local (η), la regla de transición con α y β negocia entre ambas, y la evaporación mantiene el aprendizaje revisable. Sobre el TSP de Rutalia, B&B certificó 35,22 km, y tanto el genético como las hormigas los alcanzaron sin certificado — empate en la instancia pequeña que elegimos para poder corregir el examen, con la verdadera divergencia reservada para las instancias grandes donde solo las metaheurísticas siguen en pie. El módulo entero cabe en una frase: formular con precisión (02-01), respetar la explosión combinatoria (02-02), exigir el óptimo mientras sea pagable (02-03) y negociar con inteligencia cuando no lo sea (02-04, 02-05). Queda una deuda deliberada: llevamos cinco lecciones hablando de rutas, tramos, puntos conectados y "aristas" — incluso la feromona vivía sobre ellas — sin definir formalmente qué es esa estructura. Esa estructura es el grafo, y es la protagonista del módulo 3: aprenderemos a representarlos con rigor (03-01), a recorrerlos (03-02) y a explotar sus algoritmos clásicos — allí nos esperan las semillas que plantamos en 01-04: el heap que impulsará Dijkstra en los caminos mínimos (03-03) y el union-find que sostendrá Kruskal en los árboles de expansión (03-04). Las rutas de Rutalia están a punto de convertirse en matemáticas de primera clase.