Ispirazione Biologica

In natura, le formiche sono in grado di trovare i percorsi più brevi tra il nido e le fonti di cibo depositando e seguendo tracce di feromoni. Durante il tragitto, le formiche rilasciano feromoni sul terreno, creando una traccia chimica che altre formiche tenderanno a seguire. La probabilità che una formica scelga un determinato percorso aumenta con l'intensità della traccia di feromone su quel percorso. Questo meccanismo porta a un ciclo di feedback positivo: i percorsi con più feromone vengono scelti più frequentemente, il che a sua volta aumenta la concentrazione di feromone su quei percorsi. Nel tempo, questo comportamento collettivo consente alla colonia di scoprire soluzioni ottimali o quasi ottimali a problemi complessi in modo decentralizzato.

Esempio: Processo di Aggiornamento dei Feromoni

# Pseudocode for updating pheromone trails in a simple graph

# Assume pheromone is a dictionary: pheromone[(i, j)] gives the pheromone value on edge (i, j)
# delta_pheromone is a dictionary: delta_pheromone[(i, j)] accumulates pheromone deposited by all ants

rho = 0.5  # Evaporation rate (0 < rho < 1)
for (i, j) in pheromone:
    # Evaporation: reduce existing pheromone
    pheromone[(i, j)] *= (1 - rho)
    # Deposit: add new pheromone from this iteration
    pheromone[(i, j)] += delta_pheromone.get((i, j), 0.0)

Applicazioni di ACO: Il Problema del Commesso Viaggiatore

L'Ottimizzazione tramite Colonia di Formiche è particolarmente efficace per risolvere problemi di ottimizzazione combinatoria, in cui l'obiettivo è trovare il miglior ordinamento o selezione da un insieme finito. Un esempio classico è il problema del commesso viaggiatore (TSP), dove è necessario trovare il percorso più breve possibile che visiti un insieme di città esattamente una volta e ritorni alla città di origine. In ACO, ogni formica artificiale costruisce un tour scegliendo probabilisticamente la prossima città da visitare, influenzata sia dall'intensità del feromone sia dalla distanza verso ciascuna città non ancora visitata. Dopo che tutte le formiche hanno completato i loro tour, le tracce di feromone vengono aggiornate per rafforzare i percorsi più brevi ed efficienti, mentre i percorsi meno ottimali perdono feromone tramite evaporazione. Questo processo iterativo consente ad ACO di esplorare efficacemente un ampio spazio di ricerca e convergere verso soluzioni di alta qualità per compiti complessi di instradamento e schedulazione.