Hledání vzoru (optimalizace) - Pattern search (optimization)

Pro další použití viz Hledání vzoru.
Příklad konvergence metody přímého vyhledávání na Broydenova funkce. Při každé iteraci se vzor buď přesune do bodu, který nejlépe minimalizuje jeho objektivní funkci, nebo se zmenší, pokud žádný bod není lepší než aktuální bod, dokud nebude dosaženo požadované přesnosti, nebo algoritmus nedosáhne předem stanoveného počtu iterací.

Hledání vzoru (také známé jako přímé vyhledávání, vyhledávání bez derivací nebo hledání černé skříňky) je rodina čísel optimalizace metody, které nevyžadují a spád. Ve výsledku jej lze použít na funkce, které nejsou kontinuální nebo rozlišitelný. Jednou z takových metod hledání vzoru je „konvergence“ (viz níže), která je založena na teorii pozitivních bází. Optimalizace se pokusí najít nejlepší shodu (řešení, které má nejnižší hodnotu chyby) v a vícerozměrná analýza prostor možností.

Dějiny

Název „hledání vzoru“ vymysleli Hooke a Jeeves.[1] Je připisována časná a jednoduchá varianta Fermi a Metropole když pracovali v Národní laboratoř Los Alamos. Popisuje to Davidon,[2] jak následuje:

Měnili jeden teoretický parametr po krocích o stejné velikosti, a když žádné takové zvýšení nebo snížení žádného z parametrů dále nezlepšilo přizpůsobení experimentálním datům, zmenšili velikost kroku na polovinu a postup opakovali, dokud nebyly kroky považovány za dostatečně malý.

Konvergence

Konvergence je metoda hledání vzoru navržená Yu, který dokázal, že konverguje pomocí teorie pozitivních bází.[3] Později Torczon, Lagarias a spoluautoři[4][5] použil techniky pozitivního základu k prokázání konvergence jiné metody hledání vzoru na konkrétní třídy funkcí. Mimo tyto třídy je vyhledávání vzorů a heuristický které mohou poskytnout užitečné přibližné řešení některých problémů, ale u jiných mohou selhat. Mimo tyto třídy není hledání vzoru iterační metoda který konverguje k řešení; ve skutečnosti mohou metody vyhledávání vzorů konvergovat k nestacionárním bodům u některých relativně krotkých problémů.[6][7]

Viz také

  • Hledání zlatých řezů koncepčně se podobá PS v zúžení rozsahu hledání, pouze pro jednorozměrné vyhledávací prostory.
  • Metoda Nelder – Mead aka. simplexní metoda se koncepčně podobá PS v zúžení rozsahu hledání pro vícerozměrné vyhledávací prostory, ale činí to udržováním n + 1 bod pro n-dimenzionální vyhledávací prostory, zatímco metody PS počítají 2n + 1 bod (centrální bod a 2 body v každé dimenzi).
  • Luus – Jaakola vzorky z a rovnoměrné rozdělení obklopuje aktuální pozici a používá jednoduchý vzorec pro exponenciální zmenšení rozsahu vzorkování.
  • Náhodné vyhledávání je příbuzná rodina optimalizačních metod, které vzorkují z a hypersféra obklopující aktuální pozici.
  • Náhodná optimalizace je příbuzná rodina optimalizačních metod, které vzorkují z a normální distribuce obklopující aktuální pozici.

Reference

  1. ^ Hooke, R .; Jeeves, T.A. (1961). ""Přímé vyhledávání „řešení numerických a statistických problémů“. Deník ACM. 8 (2): 212–229. doi:10.1145/321062.321069.
  2. ^ Davidon, W.C. (1991). "Variabilní metrická metoda pro minimalizaci". SIAM Journal on Optimization. 1 (1): 1–17. CiteSeerX  10.1.1.693.272. doi:10.1137/0801001.
  3. ^ * Yu, Wen Ci. 1979. “Pozitivní základ a třída technik přímého vyhledávání ”. Scientia Sinica [Zhongguo Kexue]: 53—68.
  4. ^ Torczon, V.J. (1997). „O konvergenci algoritmů pro vyhledávání vzorů“ (PDF). SIAM Journal on Optimization. 7 (1): 1–25. CiteSeerX  10.1.1.50.3173. doi:10.1137 / S1052623493250780.
  5. ^ Dolan, E.D .; Lewis, R.M .; Torczon, V.J. (2003). „K místní konvergenci vyhledávání vzorů“ (PDF). SIAM Journal on Optimization. 14 (2): 567–583. CiteSeerX  10.1.1.78.2407. doi:10.1137 / S1052623400374495.
  6. ^ * Powell, Michael J. D. 1973. ”V pokynech pro vyhledávání pro minimalizační algoritmy.” Matematické programování 4: 193—201.
  7. ^ * McKinnon, K. I. M. (1999). „Konvergence metody Nelder – Mead simplex do nestacionárního bodu“. SIAM J. Optim. 9: 148–158. CiteSeerX  10.1.1.52.3900. doi:10.1137 / S1052623496303482. (shrnutí algoritmu online).