Алгоритмізація методу Хука-Дживса

ЛЕКЦІЯ № 6

6. МЕТОДИ ПРЯМОГО ПОШУКУ

Методи прямого пошуку не застосовують ніякої інформації, крім значень цільової функції. Тобто в цих методах використовуються тільки значення цільової функції і не застосовуються вектор-градієнти або матриці Гессе. У тих випадках, коли градієнти або матриці Гессе можуть бути легко обчислені, прямий метод виявляється, менш ефективним. Проте у ряді випадків прямі методи є єдиними практично застосованими, наприклад, якщо функція f (х) має розриви першої похідної.

Якщо f (х) задана не в явному вигляді, а системою рівнянь, що відносяться до різних підсистем деякої системи, то аналітичне або числове визначення похідних стає дуже складним або навіть неможливим. Іншим випадком, коли методи прямого пошуку можуть конкурувати з іншими групами методів, є випадок, коли функції f (х) притаманні кілька локальних екстремумів. Необхідність розробки прямих методів пов'язана з тим, що в інженерних додатках часто доводиться стикатися з випадками, коли цільові функції не задані в явному вигляді.

До цієї групи відносяться наступні методи:

1. Метод координатного спуску.

2. Метод Нелдора-Міда.

3. Метод Хука-Дживса.

Найпростіша ідея прямого пошуку полягає в скануванні можливого простору змінних .

Розглянемо спочатку область D двовимірного простору , ε – задана точність пошуку екстремуму. У результаті сканування обчислюємо значення цільової функції Потім знаходимо значення функції У цьому виразі верхній індекс означає номер кроку сканування.

Для направленого сканування існують два способи обходу області D. Для випадку двох змінних ці способи графічно відображені на рис. 6.1.

Також проста ідея з вибором базової точки та оцінювання значень цільової функції в області базової точки, наприклад в квадратному зразку.

Методам прямого пошуку не притаманна висока ефективність. Значна трудомісткість пов’язана з великою кількістю обчислень цільової функції.

Метод Хука-Дживса

Метод Хука-Дживса є комбінацією так званого досліджуючого пошуку з циклічною зміною змінних і прискорюючого пошуку за зразком. Схематично стратегія пошуку зображена на рис. 6.2.

Цей метод є аналогом методу циклічного покоординатного спуску з кроком, який змінюється в процесі роботи алгоритму.

Хук і Дживс у 1961 році придумали евристичний метод n -вимірного прямого пошуку, метод є вельми ефективним та оригінальним. Він є популярним серед методів прямого пошуку до сих пір. Зазначимо, що в евристичних методах реалізуються процедури пошуку за допомогою інтуїтивних геометричних уявлень.

Суть методу, пов’язаного з мінімізацією, наступна.

1. Досліджуючий пошук. З початку для вибору базової точки досліджується окіл по різним координатам вектору х (може бути з різним кроком). Після того, як вибрано прийнятний напрям (фіксується нова базова точка) виконується перехід до етапу 2. Якщо значення цільової функції f (х) збільшилося, то необхідно повернутися в попередню точку і зробити половинний крок.

2. Встановлення конфігурацій (пошук за зразком). Із базової точки в прийнятному напрямку робиться більший крок і цей крок збільшується до тих пір, поки цільова функція зменшується. Коли функція перестає зменшуватися, то від прийнятої конфігурації відмовляються і розмір кроку зменшують. Виконується нове обстеження околу. Таким чином, робиться спроба пошуку яру цільової функції, а потім рух по цьому яру. Пошук за зразком – це рух вздовж прямої, що з’єднує дві базові точки.

Уведемо позначення:

– поточна базова точка;

– попередня базова точка;

– нова базова точка;

– точка, побудована при русі за зразком.

Як тільки рух за зразком не призводить до зменшення цільової функції, точка фіксується як тимчасова базова точка і знову проводиться досліджуючий пошук.

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

Алгоритмізація методу Хука-Дживса

Крок 1. Задаються початкові умови – , крок переміщення Δ х, точність обчислення екстремуму – ε, коефіцієнт зменшення кроку – β > 1, кількість ітерацій .

Крок 2. Проводиться досліджуючий пошук

в залежності від зменшення .

Крок 3. Оцінити, чи відбулося зменшення цільової функції.

Якщо Крок 5.

Якщо Крок 4.

Крок 4. Закінчення пошуку.

Якщо вихід з процедури, друк результатів , .

Якщо перехід на Крок 2.

Крок 5. Провести пошук за зразком

Крок 6. Оцінити зменшення цільової функції.

Якщо Крок 5.

Якщо Крок 4.

Зауваження. Перевагою методу Хука-Дживса є те, що він дозволяє відновлювати напрямок руху вздовж яру, коли через викривлення яру встановлена конфігурація втрачається.

Приклад. Знайти методом Хука-Дживса мінімум функції

з точністю ε = 10^–1, при заданих початкових умовах

,

1. Досліджуючий пошук

Фіксуємо

успіх.

Фіксуємо

успіх.

2. Пошук за зразком

успіх.

Тимчасова базова точка

успіх.

Тимчасова базова точка

успіх.

Тимчасова базова точка

невдача.

3. Дослідницький пошук

Повернення до попередньої базової точки

невдача

4. Дослідницький пошук

невдача

5. Дослідницький пошук

невдача

6. Дослідницький пошук

невдача

Вихід із ітераційної процедури. Розв’язанням задачі оптимізації є остання базова точка

Стратегія пошуку наведена на рис. 6.3.

Метод ярів

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

Метод ярів має хорошу геометричну ілюстрацію, яку можна побачити на рис. 6.4 на поверхні та лініях рівня (дні яру).

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

Геометрична інтерпретація методу наступна.

Із довільної точки А ₀ (рис. 6.4, а) здійснюється ряд ітерацій локального спуску, поки зменшення цільової функції . Нехай локальний спуск призвів нас в деяку точку В ₀. Зафіксуємо її і виберемо іншу довільну точку А ₁, з якої також здійснимо локальний спуск і попадемо в точку В ₁.

Далі з’єднуємо точки В ₀ і В ₁ і робимо більший крок вздовж променю В ₀ В ₁ в бік зменшення цільової функції. Попадаємо в точку А2, з якої знову здійснюємо локальний спуск. Таким чином, процедура пошуку мінімуму функції повторюється.

Такою почерговою зміною суттєвих і несуттєвих змінних добре відслідковується дно яру та шлях до глобального екстремуму.

Зауваження. Недоліком методу є те, що складно розділити змінні на суттєві та несуттєві.

Деяким розвитком методу ярів є метод релаксації.

6.3. Метод деформованого багатогранника
(метод Нелдера-Міда)

Метод Нелдера-Міда полягає в тому, що для мінімізації функції n змінних f (х) в n -вимірному просторі будується багатогранник, який має (n + 1) вершину. Очевидно, що кожна вершина відповідає деякому вектору х. Обчислюються значення цільової функції f (х) в кожній з вершин багатогранника, визначаються максимальне з цих значень і відповідна йому вершина х [ h ]. Через цю вершину і центр ваги інших вершин проводиться проекціювальна пряма, на якій знаходиться точка х [ q ] з меншим значенням цільової функції, ніж в вершині х [ h ] (рис. 6.5). Потім виключається вершина х [ h ]. З решти вершин і точки x [ q ] будується новий багатогранник, з яким повторюється описана процедура. В процесі виконання таких операцій багатогранник змінює свої розміри, що і зумовило назву методу.

Уведемо наступні позначення:

x [ i, k ] =(x ₁[ i, k ], …, x_j [ i, k ], …, x_n [ i, k ])^T,

где i = 1,..., п + 1; k = 0, 1,..., – i -а вершина багатокутника на k- му кроці пошуку; х [ h, k ] – вершина, в якій значення цільової функції максимально, тобто f (х [ h, k ] = max{ f (x [1, k ] ), …, f (x [ n +1, k ])}; х [ l, k ] – вершина, в якій значення цільової функції мінімально, тобто f (х [ l, k ] ) = min { f (x [1, k ] ), …, f (x [ n +1, k ])}; х [ п +2, k ] – центр ваги всіх вершин, за винятком х [ h, k ].

Координати центра ваги обчислюються за формулою:

Алгоритм методу деформованого багатогранника полягає в наступному.

1. Здійснюється проекціювання точки х [ h, k ] через центр ваги

x [ n + 3, k ] = x [ n + 2, k ] + a (x [ n + 2, k ] – x [ h, k ]),

де а > 0 – деяка константа. Зазвичай а = 1.

2. Виконується операція розтягнення вектора х [ n + 3, k ] – х [ n + 2, k ]:

x [ n+ 4, k ] =x [ n+ 2, k g] + x [ n+ 3, k ] – x [ n+ 2, k ],

де γ > 1 – коефіцієнт розтягнення. Найбільш задовільні результати отримують при

Якщо f (x [ n + 4, k ]) < f (х [ l, k ]), то х [ h, k ] замінюють на x [ n + 4, k ] і продовжують обчислення з п. 1 при k = k + 1. В іншому випадку х [ h, k ] замінюють на х [ n + 3, k ] і переходять до п. 1 при k = k + 1.

3. Якщо f (x [ n+ 3, k ] ) > f (х [ i, k ] ) для всіх i, не рівних h, то стискають вектор x [ h, k ] – x [ n+ 2, k ]:

x [ n+ 5, k ] =x [ n+ 2, k b] + х [ h, k ] – x [ n+ 2, k ],

де b > 0 – коефіцієнт стиснення. Найкращі результати отримують при 0,4 <b= <= 0,6.

4. Якщо f (x [ n+ 3, k ]) > f (x [ h, k ]), то всі вектори х [ i, k ] – х [ l, k ] i= 1,..., п + 1, зменшують у два рази:

x [ i, k ] = x [ l, k ] + 0,5(x [ i, k ] – x [ l, k ]).

Потім переходять до п. 1 при k = k + 1.

У діалоговій системі оптимізації вихід з підпрограми, що реалізує метод деформованого багатогранника, здійснюється при граничному стисненні багатогранника, тобто при виконанні умови

,

де е = (е ₁, …, е_n) – заданий вектор.

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

Зазначимо, що Нелдер і Мід запропонували кілька модифікацій методу деформованого багатогранника, які дозволяють багатогранникам бути будь-якої довільної форми.