Optimalizace včelím rojem

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Optimalizace 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.[1]

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.[2] 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[editovat | editovat zdroj]

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á. 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)[editovat | editovat zdroj]

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ů.[3]

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). 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í. 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[editovat | editovat zdroj]

Algoritmů toho typu existuje velmi mnoho. Lze sem řadit Bee System[4], Queen-bee evolution[5], nebo včelami inspirovaný operátor křížení[6].

Optimalizační metody inspirované sháněním potravy[editovat | editovat zdroj]

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. 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í. Rovněž se zdá být tento přístup výhodný v dynamicky se vyvíjejícím prostředí.[1]

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 BCO a BCOA[7])

Artificial Bee Colony Algorithm (ABC)[editovat | editovat zdroj]

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.[8]

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í. 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. 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)[editovat | editovat zdroj]

Bees Algorithm (česky Včelí algoritmus) publikoval Pham v roce 2005 jako metodu pro optimalizaci spojitých i kombinatorických funkcí.[9]

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. 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)[editovat | editovat zdroj]

Název lze přeložit jako optimalizační algoritmus včelím rojem. Poprvé byl publikován Teodorovićem v roce 2005.[10] Jedná se o vylepšení staršího Bee System algorithm (lze přeložit jako algoritmus včelího systému).[11] 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. 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[11], 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.

Související články[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. a b Dervis Karaboga and Bahriye Akay. 2009. A survey: algorithms simulating bee swarm intelligence. Artif. Intell. Rev. 31, 1-4 (June 2009), 61-85. DOI=10.1007/s10462-009-9127-4 [1]
  2. Konrad, D., Beekman, M., Middendorf, M.: Honeybee Optimisation – An Overview and a New Bee Inspired Optimisation Scheme; Adaptation, Learning, and Optimization; Springer Berlin Heidelberg 2010; ISBN 978-3-642-17390-5; str. 295-327; svazek 8; [2]; springerlink: 10.1007/978-3-642-17390-5_13
  3. Omid Haddad, Abbas Afshar, and Miguel Mariño. Honey-Bees mating optimization (HBMO) algorithm: A new heuristic approach for water resources optimization. Water Resources Management, 20(5):661–680, October 2006.
  4. Sato, T.; Hagiwara, M.; , "Bee System: finding solution by a concentrated search," Systems, Man, and Cybernetics, 1997. 'Computational Cybernetics and Simulation'., 1997 IEEE International Conference on , vol.4, no., pp.3954-3959 vol.4, 12-15 Oct 1997 doi: 10.1109/ICSMC.1997.633289 [3]
  5. Sung Hoon Jung; , "Queen-bee evolution for genetic algorithms," Electronics Letters , vol.39, no.6, pp. 575- 576, 20 March 2003, doi: 10.1049/el:20030383 [4]
  6. Karci, A.: Imitation of Bee Reproduction as a Crossover Operator in Genetic Algorithms; PRICAI 2004: Trends in Artificial Intelligence; Springer Berlin / Heidelberg 2004; str 1015-1016; Doi: 10.1007/978-3-540-28633-2_141 [5]
  7. Chong C, Low MYH, Sivakumar AI and Gay KL (2006) "A Bee Colony Optimization Algorithm to Job Shop Scheduling" Simulation Conference, WSC 06. Monterey, CA.
  8. D. Karaboga, An Idea Based On Honey Bee Swarm for Numerical Optimization, Technical Report-TR06,Erciyes University, Engineering Faculty, Computer Engineering Department 2005.
  9. Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S and Zaidi M. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre, Cardiff University, UK, 2005
  10. Teodorović, D., Dell'Orco, M.: Bee colony optimization - a cooperative learning approach to complex transportation problems; Advanced OR and AI Methods in Transportation; str 51-60; Poznan, 2005.
  11. a b Lucic, P., Teodorovic, D.: Bee system: Modeling combinatorial optimization transportation engineering problems by swarm intelligence; Preprints of the TRISTAN IV Triennial Symposium on Transportation Analysis; str. 441–445; 2001