Den algoritmiske verdenen er vakker med mangfoldige strategier og verktøy som utvikles døgnet rundt for å gjengi behovet for høyytelses databehandling. Faktisk, når algoritmer er inspirert av naturlover, observeres interessante resultater. Evolusjonsalgoritmer tilhører en slik klasse av algoritmer. Disse algoritmene er designet for å etterligne visse atferd samt evolusjonære trekk ved det menneskelige genomet. Dessuten er slik algoritmisk design ikke bare begrenset til mennesker, men kan også være inspirert av den naturlige oppførselen til visse dyr. Det grunnleggende målet med å lage slike metoder er å gi realistiske, relevante og likevel noen rimelige løsninger på problemer som hittil har vært uløselige med konvensjonelle midler.
Ulike optimaliseringsteknikker har dermed utviklet seg basert på slike evolusjonære algoritmer og derved åpnet opp domenet til metaheuristikk. Metaeuristisk har blitt avledet fra to greske ord, nemlig Meta betydning ett nivå over og heuriskein betydning å finne . Algoritmer som Particle Swarm Optimization (PSO) og Ant Colony Optimization (ACO) er eksempler på svermintelligens og metaheuristikk. Målet med svermintelligens er å designe intelligente multiagentsystemer ved å hente inspirasjon fra den kollektive oppførselen til sosiale insekter som maur, termitter, bier, veps og andre dyresamfunn som fugleflokker eller fiskestimer.
Bakgrunn:
1 milliard til million
Ant Colony Optimization-teknikken er rent inspirert fra fôrsøking oppførsel av maurkolonier, først introdusert av Marco Dorigo på 1990-tallet. Maur er eusosiale insekter som foretrekker samfunnets overlevelse og opprettholdelse i stedet for som individuelle arter. De kommuniserer med hverandre ved hjelp av lyd, berøring og feromon. Feromoner er organiske kjemiske forbindelser utskilt av maurene som utløser en sosial respons hos medlemmer av samme art. Dette er kjemikalier som er i stand til å fungere som hormoner utenfor kroppen til det utskillende individet, for å påvirke oppførselen til de mottakende individene. Siden de fleste maur lever på bakken, bruker de jordoverflaten til å etterlate feromonstier som kan følges (luktes) av andre maur.
Maur lever i fellesskapsreir og det underliggende prinsippet til ACO er å observere bevegelsen til maurene fra reirene deres for å søke etter mat på kortest mulig vei. Til å begynne med begynner maur å bevege seg tilfeldig på jakt etter mat rundt reirene deres. Dette randomiserte søket åpner for flere ruter fra reiret til matkilden. Nå, basert på kvaliteten og kvantiteten på maten, bærer maur en del av maten tilbake med nødvendig feromonkonsentrasjon på returveien. Avhengig av disse feromonforsøkene, vil sannsynligheten for valg av en spesifikk vei av følgende maur være en veiledende faktor for matkilden. Tydeligvis er denne sannsynligheten basert på konsentrasjonen så vel som fordampningshastigheten til feromon. Det kan også observeres at siden fordampningshastigheten til feromon også er en avgjørende faktor, kan lengden på hver vei lett gjøres rede for.
I figuren ovenfor er det for enkelhets skyld bare blitt vurdert to mulige veier mellom matkilden og maurredet. Stadiene kan analyseres som følger:
noe rask sortering
- Trinn 1: Alle maur er i reiret sitt. Det er ikke noe feromoninnhold i miljøet. (For algoritmisk design kan gjenværende feromonmengde vurderes uten å forstyrre sannsynligheten) Trinn 2: Maur begynner søket med lik (0,5 hver) sannsynlighet langs hver vei. Det er klart at den buede banen er lengre, og derfor er tiden det tar for maur å nå matkilden lengre enn den andre. Trinn 3: Maurene gjennom den kortere veien når matkilden tidligere. Nå står de tydeligvis overfor et lignende seleksjonsdilemma, men denne gangen på grunn av feromonspor langs den kortere veien som allerede er tilgjengelig, er sannsynligheten for seleksjon høyere. Trinn 4: Flere maur kommer tilbake via den kortere veien og deretter øker også feromonkonsentrasjonene. På grunn av fordampning reduseres dessuten feromonkonsentrasjonen i den lengre banen, noe som reduserer sannsynligheten for valg av denne banen i ytterligere stadier. Derfor bruker hele kolonien gradvis den kortere veien med høyere sannsynlighet. Så baneoptimalisering er oppnådd.
Algoritmisk design:
Når det gjelder ovennevnte oppførsel til maurene, kan det nå utvikles et algoritmisk design. For enkelhets skyld har en enkelt matkilde og en enkelt maurkoloni blitt vurdert med bare to mulige kryssingsveier. Hele scenariet kan realiseres gjennom vektede grafer der maurkolonien og matkilden fungerer som toppunkter (eller noder); banene fungerer som kantene og feromonverdiene er vektene knyttet til kantene.
La grafen være G = (V, E) hvor V, E er kantene og toppunktene til grafen. Toppene i henhold til vår vurdering er Is (Kilde toppunkt – maurkoloni) og Id (Destinasjon vertex – Matkilde), De to kantene er OG1 og OG2 med lengder L1 og L2 tildelt hver. Nå kan de tilknyttede feromonverdiene (som indikerer deres styrke) antas å være det R1 og R2 for hjørnene E1og E2hhv. Dermed for hver maur, startsannsynligheten for valg av vei (mellom E1og E2) kan uttrykkes som følger:
Tydeligvis, hvis R1>R2, sannsynligheten for å velge E1er høyere og omvendt. Nå, mens du går tilbake gjennom denne korteste veien, si EJeg, er feromonverdien oppdatert for den tilsvarende banen. Oppdateringen gjøres basert på lengden på banene samt fordampningshastigheten til feromon. Så oppdateringen kan realiseres trinnvis som følger:
- I henhold til veilengde –
I oppdateringen ovenfor fungerer i = 1, 2 og 'K' som en parameter for modellen. Dessuten er oppdateringen avhengig av lengden på banen. Kortere banen, høyere er feromonet lagt til. I henhold til fordampningshastigheten til feromonen -
Parameteren 'v' tilhører intervall (0, 1] som regulerer feromonfordampningen. Videre er i = 1, 2.
Ved hver iterasjon plasseres alle maurene ved kildetoppunktet Vs(maurkoloni). Deretter beveger maur seg fra Vstil Vd(matkilde) etter trinn 1. Deretter gjennomfører alle maurene hjemturen og forsterker den valgte stien basert på trinn 2.
java system.out.println
Pseudokode:
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>
Feromonoppdateringen og kondisjonsberegningene i pseudokoden ovenfor kan bli funnet gjennom de trinnvise implementeringene nevnt ovenfor.
Dermed er introduksjonen av ACO-optimaliseringsteknikken etablert. Anvendelsen av ACO kan utvides til ulike problemer som den berømte TSP (Travelling Salesman Problem) .
Referanser:
https://www.ics.uci.edu/~welling/teaching/271fall09/antcolonyopt.pdf