5.3) рисунок схеми та завдання за варіантом; 5.4) ЦФ та графіки ЦФ в межах, що містять мінімум, для кожного із опорів;

5.5) результати пошуку мінімуму ЦФ методом «золотого перетину» для обраного опору; 5.6) файл завдання та фрагмент вихідного файлу, що містить результати

пошуку мінімуму за допомогою пакету NetALLTED; 5.7) зведена таблиця з результатами по КОЦФ (табл. 7.3); 5.8) висновки.

6 Контрольні запитання

6.1) Типи ЦФ, що використовуються в NetALLTED.

6.2) За допомогою яких директив NetALLTED задаються характеристики, що оптимізуються?

6.3) Головні відмінності вирішення задачі одномірної мінімізації за допомогою NetALLTED та розробленої програми МЗП.

6.4) Можливі види закінчення пошуку в NetALLTED.

59

ЛАБОРАТОРНА РОБОТА № 8.

ВИКОРИСТАННЯ МЕТОДІВ БЕЗУМОВНОЇ БАГАТОПАРАМЕТРИЧНОЇ ОПТИМІЗАЦІЇ ДЛЯ ВИРІШЕННЯ ПРАКТИЧНИХ ЗАДАЧ

1 Мета роботи

Ознайомитись на практиці з використанням методів багатопараметричної оптимізації для вирішення практичних задач в галузі електроніки за допомогою пакету NetALLTED.

2 Короткі теоретичні відомості

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

-методи випадкового пошуку;

-детерміновані (регулярні) методи;

-методи з використанням алгоритмів чисельного інтегрування.

Метод випадкового пошуку зі зменшенням інтервалу пошуку (ВПЗІП). Багато методів випадкового пошуку екстремуму зводяться в тій чи іншій формі до побудови послідовності {x(k ) }, що визначається співвідношенням: x(k +1) = x(k ) + λξ(k ) , де λ(k ) - деяка позитивна скалярна величина, ξ(k ) = [ξ1(k ) ,ξ2(k ) ,...,ξn(k ) ] - деяка реалізація n - мірного випадкового вектора ξ . При цьому, як робочий напрямок ξ(k ) вибирається такий, щоб

виконувалася умова f (x(k+1) ) < f (x(k ) ) .

Усі методи випадкового пошуку можуть бути розділені на дві підмножини [7]: алгоритми без навчання й алгоритми із самонавчанням.

60

До першого відносяться методи, у яких область зміни вектора варійованих параметрів x , а також закон розподілу випадкового вектора ξ не залежить від номеру кроку пошуку. До таких методів можна віднести метод прямої вибірки, метод групової вибірки зі зменшенням інтервалу (ГВПЗІ) та деякі інші алгоритми [1, 7]. Головна особливість алгоритму без навчання полягає в тому, що для розрахунку координат нової робочої точки не враховується інформація, яка отримана на попередніх кроках пошуку.

Частково від цього недоліку звільнені алгоритми із самонавчанням. Одним з найбільш відомих на практиці алгоритмів цієї групи є алгоритм ВПЗІП. Основна ідея цього алгоритму полягає в наступному.

На кожному кроці пошуку N раз (N – розмір вибірки) оцінюються значення ЦФ f (x( j) ) , j =1(1)N . Складові кожного з векторів хj генеруються згідно рівномірному закону розподілу із області допустимих значень параметрів, що варіюються , випадковим чином згідно співвідношенню:

xi(kj) = xi(mink ) +ηij (xi(maxk ) − xi(mink ) ),i =1(1)n,

де η j - множник, який виробляється генератором випадкових чисел з інтервалу [0,1], к – номер кроку. Для кожного значення перевіряється умова:

f (x( j) ) ≤ fп(k ) ,

де fп(k ) - порогове значення ЦФ на к-му кроці пошуку. Якщо ця умова виконується, то спроба вважається успішною. По всім успішним спробам ведеться облік відповідних значень ЦФ і значень варійованих параметрів з метою визначення найменшого значення ЦФ та границь змін

61

варійованих параметрів для наступного кроку ( xi(mink+1) , xi(maxk+1) , i =1(1)n ). Причому:

j

де p – кількість успішних спроб. У якості порогового рівня на k +1 кроці fп(k+1) приймається значення fmi(kп) (рис. 8.1).

f

fn(0)

fn(1)

x(1)min

Рисунок 8.1 – Зменшення інтервалу методом ВПЗІП

У якості критерію закінчення пошуку може бути використано співвідношення:

62

де ε – точність пошуку.

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

fп(k+1) = fп(k ) +0.5( fп(k ) − ),

де

На практиці, область оптимуму надійно утримувалась при m=5.

З метою недопущення втрати оптимуму перед переходом до наступного кроку, доцільно перевірити межи допустимої області (точки xi(mink ) , xi(maxk ) , i =1(1)n ) на виконання умови (8.1). В тих випадках, коли для якихось з цих точок умова (8.1) виконується, то на наступному кроці відповідна межа не змінюється.

Значний вплив на ефективність алгоритму оказує вибір початкового начального значення ЦФ fп(0) . Вибір занадто малого значення fп(0)

збільшує ймовірність втрати області оптимуму навіть при проведенні великої кількості спроб на кожному кроці пошуку екстремуму. В той же

63

час завдання великого порогового значення не визиває суттєвого

зменшення області пошуку на першому кроці оптимізації, який в цьому випадку перетворюється лише на вибір більш коректного fп(0) . Тому на практиці величина fп(0) обирається на основі оцінки початкового значення ЦФ f (x(0) ) за допомогою наступних співвідношень:

залежність результату пошуку від координат початкової точки x(0) і від кількості варійованих параметрів. Їх перевагою так само варто вважати і те, що для визначення напрямку зменшення f (x) використовується

інформація тільки про значення самої ЦФ.

При використанні методів випадкового пошуку, хоча і можна досить

вдається одержати результат за прийнятну кількість оцінок ЦФ.

Усе це робить доцільним і можливим використовувати методи випадкового пошуку лише на деяких початкових етапах розв’язку

64

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

Метод Бройдена-Флетчера-Гольдфарба-Шенно (BFGS).

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

В основу цих методів покладена апроксимація зворотної матриці Гессе Η−1 (x(k ) ) деякою допоміжною матрицею η(k ) , що й обумовило назву самих алгоритмів. При такому підході усувається один з головних недоліків ньютонівських методів, що ускладнюють їхнє ефективне використання для розв’язку задач параметричної оптимізації складних систем - необхідність обчислення матриці других похідних та

забезпечення її додатної визначеності.

Загальна ітераційна формула для всіх квазіньютонівських методів має вигляд:

Значення елементів матриці η(k ) обчислюються на основі інформації про цільову функцію в k -ій та ( k −1)-ій точках пошуку f (x(k ) ) , f (x(k−1) ) , її

різноманіття квазіньютонівських методів мінімізації.

Для апроксимації матриці η(k ) використовується наступне співвідношення:

65

g(x) = g(x(k ) ) + H (x(k ) )(x − x(k ) ),

тоді для x(k +1) маємо:

g(x(k +1) ) = g(x(k ) ) + Η(x(k ) )(x(k +1) − x(k ) ) g(x(k +1) ) − g(x(k ) ) = Η(x(k ) )(x(k +1) − x(k ) ) .

Помноживши обидві частини рівняння на Η−1 (x(k ) ) , отримаємо:

(x(k +1) − x(k ) ) = Η−1(x(k ) )[g(x(k +1) ) − g(x(k ) )]

(Якщо f (x) – квадратична функція, то Η(x(k ) ) = Η , тобто матриця Гессе постійна). Це рівняння можна розглядати як систему n лінійних рівнянь, що містять n невідомих параметрів, котрі необхідно оцінити для того, щоб апроксимувати Η−1 (x) або Η(x) при заданих значеннях f (x), g(x), x на більш ранніх етапах пошуку. У досить великій групі методів Η−1 (x(k +1) )

апроксимується з допомогою інформації, отриманої на к-му кроці:

66

Η−1 (x(k +1) ) ≈ ωη(k +1) = ω(η(k ) +ηc(k ) ),

де ω - масштабуючий множник (константа, що зазвичай дорівнює 1). На (k+1) – му кроці відомі наступні значення: x(k ) , g(x(k ) ), g(x(k +1) ),η(k ) . Необхідно обчислити η(k +1) таким чином, щоб задовольнялось співвідношення:

η(k +1) [g(x(k +1) ) − g(x(k ) )]= ω1 (x(k +1) − x(k ) ),

або:

де

g(k ) = g(x(k+1) ) − g(x(k ) ) x(k ) = x(k +1) − x(k ) .

Враховуючи, що ηc(k ) =η(k +1) −η(k ) , і підставляючи це у попереднє рівняння, отримаємо:

67

алгоритм Давідона–Флетчера–Пауелла. Можуть бути і інші можливі вибори векторів y, z.

Якщо кроки x(k ) визначаються шляхом мінімізації f (x) у напрямку

S (k ) , то всі методи, з допомогою яких обчислюють симетричну матрицю

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

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

Вхідні дані:

Початкова точка x(0) , параметри завершення ε1,ε2 .

1) Задати координати початкової точки , k=0. Обчислити g(x(k ) ) . Нехай

η(0) = I , де I – одинична діагональна матриця.

68

g(k ) >ε1 , якщо f (x) → 0 .

або:

xi(k ) > ε2 , якщо xi → 0 .

6)Якщо нерівності не виконуються, пошук завершується, інакше п.7.

7)k=k+1. Обчислити η(k ) за допомогою одного з квазіньютоновських методів, наприклад BFGS:

69

Перехід до п. 2.

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

Розглянемо порядок застосування методів багатомірного пошуку для вирішення задач оптимізації певних характеристик електричної схеми.

Нехай для схеми (рис. 8.2) необхідно змінюючи значення опорів R1,R2 отримати напругу у 2-му вузлі U2 =V=3 В.

Рисунок 8.2 – Схема електрична

Параметри схеми: E1 = 5 В, R1=R2=5 Ом.

Вочевидь, що одним з рішень буде значення, яке отримано в прикладі для ЛР №7. Скористаємось сформованою ЦФ з ЛР №7 :

. F(R1, R2) = (V −U 2)2

ЦФ в залежності від значення опорів R1,R2 буде мати вигляд (рис. 8.3):

70