jlouis@pc-063.diku.dk (Jesper Louis Andersen) wrote
> Routing via scentnedliggelse fra de ''myrer'' der passerer en router? Det lyder
> som swarm-intelligence. Blev det effektivt?
Hmmmm, godt spørgsmål.
Den korte version er - vi har en formodning om at det kan blive
effektivt - i visse situationer...
En lidt længere version følger... (men kortere end rapporten
)
Marco Dorigo (der er en af de tunge drenge bag myre-algoritme-tingen)
og et par andre forskere har rapporteret (og skrevet en bunke artikler
om) at have lavet nogle overordentligt velfungerende og effektive
myrealgoritmer. Bl.a. en routing-algoritme 'AntNet' til
packet-switchede netværk (internettet). Det må siges at være den
myrealgoritme vi primært har ladet os inspirere af i dette projekt. De
anfører at i deres tests router den bedre end en række
standardrouting-algoritmer (bl.a. Bellman-Ford og OSPF) på et tungt
belastet netværk. Med "bedre" forstås her lavere pakkedød og hurtigere
sendetid for pakker.
Hele tricket skulle være at myrealgoritmer har en indbygget
adaptivitet i forhold til skiftende parametre for problemet de
forsøger at optimere en løsning til. Derfor interesserede vi os heller
ikke for specielt for statiske problemstillinger, men kastede os over
routing, der jo er et forbandet dynamisk problem. "forbandet", da
problemstillingen ikke bare er dynamisk i sig selv, men det kan
faktisk ændre på parametrene bare at forsøge at måle på situationen på
netværket (ved f.eks. at sende testpakker ud.)
Vores undersøgelser har været mere kvalitative i den forstand at vi
undersøgte hvilke makrofænomener vi rent faktisk kunne dreje
routing-algoritmen hen imod. Derfor lavede vi et
myre-routing-algoritme 'skelet', og implementerede en række
heuristikker (smarte tricks), som vi kunne skrue på via parametre.
Dermed blev det muligt at stille spørgsmål som: Kan vi få
routing-algoritmen (ARS) til at primært at route henover den korteste
vej? Kan vi få routing-algoritmen til at prioritere at pakkedød meget
sjældent skal ske? Etc. etc.
(Nu må jeg hellere forsøge at runde af) - Vi fandt, at det faktisk var
muligt at opnå disse effekter, og fik da også noget der lignede meget
fine routing-tider og lav pakkedød i forhold til en lille
'dæmon'-algoritme vi implementerede som en slags reference-ramme.
(Basalt set havde denne 'dæmon'-routing-algoritme et øjebliksbillede
af hele netværket i hvert klokke-tick.)
Men(!) - det var altså kun nogle få tests, primært på et simpelt 10x10
grid netværk med én sender og én modtager. Så der er ikke meget sjov i
det endnu. Men forhåbentlig får vi tid til at kigge lidt mere på det,
på et senere tidspunkt. Det kunne være sjovt at gå lidt videre med
det...
Hmmm, det blev vist lidt langt... Men sådan går det når man bliver
spurgt om noget som er spændende. Tak for tiden, hvis der var nogen
der gad at læse så langt
vh troels