Abstract Ant Colony Optimization (ACO) är ett populärt optimeringsparadigm inspirerat av förmågan hos naturliga myrkolonier att hitta kortaste vägar mellan deras bo och en matkälla. Detta har lett till många framgångsrika tillämpningar för olika kombinatoriska problem. Orsaken till framgången för ACO är dock inte väl förstådd och det finns ett behov av en strikt teoretisk grund. Vi analyserar körtiden för en enkel myrkolonioptimerare för stokastiska kortaste stigproblem där kantvikter utsätts för buller som speglar förseningar och osäkerhet. I synnerhet tar vi hänsyn till olika bullermodeller, allt från allmänt godtyckligt buller med möjliga beroenden till mer specifika modeller som oberoende gammadistribuerat buller. Frågan är om myrorna kan hitta eller ungefär kortaste vägar i närvaro av buller. Vi karakteriserar fall där myrorna kan upptäcka de riktigt kortaste vägarna effektivt. För allmänna fall vi bevisa övre gränser för tiden tills algoritmen finner rimliga approximationer. I kontrast, för oberoende gamma-distribuerat buller presenterar vi en graf där myrsystemet behöver exponentiellt tid för att hitta en bra approximation. Myrsystemets beteende förändras dramatiskt när ljudet är perfekt korrelerat då myrorna hittar kortaste vägar effektivt. Våra resultat kastar ljus över kompromisser mellan bullerstyrka, approximativa garantier och förväntade körtider.
REF analyserade körtiden för en enkel ACO för stokastiska kortaste vägproblem där kantvikter utsätts för buller, och visade förmåga och begränsning av ACO under olika bullermodeller.
A Simple Ant Colony Optimizer for Stochastic Shortest Path Problems
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}