Hook-Jeeves -menetelmä

Hook-Jeeves-menetelmää ( eng.  Hooke-Jeeves, Pattern search ), joka tunnetaan myös konfigurointimenetelmänä - kuten Nelder-Mead-algoritmi , käytetään etsimään funktion ehdotonta paikallista ääripäätä ja se viittaa suoriin menetelmiin, ts. , se perustuu suoraan funktion arvoihin. Algoritmi on jaettu kahteen vaiheeseen: tutkivaan etsintään ja kuviohakuun.

Alkuvaiheessa asetetaan aloituspiste (merkitkäämme sitä 1:llä) ja askeleet h i koordinaatteja pitkin. Sitten jäädytetään kaikkien paitsi 1. koordinaattien arvot, lasketaan funktion arvot pisteissä x 0 + h 0 ja x 0 -h 0 (jossa x 0  on pisteen ensimmäinen koordinaatti ja h 0  on askelarvo tätä koordinaattia pitkin) ja siirry pisteeseen, jolla on pienin funktioarvo. Tässä vaiheessa jäädytetään kaikkien paitsi 2. koordinaattien arvot, lasketaan funktioarvot pisteissä x 1 +h 1 ja x 1 -h 1 , siirrytään pisteeseen, jossa on pienin funktioarvo jne. kaikille koordinaateille. Jos jollekin koordinaatille arvo aloituspisteessä on pienempi kuin arvot molempiin askelmiin, niin askelta tätä koordinaattia pitkin pienennetään. Kun askeleet kaikissa koordinaateissa h i ovat pienempiä kuin vastaavat e i :n arvot, algoritmi päättyy ja piste 1 tunnistetaan minimipisteeksi.

Kuva ensimmäisestä vaiheesta kahdelle koordinaatille:

Siten kaikkien koordinaattien tutkivan haun jälkeen saamme uuden pisteen, jolla on pienin funktion arvo lähialueella (merkitsimme sitä numerolla 2). Nyt voit siirtyä algoritmin toiseen vaiheeseen.

Näytteen mukaisen etsintävaiheessa piste 3 piirretään suuntaan 1 - 2 samalla etäisyydellä. Sen koordinaatit  saadaan kaavalla Jos tässä vaiheessa tutkivan haun tuloksena oli mahdollista saada pisteestä 3 erilainen piste 4, nimetään pisteet 2 uudelleen 1:ksi ja 4 2:ksi ja toistetaan haku kuvion mukaan. Jos pisteestä 3 erilaista pistettä 4 ei voida löytää, nimetään piste 2 uudelleen pisteeksi 1 ja toistetaan algoritmin 1. vaihe - tutkiva haku.

Kuva toisesta vaiheesta kahdelle koordinaatille:

Pisteiden nimet uudelleennimeämisen jälkeen on merkitty sulkeisiin. Kuvassa näkyy selkeästi, kuinka algoritmi korjaa suuntaaan löydettyjen funktioarvojen mukaan.

Kirjallisuus

1. R. Hook, T. A. Jeeves "Suora etsintä ratkaisua numeerisiin ja staattisiin ongelmiin", 212-219 s., 1961.
2. CT Kelly. Iteratiiviset optimointimenetelmät, 180 s

Linkit

• https://web.archive.org/web/20120905151449/http://www.theweman.info/topics/t4r5part1.html
• Moniulotteiset optimointimenetelmät Intuit.ru:ssa .
• A.V. Attetkov, S.V. Galkin, V.S. Zarubin. Hook - Jeeves -menetelmä // Optimointimenetelmät . - M . : Kustantaja MSTU im. N.E. Bauman, 2003. - S. 285. - 440 s. - (Matematiikka teknillisessä yliopistossa; numero XIV).  (linkki ei saatavilla)