На головну

градієнтні методи

  1. I.3.3. Методи виносу в натуру проектних точок.
  2. I.3.4. Методи підготовки даних для перенесення проекту на місцевість.
  3. IV. Багатовимірні статистичні методи
  4. R-методи.
  5. Адміністративні методи управління персоналом
  6. Адміністративні методи управління.
  7. Активні і інтенсивні методи навчання

У багатьох алгоритмах багатовимірної оптимізації так чи інакше використовується інформація про градієнтах. Проілюструємо це положення наступним простим прикладом. Уявімо собі, що альпіністові зав'язали очі і сказали, що він повинен дістатися до вершини «унімодальної» гори. Навіть нічого не бачачи, він може це зробити, якщо весь час буде рухатися вгору. Хоча будь-яка провідна вгору стежка в кінцевому рахунку призведе його до вершини, найкоротшою з них буде найкрутіша, якщо, правда, альпініст НЕ натрапить на вертикальний обрив, який доведеться обходити. (Математичним еквівалентом обриву на поверхні, утвореної цільовою функцією, є ті її місця, де поставлені умовні обмеження.) Припустимо поки, що завдання оптимізації не містить обмежень. Пізніше ми включимо їх в схему пошуку. Метод оптимізації, в основу якого покладено ідею руху по самій крутій стежці, називається методом найшвидшого підйому або найшвидшого спуску. Вектор градієнта перпендикулярний лінії рівня і вказує напрямок до нової точки в просторі проектування. Відзначимо, що градієнтний метод на відміну від методу дотичній до лінії рівня можна використовувати стосовно до будь-якої унімодальної функції, а не тільки тих, у яких ця властивість явно виражена.

 Щоб краще зрозуміти ідею градієнтних методів, докладніше зупинимося на властивостях градієнтів. Розглянемо систему незалежних одиничних векторів е1, е2, е3,. ., eN, спрямованих уздовж осей координат x1 , х2 , х3 ,. . ., xN , є в той же час: проектними параметрами. Вектор градієнта довільної цільової функції F (х1, х2, х3 ,. . ., ХN ) має вигляд

де приватні похідні обчислюються в розглянутій точці. Цей вектор направлений вгору, в напрямку підйому; зворотний: йому вектор вказує напрямок спуску. Одиничний вектор градієнта часто представляють у вигляді.

де

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

Тут D - невелике зміщення в напрямку хj. Цю формулу часто називають «наближенням січної». Отриману інформацію про направлення градієнта можна використовувати по-різному для побудови алгоритму пошуку.

Ступінчастий найшвидшого підйом

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

Найшвидшого підйом з використанням одновимірного пошуку

У деяких методах пошуку інформація про градієнті використовується для ведення одновимірного пошуку в напрямку найшвидшого підйому або спуску, причому використовується співвідношення

хi. нов =хi. ст + Svi

де S - новий одновимірний параметр, значення якого відраховуються в напрямку градієнта. Отримавши одновимірний оптимум в напрямку даного градієнта, знаходять новий градієнт і повторюють процес до тих пір, поки наступні обчислення дозволяють поліпшувати отриманий результат. Головне достоїнство цього методу полягає в тому, що параметр S можна використовувати в якості незалежної змінної для пошуку за методом Фібоначчі, і це забезпечує високу ефективність методу. Інша важлива перевага розглянутих методів полягає в тому, що вони дозволяють відходити від сідлових точок поверхні, описуваної цільовою функцією (рис. 7.5). Відзначимо, однак, що, як видно з малюнка, для мультимодальних функцій градієнтні методи дозволяють знайти лише локальний оптимум. Тому, якщо характер поверхні недостатньо добре відомий, слід випробувати декілька вихідних точок і переконатися, що в усіх випадках виходить одне і те ж оптимальне рішення. Іншою причиною, яка знижує ефективність градієнтних методів, є злами ліній рівня цільової функції. Так як такі точки відповідають розриву в нахилі ліній контуру, то тут можливі помилки у визначенні напрямку подальшого пошуку. Тому пошук може сповільнитися і йти зигзагами поперек лінії зламу, а час, необхідний для отримання рішення, буде настільки велике, що рахунок доведеться припинити. Насправді більшість досліджуваних поверхонь має одну або більше ліній зламу, які нерідко проходять через точку оптимуму. Тому, наткнувшись на лінію зламу, слід надалі

Мал. 6.5 бімодальною цільова функція

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

6.5. метод Флетчера-Ривса

Цей метод дозволяє знайти мінімум нелінійної цільової функції багатьох змінних виду

M = F (x1 , x2,. . ., XN)

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

Мал. 6.6 Блок-схема алгоритму методу Флетчера - Ривса

ходящая початкова точка простору проектування і шляхом обчислення компонент вектора градієнта

визначається напрямок найшвидшого спуску. індекс k =1 відповідає вихідної точки. Потім в напрямку найшвидшого спуску ведеться одномірний пошук по формулі

хi. нов = хi. ст + Svi , I = 1,2, ..., N,

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

де

індекс k вказує на послідовність обчислень в процесі ітерацій. Нові напрямки називаються «сполученими» і відповідають поточній локальній квадратичної апроксимації функції. Потім за новим напрямком проводять одномірний пошук і, знайшовши мінімум, перевіряють, чи досягнута необхідна ступінь збіжності. Якщо перевірка показує, що це так, то рахунок припиняється. В іншому випадку визначають нові пов'язані напряму, k збільшують на одиницю і продовжують процес до тих пір, поки не буде забезпечена збіжність або поки пошук не буде проведений за всіма N + 1 напрямками. Закінчивши цикл пошуку по N + 1 напрямками, починають новий цикл, в якому знову використовується напрямок найшвидшого спуску. Гідність цього алгоритму полягає в тому, що він дозволяє використовувати переваги градієнтних методів, які проявляються при дослідженні цільової функції з розривними похідними. Так як N + 1 напрямків пошуку другої сукупності відрізняються від напрямків одиничних векторів градієнту, то пошук не "зависає на зламі», а йде уздовж лінії, що з'єднує точки зламів лінії рівня, яка, як правило, проходить через точку оптимуму. Взагалі можна стверджувати, що методи, засновані на визначенні нових напрямків пошуку на основі накопичених даних про локальному поведінці функції, за самою своєю природою більш ефективні, ніж методи, в яких напрямок пошуку задається заздалегідь. Саме тому метод Флетчера - Ривса володіє великими перевагами в порівнянні з методами найшвидшого спуску або підйому. Його недолік полягає в тому, що, будучи складніше зазначених методів, він вимагає розробки більш складних програм.

6.6. Метод Девідона-Флетчера-Ривса

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

M = F (x1 , x2 , ..., xN).

Необхідні приватні похідні цільової функції по незалежним змінним. Оскільки в основі методу лежить припущення про унімодального цільової функції, в тих випадках, коли є підстави припускати, що вона не є такою, слід брати кілька вихідних точок. На рис. 6.7 представлена ??схема алгоритму методу Девідона - Флетчера - Пауелла. Алгоритм виконується наступним чином. Спочатку в просторі проектування вибирають відповідну початкову точку. Потім, обчислюючи складові вектора градієнта

визначають напрямок пошуку. тут k -номер ітерації, а Нi,j - Елементи симетричною позитивно певної матриці розмірності NxN. В процесі ітерацій ця матриця перетворюється в матрицю, зворотну матриці Гессе, елементами


Мал. 6.7 Блок-схема алгоритму методу Девідона - Флетчера - Пауелла

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

хi. нов = хi. ст + Svi , I = 1,2, ..., N,

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

Елементи матриць А(k) і B(k), Що мають розмірність NxN, обчислюються за формулами

де верхнім індексом t позначені транспонований матриці, a Dx(k) и DG(k) - Відповідно вектори-стовпці різниць значень хi і градієнтів в двох точках. Вектори-стовпці визначаються виразами

Відповідно до правил матричного обчислення числители виразів для. А(k) і В(k) являють собою матриці розмірності NxN, а знаменники є скалярами. Визначивши новий напрямок пошуку, проводять одномірний пошук і продовжують ітераційний процес. При виконанні описуваного алгоритму пошук після першої спроби ведеться в тих напрямках, в яких цільова функція в найближчій околиці має значення, що наближаються до оптимального. Лише в окремих випадках ці напрямки збігаються з напрямом градієнта. Тому даний алгоритм часто називають методом «відхиленого» градієнта. Зазначене властивість методу Девідона - Флетчера - Пауелла дозволяє обходити труднощі, пов'язані з розривами похідних в просторі проектування. Широко поширена думка, що цей метод є найбільш ефективним з усіх градієнтних методів. На відміну від методу Флетчера - Ривса він дає повну інформацію про кривизну поверхні цільової функції в точці мінімуму, однак при цьому потрібно більший обсяг пам'яті і більший час рахунку для обробки матриці Н.

6.7. Метод конфігурацій Хука-Дживса

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

M = F (х1 , x2 . . ., xN)

Мал. 6.8 Блок-схема алгоритму методу конфігурацій Хука - Дживса

при відсутності обмежень. На рис. 6.8 представлена ??схема алгоритму цього методу. Виконується він наступним чином. Спочатку вибирається вихідна базова точка простору проектування і величини кроків, які будуть використані при дослідженні функції. Потім відповідно до схеми рис. 6.9 проводиться дослідження з заданими приростами в напрямках, які відповідають усім незалежним змінним. Там, де отримано уточнене значення функції, поміщають нову тимчасову базову точку. Закінчивши етап дослідження, вибирають нову базову точку і виробляють «зрушення схеми». Ця операція полягає в екстраполяції уздовж лінії, що з'єднує нову і колишню базові точки. Відстань зсуву за нову базову точку кілька перевищує відстань між двома колишніми базовими точками. Математично екстраполяція визначається формулою

де  - Нова тимчасова базова точка, або «точка зростання», i - змінний індекс, k - Порядковий номер стадії пошуку, а а - коефіцієнт посилення, який більше або дорівнює одиниці. Потім досліджують околиця нової тимчасової базової точки, щоб з'ясувати, чи не містить вона точку, прийнявши яку за наступну базову можна наблизитися до оптимального рішення. Цей пошук також ведеться за схемою, показаної на рис. 7.9. Якщо знайдена тимчасова точка росту або одна з сусідніх з нею точок має перевагу перед іншими, то вся процедура повторюється з використанням її в якості базової. Завдяки введенню коефіцієнта посилення, кожне наступне дослідження околиці точки здійснюється на все більшому і більшому видаленні від вихідної точки до тих пір, поки в процесі пошуку не опиниться пройденим пік або лінія розриву похідної. В цьому випадку повертаються до попередньої «кращої базової точці», звужують область дослідження і повторюють весь процес знову. Якщо послідовно зменшуваний крок виявляється менше деякої заздалегідь заданої величини і при цьому відсутня помітна зміна значення цільової функції, пошук припиняється. Після декількох змін напрямку пошуку метод Хука - Дживса забезпечує збіг розподілу розрахункових точок з лінією розриву похідних. Зазвичай після завершення вибору схеми пошуку зрушення на кожному наступному кроці збільшується, поки не перевищить величину початкового етапу в 10 або навіть в 100 разів. Тому в разі, коли зсув виявляється невдалим, єдиний спосіб продовжити пошук - повернутися до найбільш вдалою з базових точок і почати все спочатку. Той факт, що даний алгоритм має властивість


Мал. 6.9 Метод дослідження, який застосовується в алгоритмі Хука - Дживса

«Прискорюватися», сприяє підвищенню його загальної ефективності. Інше достоїнство методу Хука - Дживса - можливість отримання з його допомогою наближеного рішення, якість якого безперервно підвищується на всіх стадіях чисельного рішення. Особливо яскраво переваги подібних методів проявляються при знаходженні екстремумів на гіперповерхні, що містять глибокі вузькі западини, т. Е. В тих випадках, коли градієнтні методи неефективні.

6.8. Метод конфігурацій Розенброка

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

M = F (x1 , x2 , ..., XN)

при відсутності обмежень. На рис. 7.10 показана схема алгоритму, який використовується в цьому методі. Виконується він наступним чином. Спочатку вибирають початкову точку, задають початкові величини кроків Si (I = 1, 2,..., N) і обчислюють цільову функцію. Потім кожноїзмінної xi повідомляють приріст Si в напрямку, паралельному відповідної осі координат в просторі проектування, і знову обчислюють цільову функцію F. Якщо її нове значення виявляється менше попереднього, то зрушення вважається вдалим і наступний крок збільшується відповідно до формули

Si= aSi.

де ALFA> 1. Якщо ж нове значення F виявляється більше попереднього, то зрушення вважається невдалим і наступний крок визначається за формулою

Si= - bSi


Мал. 6.10 Блок-схема алгоритму методу конфігурацій Розенброка

де b <1. Здійснивши зрушення по всім змінним, перевіряють відповідність і, якщо вона досягнута, пошук припиняють. В іншому випадку вводять додаткову перевірку, щоб з'ясувати, чи були зроблені хоча б один успішний і один безуспішний зсув в кожному напрямку. Якщо такого поєднання зрушень не було, вся процедура повторюється, починаючи з першої змінної. Якщо ж подібне поєднання виявлено для кожного напрямку, осі повертають так, щоб вихідний напрямок пошуку співпало з найбільш перспективним з раніше розглянутих напрямків. Потім вибирають нові значення кроків і продовжують пошук по всім змінним, користуючись новою системою координат. На відміну від інших, цей алгоритм націлений на відшукання оптимальної точки в кожному напрямку, а не просто на фіксований зсув в усіх напрямках. Величина кроку в процесі пошуку безперервно змінюється в залежності від конфігурації рельєфу поверхні. Поєднання обертання вектора, спрямованого уздовж лінії розриву похідних, з регулюванням масштабу робить метод Розенброка виключно ефективним при вирішенні складних завдань оптимізації.



Метод багатовимірного пошуку | Метод квадратичної апроксимації

незбалансована ТЗ | ТЗ з проміжними пунктами | Знаходження найкоротшого шляху на шляху зв'язку за допомогою ТЗ (маршрутизації) | Використання лінійного програмування на виробництві. Графік змін | Складання графіка відпусток | Оптимальна розстановка сили на підприємствах | Нелінійне програмування. Постановка задачі | метод дихотомії | Метод золотого перерізу | метод Фібоначчі |

© um.co.ua - учбові матеріали та реферати