Оптимізаційні методи планування експериментів Крокова процедура метод Гаусса-Зейделя метод крутого сходження

Цю статтю потрібно відредагувати. Щоб вона відповідала ВИМОГАМ.

{{{img}}}
Імя	Володимир
Прізвище	Готович
По-батькові
Факультет	ФІС
Група	СНм-51
Залікова книжка

Оптимізаційні методи планування експериментів. Крокова процедура, метод Гаусса-Зейделя, метод крутого сходження

 http://elartu.tstu.edu.ua/handle/123456789/372 Презентація доповіді (університетський репозиторій).

Факторний простір та поверхня відклику

Розглянемо простий експеримент, який характеризується двома факторами та одним параметром. Якщо фактори є сумісними між собою, то на площині можна зобразити певну область, в межах якої знаходяться точки, які відповідають станам “чорного ящика” (досліджуваного експериментально об’єкта). Якщо провести ще одну координатну вісь, то отримаємо деяку область простору, в межах якої знаходяться точки, що відповідають значенню параметра оптимізації (рис. 1). Ця область в просторі називається поверхнею відклику а сам простір, в якому будується поверхня відклику, називається факторним простором. Розмірність факторного простору залежить від кількості факторів.

Рис.1 - Поверхня відклику

У випадку двох факторів достатньо обмежитися площиною. Якщо спроектувати поверхню відклику на площину, на якій визначаються фактори оптимізації, то отримана проекція, наприклад, може виглядати так, як показано на рис. 2.</p>

Рис.2 - Проекція поверхні відклику на площину

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

Задача оптимізації

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

[math]\overline{x}=\left( {{x}_{1}},{{x}_{2}},...,{{x}_{n}} \right)[/math]

Задача оптимізації зводиться до пошуку таких значень параметрів [math]x_{1}^{0},x_{2}^{0},...,x_{n}^{0}[/math], при яких цільова функція досягає екстремуму (максимуму або мінімуму). Для однозначності загальних міркувань вважатимемо оптимальним максимальне значення виходу:

[math]{{y}_{}}(x)={{y}_{max}}(x);[/math]

[math]{{y}_{opt}}(\overline{{{x}^{0}}})={{y}_{\max }}(\overline{x})[/math]

Залежність

[math]y(\overline{x})=f({{x}_{1}},{{x}_{2}},{{x}_{3}},...,{{x}_{n}})[/math]

утворює деяку поверхню в [math](n+1)[/math] - вимірному просторі [math]{{x}_{1}},{{x}_{2}},{{x}_{3}},...,{{x}_{n}}[/math]. Цю поверхню прийнято називати поверхнею відклику, а окремі її точки або значення [math]y[/math] в точках [math]x[/math] факторного простору – просто відкликом. В тих випадках, коли залежність [math]y=(\overline{x})[/math] задана або утворена в аналітичній формі, координати [math](x_{1}^{0},x_{2}^{0},...,x_{n}^{0})[/math] точки екстремуму [math]\overline{{{x}^{0}}}[/math] функції [math]y=(\overline{x})[/math] можна знайти, розв'язавши систему диференціальних рівнянь виду:

[math]\frac{\partial y(\overline{x})}{\partial {{x}_{i}}}=0;i=1,2,...,n.[/math]

Розв'язком цієї системи є стаціонарна точка [math]\overline{x}[/math], в якій градієнт функції [math]y=(\overline{x})[/math] перетворюється в нуль:

[math]grady(\overline{x})=0.[/math]

Нагадаємо, що

[math]grady=\frac{\partial y}{\partial {{x}_{1}}}\overline{{{L}_{1}}}+\frac{\partial y}{\partial {{x}_{2}}}\overline{{{L}_{2}}}+...+\frac{\partial y}{\partial {{x}_{n}}}\overline{{{L}_{n}}},[/math]

де [math]\overline{{{L}_{i}}}[/math] – напрямний вектор координатної осі [math]{{x}_{i}}[/math]. У більшості практичних випадків аналітична залежність [math]y=(\overline{x})[/math] невідома і єдине, що є у розпорядженні дослідника – це можливість спостерігати значення відклику при будь-якій комбінації варійованих факторів [math]({{x}_{1}},{{x}_{2}},{{x}_{3}},...,{{x}_{n}})[/math]. Задача оптимізації ускладнюється, якщо залежність [math]y=(\overline{x})[/math], яка описує властивості об'єкта дослідження, змінюється таким чином, що координати екстремальної стаціонарної точки зсуваються. Тоді говорять, що об'єкту притаманні дрейфуючі характеристики. При розв'язанні задач оптимізації користуються двома способами:
1) визначають повну математичну модель і задачу розв'язують аналітичним або чисельним способом;
2) здійснюють експериментальний пошук стаціонарної точки [math]\overline{{{x}^{0}}}[/math] у факторному просторі змінних [math]{{x}_{1}},{{x}_{2}},{{x}_{3}},...,{{x}_{n}}[/math].
Другий спосіб набуває все більшого визнання, оскільки дає можливість оптимального поєднання експериментальної роботи і математичного опрацювання при максимальному виході інформації.

Кроковий принцип пошуку оптимуму

За умови, коли ми свідомо відмовляємося при пошуку оптимуму від повного перебору всіх можливих значень функції відклику, доводиться накладати обмеження на математичну модель досліджуваного об’єкта ще до початку експерименту. Йдеться про те, що з метою спрощення задачі припускають про неперервний характер поверхні відклику та про наявність однієї єдиної точки відклику, хай навіть і на межі області визначення факторів експерименту.
Якщо, наприклад, ми знатимемо значення параметра оптимізації в декількох сусідніх точках факторного простору, то ми зможемо (на основі попередньо зробленого припущення про безперервність функції відклику) приблизно обчислити значення цього параметра, на які можна очікувати в інших, сусідніх точках. Отже, можна знайти такі точки, для яких очікується найбільше збільшення (або зменшення, якщо ми шукаємо мінімум) параметра оптимізації. Тоді вже очевидно, що наступний експеримент треба переносити саме в ці точки факторного простору. Тобто, слід просуватися в цьому напрямку, нехтуючи іншими (ось де економляться досліди). Провівши новий експеримент, знову можна оцінити напрям, в якому швидше за все слід рухатися.
Оскільки оптимум єдиний, ми таким чином рано чи пізно неодмінно його досягнемо. Іншими словами, ми вибираємо у факторному просторі якусь точку і розглядаємо безліч точок в її околі, тобто вибираємо в області визначення факторів невелику підобласть. Тут ми хочемо провести експеримент, на підставі якого повинна бути побудована перша модель. Цю модель ми маємо намір використовувати для прогнозу результатів дослідів в тих точках, які не входили в експеримент. Якщо ці точки лежать всередині нашої невеликої підобласті, то такий прогноз називається інтерполяцією, а якщо ззовні – екстраполяцією. Чим далі від області експерименту лежить точка, для якої ми хочемо передбачити результат, тим з меншою упевненістю це можна робити. Тому ми вимушені екстраполювати недалеко і використовувати результати екстраполяції для вибору умов проведення наступного експерименту. Далі цикл повторюється. В цьому і полягає кроковий принцип оптимізації. Також отриману модель можна використовувати для перевірки різних гіпотез про природу досліджуваного явища. Наприклад, можна перевірити апріорне припущення про те, що зростання значення певного фактора призводить до зростання значення параметра оптимізації. Така перевірка називається інтерпретацією моделі.
На рис. 3 найпростіший варіант крокового пошуку точки оптимуму. Хрестиками позначені окремо взяті точки (умови досліду).

Рис.3 - Найпростіший приклад крокового пошуку точки оптимуму

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

Метод Гаусса-Зейделя

Суть методу Гаусса-Зейделя полягає у послідовному просуванні до екстремуму, яке здійснюється шляхом почергового варіювання кожним із параметрів до досягнення часткового екстремуму вихідної величини. Інакше кажучи, робоча точка [math]x[/math] пересувається поперемінно вздовж кожної із координатних осей [math]{{x}_{i}};i=1,2,...,n[/math] факторного простору, причому перехід до нової [math]\left( i+1 \right)[/math]-ї координати здійснюється після досягнення часткового екстремуму цільової функції [math]y=(\overline{x})[/math] на попередньому напрямі, тобто в точці [math]{{x}_{i0}}[/math], де

[math]\frac{\partial y\left( {{x}_{1}},{{x}_{2}},...,{{x}_{i0}},...,{{x}_{n}} \right)}{\partial x}=0.[/math]

Досягнувши часткового екстремуму по останній координаті [math]{{x}_{n}}[/math], переходять знову до варіювання першої і т. д. Таким чином, характерною особливістю методу є необхідність тривалої стабілізації всіх факторів (параметрів процесу), крім одного, за яким відбувається рух. Напрям руху уздовж [math]\left( i+1 \right)[/math] -ї координатної осі обирається за результатами двох пробних експериментів, які полягають у вимірюванні відклику [math]y(\overline{{{x}_{i+1;1}}})[/math] і [math]y(\overline{{{x}_{i+1;2}}})[/math] в околі базової точки [math]{{x}_{i,0}}[/math], тобто точки часткового екстремуму за попередньою [math]i[/math]-змінною. Викладені загальні міркування ілюструються на прикладі двофакторної задачі (рис. 4). Тут цифрами 10, 20, 30 позначено лінії рівного рівня вихідного параметра [math]y[/math] в деяких відносних одиницях.

Рис.4 - Застосування методу Гауса-Зейделя при пошуку точки оптимуму для двофакторної задачі

При практичному використанні методу Гаусса-Зейделя для оптимізації двофакторного процесу, бажана така послідовність операцій:
1) визначається початкова точка [math]{{x}_{0}}[/math] руху до оптимуму. В реальних умовах вона відповідає прийнятому технологічному режиму, висівному регламенту або раціону годівлі;
2) задається крок варіювання [math]\Delta {{x}_{i}}[/math] по кожній незалежній змінній [math]{{x}_{i}}(i=1,2,...)[/math];
3) здійснюється пробний рух з центром у початковій точці для з’ясування напрямку руху в першому робочому циклі (вздовж осі [math]{{x}_{1}}[/math]). З цією метою з базової точки [math]{{x}_{0}}[/math] варіацією параметра [math]{{x}_{1}}[/math] на [math]\Delta {{x}_{1}}[/math] і [math]-\Delta {{x}_{1}}[/math] виконуються два пробних кроки в точці (при [math]n=2[/math]):

[math]\overline{{{x}_{1,1}}}=({{x}_{1}}-\Delta {{x}_{1}},{{x}_{2}})[/math] та [math]\overline{{{x}_{1,2}}}=({{x}_{1}}+\Delta {{x}_{1}},{{x}_{2}}).[/math]

Проводиться однократне вимірювання відклику [math]y(\overline{{{x}_{1,g}}}),g=1,2,...[/math];
4) здійснюється порівняння значень відклику у пробних точках і його результати виражаються за допомогою функції

[math]sgn[ y(\overline{{{x}_{1,2}}})-(\overline{{{x}_{1,1}}}) ][/math]

5) здійснюється перший цикл робочого руху (з тим же кроком [math]\Delta {{x}_{1}}[/math]) в напрямку зростання цього відклику. Нові координати точки дорівнюватимуть:

[math]\begin{align} & \overline{{{x}_{1,3}}}=({{x}_{1}}+2\varphi \Delta {{x}_{1}},{{x}_{2}}); \\ & \overline{{{x}_{1,4}}}=({{x}_{1}}+3\varphi \Delta {{x}_{1}},{{x}_{2}}); \\ & \overline{{{x}_{1,l}}}=({{x}_{1}}+(l-1)\varphi \Delta {{x}_{1}},{{x}_{2}}); \\ & \overline{{{x}_{1,l+1}}}=({{x}_{1}}+\varphi l\Delta {{x}_{1}},{{x}_{2}}). \\ \end{align}[/math]

6) проводиться вимірювання значень відклику після кожного робочого кроку

[math]y(\overline{{{x}_{1,3}}}),y(\overline{{{x}_{1,4}}}),...,y(\overline{{{x}_{1,l}}}),y(\overline{{{x}_{1,l+1}}});[/math]

7) припиняється перший цикл крокового руху після досягнення у деякій точці [math]\overline{{{x}_{1,i}}}[/math] часткового екстремуму цільової функції по відповідній змінній

[math]\frac{\partial y(\overline{{{x}_{i,l}}})}{\partial {{x}_{i}}}=0.[/math]

Критерієм зупинки є виконання рівності [math]y({{x}_{i,l+1}})\lt y({{x}_{i,l}})[/math].
8) точка [math]\overline{{{x}_{i,l}}}[/math] є вихідною для нових пробних експериментів у точках

[math]\begin{align} & \overline{{{x}_{2,l+2}}}=({{x}_{1,l}},{{x}_{2}}-\Delta {{x}_{2}}); \\ & \overline{{{x}_{2,l+3}}}=({{x}_{1,l}},{{x}_{2}}+\Delta {{x}_{2}}). \\ \end{align}[/math]

Якщо у пробному русі по [math]i[/math]-й змінній обидва кроки були невдалими [math]y({{x}_{i,l\pm k}})\lt y({{x}_{i,l}})[/math], то переходять до варіювання наступним [math](i+1)[/math] параметром
9) в подальшому процедура є аналогічною до описаних вище. Після закінчення другого циклу переходять до третього (знову по осі [math]{{x}_{1}}[/math]) і т.д.
Пошук припиняється в деякій точці [math]\overline{{{x}_{m}}}[/math], подальший будь-який рух від якої призводить до зменшення (якщо досягнуто мінімуму – до збільшення) значення вихідного параметра. З точністю до максимального кроку варіювання [math]{{(\Delta {{x}_{i}})}_{\max }}[/math] це і буде точка екстремуму цільової функції.
До недоліків методу варто віднести те, що процедура пошуку оптимуму є досить тривалою, особливо у випадку, коли є багато факторів (змінних в моделі досліджуваного процесу). Також можливі деякі труднощі при пошуку оптимуму, зумовлені особливостями цільової функції. Тому досить часто обмежуються почерговим однократним варіюванням по кожній із змінних. Метод широко використовується у прикладних дослідженнях. Наприклад, при розв’язуванні систем рівнянь типу:

[math]\left\{ \begin{align} & {{a}_{11}}{{x}_{1}}+...+{{a}_{1n}}{{x}_{1}}={{b}_{1}}; \\ & ... \\ & {{a}_{n1}}{{x}_{1}}+...+{{a}_{nn}}{{x}_{n}}={{b}_{n}}. \\ \end{align} \right.[/math]

Або ж для знаходження оптимуму таких функцій, як:

[math]f({x}_{1},{x}_{2})=10{x}_{1}^{2}+2{( {x}_{2}-5 )}^{2},[/math]

[math]f({x}_{1},{x}_{2},{x}_{3})=3+2{x}_{1}+{x}_{2}+{x}_{1}^{2}+2{{x}_{2}}^{2}+{x}_{1}{x}_{2}+5{x}_{3}[/math]

Метод крутого сходження (Бокса-Уілсона)

Метод крутого сходження, або метод Бокса-Уілсона, поєднує істотні елементи методу Гауса-Зейделя і градієнтного методу з методами повнофакторного і дробового факторного експерименту. Так, при використанні алгоритму крутого сходження кроковий рух з точки [math]\overline{{{x}_{k}}}[/math] здійснюється в напрямі найшвидшого зростання рівня виходу, тобто по [math]grad(\overline{{{x}_{k}}})[/math]. Тобто, у факторному просторі знаходиться напрямок, в якому найшвидше зростає (спадає у випадку пошуку мінімуму) вихідний параметр досліджуваного об’єкта. Проте, на відміну від градієнтного методу, коректування напряму здійснюється не після кожного наступного кроку, а після досягнення в деякій точці [math]\overline{{{x}_{m}}}[/math] на даному напрямку часткового екстремуму цільової функції (рис. 5), аналогічно методу Гаусса-Зейделя.

Рис.5 - Застосування методу крутого сходження при пошуку точки оптимуму для двофакторної задачі

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

[math]y={{b}_{0}}+{{b}_{1}}{{x}_{1}}+...+{{b}_{n}}{{x}_{n}}.[/math]

Оскільки координатами вектора [math]grady(\overline{x})=\left( \frac{\partial y}{\partial {{x}_{1}}},\frac{\partial y}{\partial {{x}_{2}}},...,\frac{\partial y}{\partial {{x}_{n}}} \right)[/math] є коефіцієнти при лінійних членах розкладу функції [math]y(\overline{x})[/math] в ряд Тейлора по ступенях [math]{{x}_{i}}(i=1,2,...,n)[/math], то відповідні компоненти вектора градієнта можуть бути утворені як коефіцієнти [math]{{b}_{1}},{{b}_{2}},...,{{b}_{n}}[/math] лінійної апроксимації поверхні відклику поблизу вихідної точки [math]\overline{x}[/math]:

[math]y= {{b}_{0}}+{{b}_{1}}{{x}_{1}}+{{b}_{2}}{{x}_{2}}+...+{{b}_{n}}{{x}_{n}}.[/math]

Найпростішим способом знаходження оцінок кожного із коефіцієнтів [math]{{b}_{1}},{{b}_{2}},...,{{b}_{n}}[/math] є їх знаходження за результатами пробних рухів з точки [math]\overline{{{x}_{k}}}[/math]. Для цього по кожній координаті роблять два пробних кроки, довжиною [math]\rho[/math], в точки [math]{{x}_{i}}-\rho[/math] та [math]{{x}_{i}}+\rho[/math]. Решту координат фіксують незмінними, що відповідає точці [math]\overline{{{x}_{k}}}[/math]. За результатами вимірювань функції відклику [math]{{y}_{1}}=y({{x}_{k1}},{{x}_{k2}},...,{{x}_{k1}}+\rho ,...,{{x}_{kn}})[/math] та [math]{{y}_{2}}=y({{x}_{k1}},{{x}_{k2}},...,{{x}_{k1}}-\rho ,...,{{x}_{kn}})[/math] в утворених точках знаходять відповідні коефіцієнти

[math]{{b}_{i}}=\frac{\Delta y}{\Delta {{x}_{i}}}=\frac{{{y}_{1}}-{{y}_{2}}}{\Delta {{x}_{i}}}.[/math]

Порядок виконання операцій при пошуку екстремуму за методом крутого сходження такий (рис. 5):
1) проводиться повний або дробовий факторний експеримент з центром у вихідній точці [math]\overline{{{x}_{0}}}[/math] для визначення [math]grady(\overline{{{x}_{0}}})[/math]. Результати експерименту піддаються статистичному аналізу, який включає:
а) перевірку відтворюваності експерименту;
б) перевірку значущості оцінок коефіцієнтів [math]{{b}_{i}}[/math] лінійної моделі об'єкта;
в) перевірку адекватності утвореної лінійної моделі

[math]y={{b}_{0}}+{{b}_{1}}{{x}_{1}}+...+{{b}_{n}}{{x}_{n}}[/math]

досліджуваному об'єкту;
2) обчислюються добутки [math]{{b}_{i}}\Delta {{x}_{i}}[/math], де [math]\Delta {{x}_{i}}[/math] – крок варіювання параметра [math]{{x}_{i}}[/math] при проведенні повнофакторного експерименту, і фактор, для якого цей добуток максимальний, береться як базовий

[math]\max ({{b}_{i}}\Delta {{x}_{i}})={{b}_{6}}\Delta {{x}_{6}};[/math]

3) для базового фактора вибирають крок варіювання при крутому сходженні [math]\rho[/math], залишаючи старий крок або впроваджуючи дрібніший;
4) визначаються розміри [math]{{\rho }_{i}}[/math] за рештою змінних процесу [math]{{x}_{j}}(j\ne i)[/math]. Оскільки під час руху по градієнту варійовані параметри повинні змінюватися пропорційно коефіцієнтам [math]{{b}_{j}}=\frac{\Delta y}{\Delta {{x}_{i}}}[/math], які є компонентами вектора [math]grady(x)[/math], то відповідні [math]{{\rho }_{j}}[/math] знаходяться за формулою

[math]{{\rho }_{j}}=\frac{{{b}_{j}}\Delta {{x}_{j}}}{\left| {{b}_{6}}\Delta {{x}_{6}} \right|}\rho ,[/math]

де [math]\rho[/math] і [math]\Delta {{x}_{j}}[/math] завжди додатні, а коефіцієнт [math]{{b}_{j}}[/math] береться із своїм знаком;
5) проводяться уявні досліди, які полягають у завбаченні значень виходу [math]{{y}_{zawb .k}}(\overline{{{x}_{k}}})[/math] у певних точках [math]\overline{{{x}_{k}}}[/math] факторного простору (рис. 6). Для цього незалежні змінні лінійної моделі об'єкта змінюються з урахуванням [math]{{b}_{i}}=\frac{\Delta y}{\Delta {{x}_{i}}}[/math] таким чином, щоб зображуюча точка [math]\overline{x}[/math] виконувала кроковий рух у напрямку вектора [math]grad(\overline{{{x}_{1}}})[/math], утвореного в п. 1, займаючи послідовно положення [math]\overline{{{x}_{1}}},\overline{{{x}_{2}}},...,\overline{{{x}_{k}}},...,\overline{{{x}_{m}}};[/math].
6) уявні досліди продовжуються до тих пір, поки виконується нерівність

[math]{{y}_{zawb .k}}\le (1..2){{y}_{\max }},[/math]

де [math]{{y}_{\max }}[/math] - максимально можливий вихід, який визначається з фізичних міркувань;
7) деякі з уявних дослідів (звичайно через кожні 2 — 3 кроки) реалізуються на об'єкті для перевірки відповідності апроксимації об'єкта утвореним рівнянням (гіперплощиною). Спостережувані значення [math]{{y}_{spost}}[/math] порівнюються із завбаченими [math]{{y}_{zawb}}[/math] (рис. 5);
8) точка [math]\overline{{{x}_{m}}}[/math], де в реальному досліді утворено максимальне значення виходу, береться за нову початкову точку, і етап крутого сходження, описаний вище, повторюється;
9) оскільки кожен етап крутого сходження наближає зображуючу (робочу) точку до області екстремуму [math]y(\overline{x})[/math], де крутість поверхні відклику менша, то для кожного наступного етапу [math]\rho[/math] береться рівним або меншим попереднього;
10) пошук припиняється, коли всі коефіцієнти [math]{{b}_{i}}(i=1,2,...,n)[/math] лінійної моделі об'єкта виходять незначущими (коли модуль градієнта стає малою величиною [math]grady(x)=0[/math]). Це свідчить про вихід в область екстремуму цільової функції.
Метод крутого сходження застосовується, зокрема, при побудові та дослідженні моделей процесів збагачення корисних копалин та ін. технологічних процесів, при гідродинамічних дослідженнях газліфтних нафтових свердловин.

Перелік використаних джерел

1. Аністратенко В. О., Федоров В. Г. Математичне планування експериментів в АПК: Навч. Посібник. – К.: Вища шк., 1993. – 375 с. іл..
2. Ю. П. Адлер, Е. В. Маркова, Ю. В. Грановский Планирование єксперимента при поиске оптимальних условий. Программированное введение в планирование эксперимента.:М. Наука 1971 г.
3. http://uk.wikipedia.org/wiki/Метод_Гауса_—_Зейделя – Метод Гауса — Зейделя (січень 2010)
4. http://uk.wikipedia.org/wiki/Метод_Бокса_—_Вілсона – Метод Бокса — Вілсона (січень 2010)