Cesko.wiki Optimalizace včelím rojem
Author
Albert FloresOptimalizace včelím rojem je algoritmický přístup v oboru umělé inteligence, který se inspiruje v chování biologických včel a napodobuje některé jeho aspekty. Vychází z něho celá řada algoritmů, které podobně jako ostatní algoritmy využívající inteligence hejna vznikají převážně od roku 1990.
Algoritmy se inspirují buďto pářícím chováním včel, jejich způsobem hledání zdrojů potravy, nebo chováním v době hledání nového hnízda. Nejedná se o úplné metody, ale o heuristiky, které se snaží poskytnout co nejlepší přibližné řešení a zároveň udržet nízké výpočetní nároky.
Optimalizační metody napodobující pářící chování včel
Rozmnožování včel vyčnívá z obvyklého schématu páření, neboť se ho účastní z celého roje pouze včelí královna a trubci. Královna se spáří s větším množstvím trubců a jejich sperma v sobě uchovává. +more Takto nasbíranou genetickou informaci pak používá při plození potomstva, takže včely z jednoho roje mají různou genetickou výbavu. Tento fakt inspiroval vznik technik, které lze spíše řadit k evolučním výpočtům, protože používají principy selekce, křížení a mutace.
Honeybee Mating Optimisation Algorithm (HBMO)
Anglický název algoritmu lze přeložit jako Včelí pářící optimalizační algoritmus, vytvořil ho v roce 2001 Abbass. Tento algoritmus byl původně určen k řešení problému splnitelnosti booleovských formulí, byl však aplikován na celou řadu dalších problémů, například optimalizace užívání vodních zdrojů.
Včelí roj je rozdělen na 4 skupiny: matky, trubce, potomky a dělnice. Matky mají svá referenční řešení (jejich genetická informace) a sbírají nová řešení (řešením rozumíme bod prohledávacího prostoru). +more Každé nové řešení odpovídá jedné genetické informaci předané od trubce. Pravděpodobnost, že matka informaci od trubce akceptuje, závisí na kvalitě takového řešení, na kvalitě matčina referenčního řešení a na rychlosti a energii matky. Každá matka má tedy kromě nasbíraných genetických informací přiděleny dvě číselné proměnné - energii a rychlost. Energie i rychlost matky postupně klesá. Matka ukončí svoji fázi sbírání řešení (biologickou analogií je páření) v momentě, kdy buď má řešení dostatek nebo jí došla energie. Matka následně náhodně vybere nějaké ze shromážděných řešení a křížením se svým referenčním řešením vytvoří potomka. Potomek se tedy zrodí s novým vlastním referenčním řešením.
Jakmile vznikne nový potomek, přichází na řadu dělnice. Dělnice se snaží vylepšit referenční řešení potomka pomocí prohledávání jeho blízkého okolí. +more Jedná se tedy o lokálnímu hledání. Pokud je nový potomek lepší než nějaká z původních matek, taková matka bude nahrazena. Tento krok je běžný v evolučních algoritmech, zajišťuje omezenou velikost populace a nároky na výpočetní výkon.
Další algoritmy vycházející z páření včel
Algoritmů toho typu existuje velmi mnoho. Lze sem řadit Bee System, Queen-bee evolution, nebo včelami inspirovaný operátor křížení.
Optimalizační metody inspirované sháněním potravy
Včelí dělnice vyhledávají potravu v okolí úlu a pokud jsou úspěšné, předají ostatním včelám v úlu informaci o kvalitě a poloze nalezeného zdroje. Tato komunikace se odehrává prostřednictvím včelího tance. +more Včela takto láká ostatní, aby ji následovaly. Počet přesvědčených včel pak závisí na kvalitě zdroje.
Toto chování je ze své povahy decentralizované a zdá se, že napomáhá zvýšit efektivitu roje, pokud je k dispozici málo zdrojů různých úrovní kvality. Částečně automaticky se tak vyvažuje poměr mezi explorací a exploatací. +more Rovněž se zdá být tento přístup výhodný v dynamicky se vyvíjejícím prostředí.
Následující výčet algoritmů nelze považovat za úplný. Existuje řada jiných algoritmů, od různých autorů, často jsou však velmi podobné (například #Bee Colony Optimization Algorithm (BCO)|BCO a BCOA)
Artificial Bee Colony Algorithm (ABC)
Název lze z originálu přeložit jako algoritmus umělého včelího roje. Algoritmus poprvé publikoval Karaboga v roce 2005.
Roj je rozdělen na tři druhy včel: dělnice, vyčkávající včely a průzkumníci. Každé dělnici náleží nějaké prozatímní řešení, které se v každém iterativním kroku dělnice pokouší zlepšit pomocí lokálního prohledávání. +more Následně se dělnice pokoušejí k sobě nalákat vyčkávající včely, které si s vyšší pravděpodobností vyberou dělnici s lepším řešením (používá se obvyklá ruletová selekce). Vyčkávající včela, která si vybrala nějakou z dělnic, se nyní pokouší zlepšit řešení dané dělnice pomocí lokálního vyhledávání. Pokud nalezne lepší řešení než má dělnice, dělnice si své řešení aktualizuje. V opačném případě setrvá dělnice na své pozici. Nezlepší-li však dělnice své řešení po několik iterací, opustí svou pozici a stane se průzkumníkem - to znamená, že si vybere nějaký náhodný bod v prohledávacím prostoru a změní se opět na dělnici, ovšem na této nové pozici.
Algoritmus má několik parametrů, které je nutné nastavit. Kromě velikosti roje a poměru mezi počtem dělnic a vyčkávajících včel je to hlavně počet iterací, po nichž dělnice opustí své řešení, nebyla-li ho schopná zlepšit. +more Tento parametr značně ovlivňuje míru exploatace. Konkrétní číselné hodnoty jsou však silně závislé na řešeném problému.
Bees Algorithm (BA)
Bees Algorithm (česky Včelí algoritmus) publikoval Pham v roce 2005 jako metodu pro optimalizaci spojitých i kombinatorických funkcí.
Roj včel je rozdělen na dvě skupiny: průzkumníci a vyčkávající včely. Na počátku jsou průzkumníci náhodně rozptýleni v prostoru. +more Z průzkumníku se pak na počátku každého iterativního kroku vybere M nejlepších včel. Tyto vybrané včely se ještě v závislosti na kvalitě svých řešení rozdělí na E elitních a M-E ostatních vybraných včel. Poté se vyčkávající včely přidruží k vybraným včelám. Elitní včela získá více následovníků než neelitní včela. Tito následovníci pak provádí lokální vyhledávání okolo sobě přiděleného průzkumníka. Pokud se jim podaří řešení vylepšit, průzkumník si ho aktualizuje. Nová generace průzkumník pro další iteraci pak bude sestávat z M vybraných průzkumníků z předchozí iterace a N-M nových průzkumníků. Iterační krok se opakuje tolikrát, dokud se nedosáhne pevně stanovený počet iterací, nebo není dosaženo dostatečně kvalitní řešení.
Tato metoda byla v nedávné době vylepšována, především byly přidány nové metody lokálního vyhledávání jako mutace, křížení, či interpolace, které pak mohou vyčkávající včely využít při zlepšování řešení průzkumníka.
Bee Colony Optimization Algorithm (BCO)
Název lze přeložit jako optimalizační algoritmus včelím rojem. Poprvé byl publikován Teodorovićem v roce 2005. +more Jedná se o vylepšení staršího Bee System algorithm (lze přeložit jako algoritmus včelího systému). Oba algoritmy byly určeny pro řešení kombinatorických problémů a jsou si velmi podobné.
Včely roje nejsou členěny do žádných skupin. Celý výpočet je rozdělen do I iterací, kde I je uživatelem zadaný parametr. +more Každá včela pracuje s nějakým svým částečným řešením, které se snaží zlepšit. Například v jedné z vědeckých publikací byl pomocí BCO řešen problém obchodního cestujícího, a tehdy částečná řešení odpovídala cestám v grafu, které včely postupně prodlužovaly. Algoritmus probíhá během iterace ve dvou fázích. V první, takzvané dopředné fázi, včely pracují se svými částečnými řešeními (například se snaží přidat další vrchol k budované cestě), zde záleží na řešeném problému. V druhé, takzvané zpětné fázi, se včely vrátí do úlu a vymění si informace o svých částečných řešeních. Málo úspěšné včely své řešení zahodí a převezmou částečné řešení jiné, úspěšnější včely. Každá včela, která své řešení nezahodila, se naopak snaží nalákat své následovníky. Implementace tohoto postupu jsou různé, ale obvykle se mezi včelami vybírá náhodně. S vyšší pravděpodobností jsou však upřednostněny úspěšnější včely.