Algoritmus roje částic / Habr

Tanec je pro včely způsob komunikace. Tímto způsobem si navzájem sdělují určité informace. Existuje několik druhů včelího tance. Každý má své vlastní charakteristiky a význam. Včely vnímají prostor zvláštním způsobem, což se odráží v signálním systému.

Význam tance pro včely

Tanec slouží hmyzu jako jakýsi kompas. Na jaře a v létě hledají zvědové zdroj nektaru a pylu a když ho najdou, vracejí se do úlu a předávají informaci sběračům. Signalizační jedinec tancem ukazuje směr vzhledem ke slunci:

• vrtící se pohyby směrem nahoru znamenají, že musíte letět směrem ke slunci;
• při pohybu v přímé linii – odletět od slunce;
• Pokud se odchýlíte doprava nebo doleva, je třeba provést příslušnou korekci za letu.

Kritické parametry pro úspěšné pochopení včelího tance

• ✓ Úhel odchylky od slunce, který není v článku specifikován, ale je klíčový pro přesné určení směru k medonosné rostlině.
• ✓ Rychlost vibrací těla včely během tance, která ovlivňuje vnímání informací ostatními včelami.

Díky tomuto systému včely sbírají nektar a pyl z konkrétní medonosné rostliny. Referenčním bodem je její aroma. To umožňuje získat určitý druh medu odpovídající dané rostlině – akát, lípa, vřes a další. Jaké druhy a odrůdy medu existují, si přečtěte zde.

Mechanismus takové komunikace je částečně spojen s vibracemi. Tělo hmyzu vibruje v důsledku kontrakce silných křídelních svalů, ale na rozdíl od letu jsou křídla během tance složená.

Vibrace signální včely se šíří po celém povrchu plástve, takže ji vnímají i ostatní jedinci. Signál vnímají pouze hmyz nacházející se ve stejném úlu.

Mnoho vědců pochybovalo o možnosti komunikace mezi hmyzem s drobnými mozky. Tento komunikační mechanismus byl potvrzen díky malému robotovi, který detailně reprodukoval všechny nuance tance. Na jeho signál musely včely letět ke speciálně uspořádaným krmítkům – experiment byl naprostým úspěchem.

Kruhový tanec

Při tomto typu tance včela provádí krouživé pohyby. Tímto způsobem signalizuje svým příbuzným, že se v blízkosti úlu – v okruhu asi 45 m – nachází bohatý zdroj nektaru a pylu.

Během kruhového tance signální včela neukazuje směr, kterým se má pohybovat do oblasti, kterou našla. Sběračky přilákané zvědem ji obklopí a pohybují se za ní. Směr jim udává vůně květů, které zůstávají na břiše hmyzu, který medonosnou rostlinu našel. Její vnímání zajišťují tykadla včely.

Kruhový tanec zvědů trvá jen několik sekund, ale stačí k přilákání dalších dělnic a předání jim potřebných informací. Včela začne tančit poté, co rozdá nasbíraný nektar – během tance ho také vylučuje. Po skončení tance se hmyz okamžitě vydá ke vchodu a odtud – ke květinám, které našel. Když včela znovu přinese potravu, začne znovu tančit. To potvrzuje, že našel bohatý zdroj výživy.

Během kruhového tance opakují blízcí jedinci pohyby zvědkyně a snaží se dotknout se jejího břicha svými tykadly. Poté se tyto včely medonosné začnou připravovat k letu – očistí se a zamíří ke vchodu.

Kroužící a kymácející se tanec včel

Vrtivý tanec

Pohyby během tohoto tance připomínají osmičku a jsou půlkruhové. Včela běží rovně a vrtí břichem. Počet máchnutí určuje blízkost nalezené medonosné rostliny. Čím více hmyz vrtí břichem, tím blíže je zdroj potravy. 8 máchnutí za sekundu znamená, že medonosná rostlina je od úlu vzdálena 6 km. Pokud včela provede 20 pohybů za sekundu, pak je zdroj potravy vzdálen asi kilometr.

Varování při interpretaci tance včel

• × Neberte v úvahu změny v chování včel za různých povětrnostních podmínek, což může vést k chybám při určování směru k medonosné rostlině.
• × Ignorujte individuální rozdíly v tancích různých včel, které mohou zkreslovat vnímanou informaci.

Včely se uchylují k kývavému tanci, když jsou medonosné rostliny ve velké vzdálenosti. Ten je určen nejen počtem chlopní břicha, ale i počtem kruhů, které udělají. Pokud je medonosná rostlina od úlu vzdálena přibližně 100 m, včela udělá přibližně 10 kruhů za 15 sekund. Pokud udělá 7 kruhů za stejnou dobu, pak je vzdálenost dvakrát větší, 4 kruhy – 1 km, 2 kruhy – 6 km.

Včely skautky mohou zkreslovat údaje o vzdálenosti k medovníku. Záleží na povětrnostních podmínkách. Při protivětru se pohyb včely zpomaluje a při zadním zrychluje, takže mohou být přítomny nějaké chyby.

Svým kývavým tancem může včela nejen určit vzdálenost nalezené medonosné rostliny, ale také naznačit směr, kterým má letět. Pokud hmyz tančí na letovém otvoru (vodorovně), pak čára spojující osmičku představuje směr k medonosné rostlině. Mezi půlkruhy osmičky je vytvořena určitá vzdálenost – ta odpovídá úhlu odchylky letu vzhledem ke slunci.

Tanec ve včelím úlu

Kruhové a kývavé tance jsou účinné a informativní, když je jasné počasí a jasná obloha. Včely ve tmě nevidí, ale určité informace vnímají čichem a hmatem.

Zvěd může určit směr, ve kterém se medonosná rostlina nachází, následovně:

• přímočarý pohyb po plástve – zdroj potravy na straně opačné než slunce;
• pohyb vzhůru – medonosná rostlina je umístěna směrem ke slunci.

1 – tanec mimo úl; 2 – kruhový tanec uvnitř úlu; 3 – kyvadlový tanec, pohyb dolů; 4 – kyvadlový tanec, pohyb nahoru; 5 – vertikální verze tance 1

Tancem mohou včely pouze ukázat vzdálenost, ve které se medonosná rostlina nachází, a směr k ní. Hmyz nemůže udávat výšku umístění potravy. Potvrdily to pokusy s vysoko zavěšenými krmítky.

Včelí vnímání prostoru

Včely mají složené oči, které představují ommatidie (strukturální prvky). Tato vlastnost jim poskytuje mozaikové vidění – hmyz nevidí celý obraz, ale každý objekt zvlášť.

Včely mají oči lámající světlo, takže pro normální orientaci je nutné jasné počasí. Díky polaroidům se hmyz dokáže orientovat i v nepřítomnosti slunce, ale je potřeba alespoň malá mezera, jinak se včela může odchýlit ze správného směru.

Tanec je způsob, jakým se včely dorozumívají. Prováděním určitých pohybů může hmyz sdělit svému úlu, jak daleko a kterým směrem se medonosná rostlina nachází. Slunce je pro včelu referenčním bodem, takže se aktivně pohybuje pouze za jasného počasí.

Hejno ptáků je skvělým příkladem kolektivního chování zvířat. Letí ve velkých skupinách a ve vzduchu se téměř nikdy nesrazí. Hejno se pohybuje plynule a koordinovaně, jako by ho někdo řídil. A každý, kdo si někdy na zahradě pověsil krmítko pro ptáky, ví, že během několika hodin ho najdou všichni ptáci v okolí.

Nejde o to, aby vůdce dával rozkazy – v mnoha ptačích hejnech prostě žádný vůdce neexistuje. Hejno je, podobně jako kolonie mravenců nebo včel, rojovou inteligencí. Ptáci v něm jednají podle určitých – poměrně jednoduchých – pravidel. Krouží na obloze, každý pták sleduje své příbuzné a koordinuje svůj pohyb podle jejich polohy. A jakmile najde zdroj potravy, upozorní je na to.

Poslední skutečnost by měla být diskutována podrobněji, protože hraje jednu z klíčových rolí v uvažované optimalizační metodě. Důvody takového „altruismu“ ptáků (a dalších zvířat jednajících podobným způsobem) byly předmětem výzkumu mnoha sociobiologů. Jedním z nejpopulárnějších vysvětlení tohoto jevu je, že výhody takového chování pro každého jedince v hejnu jsou větší než takové zjevné nevýhody, jako je nutnost soutěžit s ostatními jedinci o potravu, kterou najdou.

Zdroje potravy jsou obvykle umístěny náhodně, takže jeden pták sám o sobě může klidně dlouho uhynout, aniž by je našel. Pokud však všichni ptáci „dodržují pravidla“ a sdílejí informace o svých nálezech se svými příbuznými, pak se šance na přežití každého z nich dramaticky zvyšují. Taková strategie je tedy pro jednotlivce neúčinná, ale klíčem k efektivitě hejna i druhu jako celku.

Boidy

Pozorování ptáků inspirovalo Craiga Reynoldse k vytvoření počítačového modelu, který v roce 1986 nazval Boids. Aby simuloval chování hejna ptáků, Reynolds naprogramoval chování každého ptáka zvlášť a také jejich interakce. Udělal to pomocí tří jednoduchých principů. Zaprvé, každý pták v jeho modelu se snažil vyhnout srážkám s ostatními ptáky. Zadruhé, každý pták se pohyboval stejným směrem jako ptáci v okolí. Zatřetí, ptáci se od sebe obvykle pohybovali ve stejné vzdálenosti.

Výsledky prvních simulací překvapily i samotného tvůrce: navzdory jednoduchosti algoritmů, které byly základem programu, vypadalo hejno na obrazovce extrémně realisticky. Ptáci se shromažďovali ve skupinách, vyhýbali se srážkám a dokonce chaoticky létali stejně jako skuteční.
Craig Reynolds se jako specialista na počítačovou grafiku zajímal především o vizuální stránku výsledků simulace, kterou vytvořil. V článku věnované Boidům však také poznamenal, že model chování, který vyvinul, by mohl být rozšířen zavedením dalších faktorů, jako je shánění potravy nebo strach z predátorů [1].

Klasický algoritmus roje částic

V roce 1995 navrhli James Kennedy a Russell Eberhart metodu pro optimalizaci spojitých nelineárních funkcí, kterou nazvali algoritmus roje částic [2]. Inspirovali se Reynoldsovým simulačním modelem a podobnou prací Heppnera a Grenadera [4]. Kennedy a Eberhart poznamenali, že oba modely jsou založeny na řízení vzdáleností mezi ptáky – a proto je synchronizace hejna funkcí úsilí, které ptáci vynakládají k udržení optimální vzdálenosti.

Algoritmus, který vyvinuli, je poměrně jednoduchý a lze jej implementovat doslova v několika desítkách řádků kódu v jakémkoli programovacím jazyce vyšší úrovně. Modeluje multiagentní systém, kde se částicoví agenti pohybují směrem k optimálním řešením a vyměňují si informace se svými sousedy.

Aktuální stav částice je charakterizován souřadnicemi v prostoru řešení (tj. řešením, které je s nimi spojeno), a také vektorem rychlosti. Oba tyto parametry jsou náhodně voleny ve fázi inicializace. Každá částice navíc ukládá souřadnice nejlepšího nalezeného řešení a také nejlepšího řešení, které prošlo všemi částicemi – simuluje se tak okamžitá výměna informací mezi ptáky.

V každé iteraci algoritmu se směr a délka vektoru rychlosti každé částice mění v souladu s informacemi o nalezených optimech:

kde je vektor rychlosti částice ( je její i-tá složka), , jsou konstanty zrychlení, je nejlepší bod nalezený částicí, je nejlepší bod, kterým projdou všechny částice v systému, je aktuální poloha částice a funkce vrací náhodné číslo od 0 do 1 včetně.

Po výpočtu směru vektoru se částice přesune do bodu . V případě potřeby se aktualizují hodnoty nejlepších bodů pro každou částici a pro všechny částice jako celek. Poté se cyklus opakuje.

Modifikace klasického algoritmu

Algoritmus roje částic se objevil relativně nedávno, ale různí výzkumníci již navrhli řadu jeho modifikací a stále se publikují nové práce na toto téma. Lze identifikovat několik způsobů, jak klasický algoritmus vylepšit, které jsou implementovány ve většině z nich. Jedná se o kombinování algoritmu s jinými optimalizačními algoritmy, snížení pravděpodobnosti předčasné konvergence změnou charakteristik pohybu částic a dynamickou změnu parametrů algoritmu během optimalizace. Nejvýznamnější modifikace jsou diskutovány níže.

LBEST

Později v roce 1995 Kennedy a Eberhart publikovali článek, ve kterém původní algoritmus nazvali „GBEST“, protože používá globálně nejlepší řešení pro generování vektorů rychlosti, a navrhli jeho modifikaci, kterou nazvali „LBEST“. Při aktualizaci směru a rychlosti částice LBEST používá informace o řešeních sousedních částic:

kde je nejlepší výsledek mezi částicí a jejími sousedy. Za sousedy se považují buď částice, které se od daného indexu liší maximálně o určitou specifikovanou hodnotu, nebo částice, jejichž vzdálenost nepřesahuje specifikovanou prahovou hodnotu.

Tento algoritmus prozkoumává prohledávací prostor důkladněji, ale je pomalejší než originál. Zároveň platí, že čím menší počet sousedů je brán v úvahu při formování vektoru rychlosti, tím nižší je rychlost konvergence algoritmu, ale tím efektivněji se vyhýbá suboptimálním řešením.

PSO vážené setrvačností

V roce 1998 navrhli Yuhui Shi a Russell Eberhart modifikaci, která se na první pohled jen mírně liší od klasického algoritmu [5]. Ve svém článku Shi a Eberhart poznamenali, že jednou z hlavních výzev při řešení optimalizačních problémů je rovnováha mezi důkladností prozkoumání vyhledávacího prostoru a rychlostí konvergence algoritmu. V závislosti na problému a charakteristikách vyhledávacího prostoru v něm by se tato rovnováha měla lišit.
S ohledem na to Shi a Eberhart navrhli změnit pravidlo pro aktualizaci vektorů rychlosti částic:

Koeficient , který nazvali koeficientem setrvačnosti, určuje zmíněnou rovnováhu mezi šíří studie a pozorností věnovanou nalezeným suboptimálním řešením. V případě , kdy , se rychlosti částic zvětšují, rozlétají se a důkladněji prozkoumávají prostor. V opačném případě se rychlosti částic v průběhu času snižují a rychlost konvergence v tomto případě závisí na volbě parametrů a .

Časově proměnný setrvačný vážený PSO

Ve svém článku z roku 1998 Shi a Eberhart poznamenali, že setrvačnost nemusí být nutně kladná konstanta: může se během fungování algoritmu měnit podle lineárního nebo dokonce nelineárního zákona [5]. V článku z roku 1999 a pozdějších pracích nejčastěji používali lineární zákon poklesu, protože je dostatečně efektivní a zároveň jednoduchý [6]. Byly však vyvinuty a úspěšně aplikovány i jiné zákony změny setrvačnosti.

Hodnota koeficientu setrvačnosti se může buď snižovat, nebo zvyšovat. Když se sníží, částice nejprve extenzivně prozkoumávají oblast hledání a nacházejí mnoho suboptimálních řešení, a postupem času se stále více soustředí na prozkoumávání svého okolí. Zvýšení setrvačnosti podporuje konvergenci algoritmu v pozdějších fázích operace.

Kanonický PSO

V roce 2002 navrhli Maurice Clerc a James Kennedy svou modifikaci algoritmu roje částic, která se stala tak populární, že se nyní nazývá kanonický algoritmus roje částic [7]. Eliminuje nutnost „hádat“ vhodné hodnoty nastavitelných parametrů algoritmu sledováním konvergence částic.

Clair a Kennedy změnili způsob výpočtu vektorů rychlosti částic zavedením dalšího faktoru:

kde a kompresní poměr je:

Tento přístup zaručuje konvergenci algoritmu bez nutnosti explicitně řídit rychlost částic.

Plně informovaný roj částic

Ve svém článku z roku 2004 Rui Mendes, James Kennedy a José Neves poznamenali, že předpoklad kanonického algoritmu roje částic, že každá částice je ovlivněna pouze tou nejúspěšnější, je v rozporu se základními přirozenými mechanismy a může vést ke snížení účinnosti algoritmu [8]. Naznačili, že nadměrné zaměření algoritmu na jediné řešení může vést ke ztrátě důležitých informací o struktuře vyhledávacího prostoru.

Na základě toho se rozhodli, že všechny částice budou „plně informované“, tj. budou přijímat informace od všech sousedních částic. Aby toho dosáhli, změnili zákon změny rychlosti v kanonickém algoritmu:

kde je množina sousedů částice, je nejlepší z bodů, kterými prochází k-tý soused. je váhová funkce, která může odrážet jakoukoli charakteristiku k-té částice, která je považována za důležitou: hodnotu účelové funkce v bodě, kde se nachází, vzdálenost od něj k dané částici atd.

Závěr

V prvním článku popisujícím algoritmus roje částic James Kennedy a Russell Eberhart navrhli myšlenku použití algoritmu k simulaci sociálního chování – Kennedyho jako sociálního psychologa tato myšlenka nesmírně přitahovala [1]. Algoritmus však byl nejrozšířenější v problémech optimalizace komplexních vícerozměrných nelineárních funkcí.

Algoritmus roje částic je široce používán mimo jiné v úlohách strojového učení (zejména pro trénování neuronových sítí a rozpoznávání obrazů), parametrické a strukturální optimalizaci (tvary, velikosti a topologie) v oblasti designu, v oblastech biochemie a biomechaniky. Z hlediska efektivity může konkurovat jiným globálním optimalizačním metodám a jeho nízká algoritmická složitost přispívá k jednoduchosti jeho implementace.

Za nejslibnější oblasti dalšího výzkumu v tomto směru by měly být považovány teoretické studie důvodů konvergence algoritmu roje částic a souvisejících otázek z oblastí rojové inteligence a teorie chaosu, kombinace různých modifikací algoritmu pro řešení složitých problémů, zvažování algoritmu roje částic jako multiagentního výpočetního systému a také studium možností zahrnutí analogií složitějších přírodních mechanismů.

Literatura

[1] Craig Reynolds, „Hejna, stáda a školy: Distribuovaný behaviorální model“, Computer Graphics, 21(4), str. 25–34, 1987.
[2] J. Kennedy, R. C. Eberhart, „Optimalizace roje částic“, In Proceedings of the IEEE International Conference on Neural Networks, s. 1942–1948, 1995.
[3] R. C. Eberhart, J. Kennedy, „Nový optimalizátor využívající teorii roje částic“ // Sborník šestého mezinárodního sympozia o mikrostrojích a humanitních vědách MHS’95, s. 39–43, 1995.
[4] F. Heppner, U. Grenander, „Stochastický nelineární model pro koordinovaná hejna ptáků“ // Všudypřítomnost chaosu, s. 233–238, 1990.
[5] Y. Shi, R. Eberhart, „Modifikovaný optimalizátor roje částic“, Sborník z Mezinárodní konference IEEE o evolučních výpočtech 1998, str. 69–73, 1998.
[6] Y. Shi, R. Eberhart, „Empirická studie optimalizace roje částic“, Sborník z konference IEEE Congress on Evolutionary Computation z roku 1999, s. 1945–1950, 1999.
[7] M. Clerc, J. Kennedy, „Roj částic – exploze, stabilita a konvergence v multidimenzionálním komplexním prostoru“ // IEEE Transactions on Evolutionary Computation, č. 6 (1), s. 58–73, 2002.
[8] R. Mendes, J. Kennedy, J. Neves, „Plně informovaný roj částic: Jednodušší, možná i lepší“ // IEEE Transactions on Evolutionary Computation, č. 8 (3), s. 204–210, 2004.

• algoritmus roje částic
• inteligence roje
• Pes
• roj částic