Реферати українською » Информатика, программирование » Градієнтний метод першого порядку


Реферат Градієнтний метод першого порядку

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

2. При виборі чинників треба виконувати такі вимоги: чинник може бути регульованим, т. е. певним регулюючим пристроєм чинник мусить змінюватись від значення xі до значення x’’і; точність зміни та управління чинником має бути відома і висока (хоча на порядок вище точності виміру вихідний перемінної), очевидно, що низька точність виміру чинника зменшує можливості відтворення експерименту; зв'язок між чинниками має бути як можна меншою (в межі має бути відсутня), це властивість називають однозначністю чинників, що він відповідає незалежності одного чинника від іншого.

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

Успіх сучасного експериментування значною мірою зобов'язаний теорії експерименту, що має дати експериментатору відповіді такі питання:

1. Як треба організувати експеримент, щоб найкраще вирішити це завдання (себто витрат часу, коштів чи точності результатів).

2. Як випливає обробляти результати експерименту, щоб отримати якомога більше інформацію про досліджуваному об'єкті.

3. Які обгрунтовані висновки можна зробити про досліджуваному об'єкті за результатами експерименту.

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

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

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

Моделювання і програмування динамічних систем

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

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

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

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

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

У кожному разі стадія чи щабель – це математична абстракція, застосовується до подання безупинної перемінної в дискретному вигляді. Стан системи характеризується сукупністю змінних, що описують систему про всяк стадії процесу.

Кожна стадія характеризується вхідними xі-1 і вихідними xі параметрами, і навіть параметрами управління uі. З допомогою управляючих впливів оптимізується результуюча оцінка ефективностімногостадийного процесу, обумовлена якаддитивная функція результатів, одержуваних з кожної стадіїui(x1і-1, uі):

 (1)

Значення критерію оптимальності RN залежить від сукупності uN управляючих впливів усім стадіях. Сукупність управлінь називається стратегією управліннямногостадийним процесом.

Основним рівнянням динамічного програмування є функціональне рівняння виду:

, (2)

де -оптимизируемая функціяN-стадийного процесу, максимальне значення критерію RN.

>Максимизация першого доданкаr1(x0,u1), це приватний критерій, що характеризує першу стадію, здійснюється лише із управління u1.

Член є значенняоптимизируемой функції наступнихN-1 стадіях імаксимизируется вибором управлінь усім стадіях, uі (I =1,…,N), оскільки значення x1 залежить від керівництва u1.

Вислів (2) єрекуррентное співвідношення, характеризує послідовність функцій останню з яких відповідає згаданої рішенню оптимальної завдання. Стратегія рішення виражається системою вибраних значень uі – членів рівняння (2), де і = 1, 2, ..., N; система дає рішення функціонального рівняння. Оптимальна стратегія виражається системою функцій uі, якімаксимизируют праву частина рівняння (2), саме: для і = 1, 2, ..., N.

Часто важливо знати сам характер оптимальної стратегії, ніж значенняоптимизируемой функції. У результаті визначення функціїfN(x) отримують одночасно послідовність рішень uі чи стратегію й у вигляді функції номери стадії і.

Рішеннярекуррентних рівнянь зазвичай виконується численними методами. Нерідко використовують наступна послідовність спокути перед застосуванням обчислювальної машини: спочатку знаходятьf1(x), потім знайденому значенням функціїf1(x) по рівнянню ( 1 ) визначають функціюf2(x); далі послідовно визначаютьf3(x) зf2(x) тощо.

За позитивного рішення завдань оптимізації і моделюванні динамічної системи методом динамічного програмування слід звернути увагу до такі основні тези:

А)оптимизируемий процес має бутидискретно-распределенним у часі чи просторі (>многостадийний процес);

Б) окремі стадії процесу повинні мати відносної незалежністю, тобто. вектор вихідних параметрів будь-який стадії повинен залежати тільки від вектора вхідних параметрів з цього стадію, і управління у ньому;

У) критерій оптимальності всього процесу має бути сформульований якаддитивная функція критеріїв оптимальності кожної стадії.

Якщо виконуються цих умов, необхідно правильно сформулювати завдання оптимізації. При формулюванні завдання оптимізації і моделювання би мало бути виявлено: 1) параметри, що характеризують стан кожної стадії; 2) управляючі параметри з кожної стадії; 3) обмеження, що накладаються на параметри стану процесу управляючі параметри. З іншого боку, має бути складено математичне опис кожної стадії і визначено критеріїв оптимальності.

 

>Градиентние методи оптимізації

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

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

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

Якщо критерій заданий рівнянням

, (3)

його градієнт у точці (x1, x2,…, xn) визначається вектором:

. (4)

Приватна похідна пропорційнакосинусу кута, утвореного вектором градієнта зi-й віссю координат. У цьому

 (5)

Поруч із визначенням напрямиградиентного вектора основним питанням, що розв'язуються під час використанняградиентних методів, є вибір кроку руху по градієнту. Розмір кроку напряміgradF значною мірою залежить від виду поверхні. Якщо крок замалий, знадобляться тривалі розрахунки; якщо дуже великий, можна проскочити оптимум. Розмір кроку повинен відповідати умові, у якому всі дії від базисної точки лежать у те ж саме напрямі, як і градієнт в базисної точці. Розміри кроку з кожної перемінної xі обчислюються з значень приватних похідних у базовій (початковій) точці:

, (6)

де До – константа, визначальна розміри кроку та однакова всімi-х напрямів. Тільки базової точці градієнт сувороортогонален до. Якщо ж кроки дуже великі у кожномуi-м напрямі, вектор з базисної точки нічого очікуватиортогонален до у новій точці.

Якщо вибір кроку був задовільним, похідна у наступному точці істотно близька до похідною в базисної точці.

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

то

  

і компонента градієнта вi-м напрямі дорівнює

. (7)

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

Попри наявні різницю міжградиентними методами, послідовність операцій у пошуку оптимуму здебільшого однакова і зводиться ось до чого:

а) вибирається базисна точка;

б) визначається собі напрямок руху від базисної точки;

в) перебуває розмір кроку;

р) визначається наступна точка пошуку;

буд) значення цільової функції у цій точці порівнюється зі її значенням у попередній точці;

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

 

>Градиентний метод першого порядку

При оптимізації методом градієнта оптимум досліджуваного об'єкта шукають у бік найбільш швидкого зростання (зменшення) вихідний перемінної, тобто. у бік градієнта. Але як й кроку зробити у бік градієнта, треба її розрахувати.Градиент можна розрахувати або за наявної моделі

>grady(X)= ,

моделювання динамічнийградиентнийполиномиальний

де - приватна похідна поi-му чиннику;

і, j,k – поодинокі вектори у бік координатних осей факторного простору, або за результатам n пробних рухів на шляху координатних осей.

Якщо математична модель статистичного процесу має вигляд лінійногополинома, коефіцієнти регресії bі якого є приватними похідними розкладання функції y =f(X) до кількох Тейлора по ступенів xі, то оптимум шукають у бік градієнта з певним кроком hі:

>пкфвн(Ч)= і1р12р2+…+ітрт

Напрям коректують після кожного кроку.

Метод градієнта разом з його численними модифікаціями є поширеним і ефективнішим методом пошуку оптимуму досліджуваних об'єктів. Розглянемо жодну з модифікацій методу градієнта – метод крутого сходження.

Метод крутого сходження, чи інакше методБокса-Уилсона, об'єднує у собі гідності трьох методів - методуГаусса-Зейделя, методу градієнтів і методу повного (чи дробового) факторного експериментів, як засобу отримання лінійної математичну модель. Завдання методу крутого сходження у тому, щобшаговое рух здійснювати у бік якнайшвидшого зростання (чи зменшення) вихідний перемінної, тобто заgrady(X). На відміну від методу градієнтів, напрям коригується не після кожного такого кроку, а під час досягнення у певній точці цьому напрямі приватногоекстремума цільової функції, як це робиться в методіГаусса-Зейделя. У точці приватногоекстремума ставиться новий факторний експеримент, визначається математична модель і знову здійснюється круте сходження. У процесі руху до оптимуму зазначеним методом регулярно проводитися статистичний аналіз проміжних результатів пошуку. Пошук припиняється, коликвадратичние ефекти в рівнянні регресії стають значимими. Це означає, що досягнуто область оптимуму.

Наведемо принцип використанняградиентних методів з прикладу функції двох змінних

 (8)

за двох додаткових умов:

, .(9)

Цей принцип (без зміни) можна застосувати незалежно від числі змінних, і навіть додаткових умов. Розглянемо площину x1, x2 (>Рис. 1). За формулою (8) кожній точці відповідає деяке значення F. На Мал.1 лінії F =const, належать цьому відношенні, представлені замкнутими кривими, оточуючими точку M*, у якій F мінімально. нехай у початковий момент значення x1 і x2 відповідають точці M0. Цикл розрахунку починається з серії пробних кроків. Спочатку величині x1 дається невеличке прирощення ; тим часом значення x2 незмінно. Потім визначається отримане у своїй прирощення величини F, що можна вважати пропорційним значенням приватної похідною

 (10)

(якщо величина завжди сама й той самий).

Мал.1

Далі дається прирощення величині x2. Саме тоді x1 =const. Отримувана у своїй прирощення величини F є мірою іншої приватної похідною:

. (11)

Визначення приватних похідних ( 10 ) і ( 11 ) означає, що знайдено вектор з координатами і , що називається градієнтом величини F і позначається так:

. (12)

Відомо, що напрям цього вектора збігаються з напрямом найбільш крутого зростання величини F. Протилежне йому напрям – це «>наискорейший спуск», інакше кажучи, найбільш круте убування величини F.

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

, , (13)

де – позитивна константа.

Після кожного працівника кроку оцінюється прирощення величини F. Якщо він виявляється негативним, то рух відбувається у правильному напрямку і треба рухатися у тому самому напрямі M0M1 далі. Якщо ж у точці M1 результат виміру показує, що , то робочі руху припиняються і розпочинається нова серія пробних рухів. У цьому визначається градієнтgradF у новій точці M1, потім робоче рух триває у новій знайденому напрямку якнайшвидшого спуску, т. е. лінією M1M2, тощо. Цей метод називається методом якнайшвидшогоспуска/крутого сходження.

Коли система розташовано неподалік мінімуму, показником чого є мале значення величини

 (14)

відбувається переключення більш «обережний» метод пошуку, так званий метод градієнта. Від методу якнайшвидшого спуску він особливий тим, після відомих визначення градієнтаgradF лише один робочий крок, потім у нової точці знову починається серія пробних рухів. Такий метод пошуку забезпечує точніше встановлення мінімуму проти методом якнайшвидшого спуску, тоді як останній дозволяє швидше наблизитися до мінімуму. Якщо у процесі пошуку точка М сягає межі можливої області й хоча тільки з величин М1, М2 змінює знак, метод змінюється від і точка

Схожі реферати:

Навігація