Hledání kukačky - Cuckoo search
![]() | tento článek potřebuje další citace pro ověření.Červen 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v operační výzkum, vyhledávání kukaček je optimalizace algoritmus vyvinutý uživatelem Xin-she Yang a Suash Debin 2009.[1][2] To bylo inspirováno povinný plodový parazitismus některých kukačka druhy kladením vajíček do hnízd jiných hostitelských ptáků (jiných druhů). Někteří hostitelští ptáci mohou být v přímém konfliktu s narušujícími kukačkami. Pokud například hostitelský pták zjistí, že vejce nejsou jejich vlastní, buď tato mimozemská vejce vyhodí, nebo jednoduše opustí své hnízdo a postaví si nové hnízdo jinde. Některé druhy kukaček, jako je Nový svět plodně parazitický Tapera se vyvinuly takovým způsobem, že samice parazitických kukaček se často velmi specializují na mimikry v barvách a vzoru vajec několika vybraných hostitelských druhů.[3] Hledání kukaček idealizovalo takové chování při chovu, a lze je tedy použít pro různé optimalizační problémy.
Metafora
Hledání kukačky (CS) používá následující reprezentace:
Každé vejce v hnízdě představuje řešení a kukaččí vejce představuje nové řešení. Cílem je použít nová a potenciálně lepší řešení (kukačky) k nahrazení ne tak dobrého řešení v hnízdech. V nejjednodušší podobě má každé hnízdo jedno vejce. Algoritmus lze rozšířit na složitější případy, kdy každé hnízdo má více vajec představujících sadu řešení.
CS je založen na třech idealizovaných pravidlech:
- Každá kukačka snáší po jednom vajíčku a své vejce ukládá do náhodně vybraného hnízda;
- Nejlepší hnízda s vysokou kvalitou vajec se přenesou do další generace;
- Počet dostupných hostitelských hnízd je pevný a vejce snášené kukačkou je objeveno hostitelským ptákem s pravděpodobností . V takovém případě může hostitelský pták vyhodit vejce / opustit hnízdo a postavit zcela nové hnízdo.
Yang a Deb navíc zjistili, že vyhledávání stylů náhodných procházek lépe provádí Lévy lety spíše než jednoduché náhodná procházka.
Algoritmus
The pseudo kód lze shrnout jako:
Objektivní funkce: Generovat počáteční populaci hostitelská hnízda; While (t]; Vyberte si hnízdo mezi n (řekněme j) náhodně; pokud (), Nahraďte j novým řešením; konec, pokud zlomek A () horších hnízd jsou opuštěna a jsou stavěna nová; Udržujte nejlepší řešení / hnízda; Pořadí řešení / hnízd a najít aktuální nejlepší; Předejte současná nejlepší řešení příští generaci; ukončete chvíli [Pro maximalizaci,
Důležitou výhodou tohoto algoritmu je jeho jednoduchost. Ve skutečnosti srovnání s jinými populacemi nebo agenty metaheuristické algoritmy jako např optimalizace roje částic a hledání harmonie, v zásadě existuje pouze jeden parametr v CS (kromě velikosti populace ). Proto je velmi snadné jej implementovat.
Náhodné procházky a velikost kroku
Důležitým problémem jsou aplikace Lévyho letů a náhodných procházek v generické rovnici pro generování nových řešení
kde je čerpáno ze standardního normálního rozdělení s nulovou střední hodnotou a jednotnou směrodatnou odchylkou pro náhodné procházky, nebo čerpáno z Lévyho rozdělení pro Lévy lety. Je zřejmé, že náhodné procházky lze také spojit s podobností mezi kukaččím vejcem a vejcem hostitele, což může být při implementaci složité. Zde je velikost kroku určuje, jak daleko může náhodný chodec zajít pro pevný počet iterací. Generování Lévyho velikosti kroku je často složité a srovnání tří algoritmů (včetně Mantegny)[4]) provedl Leccardi[5] který našel implementaci přístupu Chambers et al[6] být výpočetně nejefektivnější vzhledem k nízkému počtu požadovaných náhodných čísel.
Pokud je s příliš velké, pak bude nové generované řešení příliš daleko od starého řešení (nebo dokonce vyskočí z hranic). Je nepravděpodobné, že by takový krok byl přijat. Pokud je s příliš malé, změna je příliš malá na to, aby byla významná, a proto takové hledání není efektivní. Správná velikost kroku je tedy důležitá, aby bylo hledání co nejefektivnější.
Jako příklad pro jednoduché izotropní náhodné procházky víme, že průměrná vzdálenost cestoval v prostoru dimenze d
kde je efektivní difúzní koeficient. Tady je velikost kroku nebo ujetá vzdálenost při každém skoku a je čas potřebný pro každý skok. Z výše uvedené rovnice vyplývá, že[7]
Pro typickou délkovou stupnici L sledované dimenze je místní vyhledávání obvykle omezeno v oblasti . Pro at = 100 až 1 000, máme pro d = 1 a pro d = 10. Proto pro většinu problémů můžeme použít s / L = 0,001 až 0,01. Přesná derivace může vyžadovat podrobnou analýzu chování Lévyho letů.[8]
Algoritmus a konvergenční analýza budou plodné, protože s metaheuristikou existuje mnoho otevřených problémů[9]
Teoretická analýza
Jako významné úsilí jsou zapotřebí teoretické analýzy ke zlepšení výkonu algoritmů CS-base:[10]
- Teoretická analýza konvergence algoritmů založených na CS
- Zajištění dostatečných a nezbytných podmínek pro nastavení parametrů řízení
- Využití nehomogenních pravidel vyhledávání pro vylepšení klasického algoritmu CS
Vylepšené algoritmy vyhledávání kukaček
Konvergenci algoritmu vyhledávání kukaček lze podstatně zlepšit genetickým nahrazením opuštěných hnízd (namísto použití náhodných náhrad z původní metody).[11]
Reference
- ^ X.-S. Yang; S. Deb (prosinec 2009). Hledání kukačky pomocí letů Lévyho. Světový kongres o přírodě a biologicky inspirovaných počítačích (NaBIC 2009). Publikace IEEE. 210–214. arXiv:1003.1594v1.
- ^ Inderscience (27. května 2010). "Kukačka navrhuje jaro". Alphagalileo.org. Citováno 2010-05-27.
- ^ R. B. Payne, M. D. Sorenson a K. Klitz, The Cuckoos, Oxford University Press, (2005).
- ^ R. N. Mantegna, Rychlý a přesný algoritmus pro numerickou simulaci stabilních stochastických procesů Lévyho, Physical Review E, sv. 49, 4677-4683 (1994).
- ^ M. Leccardi, Porovnání tří algoritmů pro generování šumu Levy, Sborník z páté konference nelineární dynamiky EUROMECH (2005).
- ^ Chambers, J. M .; Mallows, C. L .; Stuck, B. W. (1976). Msgstr "Metoda simulace stabilních náhodných proměnných". Journal of the American Statistical Association. 71: 340–344. doi:10.1080/01621459.1976.10480344.
- ^ X.-S. Yang, Přírodní inspirované metheuristické algoritmy, 2. vydání, Luniver Press, (2010).
- ^ M. Gutowski, Lévyho lety jako základní mechanismus globálních optimalizačních algoritmů, ArXiv Mathematical Physics e-Prints, červen, (2001).
- ^ X. S. Yang, Metaheuristická optimalizace: analýza algoritmů a otevřené problémy, in: Experimental Algorithms (SEA2011), Eds (P. M. Pardalos and S. Rebennack), LNCS 6630, pp.21-32 (2011).
- ^ Cheung, N.J .; Ding, X .; Shen, H. (2016-01-21). „Algoritmus nehomogenního vyhledávání kukaček založený na kvantovém mechanismu pro skutečnou optimalizaci parametrů“. Transakce IEEE v kybernetice. 47 (2): 391–402. doi:10.1109 / TCYB.2016.2517140.
- ^ de Oliveira, Victoria Y.M .; de Oliveira, Rodrigo M.S .; Affonso, Carolina M. (2018-07-31). „Přístup kukačkového vyhledávání vylepšen genetickým nahrazením opuštěných hnízd použitým pro optimální alokaci distribuovaných generačních jednotek. Generování, přenos a distribuce IET. 12 (13): 3353–3362. doi:10.1049 / iet-gtd.2017.1992. ISSN 1751-8687.