Основні методи - Оптимізація багатовимірної нелінійної функції
1. Метод випадкових напрямів.
З поточної (або заданої початкової) точки робиться крок у випадковому напрямку , де - Випадковий вектор з модулем, рівним одиниці (випадково тільки його напрям); - Коефіцієнт пропорційності кроку. Якщо (при пошуку мінімуму критерію оптимальності), то нова точка приймається за поточну, і з неї робляться кроки в надії знайти найкращу точку. Якщо , то роблять нову спробу, тобто новий крок.
Пошук закінчують, коли за задану кількість спроб не вдається знайти точку з кращим значенням критерію оптимальності, ніж поточна.
Існують модифікації методу, в одній з яких після серії невдалих спроб зменшується коефіцієнт, що дозволяє уточнити положення оптимуму. І тут умовою закінчення є трохи значення кроку (тобто ).
Існує також модифікація методу зі зворотним кроком. Відмінною її особливістю є те, що при невдалому кроці з точки відразу відбувається крок у зворотному напрямку. При достатньому віддаленні від оптимуму така стратегія пошуку може бути дуже ефективною. Якщо зворотний крок виявився невдалим, можна зробити новий крок з поточної точки або перейти до пошуку зі зменшеним кроком. В останньому випадку існує небезпека уповільнення пошуку далеко від оптимуму, особливо в яру.
2. Метод пошуку з «покаранням випадковістю».
Метод є аналогом методу якнайшвидшого спуску, тільки напрямок локального пошуку не градієнтний, а випадковий. Як і в попередньому методі, з поточної точки роблять випадкові кроки доти, доки не буде знайдено точку з кращим значенням критерію оптимальності. Потім у цьому напрямі регулярним методом одновимірного пошуку шукають оптимуму. У точці оптимуму у напрямку знову випадково шукають новенапрямок і т.д.
Умовою закінчення зазвичай є неможливість отримання кращої точки з поточної за попередньо задану кількість спроб.
3. Метод з «блукаючим пошуком».
Даний метод є статистичним розширенням градієнтного методу та реалізується відповідно до алгоритму
де - випадковий вектор з одиничним модулем, - коефіцієнти, що характеризують внесок випадкової складової та регулярної складової () у величину кроку.
Найчастіше у формулі використовується не градієнт , а складові напрямні косинуси градієнта, що дозволяє витримувати задане співвідношення між регулярною і випадковою складовими кроку.
Теоретично доводиться, що цей алгоритм найімовірніше призведе до глобального екстремуму. В алгоритмі можуть використовуватися алгоритми корекції кроку, властиві градієнтному методу, що включається після невдалих спроб. Умовою закінчення є трохи значення кроку.
Стратегія пошуку може передбачати не постійне, а періодичне додавання до градієнтного кроку випадкового вектора. Частота випадкових «стрибків» повинна зменшуватися з наближенням до оптимуму і збільшуватися далеко від нього. Для цього існують спеціальні алгоритми самонавчання, наприклад:
де - число кроків регулярним градієнтним способом без випадкової складової, тобто. період додавання випадкової складової;
- задане ціле число (рекомендується при цьому в процесі пошуку буде змінюватися в діапазоні).
Назад пропорційно частоті «стрибків» змінюється частка випадкової складової у кроці, тобто. . Умовою закінчення пошуку буде, як і регулярному градієнтному методі, близькість градієнта до нуля.
Метод сліпого пошуку
Ідея методу дуже проста та наочна. ВипадковимТаким чином, у допустимій області береться точка, і порівнюється значення критерію в ній з поточним найкращим. Якщо нова випадково взята точка, що гірше зберігається в якості поточної кращої, то беруть іншу точку. Якщо ж знайшли точку, в якій критерій кращий, то її запам'ятовують як поточну кращу. Гарантується, що з необмеженому зростанні кількості спроб ми наближатися до глобального оптимуму, тобто. знайдене поточне найкраще значення буде настільки завгодно близько до точного рішення.
Насправді пошук припиняють, коли кількість неуспішних спроб перевищує наперед задане число .
Цей пошук можна застосовувати для пошуку початкового наближення, задавши порівняно невелику кількість спроб. Метод простий у алгоритмічному плані і вимагає прикладу з конкретними значеннями.
Для отримання випадкових чисел, що належать відкритому інтервалу (), використовують функцію перетворення