14.3.5 Метод конфігурацій Хука – Дживса

Цей метод полегшує пошук і не вимагає обчислення похідних. Пошук ведеться вздовж ліній розриву похідних у припущенні, що зміщення в просторі проектування, які опинилися вдалими на ранній стадії пошуку, можуть призвести до успіху і на його більш пізніх стадіях. Метод Хука – Дживса перевизначений для пошуку мінімуму унімодальної функції багатьох змінних

          (14.26)

при відсутності обмежень. На рис. 14.10 представлена схема алгоритму цього методу.

    

Рисунок 14.10 - Схема алгоритму методу конфігурацій Хука – Дживса

Виконується він наступним чином. Спочатку вибирається вхідна базова точка простору проектування і величини кроків, що будуть використані при дослідженні функції. Після цього у відповідності зі схемою рис. 14.11 проводиться дослідження із заданими приростом у напрямках, відповідних всім незалежним змінним.

Там, де отримано уточнене значення функції, розміщують нову тимчасову базову точку. Закінчивши етап дослідження, вибирають нову базову точку і виконують «зрушення схеми». Ця операція полягає в екстраполяції вздовж лінії, що з'єднує нову і колишню базові точки. Відстань зсуву за нову базову точку декілька перевищує відстань між двома колишніми базовими точками. Математично екстраполяція визначається формулою (14.27)

          (14.27)

де – нова тимчасова базова точка, або «точка зростання», – змінний індекс, – порядковий номер стадії пошуку, а – коефіцієнт підсилення, що більше або рівний одиниці. Після цього досліджують окіл нової тимчасової базової точки, щоб з'ясувати, чи не містить вона точку, прийнявши яку за наступну базову можна наблизитися до оптимального рішення. Цей пошук також ведеться по схемі, яка показана на рис. 14.11.

    

     Рисунок 14.11 - Алгоритм дослідження цільової функції на основі методу Хука Дживса

Якщо знайдена тимчасова точка зростання або одна з сусідніх з нею точок має перевагу перед іншими, то вся процедура повторюється з використанням її в якості базової. Завдяки введенню коефіцієнта підсилення, кожне наступне дослідження околу точки здійснюється на все більшому і більшому віддаленні від вхідної точки до тих пір, доки в процесі пошуку не виявиться пройденим пік або лінія розриву похідної. В цьому випадку вертаються до попередньої «кращої базової точки», звужують область дослідження і повторюють весь процес знову. Якщо крок, який зменшується, послідовно виявляється меншим за деяку заздалегідь задану величину і при цьому відсутня помітна зміна значення цільової функції, пошук припиняється. Після декількох змін напрямку пошуку метод Хука – Дживса забезпечує збіг розподілу розрахункових точок з лінією розриву похідних. Звичайно після завершення вибору схеми пошуку зсуву на кожному наступному кроці збільшується, доки не перевищить величину вхідного кроку в 10 або навіть в 100 раз. Тому у випадку, коли зрушення виявляється невдалим, єдиний засіб продовжити пошук — повернутися до найбільш вдалої з базових точок і почати усе спочатку. Той факт, що даний алгоритм володіє властивістю «прискорюватися», сприяє підвищенню його загальної ефективності. Друга перевага методу Хука – Дживса – можливість отримання за його допомогою наближеного рішення, якість якого безупинно підвищується на всіх стадіях чисельного рішення. Особливо явно переваги подібних засобів виявляються при відшуканні екстремумів на гіперповерхнях, які містять глибокі вузькі западини, тобто тоді, коли градієнтні методи неефективні.