Inteligence hejna

Technology

12 hours ago

Author

Inteligence hejna (angl. swarm intelligence - SI) je kolektivní chování decentralizovaných, samo-organizovaných systémů přírodních či umělých. Využívá ji technika umělé inteligence. Výraz zavedli Gerardo Beni a Jing Wang v roce 1989, v kontextu celulárních robotických systémů.

Tyto systémy se obvykle skládají z populace jednoduchých agentů, kteří interagují lokálně mezi sebou a se svým okolím. Agenti se řídí velmi jednoduchými pravidly. +more Přestože neexistuje centralizovaná struktura řízení, která určuje, jak se mají chovat jednotlivci, lokální interakce mezi těmito agenty vedou ke vzniku složitého globálního chování.

Přírodní příklady inteligence hejna zahrnují mravenčí kolonie, hejna ptáků, zvířata ve stádech, bakteriální růst a hejna ryb. Přesto může jít pouze o snahu jednotlivců udržovat si maximální možnosti. +more Chování, které vytváří zvířecí hejna, může být značně jednoduché a to i s prvky náhody.

Uplatnění zásad hejna na roboty se nazývá robotika hejna, zatímco termín 'inteligence hejna' odkazuje na obecnější soubor algoritmů.

Algoritmy založené na inteligenci hejna

Inteligence hejna je na jednu stranu významný náhled na implementaci adaptivních systémů. V tomto smyslu se jedná o rozšíření evolučních algoritmů. +more Na druhou stranu lze tuto ideu považovat za rozšíření celulárních automatů. O technikách bližším evolučním algoritmům existuje mnoho vědeckých článků, zmíněný druhý pohled je v tomto směru novější a méně prozkoumaný.

Většina současných postupů využívajících paradigmatu hejna optimalizuje účelovou funkci, v závislosti na definici se pak snažíme najít globální minimum nebo maximum dané funkce. Algoritmy často nabízejí i vícero řešení. +more To má význam, pokud existuje globálních optim více a nás nezajímá jen jedno. Potom hovoříme o multimodální optimalizaci.

Tyto postupy lze považovat za metaheuristiky prohledávající prostor odpovídající definičnímu oboru účelové funkce. Jejím definičním oborem je typicky n-dimenzionální eukleidovský prostor, nejedná se však o podmínku, protože mnoho z algoritmů prohledává i diskrétní prostor. +more Prohledávací prostor není obvykle prohledán celý, nejedná se tedy o úplné prohledávání a většinou nelze nic zaručit o nalezeném řešení.

Výhodou těchto metod je obvykle rychlost a nízká výpočetní náročnost oproti metodám jiným. Významným přínosem je schopnost poskytnout alespoň přibližné řešení tam, kde nám často ani není známo, zda existuje nějaký exaktní postup jak řešení najít.

Průběh prohledávání lze ve většině případů takto neformálně zjednodušit: K prohledávání prostoru máme k dispozici nějaké hejno, které sestává z jednotlivých členů. Členové hejna jsou na počátku v prostoru náhodně rozmístěni. +more Následně se iteruje zlepšovací krok, který se buď provádí konstantně-krát, nebo dokud nenalezneme uspokojivé řešení, nebo dokud se daří řešení zlepšovat. Během zlepšovacího kroku se pozmění poloha členů hejna v závislosti na informacích, které zatím dohromady nasbírali. Právě v tomto sociálním chování spočívá síla tohoto přístupu. Často jsou méně úspěšní členové lákáni k pozici těch úspěšnějších. Ve skutečnosti však nemusí nutně docházet k jakýmkoliv zlepšením, nicméně i takové kroky mohou být nutné, aby hejno neuvízlo v lokálním minimu (resp. maximu).

Problém zachycení v lokálním optimu je často označován i jako problém předčasné konvergence. Pokud bychom se dívali na polohu každého člena hejna v čase jako na řadu, některé algoritmy (například optimalizace hejnem částic) postupně s časem zmenšují změny poloh částic, aby se ustálila jejich poloha. +more Pokud je toto zpomalení příliš prudké, hrozí uvíznutí v lokálním optimu. Naopak nedostatečné ustálení polohy částic může vést ke zbytečně nepřesnému řešení, které stačilo malými opatrnými změnami zlepšit. Toto je známo i jako problém explorace versus exploatace.

Následující seznam používaných technik nelze považovat za úplný, neboť tento obor se stále vyvíjí a neustále vzniká hojně modifikací původních algoritmů, hybridní metody a i zcela nové přístupy.

Optimalizace hejnem částic

V originále Particle Swarm Optimization (PSO). Hejno sestává z jednotlivých částic, které se pohybují v prohledávacím prostoru. +more Každá částice má svoji polohu a vektor rychlosti. Rychlost se pak upravuje v závislosti na doposud nalezených optimech (správněji kvazioptimech) celým hejnem a částicí samotnou. Existuje celá řada modifikací tohoto postupu, hejno se často rozděluje do menších "pod-hejn" resp. nik. Zavádí se různé topologie, které definují jak si mezi sebou částice vyměňují informace.

Optimalizace mravenčí kolonií

V originále Ant Colony Optimization (ACO). Tento postup pracuje spíše s diskrétním prostorem. +more Ilustrativní příklady jeho použití jsou například hledání nejkratší cesty v grafu, nebo řešení problému obchodního cestujícího. Jednotliví mravenci pak prochází grafem a v navštívených místech zanechávají feromon. Každý mravenec, který pak stojí před rozhodnutím kudy se vydat, volí s vyšší pravděpodobností ten směr, kde se nachází silnější feromonová stopa. Feromonová stopa se s časem vytrácí. Charakteristickým prvkem této metody je výměna informace mezi členy hejna skrze prostředí.

Optimalizace včelím rojem

Toto téma zahrnuje celou skupinu algoritmů, které se inspirují chováním včel. Zásadní roli zde hraje přímá výměna informace mezi jednotlivými včelami na rozdíl od užití feromonu mravenčí kolonií. +more Obvykle je roj rozdělen na specializované skupiny: královny, průzkumné včely vyhledávající nové zdroje potravy, včely následující úspěšné průzkumné včely a podobně.

Optimalizace hejnem světlušek

V originále Glowworm Swarm Optimization. Autoři tohoto přístupu vybavují každého člena hejna virtuální svítivou látkou (luciferin) v závislosti na jeho úspěšnosti při procházení prohledávacím prostorem. +more Čím úspěšnější, tím více září a přitahuje ke své pozici ostatní světlušky. U každé světlušky se zároveň předpokládá omezená vzdálenost, kam až dohlédne. Tato vzdálenost se i dynamicky vyvíjí a algoritmus dosahuje zajímavých výsledků při multimodální optimalizaci.