Biologisk inspirasjon

I naturen er maur i stand til å finne de korteste rutene mellom reiret sitt og matkilder ved å legge ut og følge feromonspor. Når maur beveger seg, avsetter de feromoner på bakken, og skaper et kjemisk spor som andre maur sannsynligvis vil følge. Sannsynligheten for at en maur velger en bestemt vei øker med styrken på feromonsporet på den veien. Denne mekanismen fører til en positiv tilbakemeldingssløyfe: stier med mer feromon velges oftere, noe som igjen øker feromonkonsentrasjonen på disse stiene. Over tid gjør denne kollektive atferden det mulig for kolonien å oppdage optimale eller nesten optimale løsninger på komplekse problemer på en desentralisert måte.

Eksempel: Prosess for oppdatering av feromon

# 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 av ACO: Problemet med den omreisende selgeren

Ant Colony Optimization er spesielt effektiv for å løse kombinatoriske optimaliseringsproblemer, hvor målet er å finne den beste rekkefølgen eller utvalget fra et endelig sett. Et klassisk eksempel er problemet med den omreisende selgeren (TSP), hvor man må finne den korteste mulige ruten som besøker et sett med byer nøyaktig én gang og returnerer til startbyen. I ACO konstruerer hver kunstig maur en tur ved å sannsynlighetsbasert velge neste by å besøke, påvirket av både feromonintensitet og avstand til hver uoppdaget by. Etter at alle maurene har fullført sine turer, oppdateres feromonsporene for å forsterke kortere, mer effektive ruter, mens mindre optimale veier mister feromon gjennom fordamping. Denne iterative prosessen gjør det mulig for ACO å effektivt utforske et stort søkeområde og konvergere mot løsninger av høy kvalitet for komplekse rute- og planleggingsoppgaver.