Metoda Hook-Jeeves

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 17 octombrie 2018; verificările necesită 2 modificări .

Metoda Hook-Jeeves ( ing.  Hooke-Jeeves, Pattern search ), cunoscută și ca metodă de configurare - ca și algoritmul Nelder-Mead , este folosită pentru a căuta un extremum local necondiționat al unei funcții și se referă la metode directe, adică , se bazează direct pe valorile funcției. Algoritmul este împărțit în două faze: căutare exploratorie și căutare model.

În stadiul inițial, punctul de plecare este stabilit (să-l notăm cu 1) și pașii h i de-a lungul coordonatelor. Apoi înghețăm valorile tuturor coordonatelor, cu excepția primei, calculăm valorile funcției în punctele x 0 + h 0 și x 0 -h 0 (unde x 0  este prima coordonată a punctului și h 0  este valoarea pasului de-a lungul acestei coordonate, respectiv) și mergeți la punctul cu cea mai mică valoare a funcției. În acest moment, înghețăm valorile tuturor coordonatelor, cu excepția celei de-a 2-a, calculăm valorile funcției în punctele x 1 +h 1 și x 1 -h 1 , trecem la punctul cu cea mai mică valoare a funcției etc. pentru toate coordonatele. Dacă pentru unele coordonate valoarea la punctul de plecare este mai mică decât valorile pentru ambele direcții ale pasului, atunci pasul de-a lungul acestei coordonate este redus. Când pașii de-a lungul tuturor coordonatelor h i devin mai mici decât valorile corespunzătoare ale lui e i , algoritmul se termină, iar punctul 1 este recunoscut ca punct minim.

Ilustrație a primei etape pentru două coordonate:

Astfel, după efectuarea unei căutări exploratorii asupra tuturor coordonatelor, vom obține un nou punct cu cea mai mică valoare a funcției din vecinătate (o notăm cu 2). Acum puteți trece la a doua fază a algoritmului.

În etapa căutării în funcție de eșantion, punctul 3 este trasat în direcția de la 1 la 2 la aceeași distanță. Coordonatele sale sunt  obtinute prin formula Dacă în această fază, în urma căutării exploratorii, s-a putut obține punctul 4, diferit de punctul 3, atunci vom redenumi punctul 2 la 1, și 4 la 2, și repetăm ​​căutarea după model. Dacă nu este posibil să găsim punctul 4 diferit de punctul 3, atunci vom redesemna punctul 2 ca punct 1 și vom repeta prima fază a algoritmului - căutarea de investigare.

Ilustrație a celei de-a doua etape pentru două coordonate:

Numele punctelor după redenumire sunt marcate între paranteze. Ilustrația arată clar modul în care algoritmul își corectează direcția în funcție de valorile funcției găsite.

Literatură

  1. R. Hook, T. A. Jeeves „Căutarea directă a unei soluții la problemele numerice și statice”, 212-219 p., 1961.
  2. CT Kelly. Metode iterative de optimizare, 180 p

Link -uri