Algoritmus mravenců

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 4. května 2022; kontroly vyžadují 2 úpravy .

Algoritmus optimalizace mravenčích kolonií ( ant kolonie optimalizace , ACO) je jedním z efektivních polynomiálních algoritmů pro hledání přibližných řešení problému obchodního cestujícího , stejně jako řešení podobných problémů hledání tras v grafech . Podstatou tohoto přístupu je analyzovat a používat model chování mravenců hledajících cesty z kolonie ke zdroji potravy a je metaheuristickou optimalizací. První verze algoritmu, kterou navrhl Dr. Marco Dorigo [1] [2] v roce 1992 , byla zaměřena na nalezení optimální cesty v grafu.

Historie

1959 – Pierre-Paul Grasset vyložil teorii stigmergie, aby vysvětlil chování kolonie termitů [3] ;
1983 – Deneborg a jeho kolegové analyzovali kolektivní chování mravenců [4] ;
1988 – Mason a Mandersky publikovali článek o „sebeorganizaci“ mezi mravenci [5] ;
1989 - práce Arona, Gosse, Denerborga a Pastelese "kolektivní chování argentinských mravenců ", která dala myšlenku algoritmu mravenčí kolonie [6] ;
1989 - implementace modelu chování při hledání potravy Eblingem a jeho kolegy [7] ;
1991 - M. Dorigo ve své doktorské disertační práci (která vyšla v roce 1992) navrhl koncept "ant system".
2001 – IREDA a spolupracovníci zveřejnili první víceúčelový algoritmus [8]
2002 - první aplikace ve vývoji grafiky, Bayesovské sítě ;
2002 – Bianchi a její kolegové navrhli první stochastický algoritmus [9] ;
2004 - Zlochin a Dorigo ukazují, že některé algoritmy jsou ekvivalentní: stochastický gradient sestup, křížová entropie a algoritmy odhadu distribuce;
2005 - První aplikace při řešení problému skládání proteinů.

Přehled

Algoritmus je založen na chování mravenčí kolonie - značení úspěšnějších cest velkým množstvím feromonu . Práce začíná umístěním mravenců na vrcholy grafu (města), poté začíná pohyb mravenců - směr je určen pravděpodobnostní metodou na základě vzorce tvaru:

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

kde:

P_{i}

je pravděpodobnost pohybu po cestě ,

i

l_{i}

je převrácená hodnota hmotnosti (délky) tého přechodu,

i

f_{i}

je množství feromonu na té křižovatce,

i

q

je hodnota, která určuje „chamtivost“ algoritmu,

p

- hodnota, která určuje "herding" algoritmu.

Řešení není přesné a může být dokonce jedno z nejhorších, nicméně díky dobře zvolené heuristice iterativní aplikace algoritmu obvykle dává výsledek, který se blíží optimálnímu.

V literatuře bylo navrženo několik metaheuristických modelů ACO. Tři z nejúspěšnějších z nich jsou:

mravenčí systém (Dorigo 1992, Dorigo et al. 1991, 1996),
mravenčí koloniální systém (ACS) (Dorigo & Gambardella 1997),
MAX-MIN mravenčí systém (MMAS) (Stutzle & Hoos 2000).

Shrnutí

Ve skutečném světě mravenci (zpočátku) chodí náhodně a poté, co najdou potravu, se vracejí do své kolonie a šíří stezky feromony . Pokud ostatní mravenci najdou takové cesty, je pravděpodobnější, že je budou následovat. Místo toho, aby řetězec sledovali, posílí ho, když se vrátí, pokud nakonec najdou zdroj potravy. Časem se feromonová stopa začne vypařovat, čímž se sníží její přitažlivá síla. Čím více času trvá cesta k cíli a zpět, tím více se feromonová stopa vypaří. Oproti tomu na krátké dráze bude průchod rychlejší a v důsledku toho zůstává hustota feromonů vysoká. Odpařování feromonů má také funkci vyhnout se hledání lokálně optimálního řešení. Pokud by se feromony neodpařily, pak by cesta zvolená jako první byla nejatraktivnější. V tomto případě by byly studie prostorového řešení omezené. Když tedy jeden mravenec najde (například krátkou) cestu z kolonie ke zdroji potravy, ostatní mravenci se s větší pravděpodobností po této cestě vydají a pozitivní zpětná vazba nakonec vede všechny mravence na stejnou nejkratší cestu.

Přečtěte si více

Původní myšlenka pochází z pozorování mravenců, jak nacházejí nejkratší cestu z kolonie ke zdroji potravy.

První mravenec najde zdroj potravy (F) jakýmkoli způsobem (a) a poté se vrátí do hnízda (N), přičemž za sebou zanechá feromonovou stopu (b).
Poté si mravenci vyberou jednu ze čtyř možných cest, poté ji zpevní a zatraktivní.
Mravenci se vydávají nejkratší cestou, protože feromony z delších cest se rychleji vypařují.

Mezi experimenty na výběr mezi dvěma cestami nestejné délky vedoucími z kolonie ke zdroji potravy si biologové všimli, že mravenci zpravidla používají nejkratší cestu [6] [10] . Model tohoto chování je následující:

Z kolonie náhodně prochází mravenec (zvaný „Blitz“).
Pokud najde zdroj potravy, vrátí se do hnízda a zanechá za sebou feromonovou stopu.
Tyto feromony přitahují další blízké mravence, u kterých je pravděpodobnější, že se touto cestou vydají.
Jakmile se vrátí do hnízda, posílí feromonovou stopu.
Pokud existují 2 trasy, stihne za stejnou dobu projít více mravenců po kratší než po dlouhé.
Kratší trasa se stane atraktivnější.
Dlouhé cesty časem zmizí v důsledku odpařování feromonů.

Mravenci využívají prostředí jako prostředek komunikace. Informace si vyměňují nepřímo, prostřednictvím feromonů, v rámci své „práce“. Výměna informací je lokální povahy: dozvědět se o nich mohou pouze mravenci, kteří se nacházejí v bezprostřední blízkosti feromonových stezek. Takový systém se nazývá stigmergie a platí pro mnoho společenských zvířat (byl studován pro případ stavění sloupů v termitích hnízdech). Tento mechanismus řešení problémů je velmi složitý a je dobrým příkladem samoorganizace systému. Takový systém je založen na pozitivní (ostatní mravenci posilují feromonovou stopu) a negativní (vypařování feromonové stopy) zpětné vazbě. Teoreticky, pokud počet feromonů zůstane stejný v průběhu času na všech trasách, pak nebude možné zvolit cestu. Díky zpětné vazbě však malé výkyvy způsobí, že jedna z tras zesílí a systém se stabilizuje směrem k nejkratší cestě.

Variace algoritmu

Následují některé z nejpopulárnějších variant algoritmu mravenčí kolonie.

Elite Ant System

Z celkového počtu mravenců vynikají tzv. „elitní mravenci“. Podle výsledků každé iterace algoritmu jsou nejlepší trasy posíleny průchodem elitních mravenců po těchto cestách a tím se zvyšuje počet feromonů na těchto cestách. V takovém systému je počet elitních mravenců dalším parametrem, který je třeba určit. Takže pro příliš mnoho elitních mravenců se algoritmus může zaseknout v místních extrémech.

MMAS (Max-Min ant system) [11]

Přidány okrajové podmínky pro počet feromonů (τ min ,τ max ). Feromony jsou ukládány pouze na globálně nejlepší nebo nejlepší v iteračních cestách. Všechny hrany jsou inicializovány hodnotou τ max .

Proporcionální pseudonáhodná pravidla

Uvedeno výše[ upřesnit ] [12] .

Ant ranking system (ASrank)

Všechna řešení jsou seřazena podle jejich vhodnosti. Počet deponovaných feromonů pro každý roztok je vážen tak, aby vhodnější roztoky obdržely více feromonů než méně vhodné.

Dlouhodobá ortogonální kolonie mravenců (COAC)

Mechanismus ukládání feromonů COAC umožňuje mravencům hledat řešení společně a efektivně. Pomocí ortogonální metody mohou mravenci v proveditelné oblasti prozkoumat své zvolené oblasti rychle a efektivně, s vylepšenou schopností globálního vyhledávání a přesností.

Metodu ortogonálního plánování a metodu adaptivního řízení poloměru lze také rozšířit na další optimalizační algoritmy a získat tak širší výhody při řešení praktických problémů [13] .

Konvergence

Aplikace

Příklad: pseudokód a vzorec

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

Hrany:
Mravenec se bude pohybovat z uzlu do uzlu s pravděpodobností: $i$ $j$

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

, kde:

\tau_{i,j}

je počet feromonů na okraji ;

i,j

\alpha

je parametr, který řídí vliv ;

\tau_{i,j}

\eta_{i,j}

atraktivita okraje (počáteční hodnota, obvykle , kde d je vzdálenost);

i,j

1/d_{{i,j}}

\beta

je parametr, který řídí vliv .

\eta_{i,j}

Aktualizace feromonů

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

kde:

\tau_{i,j}

je množství feromonu na oblouku ,

i,j

\rho

je rychlost odpařování feromonů,

\Delta \tau _{i,j}

je množství uloženého feromonu, obvykle definovaného jako:

\Delta \tau _{i,j}^{k}={\begin{cases}1/L_{k}&{\mbox{if ant }}k{\mbox{ cestuje na hraně }}i,j\ \0&{\mbox{inak}}\end{cases}}

kde je cena mravenčí tý cesty (obvykle délka). $L_{k}$ $k$

Další příklady

Workshop: problémy plánování Auto: problém se směrováním

Nejviditelnější a nejoblíbenější oblastí použití algoritmů mravenčích kolonií je dopravní logistika. Úkoly dopravní logistiky zahrnují takové NP-obtížné úkoly, jako je problém cestujícího prodejce a směrování vozidel [14] .

Problém zadání Zadaný úkol

Potíže s definováním

Algoritmy Stigmergy

Termín „stigmergie“ zavedl francouzský biolog P.-P. Grasse v roce 1959 popsat chování termitů . Definoval to jako: „ Stimulace pracovníků zvýšením jejich produktivity. » Termín pochází ze dvou řeckých slov „stigma“ (znamení, značka) a „ergo“ (práce, jednání) [15] .

Viz také

Poznámky

↑ A. Colorni, M. Dorigo et V. Maniezzo, Distributed Optimization by Ant Colonies , actes de la première conférence européenne sur la vie artificielle, Paříž, Francie, Elsevier Publishing, 134-142, 1991.
↑ M. Dorigo, Optimalizace, učení a přirozené algoritmy , PhD práce, Politecnico di Milano, Itálie, 1992.
↑ P.-P. Grasse, La rekonstrukce du nid et les koordinace inter-individuelles chez Belicositermes natalensis et Cubitermes sp. La theorie de la Stigmergie: Essai d'interpretation du comportement des termites constructeurs , Insectes Sociaux, číslo 6, s. 41-80, 1959.
↑ JL Denebourg, JM Pasteels a JC Verhaeghe, Pravděpodobnostní chování mravenců: strategie chyb? , Journal of Theoretical Biology, číslo 105, 1983.
↑ F. Moyson, B. Manderick, Kolektivní chování mravenců: příklad sebeorganizace v masivním paralelismu , Actes de AAAI Spring Symposium on Parallel Models of Intelligence, Stanford, Kalifornie, 1988.
↑ 1 2 S. Goss, S. Aron, J.-L. Deneubourg a J.-M. Pasteels, Samoorganizovaný průzkumný vzor argentinského mravence , Naturwissenschaften, svazek 76, strany 579-581, 1989
↑ M. Ebling, M. Di Loreto, M. Presley, F. Wieland a 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 a M. Middendorf, Bi-Criterion Optimization with Multi Colony Ant Algorithms , Evolutionary Multi-Criterion Optimization, First International Conference (EMO'01), Curych, Springer Verlag, str. 359–372, 2001.
↑ L. Bianchi, LM Gambardella et M. Dorigo, An ant kolonie optimalizace přístupu k problému pravděpodobnostního cestujícího prodejce , PPSN-VII, Sedmá mezinárodní konference o paralelním řešení problémů z přírody, Poznámky k přednáškám z informatiky, Springer Verlag, Berlín, Allemagne , 2002.
↑ J.-L. Deneubourg, S. Aron, S. Goss a J.-M. Pasteels, Samoorganizující se průzkumný vzor argentinského mravence , Journal of Insect Behaviour, svazek 3, strana 159, 1990
↑ T. Stützle a HH Hoos, MAX MIN Ant System , Future Generation Computer Systems, svazek 16, strany 889–914, 2000
↑ M. Dorigo a LM Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem , IEEE Transactions on Evolutionary Computation, svazek 1, číslo 1, strany 53-66, 1997.
↑ X Hu, J Zhang a Y Li (2008). Ortogonální metody založené na hledání mravenčích kolonií pro řešení průběžných optimalizačních problémů. Journal of Computer Science and Technology , 23(1), s.2-18.
↑ Kazharov A. A., Kureichik V. M. Ant algoritmy pro řešení dopravních problémů. Novinky Ruské akademie věd. Teorie a řídicí systémy. 2010. č. 1. S. 32-45.
↑ Bonabeau, E. "Úvod editora: Stigmergie." speciální vydání umělého života na Stigmergy. Ročník 5, číslo 2 / jaro 1999, s.95-96. http://www.stigmergicsystems.com/stig_v1/stigrefs/article1.html

Literatura

M. Dorigo , 1992. Optimalizace, učení a přirozené algoritmy , PhD práce, Politecnico di Milano, Itálie.
M. Dorigo, V. Maniezzo & A. Colorni, 1996. "Ant System: Optimization by a Colony of Cooperating Agents", IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1): 29-41.
M. Dorigo & LM Gambardella , 1997. "Systém mravenčí kolonie: Kooperativní učební přístup k problému cestujícího obchodníka." IEEE Transactions on Evolutionary Computation, 1(1): 53-66.
M. Dorigo, G. Di Caro & LM Gambardella, 1999. "Ant Algorithms for Discrete Optimization". Umělý život, 5(2): 137-172.
E. Bonabeau, M. Dorigo a G. Theraulaz, 1999. Swarm Intelligence: From Natural to Artificial Systems , Oxford University Press. ISBN 0-19-513159-2
M. Dorigo & T. Stützle, 2004. Optimalizace kolonií mravenců , MIT Press. ISBN 0-262-04219-3
M. Dorigo, 2007. Optimalizace kolonie mravenců . Scholarpedia.
C. Blum, 2005 Optimalizace mravenčích kolonií: Úvod a současné trendy. Physics of Life Reviews, 2: 353-373
Algoritmy Shtovba S. D. Ant, Exponenta Pro. Matematika v aplikacích. 2004. č. 4
Kirsanov M.N. Grafy v Maple. — M .: Fizmatlit , 2007. — 168 s. - ISBN 978-5-9221-0745-7 . http://vuz.exponenta.ru/PDF/book/GrMaple.pdf http://eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
M. Dorigo, M. Birattari & T. Stützle, 2006 Optimalizace mravenčí kolonie: Umělí mravenci jako technika výpočetní inteligence .

Odkazy

Optimalizační metody
Jednorozměrný	metoda zlatého řezu Dichotomie Parabolová metoda Vyhledávání v mřížce Jednotná metoda vyhledávání bloků Fibonacciho metoda Ternární hledání Piyavského metoda Stronginovou metodou
Nulové pořadí	Gaussova metoda Metoda Nelder-Mead Hook-Jeevesova metoda Rosenbrockova metoda Powellova metoda
První objednávka	gradientní sestup Zeutendijkova metoda Souřadnicový sestup Metoda konjugovaného gradientu Kvazi-newtonské metody Levenberg-Marquardtův algoritmus
druhá objednávka	Newtonova metoda Newton-Raphsonova metoda Algoritmus Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastické	Metoda Monte Carlo Simulované žíhání Evoluční algoritmy diferenciální evoluce Algoritmus mravenců Metoda roje částic Algoritmus včelstva Metoda náhodné chůze
Metody lineárního programování	Simplexní metoda Gomoriho algoritmus Elipsoidní metoda Potenciální metoda
Metody nelineárního programování	Sekvenční kvadratické programování