Náhodné vyhledávání - Random search
Náhodné vyhledávání (RS) je číselná rodina optimalizace metody, které nevyžadují přechod problému, který má být optimalizován, a RS lze tedy použít na funkce, které nejsou kontinuální nebo rozlišitelný. Tyto optimalizační metody jsou také známé jako metody přímého vyhledávání, bez derivací nebo black-box.
Jméno „náhodné vyhledávání“ je přisuzováno Rastriginovi[1] který provedl časnou prezentaci RS spolu se základní matematickou analýzou. RS pracuje tak, že se iterativně pohybuje do lepších pozic ve vyhledávacím prostoru, které jsou vzorkovány z a hypersféra obklopující aktuální pozici.
Algoritmus zde popsaný je typem místního náhodného vyhledávání, kde každá iterace závisí na kandidátním řešení předchozí iterace. Existují alternativní metody náhodného vyhledávání, které vzorkují z celého prostoru vyhledávání (například čisté náhodné vyhledávání nebo jednotné globální náhodné vyhledávání), ale nejsou v tomto článku popsány.
Algoritmus
Nechat F: ℝn → ℝ musí být funkce fitness nebo cena, kterou je třeba minimalizovat. Nechat X ∈ ℝn určit pozici nebo kandidáta na řešení ve vyhledávacím prostoru. Základní algoritmus RS lze potom popsat jako:
- Inicializovat X s náhodnou pozicí ve vyhledávacím prostoru.
- Dokud nebude splněno kritérium ukončení (např. Počet provedených iterací nebo dosaženo odpovídající kondice), opakujte následující kroky:
- Vyzkoušejte novou pozici y z hypersféra daného poloměru obklopujícího aktuální polohu X (viz např. Marsagliova technika pro vzorkování hypersféry.)
- Li F(y) < F(X) poté se přesuňte do nové polohy nastavením X = y
Varianty
V literatuře byla zavedena řada variant RS:
- Náhodné vyhledávání s fixní velikostí kroku (FSSRS) je Rastriginovo [1] základní algoritmus, který vzorkuje z hypersféry s pevným poloměrem.
- Náhodné hledání optimální velikosti kroku (OSSRS) od Schumera a Steiglitze [2] je primárně teoretická studie o tom, jak optimálně upravit poloměr hypersféry tak, aby umožňoval rychlou konvergenci k optimálnímu. Skutečná implementace OSSRS potřebuje přiblížit tento optimální poloměr opakovaným vzorkováním, a proto je její provedení nákladné.
- Adaptivní krokové náhodné vyhledávání (ASSRS) od Schumera a Steiglitze [2] pokusy heuristicky přizpůsobit poloměr hypersféry: jsou generována dvě nová kandidátní řešení, jedno se současnou jmenovitou velikostí kroku a jedno s větší velikostí kroku. Větší velikost kroku se stane novou nominální velikostí kroku právě tehdy, pokud to povede k většímu zlepšení. Pokud u několika iterací žádný z kroků nevede ke zlepšení, zmenší se nominální velikost kroku.
- Optimalizované náhodné vyhledávání relativní velikosti kroku (ORSSRS) podle Schrack and Choit [3] aproximujte optimální velikost kroku jednoduchým exponenciálním zmenšením. Vzorec pro výpočet redukčního faktoru je však poněkud komplikovaný.
Viz také
- Náhodná optimalizace je úzce příbuzná rodina optimalizačních metod, které vzorkují z a normální distribuce místo hypersféry.
- Luus – Jaakola je úzce související optimalizační metoda využívající a rovnoměrné rozdělení v jeho vzorkování a jednoduchý vzorec pro exponenciální zmenšení rozsahu vzorkování.
- Hledání vzoru podniká kroky podél os vyhledávacího prostoru pomocí exponenciálně se zmenšujících velikostí kroků.
Reference
- ^ A b Rastrigin, L.A. (1963). Msgstr "Konvergence metody náhodného vyhledávání v extremálním řízení systému mnoha parametrů". Automatizace a dálkové ovládání. 24 (10): 1337–1342.
- ^ A b Schumer, M. A.; Steiglitz, K. (1968). Msgstr "Náhodné hledání velikosti adaptivního kroku". Transakce IEEE na automatickém ovládání. 13 (3): 270–276. CiteSeerX 10.1.1.118.9779. doi:10.1109 / tac.1968.1098903.
- ^ Schrack, G .; Choit, M. (1976). Msgstr "Optimalizovaná náhodná vyhledávání relativní velikosti kroku". Matematické programování. 10 (1): 230–244. doi:10.1007 / bf01580669.