Ant algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 4.5.2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Muurahaispesäkkeiden optimointialgoritmi ( muurahaispesäkkeiden optimointi , ACO ) on yksi tehokkaista polynomialgoritmeista löytääkseen likimääräisiä ratkaisuja matkustavan myyjän ongelmaan sekä ratkaista vastaavia ongelmia reittien löytämisessä kaavioista . Lähestymistavan ydin on analysoida ja käyttää muurahaisten käyttäytymismallia, joka etsii tapoja pesäkkeestä ravinnon lähteeseen, ja se on metaheuristinen optimointi. Algoritmin ensimmäinen versio, jonka tohtori Marco Dorigo [1] [2] ehdotti vuonna 1992 , pyrittiin löytämään optimaalinen polku graafista.

Historia

1959 - Pierre-Paul Grasset esitti stigmergiateorian selittääkseen termiittiyhdyskunnan käyttäytymisen [3] ;
1983 - Deneborg ja hänen kollegansa analysoivat muurahaisten kollektiivista käyttäytymistä [4] ;
1988 - Mason ja Mandersky julkaisivat artikkelin muurahaisten "itseorganisoitumisesta" [5] ;
1989 - Aronin, Gossin, Denerborgin ja Pastelesin työ " Argentiinan muurahaisten kollektiivinen käyttäytyminen ", joka antoi idean muurahaisyhdyskuntaalgoritmista [6] ;
1989 - Ebling ja hänen kollegansa ottavat käyttöön käyttäytymismallin ruokaa etsiessään [7] ;
1991 - M. Dorigo ehdotti "muurahaisjärjestelmän" käsitettä väitöskirjassaan (joka julkaistiin vuonna 1992).
2001 – IREDA ja yhteistyökumppanit julkaisivat ensimmäisen monikäyttöalgoritmin [8]
2002 - ensimmäinen sovellus grafiikan kehityksessä, Bayesin verkot ;
2002 - Bianchi ja hänen kollegansa ehdottivat ensimmäistä stokastista algoritmia [9] ;
2004 - Zlochin ja Dorigo osoittavat, että jotkut algoritmit ovat vastaavia: stokastisen gradientin laskeutumisen, ristientropian ja jakauman estimointialgoritmit;
2005 - Ensimmäiset sovellukset proteiinin laskostumisongelman ratkaisemisessa.

Yleiskatsaus

Algoritmi perustuu muurahaispesäkkeen käyttäytymiseen, joka merkitsee onnistuneempia polkuja suurella määrällä feromonia . Työ alkaa muurahaisten sijoittamisella kaavion kärkipisteisiin (kaupungit), sitten muurahaisten liike alkaa - suunta määritetään todennäköisyyslaskentamenetelmällä, joka perustuu muodon kaavaan:

P_{i}={\frac {{l_{i}}^{q}\cdot {f_{i}}^{p}}{\sum _{k=0}^{N}{{l_{k }}^{q}\cdot {f_{k}}^{p}}}}

missä:

P_{i}

on todennäköisyys liikkua polkua pitkin ,

i

l_{i}

on käänteisluku : nnen siirtymän painosta (pituudesta) ,

i

f_{i}

on feromonin määrä liitoskohdassa,

i

q

on arvo, joka määrittää algoritmin "ahneuden",

s

- arvo, joka määrittää algoritmin "paimentamisen".

Ratkaisu ei ole tarkka ja voi olla jopa yksi huonoimmista, mutta hyvin valitun heuristiikan vuoksi algoritmin iteratiivinen soveltaminen antaa yleensä tuloksen, joka on lähellä optimaalista.

Kirjallisuudessa on ehdotettu useita ACO:n metaheuristisia malleja. Niistä kolme menestyneintä ovat:

muurahaisjärjestelmä (Dorigo 1992, Dorigo et al. 1991, 1996),
muurahaisyhdyskuntajärjestelmä (ACS) (Dorigo & Gambardella 1997),
MAX-MIN muurahaisjärjestelmä (MMAS) (Stutzle & Hoos 2000).

Yhteenveto

Todellisessa maailmassa muurahaiset (alkuvaiheessa) kävelevät satunnaisesti ja löydettyään ruokaa palaavat yhdyskuntaansa polttaen polkuja feromonien kanssa. Jos muut muurahaiset löytävät tällaisia polkuja, ne todennäköisemmin seuraavat niitä. Sen sijaan, että seuraisivat ketjua, he vahvistavat sitä palatessaan, jos he lopulta löytävät ruokalähteen. Ajan myötä feromonijälki alkaa haihtua, mikä vähentää sen houkuttelevuutta. Mitä enemmän aikaa kuluu polun kulkemiseen kohteeseen ja takaisin, sitä enemmän feromonijälki haihtuu. Vertailun vuoksi lyhyellä tiellä kulku on nopeampaa, ja sen seurauksena feromonien tiheys pysyy korkeana. Feromonihaihdutuksen tehtävänä on myös välttää paikallisesti optimaalisen ratkaisun etsiminen. Jos feromonit eivät haihtuisi, ensin valittu reitti olisi houkuttelevin. Tässä tapauksessa tilaratkaisujen tutkimukset olisivat rajallisia. Siten, kun yksi muurahainen löytää (esimerkiksi lyhyen) polun yhdyskunnasta ravintolähteeseen, muut muurahaiset seuraavat todennäköisemmin tätä polkua, ja positiivinen palaute johtaa lopulta kaikki muurahaiset samalle lyhimmälle polulle.

Lue lisää

Alkuperäinen idea tulee tarkkailemalla muurahaisia, kun ne löytävät lyhimmän polun yhdyskunnasta ravintolähteeseensä.

Ensimmäinen muurahainen löytää ravinnonlähteen (F) millä tahansa keinolla (a) ja palaa sitten pesään (N), jättäen jälkeensä feromonijäljen (b).
Sitten muurahaiset valitsevat yhden neljästä mahdollisesta polusta, vahvistavat sitä ja tekevät siitä houkuttelevan.
Muurahaiset valitsevat lyhimmän reitin, koska pitemmiltä reiteiltä peräisin olevat feromonit haihtuvat nopeammin.

Kokeissa, joissa valittiin kahden eripituisen polun välillä, jotka johtavat pesäkkeestä ravintolähteeseen, biologit ovat havainneet, että muurahaiset käyttävät yleensä lyhintä reittiä [6] [10] . Malli tälle käytökselle on seuraava:

Muurahainen (kutsutaan "Blitz") kulkee satunnaisesti pesäkkeestä.
Jos se löytää ravinnonlähteen, se palaa pesään jättäen taakseen feromonijäljen.
Nämä feromonit houkuttelevat muita lähellä olevia muurahaisia, jotka todennäköisemmin valitsevat tämän reitin.
Palattuaan pesään ne vahvistavat feromonipolkua.
Jos reittiä on 2, niin useammilla muurahaisilla on aikaa kulkea lyhyempää samaan aikaan kuin pitkää.
Lyhyemmästä reitistä tulee houkuttelevampi.
Pitkät polut häviävät lopulta feromonien haihtumisen vuoksi.

Muurahaiset käyttävät ympäristöä viestintävälineenä. He vaihtavat tietoja epäsuorasti feromonien kautta "työnsä" aikana. Tiedonvaihto on luonteeltaan paikallista: vain feromonipolkujen välittömässä läheisyydessä olevat muurahaiset voivat oppia niistä. Tällaista järjestelmää kutsutaan stigmergiaksi ja se on totta monille sosiaalisille eläimille (se on tutkittu pilarien rakentamisen tapauksessa termiittipesissä). Tämä ongelmanratkaisumekanismi on erittäin monimutkainen ja on hyvä esimerkki järjestelmän itseorganisoitumisesta. Tällainen järjestelmä perustuu positiiviseen (muut muurahaiset vahvistavat feromonipolkua) ja negatiiviseen (feromonijäljen haihtuminen) palautteeseen. Teoriassa, jos feromonien määrä pysyy samana ajan mittaan kaikilla reiteillä, polun valitseminen on mahdotonta. Pienet heilahtelut saavat kuitenkin palautteen vaikutuksesta yhden reiteistä voimakkaamman ja järjestelmän vakiintumaan kohti lyhintä polkua.

Algoritmin muunnelmia

Seuraavassa on joitain muurahaisyhdyskuntaalgoritmin suosituimpia muunnelmia.

Elite Ant System

Muurahaisten kokonaismäärästä erottuvat niin sanotut "eliittimuurahaiset". Algoritmin jokaisen iteraation tulosten mukaan parhaita reittejä vahvistetaan ohittamalla eliittimuurahaisia näitä reittejä pitkin ja siten feromonien määrä näillä reiteillä kasvaa. Tällaisessa järjestelmässä eliittimuurahaisten lukumäärä on lisäparametri, joka on määritettävä. Joten liian monen eliittimuurahaisen kohdalla algoritmi voi juuttua paikallisiin ääripäihin.

MMAS (Max-Min ant system) [11]

Lisätty rajaehdot feromonien lukumäärälle (τ min ,τ max ). Feromonit talletetaan vain maailmanlaajuisesti parhaille tai parhaille iteraatioreiteille. Kaikki reunat alustetaan arvolla τ max .

Suhteelliset pseudosatunnaissäännöt

Esitetty yllä[ selventää ] [12] .

Ant ranking system (ASrank)

Kaikki ratkaisut luokitellaan niiden sopivuuden mukaan. Saostettujen feromonien määrä jokaisessa liuoksessa painotetaan siten, että sopivammat liuokset saavat enemmän feromoneja kuin vähemmän sopivat.

Pitkäaikainen ortogonaalinen muurahaissiirtokunta (COAC)

COAC-feromonikerrostumismekanismin avulla muurahaiset voivat etsiä ratkaisuja yhteistyössä ja tehokkaasti. Ortogonaalista menetelmää käyttämällä muurahaiset sopivalla alueella voivat tutkia valitsemiaan alueita nopeasti ja tehokkaasti tehostetulla maailmanlaajuisella hakukyvyllä ja tarkkuudella.

Ortogonaalista suunnittelumenetelmää ja adaptiivista säteensäätömenetelmää voidaan laajentaa myös muihin optimointialgoritmeihin saadakseen laajempia etuja käytännön ongelmien ratkaisemisessa [13] .

Lähentyminen

Sovellus

Esimerkki: pseudokoodi ja kaava

procedure ACO_MetaHeuristic while(not_termination) generateSolutions() daemonActions() pheromoneUpdate() end while end procedure

Reunat:
Muurahainen siirtyy solmusta toiseen todennäköisyydellä: $i$ $j$

p_{i,j}={\frac {(\tau _{i,j}^{\alpha })(\eta _{i,j}^{\beta })}{\sum (\tau _{ i,j}^{\alpha })(\eta _{i,j}^{\beta )))))

, missä:

\tau_{i,j}

on reunassa olevien feromonien lukumäärä ;

i, j

\alpha

on parametri, joka ohjaa vaikutusta ;

\tau_{i,j}

\eta_{i,j}

reunan houkuttelevuus (alkuarvo, yleensä , missä d on etäisyys);

i, j

1/d_{{i,j}}

\beeta

on parametri, joka ohjaa arvon vaikutusta .

\eta_{i,j}

Feromonipäivitys

\tau _{i,j}=(1-\rho )\tau _{i,j}+\Delta \tau _{i,j}

missä:

\tau_{i,j}

on feromonin määrä kaaressa ,

i, j

\rho

on feromonien haihtumisnopeus,

\Delta \tau _{i,j}

on talletetun feromonin määrä, joka yleensä määritellään seuraavasti:

\Delta \tau _{i,j}^{k}={\begin{cases}1/L_{k}&{\mbox{if ant }}k{\mbox{ kulkee reunassa }}i,j\ \0&{\mbox{muutoin}}\end{cases}}

missä on muurahaisen polun hinta (yleensä pituus). $L_{k}$ $k$

Muita esimerkkejä

Workshop: suunnittelun ongelmia Auto: reititysongelma

Ilmeisin ja suosituin muurahaisyhdyskuntaalgoritmien sovellusalue on kuljetuslogistiikka. Kuljetuslogistiikan tehtäviin kuuluvat sellaiset NP-vaikeat tehtävät kuin matkustava myyjäongelma ja ajoneuvojen reititys [14] .

Tehtäväongelma Määrätty tehtävä

Vaikeuksia määritellä

Stigmergy-algoritmit

Termin "stigmergia" otti käyttöön ranskalainen biologi P.-P. Grasse vuonna 1959 kuvaamaan termiittien käyttäytymistä . Hän määritteli sen seuraavasti: " Työntekijöiden stimulointi lisäämällä heidän tuottavuuttaan. » Termi tulee kahdesta kreikan sanasta "stigma" (merkki, merkki) ja "ergo" (työ, toiminta) [15] .

Katso myös

Muistiinpanot

↑ A. Colorni, M. Dorigo ja V. Maniezzo, Ant Coloniesin hajautettu optimointi , esitys de la Premier Conférence sur la vie artificielle, Pariisi, Ranska, Elsevier Publishing, 134-142, 1991.
↑ M. Dorigo, Optimointi, oppiminen ja luonnolliset algoritmit , PhD-väitöskirja, Politecnico di Milano, Italia, 1992.
↑ P.-P. Grasse, La reconstruction du nid et les koordinations inter-individuelles chez Belicositermes natalensis et Cubitermes sp. La theorie de la Stigmergie: Essai d'interpretation du Comportement des termites constructeurs , Insectes Sociaux, numero 6, s. 41-80, 1959.
↑ JL Denebourg, JM Pasteels ja JC Verhaeghe, Probabilistic Behavior in Ants: a Strategy of Errors? , Journal of Theoretical Biology, numero 105, 1983.
↑ F. Moyson, B. Manderick, The kollektiivinen käyttäytyminen Ants: esimerkki itseorganisaatiosta massiivisessa rinnakkaisuudessa , Actes de AAAI Spring Symposium on Parallel Models of Intelligence, Stanford, Kalifornia, 1988.
↑ 1 2 S. Goss, S. Aron, J.-L. Deneubourg et J.-M. Pasteels, Argentiinan muurahaisen itseorganisoitunut tutkimusmalli , Naturwissenschaften, osa 76, sivut 579-581, 1989
↑ M. Ebling, M. Di Loreto, M. Presley, F. Wieland ja D. Jefferson, An Ant Foraging Model Implemented on the Time Warp Operating System , Proceedings of the SCS Multiconference on Distributed Simulation, 1989
↑ S. Iredi, D. Merkle et M. Middendorf, Bi-Criterion Optimization with Multi Colony Ant Algorithms , Evolutionary Multi-Criterion Optimization, First International Conference (EMO'01), Zurich, Springer Verlag, sivut 359–372, 2001.
↑ L. Bianchi, LM Gambardella et M. Dorigo, Ant colony optimization approach to probabilistic travelling saleman problem , PPSN-VII, Seventh International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Springer Verlag, Berliini, Allemagne , 2002.
↑ J.-L. Deneubourg, S. Aron, S. Goss et J.-M. Pasteels, Argentiinan muurahaisen itseorganisoituva tutkimusmalli , Journal of Insect Behavior, osa 3, sivu 159, 1990
↑ T. Stützle et HH Hoos, MAX MIN Ant System , Future Generation Computer Systems, osa 16, sivut 889–914, 2000
↑ M. Dorigo et LM Gambardella, Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem , IEEE Transactions on Evolutionary Computation, osa 1, numero 1, sivut 53-66, 1997.
↑ X Hu, J Zhang ja Y Li (2008). Ortogonaalisiin menetelmiin perustuva muurahaispesäkehaku jatkuvien optimointiongelmien ratkaisemiseksi. Journal of Computer Science and Technology , 23(1), s. 2-18.
↑ Kazharov A. A., Kureichik V. M. Ant algoritmit kuljetusongelmien ratkaisemiseen. Venäjän tiedeakatemian uutisia. Teoria ja ohjausjärjestelmät. 2010. Nro 1. S. 32-45.
↑ Bonabeau, E. "Toimittajan esittely: Stigmergy." Stigmergy -keinoelämän erikoisnumero . Osa 5, numero 2 / kevät 1999, s. 95-96. http://www.stigmergicsystems.com/stig_v1/stigrefs/article1.html

Kirjallisuus

M. Dorigo , 1992. Optimointi, oppiminen ja luonnolliset algoritmit , PhD-tutkielma, Politecnico di Milano, Italia.
M. Dorigo, V. Maniezzo & A. Colorni, 1996. "Ant System: Optimization by a Colony of Cooperating Agents", IEEE Transactions on Systems, Man, and Cybernetics - Osa B, 26(1): 29-41.
M. Dorigo & LM Gambardella , 1997. "Muurahaisyhdyskuntajärjestelmä: yhteistoiminnallinen oppimismenetelmä matkustavan myyjän ongelmaan." IEEE Transactions on Evolutionary Computation, 1(1): 53-66.
M. Dorigo, G. Di Caro & LM Gambardella, 1999. "Ant Algorithms for Discrete Optimization". Keinotekoinen elämä, 5(2): 137-172.
E. Bonabeau, M. Dorigo et G. Theraulaz, 1999. Swarm Intelligence: From Natural to Artificial Systems , Oxford University Press. ISBN 0-19-513159-2
M. Dorigo & T. Stützle, 2004. Ant Colony Optimization , MIT Press. ISBN 0-262-04219-3
M. Dorigo, 2007. Ant Colony Optimization . Scholarpedia.
C. Blum, 2005 Muurahaispesäkkeiden optimointi: Johdanto ja viimeaikaiset trendit. Physics of Life Reviews, 2: 353-373
Shtovba S. D. Ant-algoritmit, Exponenta Pro. Matematiikka sovelluksissa. 2004. Nro 4
Kirsanov M.N. Kaaviot vaahterassa. — M .: Fizmatlit , 2007. — 168 s. - ISBN 978-5-9221-0745-7 . http://vuz.expponenta.ru/PDF/book/GrMaple.pdf http://eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
M. Dorigo, M. Birattari & T. Stützle, 2006 Muurahaisyhdyskuntien optimointi: tekomuurahaiset laskennallisena älykkyystekniikana .

Linkit

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi