Come fanno le formiche a trovare la strada più corta
Nessuna formica misura niente, e nessuna riesce a vedere l'intero percorso. La colonia converge lo stesso sulla via più corta, e lo fa con una sostanza che evapora.
Una traccia che svanisce, e perché è proprio quello il punto
Livello Base — linguaggio semplice, senza matematica
Guarda delle formiche che trovano del cibo e nel giro di un'ora c'è una linea scura e ordinata di formiche che ci corrono dritte. Sembra organizzato. Non lo è: nessuna formica ha deciso quel percorso, e nessuna riesce a vederne entrambe le estremità. Quello che è successo davvero è più semplice e molto più strano.
Una formica che trova del cibo porta una briciola a casa e sgocciola dietro di sé una traccia odorosa per tutto il tragitto. Un'altra formica che gira lì vicino sente quell'odore e tende a seguirlo invece di vagare a caso, e se arriva al cibo torna indietro lasciando la sua traccia. Quindi un percorso che viene usato diventa più forte, e un percorso più forte viene usato di più. Questo anello è tutto il meccanismo.
Ma quello da solo bloccherebbe per sempre il primo percorso trovato. Il motivo per cui la colonia finisce su quello più corto è un dettaglio che sembra un difetto: l'odore evapora. Su un percorso corto le formiche completano il giro in fretta e rinfrescano l'odore spesso. Su un percorso lungo l'odore ha più tempo per svanire fra un passaggio e l'altro. La via corta si accumula; quella lunga si disperde.
Nessuno ha misurato niente. La misura l'ha fatta il tempo, e l'evaporazione l'ha trasformata in un numero. Premi il pulsante per far cadere una roccia sulla pista vincente e guarda la colonia esitare, sbandare, e poi trovare la via attorno - che è l'altro vantaggio di un sistema senza piano: non c'è nessun piano da rompere.
Da sapere
- Se l'odore non evaporasse, la colonia resterebbe per sempre incollata al primo percorso trovato. Il dimenticare non è un limite del sistema, è la parte che lo fa funzionare.
- Una singola formica ha circa 250.000 neuroni e nessuna idea di che cosa stia facendo la colonia. La ricerca del percorso esiste solo a livello di gruppo.
- Nel classico esperimento del doppio ponte del 1989, formiche argentine a cui venivano offerti due percorsi di lunghezza diversa convergevano su quello corto in pochi minuti - e quando erano della stessa lunghezza ne sceglievano comunque uno, a caso.
Stigmergia, retroazione positiva e ottimizzazione a colonia di formiche
Livello Studente — le equazioni principali
Il concetto organizzatore è la stigmergia: coordinamento attraverso la modifica dell'ambiente condiviso invece che per comunicazione diretta. Nessuna formica manda un messaggio a un'altra formica. Cambia il mondo - deposita una sostanza chimica - e il mondo cambiato cambia quello che farà la formica successiva. Questo disaccoppia del tutto gli agenti: non hanno bisogno di identità, di memoria l'uno dell'altro né di simultaneità.
La dinamica è una competizione fra due retroazioni. Quella positiva è autocatalitica: il ritmo di deposito su un percorso cresce col traffico che ci passa, e il traffico cresce con la concentrazione, dando un rinforzo esponenziale. Quella negativa è l'evaporazione, un semplice decadimento esponenziale \(\tau \leftarrow (1-\rho)\tau\). La lunghezza del percorso entra solo attraverso i tempi: un percorso più corto ha un giro più breve, quindi viene rinforzato più di frequente, e con l'evaporazione che va a ritmo costante quella differenza di frequenza diventa una differenza di concentrazione.
L'esperimento del doppio ponte di Deneubourg lo ha reso quantitativo. Le formiche argentine a un bivio scelgono il ramo A con probabilità \(p_A = (k+\tau_A)^n / [(k+\tau_A)^n + (k+\tau_B)^n]\), con \(n \approx 2\). La non linearità conta: con \(n > 1\) un piccolo vantaggio di concentrazione si traduce in un grande vantaggio di probabilità, ed è questo che rompe la simmetria in modo deciso invece di lasciare la colonia divisa.
Dorigo ha trasformato questo in ottimizzazione a colonia di formiche, una metaeuristica in cui formiche artificiali costruiscono soluzioni a problemi combinatori - commesso viaggiatore, instradamento di veicoli, instradamento di rete - scegliendo componenti con probabilità pesata dal feromone e da un'euristica specifica del problema, e poi depositando feromone in proporzione alla qualità della soluzione. È competitiva sui problemi in cui il panorama dei costi cambia nel tempo, proprio perché un sistema con evaporazione dimentica l'informazione vecchia invece di impegnarsi su di essa.
Formule chiave
| Scelta del ramo | \(p_A = \dfrac{(k+\tau_A)^n}{(k+\tau_A)^n+(k+\tau_B)^n}\) | n ≈ 2 |
|---|---|---|
| Evaporazione | \(\tau \leftarrow (1-\rho)\,\tau\) | |
| Deposito | \(\Delta\tau = \dfrac{Q}{L}\) | percorso più corto, più per giro |
| Transizione ACO | \(p_{ij} = \dfrac{\tau_{ij}^{\alpha}\eta_{ij}^{\beta}}{\sum_{l}\tau_{il}^{\alpha}\eta_{il}^{\beta}}\) | |
Da sapere
- L'esponente di scelta del ramo, circa 2, è ciò che rende decisa la decisione. Con una regola lineare la colonia dividerebbe il traffico invece di impegnarsi sul percorso più corto.
- L'ottimizzazione a colonia di formiche è usata in instradamento reale di veicoli e di telecomunicazioni, e il suo vantaggio sta nei problemi dinamici, dove l'evaporazione permette al sistema di dimenticare una rotta che ha smesso di essere buona.
- Le formiche legionarie costruiscono autostrade a tre corsie col traffico in uscita sui lati e le formiche cariche di ritorno al centro, cosa che emerge da semplici regole di svolta e non da un codice della strada.
Rottura di simmetria, prove di convergenza e i limiti dell'analogia
Livello Esperto — profondità matematica completa
01La rottura di simmetria come biforcazione
Con due rami uguali le equazioni di campo medio hanno un punto fisso simmetrico a feromone pari. La sua stabilità dipende dalla non linearità: per \(n > 1\) lo stato simmetrico perde stabilità sopra una densità critica di traffico in una biforcazione a forcone, e la colonia si impegna su un ramo scelto dalla fluttuazione. Sotto quella densità lo stato simmetrico è stabile e il traffico si divide davvero. Che una colonia scelga o divida non è quindi una proprietà delle formiche ma del ritmo di flusso, il che è verificabile ed è stato confermato.
02Che cosa viene davvero ottimizzato
Chiamarla ottimizzazione del cammino più corto esagera. Il meccanismo è il rinforzo di ciò che viene rinforzato più spesso, e la lunghezza del percorso è solo una delle cose che influenzano il tempo di percorrenza. Pendenza, superficie, congestione e pericolo entrano allo stesso modo, il che significa che la colonia ottimizza la percorribilità pesata nel tempo, non la distanza. Esperimenti con una via lunga e veloce contro una corta e lenta confermano che la colonia prende quella veloce. È un risultato più forte dell'inquadramento abituale, perché le formiche non hanno mai avuto accesso alla distanza.
03Convergenza, e che cosa si può dimostrare
Per le varianti ACO con un limite inferiore sul feromone, come MAX-MIN Ant System, si può dimostrare che la probabilità di trovare la soluzione ottima tende a uno al tendere delle iterazioni all'infinito, e che l'algoritmo converge in valore a quella soluzione. È il limite inferiore a far funzionare la dimostrazione: senza un pavimento, la convergenza prematura può portare a zero la probabilità di qualche componente e rendere l'ottimo irraggiungibile. È un raro caso di metaeuristica bioispirata con una vera teoria della convergenza e non solo risultati empirici.
04Dove l'analogia si rompe
Le colonie reali usano feromoni multipli con volatilità e significati diversi, memoria privata del percorso che può scavalcare del tutto la traccia, corsa in tandem in cui una formica guida fisicamente un'altra, e variabilità individuale nella reattività che tiene una riserva di esploratrici mentre la maggioranza sfrutta. Alcune specie non usano quasi per niente le tracce. Il modello a feromone unico è la caricatura di una strategia di un sottoinsieme di specie, ed è la caricatura a essere stata ingegnerizzata, il che è un esito ragionevole ma non è un'affermazione sulle formiche.
05La lezione generale sul calcolo distribuito
L'affermazione interessante riguarda il calcolo, non gli insetti. La colonia risolve un problema globale con agenti che non hanno informazione globale, né indirizzi, né sincronizzazione, né garanzie di affidabilità, usando un mezzo condiviso che decade. Il decadimento è l'ingrediente essenziale: limita la memoria, scarta automaticamente l'informazione vecchia e rende il sistema adattivo senza che nessuno decida di adattarsi. Quella combinazione - regole locali, ambiente condiviso modificabile, dimenticanza - è lo schema di progetto, e ricompare nei protocolli di instradamento, nel bilanciamento di carico e nell'apprendimento per rinforzo con sconto, dove il fattore di sconto gioca esattamente il ruolo dell'evaporazione.
Formule chiave
| Dinamica di campo medio | \(\dot\tau_A = \phi\,p_A(\tau) \dfrac{Q}{L_A} - \rho\tau_A\) | |
|---|---|---|
| Biforcazione | \(n>1 \Rightarrow \text{stato simmetrico instabile sopra } \phi_c\) | |
| Limite MAX-MIN | \(\tau_{\min} \le \tau_{ij} \le \tau_{\max}\) | ciò che rende dimostrabile la convergenza |
| Analogia con lo sconto | \(\tau \leftarrow (1-\rho)\tau \;\longleftrightarrow\; \gamma^{t}\) | |
Da sapere
- Che una colonia si impegni su un ramo o divida il traffico dipende dal ritmo di flusso, attraverso una biforcazione a forcone. Le stesse formiche fanno cose diverse a densità diverse.
- Offerta una via lunga e veloce contro una corta e lenta, le colonie prendono quella veloce. Non hanno mai avuto accesso alla distanza, solo al tempo di andata e ritorno.
- MAX-MIN Ant System ha una vera dimostrazione di convergenza, e funziona perché il feromone ha un pavimento. Senza quel limite inferiore la convergenza prematura può rendere irraggiungibile l'ottimo.