Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Модифікація алгоритму послідовного
СИМПЛЕКСНОГО ПОШУКУ У справжньому параграфі розглянута вище постановка загальної задачі оптимізації (2.1) обмежується вимогам відшукання локального екстремуму функції в області . Порівняльний аналіз ефективності роботи різних процедур симплексного пошуку /42,91,92/ показав, що найбільш ефективною процедурою є алгоритм Нелдера-Міда в комбінації з методом ковзного допуску /43/, який надалі буде використовуватися в якості базового. Даний алгоритм полягає в організації в області пошуку - верхового правильного багатогранника (симплекса) з довгої ребра і його руху в антиградієнтом напрямку, не виходячи за межі , за допомогою операцій відбиття, наближення, розтягання, стиску й редукції. Усі операції, за винятком редукції, проводяться в напрямку напівпрямої, що проходить від “гіршої” вершини симплекса через центр (“ваги”) протилежної до неї грані. Отримана в результаті операцій точка заміняє “гіршу” вершину симплекса. Гнучка організація руху симплекса дозволяє йому успішно долати “яри”, “хребти” і сідлові точки на поверхні функції мети. Однак, швидкість просування симплекса в антиградієнтом напрямку може бути суттєво збільшена за рахунок проведення операцій відбиття й розтягання не через центр протилежної до “гіршої” вершини грані, а ближче до напрямку дійсного антиградієнта. Цього можна досягти, завдяки оцінці градієнта гіперплощини, що проходить через вершини симплекса /40,46/ або застосовуючи рекомендації Умеда-Ічикави по обчисленню зваженого “центру ваги” /40,42,54/. Іншою модифікацією базового алгоритму, спрямованої на істотне підвищення швидкості пошуку екстремуму, є застосування квадратичної екстраполяції функції мети в напрямку вдалого розтягання й оцінки по екстраполюючій параболі мінімуму /42/. Нижче пропонується модифікований алгоритм симплексного пошуку, що володіє підвищеною швидкістю пошуку екстремуму функції декількох змінних при наявності обмежень. Причому, квадратична екстраполяція функції мети в даній модифікації проводиться з урахуванням можливості порушення обмежень задачі на операціях відбиття й розтягання /93,94/. У припустимій області згідно з рекомендаціями /43/ будується вихідний симплекс із -ою вершиною й довжиною ребра . Нехай в “найгіршій” вершині симплекса функція мети ,а в найкращій вершині . Розрахунки завершеного “центру ваги” протилежної до грані симплекса проводиться згідно /54/
(2.2) де - ваги вершин симплекса, - число незалежних змінних задачі (2.1). Зважений “центр ваги” дозволяє симплексу рухатися в напрямку, більш близькому до напрямку антиградієнта. Операція відбиття “найгіршої” точки через “центр ваги” симплекса проводиться згідно з вираженням (2.3) де - координати точки відбиття, а - коефіцієнт відбиття . Отримана точка відповідно до методу ковзного допуску /43/ перевіряється на допустимість і якщо потрібно, то переводиться в припустиму область (2.1). У методі ковзного допуску в досліджуваній точці перевіряється нерівність (2.4) де - значення критерію ковзного допуску, обумовлене як - довга ребра вихідного симплекса, - номер ітерації, - функціонал над множиною обмежень вид, що має:
-функція Хевисайда: Якщо нерівність не виконується, то досліджувана точка X переводиться в припустиму область D шляхом мінімізації функціонала T(X) у простір . Мінімізація T(X) може проводиться тим же алгоритмом послідовного симплексного пошуку. Після введення в припустиму область визначається значення функції в ній і рівняється зі значеннями функції у вершинах симплекса. Якщо , то виконується операція розтягання де -коефіцієнт розтягання . У точці перевіряється нерівність (2.4) і у випадку його виконання точка розтягання вводиться в припустиму область - . Якщо , то з метою підвищення швидкості пошуку проводиться квадратична екстраполяція по напрямкові напівпрямої, що проходить через точки й . А якщо ні, то, “гірша” вершина заміняється на відбиту . Пропонована модифікація алгоритму, у відмінності від наведеної в /42/, пропонує проведення екстраполяції функції мети не по напрямкові напівпрямої, що проходить через і , а по напрямкові напівпрямої, що проходить через і , уже введених у припустиму область D. Оскільки операція розтягання суттєво видаляє точку від “центру ваги” симплекса , то при цьому досить часті випадки порушення в ній обмежень задачі (2.1). І тому що після проведених крапок відбиття й розтягання в припустиму область D ці точки їжаку не лежать на одній прямій з “гіршою” крапкою симплекса , то провести екстраполяцію, як пропонується в /42/, не представляється можливим. Нижче пропонується процедура екстраполяції функції мети, що враховує можливість порушення обмежень задачі в процесі пошуку
Квадратична екстраполяція функції мети по напрямкові здійснюється по трьом точкам: - уведеної в область D точки розтягання , - уведеної в області D точки відбиття й - проекції “гіршої” точки на пряму H, що проходить через точки й . Перед екстраполяцією необхідно визначити проекцію на й значення функції в ній , де (2.6) , Відносна точка мінімуму екстраполюючої параболи , що перебуває на прямій H із крапкою відліку в , визначається вираженням (2.7) де . Точка мінімуму екстраполюючої параболи в просторі (2.8) Перевіряється на приналежність припустимої області D і якщо необхідно, те вводиться в припустиму область. У припустимій точці визначається значення функції мети , яке потім рівняється с. Якщо , то заміняється на . А якщо ні, то заміняється на . В іншому алгоритм відповідає наведеному в /43/. Якщо , де , , то відбиття також зізнається вдалим і припустима відбита точка заміняє “гіршу” вершину симплекса . Якщо , то проводиться наближення відбитої точки , (2.9) Де - коефіцієнт стиску ; якщо , те виконується операція стиску (2.10) Отримана точка вводиться в припустиму область і в ній визначається значення функції мети . Якщо то виконується операція редукції симплекса до кращої точки (2.11) Розглянутий алгоритм послідовного симплексного пошуку є досить універсальною процедурою оптимізації. Він може використовуватися при експериментальній оптимізації виробничих процесів без попередньої побудови їх моделей і ефективний при розв'язку задач оптимізації з обмеженнями типу рівностей. Однак у більш приватних задач оптимізації, що не мають обмежень – рівностей, комплексний пошук Боксу /53/ має більшу швидкість збіжності /42/. Наступний параграф присвячений розгляду алгоритму комплексного пошуку й розробці його модифікації, що підвищує його надійність.
|
||||||
Последнее изменение этой страницы: 2017-02-09; просмотров: 130; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.143.205.169 (0.022 с.) |