Hook-Jeevesova metoda

Metoda Hook-Jeeves ( angl.  Hooke-Jeeves, Pattern search ), známá také jako konfigurační metoda - podobně jako algoritmus Nelder-Mead , se používá k hledání nepodmíněného lokálního extrému funkce a odkazuje na přímé metody, tj. , závisí přímo na hodnotách funkce. Algoritmus je rozdělen do dvou fází: průzkumné vyhledávání a vyhledávání vzorů.

V počáteční fázi je nastaven počáteční bod (označme ho 1) a kroky h i podél souřadnic. Poté zmrazíme hodnoty všech souřadnic kromě 1., vypočítáme hodnoty funkce v bodech x 0 + h 0 a x 0 -h 0 (kde x 0  je první souřadnice bodu a h 0  je hodnota kroku podél této souřadnice, v tomto pořadí) a přejděte k bodu s nejmenší hodnotou funkce. V tomto okamžiku zmrazíme hodnoty všech souřadnic kromě 2., vypočítáme funkční hodnoty v bodech x 1 +h 1 a x 1 -h 1 , přesuneme se do bodu s nejmenší funkční hodnotou atd. pro všechny souřadnice. Pokud je pro některou souřadnici hodnota v počátečním bodě menší než hodnoty pro oba směry kroku, pak se krok podél této souřadnice zmenší. Když jsou kroky podél všech souřadnic h i menší než odpovídající hodnoty e i , algoritmus končí a bod 1 je rozpoznán jako minimální bod.

Ilustrace první fáze pro dvě souřadnice:

Po provedení průzkumného hledání nad všemi souřadnicemi tedy dostaneme nový bod s nejmenší hodnotou funkce v okolí (označíme ho 2). Nyní můžete přejít do 2. fáze algoritmu.

Ve fázi hledání podle ukázky se bod 3 vynese ve směru od 1 do 2 ve stejné vzdálenosti. Jeho souřadnice se  získají podle vzorce Pokud bylo v této fázi v důsledku průzkumného hledání možné získat bod 4, odlišný od bodu 3, pak přejmenujeme bod 2 na 1 a 4 na 2 a zopakujeme hledání podle vzoru. Pokud se nepodaří najít bod 4 odlišný od bodu 3, pak bod 2 přeoznačíme na bod 1 a zopakujeme 1. fázi algoritmu - zjišťovací hledání.

Ilustrace druhého stupně pro dvě souřadnice:

Názvy bodů po přejmenování jsou označeny v závorkách. Obrázek jasně ukazuje, jak algoritmus koriguje svůj směr v závislosti na nalezených hodnotách funkce.

Literatura

1. R. Hook, T. A. Jeeves "Přímé hledání řešení numerických a statických problémů", 212-219 s., 1961.
2. ČT Kelly. Iterační metody pro optimalizaci, 180 s

Odkazy

• https://web.archive.org/web/20120905151449/http://www.theweman.info/topics/t4r5part1.html
• Vícerozměrné optimalizační metody na Intuit.ru .
• A.V. Attetkov, S.V. Galkin, V.S. Zarubin. Hook-Jeevesova metoda // Optimalizační metody . - M . : Vydavatelství MSTU im. N.E. Bauman, 2003. - S. 285. - 440 s. - (Matematika na VUT; číslo XIV).  (nedostupný odkaz)