Algoritminen maailma on kaunis, sillä erilaisia strategioita ja työkaluja kehitetään kellon ympäri, jotta voidaan vastata tehokkaan tietojenkäsittelyn tarpeeseen. Itse asiassa, kun algoritmit saavat inspiraationsa luonnonlaeista, saadaan mielenkiintoisia tuloksia. Evoluutioalgoritmit kuuluvat sellaiseen algoritmiluokkaan. Nämä algoritmit on suunniteltu jäljittelemään tiettyjä käyttäytymismalleja sekä ihmisen genomin evoluutiopiirteitä. Lisäksi tällainen algoritminen suunnittelu ei rajoitu vain ihmisiin, vaan se voi olla inspiroitunut myös tiettyjen eläinten luonnollisesta käyttäytymisestä. Tällaisten metodologioiden valmistuksen perustavoitteena on tarjota realistisia, relevantteja ja silti joitakin edullisia ratkaisuja ongelmiin, joita ei tähän mennessä ole voitu ratkaista tavanomaisin keinoin.
Erilaiset optimointitekniikat ovat siis kehittyneet perustuen tällaisiin evoluutioalgoritmeihin ja siten avanneet metaheuristiikan aluetta. Metaheuristinen on johdettu kahdesta kreikan sanasta, nimittäin Meta merkitys yhden tason yläpuolella ja heuriskein merkitys löytää . Algoritmit, kuten PSO (Particle Swarm Optimization) ja Ant Colony Optimization (ACO), ovat esimerkkejä parven älykkyydestä ja metaheuristiikasta. Parviälyn tavoitteena on suunnitella älykkäitä monen tekijän järjestelmiä ottamalla inspiraatiota sosiaalisten hyönteisten, kuten muurahaisten, termiittien, mehiläisten, ampiaisten ja muiden eläinyhteisöjen, kuten lintuparvien tai kalaparvien, kollektiivisesta käyttäytymisestä.
Tausta:
Ant Colony Optimization -tekniikka on puhtaasti inspiroitunut ravinnonhaku muurahaisyhdyskuntien käyttäytyminen, jonka Marco Dorigo esitteli ensimmäisen kerran 1990-luvulla. Muurahaiset ovat eusosiaalisia hyönteisiä, jotka pitävät parempana yhteisön selviytymistä ja ylläpitämistä yksittäisten lajien sijaan. He kommunikoivat keskenään äänen, kosketuksen ja feromonien avulla. Feromonit ovat muurahaisten erittämiä orgaanisia kemiallisia yhdisteitä, jotka laukaisevat sosiaalisen reaktion saman lajin jäsenissä. Nämä ovat kemikaaleja, jotka pystyvät toimimaan hormonien tavoin erittävän yksilön kehon ulkopuolella vaikuttamaan vastaanottavien yksilöiden käyttäytymiseen. Koska useimmat muurahaiset elävät maassa, ne käyttävät maan pintaa jättääkseen feromonijälkiä, joita muut muurahaiset voivat seurata (haistaa).
Muurahaiset elävät yhteisön pesissä ja ACO:n perusperiaatteena on tarkkailla muurahaisten liikkumista pesistä, jotta he voivat etsiä ruokaa mahdollisimman lyhyitä polkuja pitkin. Aluksi muurahaiset alkavat liikkua satunnaisesti etsiessään ruokaa pesänsä ympäriltä. Tämä satunnaistettu haku avaa useita reittejä pesästä ravinnon lähteeseen. Nyt, ruoan laadun ja määrän perusteella, muurahaiset kuljettavat osan ruoasta takaisin tarvittavalla feromonipitoisuudella paluupolullaan. Näistä feromonikokeista riippuen todennäköisyys, että seuraavat muurahaiset valitsevat tietyn polun, olisi ohjaava tekijä ravinnon lähteessä. Ilmeisesti tämä todennäköisyys perustuu feromonin pitoisuuteen sekä haihtumisnopeuteen. Voidaan myös havaita, että koska feromonin haihtumisnopeus on myös ratkaiseva tekijä, kunkin reitin pituus voidaan helposti laskea.
Yllä olevassa kuvassa on yksinkertaisuuden vuoksi otettu huomioon vain kaksi mahdollista reittiä ravinnonlähteen ja muurahaispesän välillä. Vaiheet voidaan analysoida seuraavasti:
df.loc
- Vaihe 1: Kaikki muurahaiset ovat pesässään. Ympäristössä ei ole feromonipitoisuutta. (Algoritmisessa suunnittelussa feromonin jäännösmäärä voidaan ottaa huomioon todennäköisyyteen vaikuttamatta.) Vaihe 2: Muurahaiset aloittavat etsinnän yhtä suurella (0,5) todennäköisyydellä jokaisella polulla. On selvää, että kaareva polku on pidempi ja siksi aika, joka muurahaisilla kestää päästäkseen ravinnon lähteeseen, on pitempi kuin toisella. Vaihe 3: Lyhyempää polkua pitkin muurahaiset saavuttavat ravinnon lähteen aikaisemmin. Nyt he ilmeisesti kohtaavat samanlaisen valintapulman, mutta tällä kertaa jo saatavilla olevan lyhyemmän polun feromonipolun vuoksi valinnan todennäköisyys on suurempi. Vaihe 4: Enemmän muurahaisia palaa lyhyempää reittiä pitkin ja myöhemmin myös feromonipitoisuudet kasvavat. Lisäksi haihtumisen vuoksi feromonipitoisuus pidemmällä reitillä pienenee, mikä pienentää tämän reitin valinnan todennäköisyyttä myöhemmissä vaiheissa. Siksi koko pesäke käyttää vähitellen lyhyempää polkua suuremmalla todennäköisyydellä. Joten polun optimointi on saavutettu.
Algoritminen suunnittelu:
Edellä kuvattuun muurahaisten käyttäytymiseen liittyen voidaan nyt kehittää algoritminen suunnittelu. Yksinkertaisuuden vuoksi yksi ruokalähde ja yksi muurahaisyhdyskunta on otettu huomioon vain kahdella mahdollisella läpikulkureitillä. Koko skenaario voidaan toteuttaa painotettujen kaavioiden avulla, joissa muurahaisyhdyskunta ja ravinnonlähde toimivat pisteinä (tai solmuina); polut toimivat reunoina ja feromoniarvot ovat reunoihin liittyviä painoja.
Anna kaavion olla G = (V, E) missä V, E ovat graafin reunat ja kärjet. Käsittelymme mukaiset kärjet ovat SISÄÄNs (lähdevertex – muurahaisyhdyskunta) ja SISÄÄNd (Kohdevertex – Ruokalähde), Kaksi reunaa ovat JA1 ja JA2 pituuksilla L1 ja L2 jokaiselle osoitettu. Nyt niihin liittyvien feromoniarvojen (osoituksena niiden vahvuudesta) voidaan olettaa olevan R1 ja R2 pisteille E1ja E2vastaavasti. Siten jokaiselle muurahaiselle polun valinnan aloitustodennäköisyys (välillä E1ja E2) voidaan ilmaista seuraavasti:
tuple java
Ilmeisesti jos R1>R2, todennäköisyys valita E1on korkeampi ja päinvastoin. Nyt kun palaat tätä lyhintä polkua pitkin, sano Ei, feromoniarvo päivitetään vastaavalle polulle. Päivitys tehdään polkujen pituuden sekä feromonin haihtumisnopeuden perusteella. Päivitys voidaan siis toteuttaa vaiheittain seuraavasti:
- Reitin pituuden mukaan -
Yllä olevassa päivityksessä i = 1, 2 ja 'K' toimivat mallin parametreina. Lisäksi päivitys riippuu polun pituudesta. Mitä lyhyempi reitti, sitä korkeampi lisätty feromoni. Feromonin haihtumisnopeuden mukaan -
Parametri 'v' kuuluu väliin (0, 1], joka säätelee feromonin haihtumista. Lisäksi i = 1, 2.
Jokaisessa iteraatiossa kaikki muurahaiset sijoitetaan lähdepisteeseen Vs(muurahaisyhdyskunta). Myöhemmin muurahaiset siirtyvät V:stäsV:lled(ruokalähde) vaiheen 1 jälkeen. Seuraavaksi kaikki muurahaiset suorittavat paluumatkansa ja vahvistavat valitsemansa polun vaiheen 2 perusteella.
Pseudokoodi:
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>
Yllä olevan pseudokoodin feromonipäivitys ja kuntolaskelmat löytyvät yllä mainittujen vaiheittaisten toteutusten kautta.
Näin ollen ACO-optimointitekniikan käyttöönotto on perustettu. ACO:n sovellus voidaan laajentaa erilaisiin ongelmiin, kuten kuuluisaan TSP (Travelling Salesman Problem) .
Viitteet:
https://www.ics.uci.edu/~welling/teaching/271fall09/antcolonyopt.pdf