Els algorismes genètics de la lliçó anterior cercaven mitjançant herència: els bons individus es reprodueixen i els seus trets es propaguen. L'optimització per colònia de formigues (ACO, Ant Colony Optimization) cerca mitjançant una cosa més estranya i més elegant: la cooperació indirecta. Cap agent no hereta res de cap altre; simplement, cadascun deixa marques a l'entorn que esbiaixen les decisions dels següents. És una idea copiada literalment de les formigues reals, i resulta especialment natural per als problemes de rutes que obsessionen Rutalia: les marques viuen exactament on viu el problema, als trams entre parades. En aquesta lliçó formalitzarem el mecanisme (feromones, probabilitats de transició, evaporació), l'implementarem complet en Python sobre la mateixa instància de 10 punts de les tres lliçons anteriors, i tancarem el mòdul amb el que vam prometre: la comparació experimental de les tres aproximacions al TSP — branch and bound, genètic i colònia de formigues — i una guia de quan triar cadascuna.

1. La inspiració: formigues, feromones i estigmèrgia
2. Anatomia d'ACO: què manté i com decideix
3. La probabilitat de transició: α i β
4. Evaporació i dipòsit de feromones
5. Implementació completa: ACO per al TSP de Rutalia
6. Ajust de paràmetres
7. Comparació experimental: B&B vs genètic vs ACO
8. Quan triar cada aproximació

L'experiment clàssic (Deneubourg, anys 80, amb formigues argentines reals): es connecta un formiguer a una font de menjar mitjançant dos ponts, un de curt i un de llarg. Al principi les formigues trien a l'atzar, meitat i meitat. Al cap d'una estona, gairebé totes usen el pont curt. Cap formiga no ha comparat els ponts; cap no sap ni tan sols que n'hi ha dos. El mecanisme:

1. Cada formiga diposita feromona (un senyal químic) en caminar.
2. Les formigues prefereixen, probabilísticament, els camins amb més feromona.
3. Les que agafen el pont curt van i tornen abans, així que el pont curt acumula feromona més de pressa.
4. Més feromona atrau més formigues, que dipositen més feromona: retroalimentació positiva.
5. La feromona s'evapora, esborrant a poc a poc els rastres que no es reforcen.

D'aquesta coordinació a través de modificacions de l'entorn — sense comunicació directa, sense cap, sense mapa — se'n diu estigmèrgia. El que la converteix en algorisme és una observació: la feromona funciona com una memòria col·lectiva de qualitat distribuïda sobre les arestes del problema, i l'evaporació com un oblit controlat que evita fixar-se en la primera solució mediocre. Marco Dorigo va formalitzar això el 1992 com a mètode d'optimització, amb el TSP com a primer camp de proves — el mateix problema, gairebé la mateixa escala, que la nostra ruta de Rutalia.

Traducció a ingredients computacionals, en paral·lel amb l'AG per fixar idees:

La diferència filosòfica: l'AG recombina solucions senceres; ACO aprèn, aresta per aresta, quines decisions locals solen aparèixer a les bones solucions. Per això ACO brilla en problemes on la solució és una seqüència de decisions sobre un mapa d'opcions — rutes, planificació, assignacions encadenades.

Una formiga situada al punt i decideix la seva parada següent j entre les no visitades, a l'atzar però amb biaix. La probabilitat de triar j és proporcional a:

on:

• τ(i,j) és la feromona de l'aresta — la memòria col·lectiva: "per aquí van passar bones rutes".
• η(i,j) és la informació heurística local, per al TSP η = 1 / distancia(i,j) — la miopia útil: "aquesta parada és a prop".
• α i β són exponents que graduen quant pesa cada font.

Els dos extrems aclareixen el paper de cada exponent:

• Amb α = 0, la feromona s'ignora: cada formiga és un veí més proper probabilístic, sense aprenentatge col·lectiu. Recordem de 02-02 que el veí més proper pur donava 43,1 km (+22 %): aquesta és més o menys la qualitat de la primera iteració d'ACO, abans que existeixi rastre.
• Amb β = 0, la distància s'ignora: les primeres rutes (aleatòries) marquen feromona, les següents les imiten, i la colònia s'autoconfirma sobre rutes dolentes — convergència prematura de llibre.

L'art és al mig: típicament α = 1 i β entre 2 i 5 (l'heurística mana al principi, quan la feromona és uniforme; el rastre va prenent el control a mesura que acumula evidència).

Un cop totes les formigues han construït les seves rutes, la matriu τ s'actualitza en dos passos:

1. Evaporació — tota aresta perd una fracció ρ de la seva feromona:

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

   Sense evaporació, els errors del passat mai no s'esborren i la primera ruta raonable es fossilitza. Amb ρ típic de 0,3–0,5, un rastre no reforçat s'extingeix en poques iteracions.

2. Dipòsit — cada formiga afegeix feromona a les arestes de la seva ruta, en quantitat inversament proporcional a la longitud:

   τ(i,j) ← τ(i,j) + Q / L per a cada aresta (i,j) d'una ruta de longitud L

   Les rutes curtes dipositen més per aresta: la retroalimentació positiva del pont de Deneubourg, en una línia de codi. Q és només una constant d'escala.

Aquest és l'esquema original (Ant System). Les variants que dominen la literatura afinen just aquí: elitista (la millor ruta històrica diposita extra), MAX-MIN (τ fitada entre un mínim i un màxim per forçar exploració), ACS (evaporació local durant la construcció). Ens quedem amb l'esquema clàssic, que ja exhibeix tot el comportament interessant.

Sobre la instància canònica del mòdul (requereix NOMS, D i longitud_ruta de 02-02; òptim conegut: 35,22 km):

Lectura guiada:

• random.choices(..., weights=pesos) implementa la ruleta de transició: no triem la millor candidata (això seria un voraç) sinó una a l'atzar amb probabilitats esbiaixades. Aquesta resta d'atzar és el que manté viva l'exploració.
• El cost per iteració és n_formigues × N decisions, cadascuna amb O(N) candidates: Θ(formigues · N²). Amb 20 formigues i 100 iteracions són 20 × 100 = 2.000 rutes construïdes — pressupost semblant al de l'AG (20.000 avaluacions, però les seves eren més barates: només mesurar, no construir).
• Guardem el millor global (millor_km) a part de la matriu τ: la colònia pot allunyar-se temporalment de la millor ruta trobada (i està bé que explori), però el resultat que lliurem mai no empitjora.
• En la nostra execució, ACO assoleix els 35,22 km òptims, típicament en les primeres desenes d'iteracions: l'historial mostra la mecànica esperada — primeres iteracions al voltant de 40-44 km (formigues gairebé voraces sobre feromona uniforme) i caiguda ràpida a mesura que el rastre acumula evidència.

El diagnòstic es fa igual que a l'AG: amb l'historial i amb diverses llavors. Si totes les formigues construeixen rutes gairebé idèntiques a la iteració 15, hi ha convergència prematura (apuja ρ o abaixa α); si el millor global continua baixant a la darrera iteració, falten iteracions.

És l'hora de tancar el que vam obrir a 02-02. Mateixa instància (10 punts, dipòsit inclòs), mateix maquinari, execucions amb les configuracions de cada lliçó:

Lectures honestes d'aquesta taula:

• En aquesta instància tots empaten a 35,22 km. No és casualitat ni mèrit de les metaheurístiques: 10 nodes és territori còmode per a qualsevol. La vam triar precisament per tenir la resposta correcta i poder verificar que cada mètode l'assoleix. La taula interessant és la fila "amb 100 parades": allà els exactes desapareixen i només queda comparar metaheurístiques entre si — contra fites inferiors, ja que l'òptim és incognoscible.
• La diferència entre AG i ACO no és la qualitat aquí, sinó el caràcter. L'AG és agnòstic: només necessita avaluar solucions, serveix igual per a motxilla que per a rutes que per a calendaris. ACO incorpora estructura del problema (heurística local η, rastre sobre arestes): sol convergir més ràpid en problemes de rutes, i pitjor — o requereix redisseny — fora d'ells.
• B&B és imbatible mentre arribi. Certificat, sense llavors, sense hiperparàmetres a calibrar. La frontera pràctica del TSP exacte amb tècniques serioses és en centenars-milers de nodes; la nostra fita casolana arriba molt menys lluny, però el principi és el mateix.

Regles de decisió que resumeixen el mòdul sencer, en versió "dilluns al matí a Rutalia":

• La instància és petita o el problema té estructura exacta explotable (PD pseudopolinòmica com la motxilla, relaxacions fortes com a PLE)? → Mètode exacte (PD, B&B, solver de PLE). És l'única opció amb certificat, i el certificat té valor de negoci: ningú no renegocia una ruta que es va demostrar òptima.
• Instància gran, funció objectiu "bruta" (penalitzacions rares, regles de negoci, finestres horàries) o el model canvia cada setmana? → Metaheurística. L'AG si el problema és heterogeni o no té estructura de ruta; ACO si és construcció seqüencial de camins sobre un mapa d'opcions. En tots dos casos: diverses llavors, historial, i una fita inferior encara que sigui grollera per saber quant deixes sobre la taula.
• Necessites el millor de tots dos? Híbrids: metaheurística per a l'incumbent inicial d'un B&B (ho vam veure a 02-03), o cerca local refinant el millor individu/formiga. A la pràctica industrial gairebé res no competeix amb un bon híbrid.
• I sempre: primer un voraç. Costa minuts, dona la línia base i de vegades (motxilla fraccionària, sistemes canònics) resulta que era òptim. Les eines sofisticades es justifiquen contra aquesta línia base, no contra el buit.

• Oblidar l'evaporació (o posar-la gairebé a zero). La feromona només creix, la primera ruta decent es fossilitza i la colònia sencera la repeteix. És l'error més comú en implementacions casolanes: l'algorisme "convergeix" sospitosament ràpid i sempre al mateix.
• η a l'inrevés. L'heurística ha de premiar les arestes curtes: η = 1/distancia. Si uses la distància directament, les formigues prefereixen els trams llargs i l'algorisme funciona activament malament. Si hi ha distàncies 0 (dues parades al mateix portal), afegeix un èpsilon.
• Triar el màxim en lloc de sortejar. Substituir la ruleta per max(candidates) converteix la colònia en N còpies del mateix voraç determinista: sense varietat no hi ha rastre a aprendre. (Les variants serioses com ACS barregen totes dues coses, però amb una probabilitat explícita.)
• Actualitzar feromona a mitja construcció quan l'esquema és d'actualització global: barreja les fases i fa el comportament irreproduïble. Construeixen totes, després evapora, després diposita.
• Comparar metaheurístiques amb una sola llavor. Amb dos mètodes estocàstics, una execució de cadascun ordena monedes a l'aire. Distribucions sobre 10-30 llavors, mateixes instàncies, mateix pressupost d'avaluacions.
• Consell: imprimeix la matriu τ (o un mapa de calor) cada 20 iteracions. Veure com el rastre es concentra sobre les arestes de la ruta òptima — i detectar quan es concentra sobre les equivocades — ensenya més que qualsevol descripció.

1. La regla de transició a mà. Una formiga és al dipòsit; queden tres parades: P (distància 2, τ = 4), Q (distància 4, τ = 1) i R (distància 1, τ = 1). Amb α = 1 i β = 1, calcula la probabilitat de triar cada parada. Repeteix amb α = 0 i amb β = 0. Comenta quina "personalitat" mostra la formiga en cada cas.

2. El paper de l'evaporació. Executa colonia_de_formigues amb ρ ∈ {0.0, 0.1, 0.5, 0.9} (10 llavors cadascun). Anota quantes llavors assoleixen 35,22 km i en quina iteració mitjana s'assoleix el millor resultat. Explica els dos extrems amb el vocabulari de la lliçó.

3. Torneig a tres. Munta un banc de proves que executi sobre la instància de Rutalia l'AG de 02-04 i l'ACO d'aquesta lliçó amb un pressupost igualat (p. ex., 20.000 avaluacions de ruta cadascun) i 20 llavors, i compari: millor resultat, mitjana i desviació. Afegeix la fila de B&B (determinista, de 02-03). Reprodueix el teu experiment les conclusions de la taula de la lliçó?

Exercici 1. Amb α = β = 1, el pes de cada candidata és τ · (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. Amb α = 0 (només heurística): pesos 0,5 / 0,25 / 1 → p ≈ 0,286 / 0,143 / 0,571 — la formiga és un veí-més-proper probabilístic i prefereix R, la més pròxima. Amb β = 0 (només feromona): pesos 4 / 1 / 1 → p ≈ 0,667 / 0,167 / 0,167 — la formiga és pur ramat i segueix el rastre cap a P encara que hi hagi opcions més properes. La regla completa negocia entre totes dues personalitats.

Exercici 2. Patró esperat: amb ρ = 0.0 la feromona mai no s'esborra; els reforços de les primeres iteracions (construïts gairebé a l'atzar) dominen per sempre i diverses llavors s'estanquen per sobre de l'òptim — fossilització. Amb ρ = 0.1 millora però encara consolida lentament els canvis d'opinió. Amb ρ = 0.5 (el nostre default), equilibri: gairebé totes les llavors assoleixen 35,22 km en poques desenes d'iteracions. Amb ρ = 0.9 la colònia és amnèsica: cada iteració gairebé esborra el que s'ha après, el rastre no acumula evidència i el comportament es queda a prop del veí-més-proper aleatori de la primera iteració; assolir l'òptim passa a dependre de la sort. L'evaporació és el comandament exploració/explotació d'ACO, igual que la mutació ho era a l'AG.

Exercici 3. Esquelet: fixa avaluacions = 20_000; per a l'AG això és mida_poblacio × generacions = 100 × 200; per a ACO, n_formigues × iteracions × 1 construcció per formiga → p. ex. 20 formigues × 100 iteracions = 2.000 construccions (si vols igualar més fi, compta cada construcció com N eleccions i ajusta). Executa cada mètode amb llavor = 0..19, guarda el millor km de cada execució i calcula mínim, mitjana i desviació amb statistics. Resultat esperat en aquesta instància: tots dos mètodes assoleixen 35,22 km en la majoria de llavors (la mitjana d'ACO sol ser igual o lleument millor per la seva heurística local; l'AG mostra una mica més de variància), i B&B aporta l'única fila amb la paraula "certificat". Si els teus números difereixen, no és un error: és la naturalesa estocàstica que aquesta lliçó t'ha ensenyat a mesurar en lloc d'ignorar.

Tanquem el mòdul d'optimització amb les tres famílies cara a cara sobre el mateix problema. La colònia de formigues ha afegit la darrera peça: cerca per cooperació estigmèrgica, on la memòria col·lectiva viu a les arestes (feromona τ), la miopia útil l'aporta l'heurística local (η), la regla de transició amb α i β negocia entre totes dues, i l'evaporació manté l'aprenentatge revisable. Sobre el TSP de Rutalia, B&B va certificar 35,22 km, i tant el genètic com les formigues els van assolir sense certificat — empat en la instància petita que vam triar per poder corregir l'examen, amb la veritable divergència reservada per a les instàncies grans on només les metaheurístiques continuen dempeus. El mòdul sencer cap en una frase: formular amb precisió (02-01), respectar l'explosió combinatòria (02-02), exigir l'òptim mentre sigui pagable (02-03) i negociar amb intel·ligència quan no ho sigui (02-04, 02-05). Queda un deute deliberat: portem cinc lliçons parlant de rutes, trams, punts connectats i "arestes" — fins i tot la feromona hi vivia — sense definir formalment què és aquesta estructura. Aquesta estructura és el graf, i és la protagonista del mòdul 3: aprendrem a representar-los amb rigor (03-01), a recórrer-los (03-02) i a explotar-ne els algorismes clàssics — allà ens esperen les llavors que vam plantar a 01-04: el heap que impulsarà Dijkstra en els camins mínims (03-03) i l'union-find que sostindrà Kruskal en els arbres d'expansió (03-04). Les rutes de Rutalia són a punt de convertir-se en matemàtiques de primera classe.