Hook-Jeeves módszer

A Hook-Jeeves metódus ( eng.  Hooke-Jeeves, Pattern search ), más néven konfigurációs módszer – a Nelder-Mead algoritmushoz hasonlóan – egy függvény feltétel nélküli lokális szélsőértékének keresésére szolgál, és direkt metódusokra utal, azaz , közvetlenül a függvény értékeire támaszkodik. Az algoritmus két fázisra oszlik: feltáró keresésre és mintakeresésre.

A kezdeti szakaszban beállítjuk a kezdőpontot (jelöljük 1-gyel) és a koordináták mentén a h i lépéseket. Ezután az 1. kivételével az összes koordináta értékét rögzítjük, kiszámítjuk a függvény értékeit az x 0 + h 0 és x 0 -h 0 pontokban (ahol x 0  a pont első koordinátája, h 0  ennek a koordinátának a lépésértéke), és menjen a legkisebb függvényértékkel rendelkező ponthoz. Ezen a ponton a 2. kivételével az összes koordináta értékét rögzítjük, kiszámoljuk a függvényértékeket az x 1 +h 1 és x 1 -h 1 pontokban, átlépünk a legkisebb függvényértékkel rendelkező pontra stb. minden koordinátához. Ha egyes koordinátáknál a kiindulási pont értéke kisebb, mint a lépés mindkét irányának értéke, akkor a lépés ezen koordináta mentén csökken. Amikor az összes h i koordináta mentén a lépések kisebbek lesznek, mint az e i megfelelő értékei , az algoritmus véget ér, és az 1-es pontot a rendszer minimumpontként ismeri fel.

Az első szakasz illusztrációja két koordináta esetén:

Így az összes koordináta feletti feltáró keresés után kapunk egy új pontot a szomszédságban a legkisebb függvényértékkel (ezt 2-vel jelöljük). Most folytathatja az algoritmus 2. fázisát.

A minta szerinti keresés szakaszában a 3. pontot 1-től 2-ig azonos távolságban ábrázoljuk. Koordinátáit  a csökkenés képlettel kapjuk meg . Ha ebben a fázisban a feltáró keresés eredményeként sikerült megszerezni a 3. ponttól eltérő 4-es pontot, akkor a 2-es pontot 1-re, a 4-et pedig 2-re nevezzük át, és megismételjük a keresést a minta szerint. Ha a 3. ponttól eltérő 4-es pontot nem találunk, akkor a 2-es pontot átjelöljük 1-esnek, és megismételjük az algoritmus 1. fázisát - vizsgáló keresést.

A második szakasz illusztrációja két koordináta esetén:

Az átnevezés utáni pontnevek zárójelben vannak jelölve. Az ábrán jól látható, hogyan korrigálja az algoritmus az irányát a talált függvényértékek függvényében.

Irodalom

1. R. Hook, T. A. Jeeves "Közvetlen keresés a numerikus és statikus problémák megoldására", 212-219 pp., 1961.
2. CT Kelly. Iteratív optimalizálási módszerek, 180 p

Linkek

• https://web.archive.org/web/20120905151449/http://www.theweman.info/topics/t4r5part1.html
• Többdimenziós optimalizálási módszerek az Intuit.ru -ban .
• A.V. Attetkov, S.V. Galkin, V.S. Zarubin. Hook - Jeeves módszer // Optimalizálási módszerek . - M . : MSTU kiadó im. N.E. Bauman, 2003. - S. 285. - 440 p. - (Matematika a Műszaki Egyetemen; XIV. szám).  (nem elérhető link)