Метод Гука — Дживса (англ. Hooke — Jeeves) або пошук за зразком (англ. Pattern search) так само, як і метод Нелдера–Міда, призначений для пошуку безумовного локального екстремуму функції і відноситься до прямих методів, тобто спирається безпосередньо на значення функції. Алгоритм складається з двох фаз: досліджуючий пошук і пошук за зразком.
Опис
На початковому етапі задається стартова точка (позначимо її 1) і кроки hi по координатах. Потім заморожуємо значення всіх координат крім 1-ї, обчислюємо значення функції в точках x0+h0 і x0-h0 (де x0 — перша координата точки, а h0 — значення кроку по цій координаті) і переходимо в точку з найменшим значенням функції. У цій точці заморожуємо значення всіх координат крім 2-ї, обчислюємо значення функції в точках x1+h1 i x1-h1, переходимо в точку з найменшим значенням функції і т. д. для всіх координат. У випадку, якщо для будь-якої координати значення у вихідній точці менше, ніж значення для обох напрямків кроку, то крок по цій координаті зменшується. Коли кроки по всіх координатах hi стануть менше відповідних значень ei, алгоритм завершується, і точка 1 визнається точкою мінімуму.
Ілюстрація першого етапу для двох координат:
Таким чином, провівши досліджуючий пошук по всіх координатах, ми отримаємо нову точку з найменшим значенням функції в околі (позначимо її 2). Тепер можна перейти до 2 фази алгоритму.
На етапі пошуку за зразком відкладається точка 3 в напрямку від 1 до 2 на тій же відстані. Її координати знаходять за формулою , де xi — точка з номером i, λ — параметр алгоритму, зазвичай вибирають рівним 2. Потім в новій точці 3 проводиться досліджуючий пошук, як на першій фазі алгоритму, за винятком того, що крок не зменшується. Якщо на цій фазі в результаті досліджуючого пошуку вдалося отримати точку 4, відмінну від точки 3, то точку 2 позначимо як 1, а 4 як 2 і повторимо пошук за зразком. Якщо не вдається знайти точку 4, відмінну від точки 3, то точку 2 позначимо як точку 1 і повторимо першу фазу алгоритму — досліджуючий пошук.
Ілюстрація другого етапу для двох координат:
У дужках зазначені імена точок після перевизначення. На ілюстрації добре помітно, як алгоритм коригує свій напрямок в залежності від знайдених значень функції.
Переваги
Даний алгоритм володіє властивістю «прискорюватися», що сприяє підвищенню його загальної ефективності. Друга перевага методу Гука—Дживса — можливість отримання за його допомогою наближеного рішення, якість якого безупинно підвищується на всіх стадіях чисельного рішення. Особливо явно переваги подібних засобів виявляються при відшуканні екстремумів на гіперповерхнях, які містять глибокі вузькі западини, тобто тоді, коли градієнтні методи неефективні. Також перевагами даного методу є проста стратегія пошуку і невеликий обсяг необхідної пам'яті.
Недоліки
Алгоритм заснований на циклічному русі по координатам, що може привести до виродження алгоритму в нескінченну послідовність пошуків через дослідження без пошуку за зразком. При використанні методу передбачається, що цільова функція яка досліджується, є унімодальною, тобто має на інтервалі дослідження тільки один оптимум. Це означає, що розв'язком може стати локальний мінімум, а не глобальний, якщо на досліджуваній області присутні кілька мінімумів.
Література
- Р. Гук, Т. А. Дживс «Прямой поиск решения для числовых и статических проблем», 212—219 с., 1961.
- C. T. Kelley. Iterative methods for optimization, 180 p
Посилання
- Методы многомерное оптимизации в .
- А.В. Аттетков, С.В. Галкин, В.С. Зарубин. Метод Хука - Дживса // Методы оптимизации. — М. : Изд-во МГТУ им. Н.Э. Баумана, 2003. — С. 285. — 440 с. — (Математика в техническом университете; Вып. XIV).[недоступне посилання з квітня 2019]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Metod Guka Dzhivsa angl Hooke Jeeves abo poshuk za zrazkom angl Pattern search tak samo yak i metod Neldera Mida priznachenij dlya poshuku bezumovnogo lokalnogo ekstremumu funkciyi i vidnositsya do pryamih metodiv tobto spirayetsya bezposeredno na znachennya funkciyi Algoritm skladayetsya z dvoh faz doslidzhuyuchij poshuk i poshuk za zrazkom Priklad zbizhnosti metodu Guka Dzhivsa na Na kozhnij iteraciyi shablon abo peremishuyetsya do tochki yaka najkrashe minimizuye jogo cilovu funkciyu abo zmenshuyetsya yaksho zhodna tochka ne ye krashoyu za potochnu tochku doki ne bude dosyagnuta bazhana tochnist abo yaksho algoritm ne dosyagne zadanogo chisla iteracij OpisNa pochatkovomu etapi zadayetsya startova tochka poznachimo yiyi 1 i kroki hi po koordinatah Potim zamorozhuyemo znachennya vsih koordinat krim 1 yi obchislyuyemo znachennya funkciyi v tochkah x0 h0 i x0 h0 de x0 persha koordinata tochki a h0 znachennya kroku po cij koordinati i perehodimo v tochku z najmenshim znachennyam funkciyi U cij tochci zamorozhuyemo znachennya vsih koordinat krim 2 yi obchislyuyemo znachennya funkciyi v tochkah x1 h1 i x1 h1 perehodimo v tochku z najmenshim znachennyam funkciyi i t d dlya vsih koordinat U vipadku yaksho dlya bud yakoyi koordinati znachennya u vihidnij tochci menshe nizh znachennya dlya oboh napryamkiv kroku to krok po cij koordinati zmenshuyetsya Koli kroki po vsih koordinatah hi stanut menshe vidpovidnih znachen ei algoritm zavershuyetsya i tochka 1 viznayetsya tochkoyu minimumu Ilyustraciya pershogo etapu dlya dvoh koordinat Takim chinom provivshi doslidzhuyuchij poshuk po vsih koordinatah mi otrimayemo novu tochku z najmenshim znachennyam funkciyi v okoli poznachimo yiyi 2 Teper mozhna perejti do 2 fazi algoritmu Na etapi poshuku za zrazkom vidkladayetsya tochka 3 v napryamku vid 1 do 2 na tij zhe vidstani Yiyi koordinati znahodyat za formuloyu x 3 x 1 l x 2 x 1 displaystyle overline x 3 overline x 1 lambda overline x 2 overline x 1 de xi tochka z nomerom i l parametr algoritmu zazvichaj vibirayut rivnim 2 Potim v novij tochci 3 provoditsya doslidzhuyuchij poshuk yak na pershij fazi algoritmu za vinyatkom togo sho krok ne zmenshuyetsya Yaksho na cij fazi v rezultati doslidzhuyuchogo poshuku vdalosya otrimati tochku 4 vidminnu vid tochki 3 to tochku 2 poznachimo yak 1 a 4 yak 2 i povtorimo poshuk za zrazkom Yaksho ne vdayetsya znajti tochku 4 vidminnu vid tochki 3 to tochku 2 poznachimo yak tochku 1 i povtorimo pershu fazu algoritmu doslidzhuyuchij poshuk Ilyustraciya drugogo etapu dlya dvoh koordinat U duzhkah zaznacheni imena tochok pislya pereviznachennya Na ilyustraciyi dobre pomitno yak algoritm koriguye svij napryamok v zalezhnosti vid znajdenih znachen funkciyi PerevagiDanij algoritm volodiye vlastivistyu priskoryuvatisya sho spriyaye pidvishennyu jogo zagalnoyi efektivnosti Druga perevaga metodu Guka Dzhivsa mozhlivist otrimannya za jogo dopomogoyu nablizhenogo rishennya yakist yakogo bezupinno pidvishuyetsya na vsih stadiyah chiselnogo rishennya Osoblivo yavno perevagi podibnih zasobiv viyavlyayutsya pri vidshukanni ekstremumiv na giperpoverhnyah yaki mistyat gliboki vuzki zapadini tobto todi koli gradiyentni metodi neefektivni Takozh perevagami danogo metodu ye prosta strategiya poshuku i nevelikij obsyag neobhidnoyi pam yati NedolikiAlgoritm zasnovanij na ciklichnomu rusi po koordinatam sho mozhe privesti do virodzhennya algoritmu v neskinchennu poslidovnist poshukiv cherez doslidzhennya bez poshuku za zrazkom Pri vikoristanni metodu peredbachayetsya sho cilova funkciya yaka doslidzhuyetsya ye unimodalnoyu tobto maye na intervali doslidzhennya tilki odin optimum Ce oznachaye sho rozv yazkom mozhe stati lokalnij minimum a ne globalnij yaksho na doslidzhuvanij oblasti prisutni kilka minimumiv LiteraturaR Guk T A Dzhivs Pryamoj poisk resheniya dlya chislovyh i staticheskih problem 212 219 s 1961 C T Kelley Iterative methods for optimization 180 pPosilannyaMetody mnogomernoe optimizacii v A V Attetkov S V Galkin V S Zarubin Metod Huka Dzhivsa Metody optimizacii M Izd vo MGTU im N E Baumana 2003 S 285 440 s Matematika v tehnicheskom universitete Vyp XIV nedostupne posilannya z kvitnya 2019