Strategie přirozeného vývoje - Natural evolution strategy
![]() | Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace.Březen 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
Strategie přirozeného vývoje (NES) jsou rodinou numerická optimalizace algoritmy pro Černá skříňka problémy. V duchu podobné evoluční strategie, iterativně aktualizují (průběžné) parametry a distribuce vyhledávání sledováním přirozeného gradientu směrem k vyšší očekávané kondici.
Metoda
Obecný postup je následující: parametrizováno distribuce vyhledávání se používá k vytvoření dávky vyhledávacích bodů a fitness funkce se hodnotí v každém takovém bodě. Parametry distribuce (které zahrnují parametry strategie) umožňují algoritmu adaptivně zachytit (místní) strukturu funkce fitness. Například v případě a Gaussovo rozdělení, toto zahrnuje průměr a kovarianční matice. Ze vzorků NES odhaduje gradient přechodu na parametry směrem k vyšší očekávané kondici. NES poté provede krok stoupání podél přirozený gradient, metoda druhého řádu, která na rozdíl od obyčejného přechodu renormalizuje aktualizaci w.r.t. nejistota. Tento krok je zásadní, protože zabraňuje oscilacím, předčasné konvergenci a nežádoucím účinkům vyplývajícím z dané parametrizace. Celý proces se opakuje, dokud není splněno kritérium zastavení.
Všichni členové rodiny NES fungují na stejných principech. Liší se typem rozdělení pravděpodobnosti a gradient přiblížení použitá metoda. Různé vyhledávací prostory vyžadují různé distribuce vyhledávání; například v nízké dimenzionálnosti může být velmi výhodné modelovat celou kovarianční matici. Ve vyšších dimenzích je naopak škálovatelnější alternativou omezit kovarianci na úhlopříčka pouze. Navíc vysoce multimodální vyhledávací prostory mohou těžit z více těžkopádné distribuce (jako Cauchy, na rozdíl od Gaussian). Poslední rozdíl nastává mezi distribucemi, kde můžeme analyticky vypočítat přirozený gradient, a obecnějšími distribucemi, kde je třeba je odhadnout ze vzorků.
Vyhledejte přechody
Nechat označte parametry distribuce vyhledávání a fitness funkce hodnocena na . NES poté sleduje cíl maximalizovat očekávaná kondice v rámci distribuce vyhledávání
přes gradientní výstup. Přechod lze přepsat jako
toto je očekávaná hodnota z krát log-deriváty na . V praxi je možné použít Monte Carlo aproximace na základě konečného počtu Vzorky
- .
Nakonec lze parametry distribuce vyhledávání iterativně aktualizovat
Přirozený gradientní výstup
Namísto použití prostého stochastického přechodu pro aktualizace NESfollow the přirozený gradient, o nichž bylo prokázáno, že mají v porovnání s plání řadu výhod (vanilka) gradient, např .:
- směr gradientu je nezávislý na parametrizaci distribuce vyhledávání
- velikosti aktualizací se automaticky upravují na základě nejistoty, a naopak se urychluje konvergence náhorní plošiny a hřebeny.
Aktualizace NES proto je
- ,
kde je Fisherova informační matice Fisherovu matici lze někdy vypočítat přesně, jinak se odhaduje ze vzorků, přičemž se logaritmické deriváty znovu používají .
Fitness tvarování
NES využívá hodnost - tvarování kondice na základě, aby byl algoritmus robustnější, a neměnný pod monotónně se zvyšujícími transformacemi fitness funkce. Za tímto účelem se fitness populace transformuje do souboru nástroj hodnoty. Nechat označit ith nejlepší jedinec. Nahrazením kondice užitečností se odhad gradientu stává
- .
Volba užitné funkce je volným parametrem algoritmu.
Pseudo kód
vstup: 1 opakovat 2 pro dělat // λ je velikost populace 3 nakreslete vzorek 4 hodnotit kondici 5 vypočítat log-deriváty 6 konec 7 přiřadit nástroje // na základě hodnosti 8 odhadnout gradient 9 odhad // nebo to přesně spočítat 10 aktualizovat parametry // η je míra učení11 dokud kritérium zastavení je splněno
Viz také
Bibliografie
- D. Wierstra, T. Schaul, J. Peters a J. Schmidhuber (2008). Strategie přirozeného vývoje. Kongres IEEE o evolučních výpočtech (CEC).
- Y. Sun, D. Wierstra, T. Schaul a J. Schmidhuber (2009). Stochastické vyhledávání pomocí přirozeného přechodu. Mezinárodní konference o strojovém učení (ICML).
- T. Glasmachers, T. Schaul, Y. Sun, D. Wierstra a J. Schmidhuber (2010). Exponenciální strategie přirozeného vývoje. Konference o genetických a evolučních výpočtech (GECCO).
- T. Schaul, T. Glasmachers a J. Schmidhuber (2011). Vysoké dimenze a těžké ocasy pro strategie přirozeného vývoje. Konference o genetických a evolučních výpočtech (GECCO).
- T. Schaul (2012). Strategie přirozeného vývoje konvergují k funkcím sféry. Konference o genetických a evolučních výpočtech (GECCO).