Головна

Метод багатовимірного пошуку

  1. Стандартний алгоритм симплекс-методу
  2. DFD - методологія в проектуванні ІС
  3. I.3.3. Методи виносу в натуру проектних точок.
  4. I.3.4. Методи підготовки даних для перенесення проекту на місцевість.
  5. III. Опис експериментальної установки та методу вимірювання
  6. III. Опис експериментальної установки та методу вимірювання
  7. III. Опис експериментальної установки та методу вимірювання

На перший погляд може здатися, що відмінність між методами багатовимірного і одновимірного пошуку полягає лише в тому, що перші вимагають більшого обсягу обчислень і що в принципі методи, придатні для функцій однієї змінної, можна застосовувати і для функцій багатьох змінних. Однак це не так, оскільки багатовимірний простір якісно відрізняється від одновимірного. Перш за все із збільшенням числа вимірювань зменшується ймовірність унімодального цільової функції. Крім того, безліч елементів, що утворюють багатовимірний простір, набагато могутніше безлічі елементів одновимірного простору. Обсяг обчислень, необхідних для звуження інтервалу невизначеності в багатовимірному просторі, є ступеневою функцією, показник якої дорівнює розмірності простору. Так, якщо в разі одновимірного простору для досягнення / = 0,1 потрібно обчислити 19 значень цільової функції, то в разі двовимірного простору це число становить 361, тривимірного-6859, чотиривимірного - 130 321, що а пятимерного - 2476 099! Оскільки при виборі оптимальної конструкції нерідко доводиться мати справу з п'ятьма і більше змінними, серйозність труднощів, обумовлених багатомірністю, стає очевидною.

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

6.1. Метод покоордінатного підйому

Логічним розвитком розглянутої вище методики одновимірного пошуку було б послідовна зміна кожного проектного параметра до тих пір, поки не буде досягнутий максимум цільової функції. По завершенні цієї процедури для всіх змінних можна повернутися до першої та подивитися, чи не можна ще більше вдосконалити рішення. Цей метод, званий методом покоордінатного підйому, не завжди дозволяє знайти оптимальне рішення. На рис. 7.1, а показана двовимірна цільова функція, відповідна для вирішення завдання цим методом. Її особливість полягає в тому, що лінії рівня близькі за формою до кіл або еліпсам, осі яких паралельні осям координат. Якщо ж ці осі нахилені до осей координат (рис. 7.1, б), то ефективність алгоритму знижується, так як для знаходження оптимуму доводиться обчислювати набагато більше значень цільової функції. Метод покоордінатного підйому абсолютно непридатний, якщо лінії рівня мають точки зламу (рис. 7.1, в). Оскільки лінії рівня такого типу досить часто зустрічаються в інженерній практиці, то перш, ніж скористатися зазначеним методом, слід переконатися, що можна вирішити завдання не має такої вади. Незважаючи на це, метод покоордінатного підйому часто використовують на першій стадії вирішення завдання, застосовуючи потім більш складні методи. До переваг методу покоордінатного підйому слід віднести можливість використання простих алгоритмів одномірного пошуку, таких, як метод золотого перетину.

Мал. 6.1 Метод покоордінатного підйому

6.2. Метод виключення областей

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

Мал. 6. 2 Метод виключення областей (дотичній до лінії рівня) в разі опуклих ліній рівня

дотичній до лінії рівня, так як в ньому використовуються дотичні до ліній рівня цільової функції. Продемонструємо цей метод на прикладі двовимірної цільової функції, лінії рівня, якої показані на рис. 6.2. Нехай довільно обрана точка простору проектування лежить на лінії рівня ,! що проходить трохи нижче піку, відповідного оптимального рішення. Проведемо через цю точку дотичну до лінії рівня. Зробити це неважко, так як дотична повинна лежати в площині лінії рівня і бути перпендикулярної локальному градієнту поверхні цільової функції. Якщо цільова функція досить гладка і унімодального, то дотична до лінії рівня розділить простір проектування на дві частини, в одній з яких ймовірність знаходження оптимуму: велика, а в інший мала. Користуючись цим прийомом в декількох вдало обраних точках, для яких відомі значення цільової функції, можна істотно звузити область пошуку. Однак здійснення цього алгоритму пов'язано з деякими труднощами. Якщо ліній рівня, увігнуті, а не опуклі, то може виявитися виключеною область, яка містить екстремум (рис, 6.3). Крім того, що залишилася після кількох винятків область невизначеності може мати конфігурацію, мало придатну для застосування інших алгоритмів.

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

Мал. 6.3 Метод виключення областей (дотичній до лінії рівня) в разі увігнутих ліній рівня

краще зрозуміти сутність цього методу, розглянемо його для випадку простору проектування, визначається двома змінними. Вихідну область невизначеності в залежності від розмірності простору відобразимо на одиничний квадрат, куб або гіперкуб. Це дозволить вести пошук в нормованої області зі стороною, що дорівнює одиниці. У гиперкубе побудуємо сітку, утворену попарно симетричними взаємно ортогональними площинами, паралельними координатним напрямками, уздовж яких змінюються проектні параметри. Ці площини перетинаються по прямих, які в свою чергу перетинаються в точках, які називаються в подальшому вузлами (рис. 6.4). Обчислимо значення цільової функції в вузлах і в центрі куба. В разі М проектних параметрів отримаємо 2М + 1 значень цільової функції, з яких виберемо найбільше. Приймемо відповідний вузол за центр гиперкуба менших розмірів і продовжимо дослідження. Процес триває до тих пір, поки не буде досягнута необхідна ступінь звуження інтервалу невизначеності. Якщо в області допустимих значень позначити ступінь звуження уздовж будь-якої осі координат через r, то лінійне звуження для 6-мірного гіперкуба дорівнюватиме f = rb, а число обчислених значень цільової функції

N = b (2M) + 1.

Мишкові рекомендує вибирати r в інтервалі значень

Мал. 6.4 Сітковий метод пошуку

2/3

6.3. Метод випадкового пошуку

Вище в цій главі говорилося про громіздкість обчислень в разі багатовимірного простору на прикладі числа значень цільової функції, які необхідно обчислити, щоб, користуючись методом сіток, отримати / = 0,1, і було показано, що це число зростає як статечна функція, показник ступеня якої дорівнює розмірності простору. Оригінальний підхід, що дозволяє обійти ці труднощі, запропонований Бруксом [1] і заснований на випадковому пошуку. Нехай простір проектування являє собою куб або гиперкуб зі стороною, що дорівнює одиниці, і розділене на кубічні комірки шляхом ділення на 10 рівних частин кожної сторони куба, що відповідає одному з проектних параметрів. При N = 2 число осередків дорівнює 100, при N = 3 воно дорівнює 1000; в загальному випадку при N вимірювань число осередків дорівнює 10N. Імовірність того, що обрана навмання осередок увійде в число 10% найбільш перспективних осередків, дорівнює 0,1, так як при N = 1 нас буде цікавити одна осередок з 10, при N = 2- Одна з десяти кращих при загальній кількості осередків 100 і т. Д. Імовірність того, що ми пропустимо одну з 10% найбільш перспективних осередків, складе 0,9. Якщо випадковим чином вибрати два осередки, то ймовірність пропуску буде 0,92, Т. Е. 0,81. Взагалі вірогідність знаходження принаймні одного осередку з найбільш перспективних, частка яких дорівнює f, після N спроб складе

P = l- (l-f)N.

У табл. 6.1 вказано, скільки клітинок треба вибрати випадковим чином, щоб забезпечити задану ймовірність при заданій частці найбільш перспективних осередків. З неї видно, що при випадковій вибірці 44 осередків ймовірність досягнення / == 0,1 складе 99%. Це дуже непогано, якщо згадати, що для 100% -ного забезпечення цільову функцію в разі п'яти змінних довелося б обчислити 2 476 099 разів.

          Таблиця 6.1
   імовірність  
f  0,80  0,90    0,95    0,99
             
 0,1    
 0,05    
 0,01    
 0,005    
             
                 

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

метод Фібоначчі | градієнтні методи


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

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