Hook-Jeeves metod

Hook-Jeeves-metoden ( eng.  Hooke-Jeeves, Pattern search ), även känd som konfigurationsmetoden - liksom Nelder-Mead-algoritmen , används för att söka efter ett ovillkorligt lokalt extremum av en funktion och hänvisar till direkta metoder, dvs. , den förlitar sig direkt på funktionens värden. Algoritmen är uppdelad i två faser: utforskande sökning och mönstersökning.

I det inledande skedet sätts startpunkten (låt oss beteckna den med 1) och stegen h i längs koordinaterna. Sedan fryser vi värdena för alla koordinater utom 1:an, beräknar funktionens värden vid punkterna x 0 + h 0 och x 0 -h 0 (där x 0  är den första koordinaten för punkten, och h 0  är stegvärdet längs denna koordinat, respektive) och gå till punkten med det minsta funktionsvärdet. Vid denna tidpunkt fryser vi värdena för alla koordinater utom den andra, beräknar funktionsvärdena vid punkterna x 1 +h 1 och x 1 -h 1 , flyttar till punkten med det minsta funktionsvärdet, etc. för alla koordinater. Om för någon koordinat värdet vid startpunkten är mindre än värdena för båda riktningarna av steget, reduceras steget längs denna koordinat. När stegen längs alla koordinater h i blir mindre än motsvarande värden på e i slutar algoritmen och punkt 1 känns igen som minimipunkten.

Illustration av det första steget för två koordinater:

Efter att ha genomfört en utforskande sökning över alla koordinater kommer vi alltså att få en ny punkt med det minsta värdet av funktionen i grannskapet (vi betecknar den med 2). Nu kan du fortsätta till den andra fasen av algoritmen.

Vid sökningsstadiet enligt provet plottas punkt 3 i riktningen från 1 till 2 på samma avstånd. Dess koordinater  erhålls genom formeln Om det i denna fas, som ett resultat av den utforskande sökningen, var möjligt att få punkt 4, annorlunda än punkt 3, kommer vi att byta namn på punkt 2 till 1 och 4 till 2 och upprepa sökningen enligt mönstret. Om det inte är möjligt att hitta punkt 4 annorlunda än punkt 3, kommer vi att omdesigna punkt 2 till punkt 1 och upprepa den första fasen av algoritmen - undersöka sökning.

Illustration av det andra steget för två koordinater:

Punktnamn efter byte är markerade inom parentes. Illustrationen visar tydligt hur algoritmen korrigerar sin riktning beroende på de funna funktionsvärdena.

Litteratur

1. R. Hook, T. A. Jeeves "Direct search for a solution to numerical and static problems", 212-219 s., 1961.
2. CT Kelly. Iterativa metoder för optimering, 180 sid

Länkar

• https://web.archive.org/web/20120905151449/http://www.theweman.info/topics/t4r5part1.html
• Flerdimensionella optimeringsmetoder i Intuit.ru .
• A.V. Attetkov, S.V. Galkin, V.S. Zarubin. Hook-Jeeves metod // Optimeringsmetoder . - M . : Förlag av MSTU im. N.E. Bauman, 2003. - S. 285. - 440 sid. - (Matematik vid Tekniska Högskolan; Utgåva XIV).  (inte tillgänglig länk)