Biologisk inspiration

I naturen er myrer i stand til at finde de korteste ruter mellem deres bo og fødekilder ved at lægge og følge feromonspor. Når myrer bevæger sig, afsætter de feromoner på jorden, hvilket skaber et kemisk spor, som andre myrer sandsynligvis vil følge. Sandsynligheden for, at en myre vælger en bestemt rute, øges med styrken af feromonsporet på denne rute. Denne mekanisme fører til en positiv feedback-loop: ruter med mere feromon vælges hyppigere, hvilket igen øger feromonkoncentrationen på disse ruter. Over tid gør denne kollektive adfærd det muligt for kolonien at finde optimale eller næsten optimale løsninger på komplekse problemer på en decentraliseret måde.

Eksempel: Feromonopdateringsproces

# 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)

Anvendelser af ACO: Problemet med den rejsende sælger

Ant Colony Optimization er særligt effektiv til løsning af kombinatoriske optimeringsproblemer, hvor målet er at finde den bedste rækkefølge eller udvælgelse fra et endeligt sæt. Et klassisk eksempel er problemet med den rejsende sælger (TSP), hvor man skal finde den kortest mulige rute, der besøger et sæt byer præcis én gang og vender tilbage til udgangsbyen. I ACO konstruerer hver kunstig myre en tur ved probabilistisk at vælge den næste by at besøge, påvirket af både feromonintensitet og afstanden til hver ikke-besøgt by. Når alle myrer har fuldført deres ture, opdateres feromonsporene for at forstærke kortere, mere effektive ruter, mens mindre optimale stier mister feromon gennem fordampning. Denne iterative proces gør det muligt for ACO effektivt at udforske et stort søgeområde og konvergere mod løsninger af høj kvalitet til komplekse rute- og planlægningsopgaver.