Osserva una vera metaeuristica di Ottimizzazione a Colonia di Formiche far evolvere dal vivo le rotte dei droni di consegna, con un autentico rinforzo delle tracce di feromone che converge verso percorsi multi-tappa più brevi nel corso di colonie successive.
Questa simulazione mette al lavoro un vero algoritmo di Ottimizzazione a Colonia di Formiche (ACO) su un problema di instradamento multi-tappa per droni di consegna — un drone deve visitare ogni punto di consegna esattamente una volta e tornare alla base, il classico Problema del Commesso Viaggiatore. Invece di scriptare un percorso, la pagina mantiene una vera matrice di feromone τ su ogni coppia di punti di consegna. In ogni colonia, ogni formica simulata costruisce un tour completo scegliendo ripetutamente la sua prossima tappa non ancora visitata con probabilità proporzionale a τ(i,j)α · η(i,j)β, dove η(i,j) = 1/distanza(i,j) è la desiderabilità euristica di un salto breve. Una volta che ogni formica della colonia ha completato il proprio tour, il feromone evapora di un fattore (1 − ρ) e ogni formica deposita nuovo feromone proporzionale a Q / L sugli archi del percorso che ha costruito — così i percorsi più brevi rinforzano i propri archi molto più fortemente di quelli lunghi.
Eseguila per un numero sufficiente di colonie e la mappa delle tracce si affina visibilmente: gli archi deboli e usati raramente svaniscono fino a scomparire, mentre una manciata di archi — quelli che continuano a comparire nei tour più brevi — diventano più luminosi, e la lunghezza del percorso migliore conosciuto (tracciata nel grafico dal vivo) continua a diminuire progressivamente. Puoi regolare dal vivo il numero di punti di consegna, il numero di formiche per colonia e il tasso di evaporazione ρ, insieme agli esponenti del peso del feromone α e del peso della distanza β che controllano quanto fortemente le formiche si fidano dell'esperienza della colonia rispetto alla distanza pura. Niente qui è scriptato o precotto — ogni colonia deriva realmente i propri percorsi dallo stato attuale del feromone e da decisioni casuali delle formiche, quindi ricominciare con una nuova mappa o parametri diversi produce ogni volta una curva di convergenza diversa.
Cos'è l'Ottimizzazione a Colonia di Formiche e quale problema risolve qui?
L'Ottimizzazione a Colonia di Formiche (ACO) è una metaeuristica ispirata al modo in cui le formiche reali trovano percorsi brevi tra il nido e il cibo usando tracce di feromone. In questa simulazione risolve un problema di instradamento di consegne multi-tappa: un drone deve visitare ogni punto di consegna esattamente una volta e tornare alla base, che è il classico Problema del Commesso Viaggiatore (TSP). Il TSP è NP-difficile, quindi per qualsiasi cosa oltre una manciata di tappe è impraticabile controllare ogni possibile ordinamento. L'ACO esegue invece molte formiche simulate che costruiscono percorsi candidati in modo probabilistico, rinforzando gli archi che tendono a comparire nei percorsi brevi, così la popolazione di percorsi migliora nel corso di colonie successive senza mai dimostrare l'ottimalità.
Come decide la regola di probabilità di transizione dell'ACO dove va ogni formica successivamente?
A ogni passo, una formica che si trova nel punto di consegna i sceglie la sua prossima tappa non visitata j con probabilità proporzionale a [τ(i,j)]^α × [η(i,j)]^β, dove τ(i,j) è il livello di feromone sull'arco (i,j) ed η(i,j) = 1/distanza(i,j) è la desiderabilità euristica — i punti più vicini appaiono più attraenti. α controlla quanto fortemente la formica segue l'esperienza accumulata dalla colonia (feromone), mentre β controlla quanto fortemente segue la pura distanza greedy. La formica effettua quindi un'estrazione casuale ponderata (a ruota della fortuna) tra tutti i candidati non visitati usando questi punteggi combinati, quindi solitamente — ma non sempre — sceglie un arco promettente, il che mantiene la colonia in fase di esplorazione.
Perché il feromone evapora, e cosa controlla il tasso di evaporazione ρ?
Dopo che ogni colonia completa i suoi tour, tutti i valori di feromone vengono moltiplicati per (1 − ρ) prima che vengano aggiunti nuovi depositi. Senza evaporazione, il feromone si accumulerebbe solamente, e qualsiasi arco fosse stato fortunato all'inizio dominerebbe per sempre — intrappolando la ricerca in una soluzione mediocre. L'evaporazione permette alle tracce deboli o stantie di svanire in modo che la colonia possa continuare a esplorare percorsi alternativi. Un ρ alto dimentica velocemente la storia ed esplora di più ma converge più lentamente e in modo più rumoroso; un ρ basso ricorda più a lungo e converge più velocemente ma rischia di bloccarsi su un percorso precoce e subottimale (convergenza prematura).
Dopo l'evaporazione, ogni formica della colonia deposita feromone di intensità Q / L su ogni arco del tour che ha costruito, dove L è la lunghezza totale del percorso di quella formica e Q è una costante fissa. Poiché il deposito è inversamente proporzionale alla lunghezza, una formica che ha trovato un percorso breve rinforza i suoi archi molto più fortemente di una formica che ne ha trovato uno lungo e inefficiente. Nel corso di molte colonie, questo rinforzo differenziale è ciò che trasforma una ricerca puramente casuale in una che concentra il feromone — e quindi il traffico futuro delle formiche — sugli archi che compaiono ripetutamente nei percorsi brevi.
Impostare α = 0 fa sì che le formiche ignorino completamente il feromone e si comportino come un'euristica greedy in stile vicino-più-prossimo guidata solo da η (distanza), quindi non si forma memoria di colonia e c'è poco miglioramento nel tempo. Impostare β = 0 fa sì che le formiche ignorino completamente la distanza e seguano solo il feromone, il che può far sì che l'intera colonia rinforzi molto rapidamente un percorso precoce, forse scadente (stagnazione). Il classico equilibrio usa un α moderato (circa 1) con un β più forte (circa 2–5) in modo che l'esplorazione iniziale sia consapevole della distanza, mentre il feromone permette comunque a una buona struttura di consolidarsi nel corso delle colonie.
Il grafico traccia la lunghezza del percorso migliore trovato finora, che per definizione non può mai peggiorare — è un minimo corrente. Si stabilizza ogni volta che nessuna formica nelle colonie più recenti è riuscita a battere il percorso campione attuale, il che è previsto: man mano che il feromone si concentra su archi buoni, la maggior parte delle formiche converge verso tour simili e i miglioramenti realmente nuovi diventano più rari. Lunghi periodi di stabilità di solito significano che la colonia si è assestata vicino a un ottimo locale per i parametri correnti; aumentare il tasso di evaporazione, il numero di formiche o l'esponente di esplorazione β può a volte smuoverla per trovare un percorso più breve.
Un risolutore esatto (branch-and-bound, programmazione dinamica o programmazione a numeri interi) può garantire il vero percorso più breve possibile, ma il suo tempo di esecuzione cresce in modo esplosivo con il numero di tappe — la programmazione dinamica richiede già circa n²·2ⁿ operazioni, il che diventa infattibile ben prima di n = 30. L'ACO rinuncia alla garanzia di ottimalità in cambio della scalabilità: produce percorsi buoni, spesso quasi ottimali, per istanze molto più grandi con una quantità fissa di calcolo, che è esattamente il compromesso che i sistemi reali di consegna e logistica fanno quando instradano decine o centinaia di tappe.