Biologisk inspiration

I naturen kan myror hitta de kortaste vägarna mellan sitt bo och födokällor genom att lägga ut och följa feromonspår. När myror rör sig, avsätter de feromoner på marken, vilket skapar ett kemiskt spår som andra myror sannolikt följer. Sannolikheten att en myra väljer en viss väg ökar med styrkan på feromonspåret på den vägen. Denna mekanism leder till en positiv återkopplingsslinga: vägar med mer feromon väljs oftare, vilket i sin tur ökar feromonkoncentrationen på dessa vägar. Med tiden gör detta kollektiva beteende det möjligt för kolonin att upptäcka optimala eller nästan optimala lösningar på komplexa problem på ett decentraliserat sätt.

Exempel: Process för uppdatering 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)

Tillämpningar av ACO: Problemet med den kringresande försäljaren

Ant Colony Optimization är särskilt effektiv för att lösa kombinatoriska optimeringsproblem, där målet är att hitta den bästa ordningen eller urvalet från en ändlig mängd. Ett klassiskt exempel är problemet med den kringresande försäljaren (TSP), där den kortaste möjliga rutten som besöker en uppsättning städer exakt en gång och återvänder till ursprungsstaden ska hittas. I ACO konstruerar varje artificiell myra en tur genom att sannolikhetsbaserat välja nästa stad att besöka, påverkad av både feromonintensitet och avstånd till varje obesökt stad. Efter att alla myror har slutfört sina turer uppdateras feromonspåren för att förstärka kortare, mer effektiva rutter, medan mindre optimala vägar förlorar feromon genom avdunstning. Denna iterativa process gör det möjligt för ACO att effektivt utforska ett stort sökutrymme och konvergera mot högkvalitativa lösningar för komplexa rutt- och schemaläggningsuppgifter.