Методи пошукової оптимізації

1. Призначення і класифікація методів пошукової оптимізації
У зв'язку зі складністю об'єктів проектування критерії якості і обмеження задачі параметричної оптимізації (1.5), як правило, занадто складні для застосування класичних методів пошуку екстремуму. Тому на практиці перевага віддається методам пошукової оптимізації. Розглянемо основні етапи будь-якого методу пошуку.
Вихідними даними в методах пошуку є необхідна точність методу  і початкова точка пошуку Х ^0.
Потім вибирається величина кроку пошуку h, і по деякому правилу відбувається отримання нових точок X ^{k +1} за попередньої точки Х ^k, при k = 0,1,2, ... Отримання нових точок продовжують до тих пір, поки не буде виконана умова перервати пошук . Остання точка пошуку вважається рішенням задачі оптимізації. Всі крапки пошуку складають траєкторію пошуку.
Методи пошуку можуть відрізнятися один від одного процедурою вибору величини кроку h (крок може бути однаковим на всіх ітераціях методу або розраховуватися на кожній ітерації), алгоритмом отримання нової точки і умовою припинення пошуку.
Для методів, які використовують постійну величину кроку, h слід вибирати значно менше точності   h »Öe). Якщо при обраній величині кроку h не вдається отримати рішення з необхідною точністю, то потрібно зменшити величину кроку і продовження пошуку від останньої точки наявної траєкторії.
В якості умов припинення пошуку прийнято використовувати наступні:
усі сусідні точки пошуку гірша, ніж попередня;
çФ (X ^{k +1)} - Ф (X ^k) ç £ e, тобто значення цільової функції Ф (Х) в сусідніх точках (нової і попередньої) відрізняються один від одного на величину не більше, ніж необхідна точність e;
SHAPE \ * MERGEFORMAT

¶

Ф (Х

k

+1

)

£

e

,

i

= 1, ...,

n

,

(2.1)

¶

x

i

тобто всі приватні похідні в новій точці пошуку практично рівні 0 чи відрізняються від 0 на величину, що не перевищує заданої точності e.
Алгоритм отримання нової точки пошуку Х ^{k +1} за попередньої точки Х ^k свій для кожного з методів пошуку, але будь-яка нова точка пошуку повинна бути не гіршою за попередню: якщо завдання оптимізації є завданням пошуку мінімуму, то Ф (Х ^{k +1)} £ Ф (Х ^k).
Методи пошукової оптимізації прийнято класифікувати по порядку похідної цільової функції, використовуваної для одержання нових точок. Так, в методи пошуку нульового порядка не потрібно обчислення похідних, а досить самої функції Ф (Х). Методи пошуку першого порядку використовують перші приватні похідні, а методи другого порядку використовують матрицю других похідних (матрицю Гессе).
Чим вище порядок похідних, тим більш обгрунтованим є вибір нової точки пошуку і тим менше число ітерацій методу. Але при цьому зростає трудомісткість кожної ітерації через необхідність чисельного розрахунку похідних.
Ефективність пошукового методу визначають за кількістю ітерацій і за кількістю обчислень цільової функції Ф (Х) на кожній ітерації методу (N). Розглянемо найбільш поширені методи пошуку, розташувавши їх у порядку зменшення числа ітерацій.
Для методів пошуку нульового порядку справедливо наступне: у методі випадкового пошуку не можна заздалегідь передбачити кількість обчислень Ф (Х) на одній ітерації N, а в методі покоординатного спуску N £ 2 × n, де n-кількість керованих параметрів X = (x1, x2. , ..., xn).
Для методів пошуку першого порядку справедливі наступні оцінки: в градієнтному методі з постійним кроком N = 2 × n; в градієнтному методі з подрібненням кроку N = 2 × n + n _1, де n ₁ - число обчислень Ф (Х), необхідних для перевірки умови дроблення кроку; в методі найшвидшого спуску N = 2 × n + n _2, де n ₂ - число обчислень Ф (Х), необхідних для розрахунку оптимальної величини кроку, а в методі Давідона - Флетчера - Пауелла (ДФП) N = 2 × n + n _3, де n ₃ - число обчислень Ф (Х), необхідних для розрахунку матриці, що наближає матрицю Гессе (для величин n _1, n _2, n ₃ справедливе співвідношення n ₁ <n ₂ <<n _3).
І, нарешті, у методі другого порядку - методі Ньютона N = 3 × n ^2. При отриманні даних оцінок передбачається наближене обчислення похідних за формулами кінцевих різниць / 6 /:
SHAPE \ * MERGEFORMAT

¶

Ф (Х) Ф (

x

1

, ...,

x

i

+

a

.

, ...,

x

n

)

-

Ф (

x

1

, ...,

x

i

.

, ...,

x

n

)

»

,

(2.2)

¶

x

i

a

SHAPE \ * MERGEFORMAT

¶

2

Ф (Х) Ф (

x

1

, ...,

x

i

+

a

.

, ...,

x

n

)

-

2

×

Ф (

x

1

, ...,

x

i

.

, ...,

x

n

) + Ф ((

x

1

, ...,

x

i

-

a

.

, ...,

x

n

)

»

,

(2.3)

¶

x

i

2

2

×

a

тобто для обчислення похідної першого порядку потрібно знати два значення цільової функції Ф (Х) в сусідніх точках, а для другої похідної - значення функції у трьох точках.
На практиці широке застосування знайшли метод найшвидшого спуску і метод ДФП, як методи з оптимальним співвідношенням числа ітерацій і їх трудомісткості.

2. Методи пошуку нульового порядка
2.1. Метод випадкового пошуку
У методі випадкового пошуку вихідними даними є необхідна точність методу e, початкова точка пошуку Х ⁰ = (x1 ^0, x2. ^0, ..., xn ⁰⁾ і величина кроку пошуку h. Пошук нових точок виробляється у випадковому напрямку, на якому і відкладається заданий крок h (рис. 2.1), таким чином отримують пробну точку Х ^{^} і перевіряють, чи є задана точка кращою, ніж попередня точка пошуку. Для задачі пошуку мінімуму це означає, що
Ф (Х ^{^)} £ Ф (Х _^k), k = 0,1,2 ... (2.4)
Якщо умова (2.4) виконано, то пробну точку включають в траєкторію пошуку Х ^{k +1} = Х ^{^.} В іншому випадку, пробну точку виключають з розгляду і виробляють вибір нового випадкового спрямування з точки Х ^k, k = 0,1,2,.
Незважаючи на простоту даного методу, його головним недоліком є той факт, що заздалегідь невідомо, скільки випадкових напрямків буде потрібно для одержання нової точки траєкторії пошуку Х ^{k +1,} що робить витрати на проведення однієї ітерації занадто великими. Крім того, оскільки при виборі напрямку пошуку не використовується інформація про цільову функції Ф (Х), кількість ітерацій в методі випадкового пошуку дуже велике.
У зв'язку з цим метод випадкового пошуку використовується для дослідження маловивчених об'єктів проектування і для виходу із зони тяжіння локального мінімуму при пошуку глобального екстремуму цільової функції / 6 /.
SHAPE \ * MERGEFORMAT

Ф (Х

^

)> Ф (Х

k

)

·

Х

^

Ф (

Х

^

)

£

Ф (Х

k

)

h

X

k

·

·

h

X

k

+1

=

X