1.4.2. Сліпий пошук

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

Спочатку випадковим чином вибирається початкова точка u₁, у якій обчислюється значення цільової функції f₀(u₁). Далі вибирається u₂ й розраховується f₀(u₂). Якщо f₀(u₂) більше (при пошуку максимуму) f₀(u₁), то значення u₂ й f₀(u₂) запам'ятовуються. Потім вибирається точка u₃, обчислюється f₀(u₃), порівнюється з f₀(u₂) і т. д.

При досить великій кількості досліджених точок можна досягти високого ступеню точності у визначенні екстремуму.

Для зменшення числа досліджуваних точок метод сліпого пошуку можна модифікувати одним з наступних способів.

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

По-друге, простір розв’язків звужується симетрично щодо кращої із заздалегідь обмеженого числа досліджуваної точки, і надалі сліпий пошук триває в цьому значно меншому просторі.

Алгоритм сліпого пошуку може бути записаний наступним чином:

де - випадкова точка;

- вміст пам´яті на кожному кроці пошуку.

1.4.3. Метод випадкових напрямків

Алгоритм цього методу полягає в тому, що із точки u⁽^k⁾, у якій відоме значення f₀(u⁽^k⁾) здійснюється крок у випадковому напрямку . Величина кроку визначається величиною крокового множника .

У результаті знаходиться нова точка:

(1.12)

Якщо при пошуку максимуму , то робиться новий крок із точки u⁽^k⁺¹⁾ у випадковому напрямку a⁽^k⁺¹⁾ і т.д.

Якщо ж , то вибирається наступний випадковий напрямок і робиться повторний крок із точки .

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

Величина крокового множника може бути постійною, або змінною і вибиратися як за допомогою регулярних алгоритмів, так і за допомогою послідовностей випадкових чисел.

Існує модифікація методу випадкових напрямків – метод випадкових напрямків із зворотним кроком. Помітною її особливістю є те, що при невдалому кроці h_k∙ із точки u⁽^k⁾ відразу здійснюється крок у зворотному напрямку – h_k∙ , тобто реалізується алгоритм:

(1.13)

Алгоритм (1.13) при достатньому віддаленні від екстремуму виявляється досить ефективним.

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

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

Потім здійснюється m пробних кроків за алгоритмом:

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