Algoritmvärlden är vacker med många olika strategier och verktyg som utvecklas dygnet runt för att klara behovet av högpresterande datoranvändning. Faktum är att när algoritmer är inspirerade av naturlagar, observeras intressanta resultat. Evolutionära algoritmer tillhör en sådan klass av algoritmer. Dessa algoritmer är utformade för att efterlikna vissa beteenden såväl som evolutionära egenskaper hos det mänskliga genomet. Dessutom är sådan algoritmisk design inte bara begränsad till människor utan kan också inspireras av det naturliga beteendet hos vissa djur. Det grundläggande syftet med att tillverka sådana metoder är att tillhandahålla realistiska, relevanta och ändå några billiga lösningar på problem som hittills är olösliga på konventionellt sätt.
Olika optimeringstekniker har alltså utvecklats baserat på sådana evolutionära algoritmer och därigenom öppnat upp metaheuristikens domän. Metaeuristisk har härletts från två grekiska ord, nämligen Meta menande en nivå över och heuriskein menande att hitta . Algoritmer som partikelsvärmoptimering (PSO) och myrkolonioptimering (ACO) är exempel på svärmintelligens och metaheuristik. Målet med svärmintelligens är att designa intelligenta multiagentsystem genom att hämta inspiration från det kollektiva beteendet hos sociala insekter som myror, termiter, bin, getingar och andra djursamhällen som fågelflockar eller fiskstim.
Bakgrund:
Ant Colony Optimization-tekniken är enbart inspirerad av födosök myrkoloniernas beteende, som först introducerades av Marco Dorigo på 1990-talet. Myror är eusociala insekter som föredrar samhällets överlevnad och upprätthållande snarare än som individuella arter. De kommunicerar med varandra med hjälp av ljud, beröring och feromon. Feromoner är organiska kemiska föreningar som utsöndras av myrorna som utlöser en social respons hos medlemmar av samma art. Dessa är kemikalier som kan agera som hormoner utanför den utsöndrande individens kropp, för att påverka beteendet hos de mottagande individerna. Eftersom de flesta myror lever på marken använder de jordytan för att lämna feromonspår som kan följas (luktas) av andra myror.
Myror lever i samhällets bon och den underliggande principen för ACO är att observera myrornas rörelse från sina bon för att söka föda på kortast möjliga väg. Inledningsvis börjar myror röra sig slumpmässigt på jakt efter mat runt sina bon. Denna randomiserade sökning öppnar upp flera vägar från boet till matkällan. Nu, baserat på matens kvalitet och kvantitet, bär myror tillbaka en del av maten med nödvändig feromonkoncentration på sin returväg. Beroende på dessa feromonförsök skulle sannolikheten för val av en specifik väg av följande myror vara en vägledande faktor för matkällan. Uppenbarligen är denna sannolikhet baserad på koncentrationen såväl som hastigheten för avdunstning av feromon. Det kan också observeras att eftersom förångningshastigheten för feromon också är en avgörande faktor, kan längden på varje väg lätt redovisas.
I figuren ovan har för enkelhets skull endast två möjliga vägar övervägts mellan födokällan och myrboet. Stadierna kan analyseras enligt följande:
- Steg 1: Alla myror är i sitt bo. Det finns inget feromoninnehåll i miljön. (För algoritmisk design kan kvarvarande feromonmängd övervägas utan att störa sannolikheten) Steg 2: Myror börjar sin sökning med lika stor sannolikhet (0,5 vardera) längs varje väg. Det är uppenbart att den krökta vägen är längre och därför är den tid det tar för myror att nå matkällan längre än den andra. Steg 3: Myrorna genom den kortare vägen når matkällan tidigare. Nu står de uppenbarligen inför ett liknande urvalsdilemma, men den här gången på grund av feromonspåret längs den kortare vägen som redan finns är sannolikheten för urval högre. Steg 4: Fler myror återvänder via den kortare vägen och därefter ökar också feromonkoncentrationerna. Dessutom, på grund av avdunstning, minskar feromonkoncentrationen i den längre banan, vilket minskar sannolikheten för val av denna väg i ytterligare steg. Därför använder hela kolonin gradvis den kortare vägen med högre sannolikheter. Så vägoptimering uppnås.
Algoritmisk design:
Angående ovanstående beteende hos myrorna kan nu en algoritmisk design utvecklas. För enkelhetens skull har en enda födokälla och en enskild myrkoloni övervägts med bara två vägar för möjlig korsning. Hela scenariot kan realiseras genom viktade grafer där myrkolonin och födokällan fungerar som hörn (eller noder); banorna fungerar som kanter och feromonvärdena är vikterna som är associerade med kanterna.
Låt grafen vara G = (V, E) där V, E är grafens kanter och hörn. Topparna enligt vår övervägande är Is (Källpunkt – myrkoloni) och Id (Destination vertex – Matkälla), De två kanterna är OCH1 och OCH2 med längder L1 och L2 tilldelas var och en. Nu kan de associerade feromonvärdena (som indikerar deras styrka) antas vara R1 och R2 för hörn E1och E2respektive. För varje myra är alltså startsannolikheten för val av väg (mellan E1och E2) kan uttryckas på följande sätt:
Uppenbarligen, om R1>R2, sannolikheten att välja E1är högre och vice versa. Nu, när du återvänder genom denna kortaste väg, säg Ei, uppdateras feromonvärdet för motsvarande sökväg. Uppdateringen görs baserat på banornas längd samt feromonets förångningshastighet. Så uppdateringen kan genomföras stegvis enligt följande:
- I enlighet med vägens längd –
I ovanstående uppdatering fungerar i = 1, 2 och 'K' som en parameter för modellen. Dessutom är uppdateringen beroende av sökvägens längd. Kortare vägen, högre tillsatt feromon. I enlighet med avdunstningshastigheten för feromon -
Parametern 'v' tillhör intervall (0, 1] som reglerar feromonavdunstning. Vidare är i = 1, 2.
Vid varje iteration placeras alla myror vid källpunkt Vs(myrkoloni). Därefter flyttar myror från Vstill Vd(matkälla) efter steg 1. Därefter genomför alla myror sin hemresa och förstärker sin valda väg baserat på steg 2.
Pseudokod:
Procedure AntColonyOptimization: Initialize necessary parameters and pheromone trials; while not termination do : Generate ant population; Calculate fitness values associated with each ant; Find best solution through selection methods; Update pheromone trial; end while end procedure>
Feromonuppdateringen och konditionsberäkningarna i ovanstående pseudokod kan hittas genom de stegvisa implementeringarna som nämns ovan.
Således har introduktionen av ACO-optimeringstekniken etablerats. Tillämpningen av ACO kan utvidgas till olika problem såsom de berömda TSP (Travelling Salesman Problem) .
Referenser:
https://www.ics.uci.edu/~welling/teaching/271fall09/antcolonyopt.pdf