Модифікований алгоритм симплексного пошуку

Розглянемо математичну постановку такої задачі: нехай потрібно відшукати локальний екстремум (мінімум) функції

(2.12)

При обмеженнях

визначальних припустиму область пошуку .

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

(2.13)

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

Відповідно до базового алгоритму /42/ на кожній ітерації комплексного пошуку заміняється “гірша” вершина комплексу. Вона відбивається через “центр ваги” інших вершин. Нехай вершини проранжировані в такий спосіб

(2.14)

Точка відбиття , що заміняє “гіршу” вершину , визначається по формулі:

(2.15)

де - позитивний коефіцієнт відбиття - “центр ваги” комплексу

(2.16)

Якщо то нова вершина виявляється як і раніше “гіршою” вершиною комплексу. У цьому випадку ділиться навпіл і визначається нова вершина порушаться деякі з обмежень задачі (2.12). ступінь порушення обмежень, як і в симплексному пошуку, оцінюється функціоналом

(2.17)

де - коефіцієнт Хевісайда:

Уведення вершини в припустиму область згідно з рекомендаціями /42/ здійснюється в три етапи. На першому етапі введення в область здійснює лінійна інтерполяція порушених обмежень і визначається гранична припустима точка :

(2.18)

де

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

(2.19)

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

(2.20)

Отримана на кожному з етапів припустима точка заміняє “гіршу” вершину комплексу . Пошук припиняється при виконанні умови

де - припустима відносна точність по функції.

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

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

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

2.3. ДЕТЕРМІНОВАНИЙ АЛГОРИТМ БАГАТОЕКСТРЕМАЛЬНОЇ ОПТИМІЗАЦІЇ ФУНКЦІЇ, ЗАДАНОЇ НА ВІДРІЗКУ

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

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

(2.21)

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

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

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

Як видне, даний алгоритм вигідно відрізняється від /49/, тим, що перетину здійснюється не навмання, а цілеспрямовано. Тому таких перетинів буде мінімальне кінцеве число й, отже, алгоритм мінімізує основні труднощі й обчислювальні витрати, пов'язані з пошуком корінь. Сам же локальний спуск при вдалому виборі одного з методів опуклого програмування не представляє скільки-небудь серйозних утруднень. Нижче на рис 2.5 представлена блок-схема алгоритму.

У якості алгоритму опуклого програмування (блок4) доцільно вибрати алгоритм із високою швидкістю збіжності й не потребуючої обчислення похідних у явному виді. Таким алгоритмом може бути одномірний алгоритм Пауелла /42,43/, що володіє квадратичною збіжністю. Найбільш відповідальною й трудомісткою ланкою алгоритму є процедура знаходження кореня рівняння (блок 5)

(2.22)

У випадку, якщо дане рівняння розв'язне аналітично відносно для певного класу функції , те виваливши з неї , отримане вираження підставляємо в блок 5 і одержуємо спеціалізований алгоритм глобального пошуку для даного класу функції (СДАГП). У блок 5 заноситься оператор

(2.23)

На жаль, у більшості випадків одержати вираження (2.23) у явному виді не вдається. Тому доводиться прибігати до чисельних методів розв'язку рівнянь /97,98/. У даному алгоритмі був застосований метод відшукання корінь довільних рівнянь Мюдлера /97,99/. З відомих методів відшукання корінь довільних рівнянь він виявляється найбільш універсальним і, як відзначається в /97/, досить надійним на практиці, хоча теоретично його збіжність у загальному випадку не доведена.

Якщо мініімізуєма функція на кінцях інтервалу [a,b] свідомо вище, чим у точці абсолютного мінімуму, що належить відрізку [a,b], то від розв'язку (2.22) доцільно перейти до розв'язку нерівності

(2.24)

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

Порівняльні характеристики даного алгоритму, як, втім, і інших багатоекстремальних алгоритмів, пропонованих у дисертації, будуть дані в наступній главі. Слід зазначити, що отриманий алгоритм ДАГП в “чисто” детермінованому виді не вдалося повідомити на багатомірний випадок. Розв'язок багатомірного рівняння (2.22) є задачею некоректної й може бути виконане аналітично лише при дуже жорстких умовах /97,100/. Розв'язок багатомірного рівняння (2.22) чисельними методами не представляється можливим, тому що вони все без винятку вимагають близької початкової точки, що в нашому випадку є метою пошуку на даному етапі (блок5). У загальному випадку розв'язок цієї задач і вдається одержати лише при використанні методу статистичних випробувань/ICI/. У якості багатомірного алгоритму опуклого програмування в блоці 4 використаний нелінійний алгоритм послідовного симплексного пошуку /43.93/, описаний 2.1 і вхідний у розроблювальний комплекс оптимізованих процедур. У комбінації ДАГП ці два методи дозволили створити досить ефективний і універсальний алгоритм глобального пошуку багатомірної функції при наявності обмежень /93,94/. Його порівняльні характеристики також будуть представлені в наступній главі.

 

ВИСНОВОК

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

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

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

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

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

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

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

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

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

 

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

1. Дудніков Е.Е., Цедіков Ю.М. Типові задачі оперативного керування непреривним виробництвом. – М.: Энергія, 1999.-272 с.

2. Салига В.И., Кораблев Н.М., Руденко О.Г. Автоматизованні системи керування технологічними процесами: Ідентифікація і оптимальне керування.- Харьков: Вища школа, 1989.

3. Кулик В.Т. Алгоритмізація об’єктів керування: Справочник.- Київ: Наукова думка, 1988.-362с.

4. Колін К.К., Ліпаев В.В. Проектування алгоритмів керування ЦВМ.-М.: Сов. радіо. 1990.-343с.

5. Маерс Г. Надійність програмного забезпечення. -М.: Мир,1980.-360с.

6. Растрігін Л.А., Мадшаров Н.Е. Введення в ідентифікацію об’єктов керування.-М.: Енергія, 1997.-215с.

7. Стронгін Р.Г. Монотонні алгоритми багатоекстремальної оптимізації. -В сб.: Численні методі нелінійного програмування,Харьков,1976.

8. Стронгін Р.Г. Численні методи в багатоекстремальних задачах.-М.:Наука,1998.-273с.

9. Захаров В.В. Метод інтегрального сглажування в багатоекстремальних и стохастичних задачах.- М.: Технічна кібернетика, 1980,№4.

10. Муравєв С.В., Карасташов В.А. Оптимізація модифіцированним комплексним методом Бокса.- Київ, 1982.

11. Мудров В.И. Кушко В.А. Методи обработки Измерений.-М.: Сов. Радио, 1986.-736с.

12. Авраменко В.П., Никитюк А.В. Іследованіе симплексних алгоритмів нелінійного програмування.- Харьков: Автоматизіровані системи керування і прибори автоматики, Вища школа.

13. Рубан А.И. Непараметричні процедури сглажування результатів експеримента. – М.: Системи керування,1997,№2,с.33-45.

14. Васильев Ф.П. Численні методи розв’язку екстремальних задач.- М: Наука, Главна редакція физико-математичної літератури, 1980.-520с.

15. Вершин В.Е. Автоматизовані системи керування технологічними процесами.- Л.: Машинобудування. 1993.-159с.

16. Цыпкин Я.З., Поляк Б.Т. Огрубленный метод максимального правдоподобия.- М.: Автомиатика, 1997, №12,с. 22-46

17. Попков Ю.С. и др. Ідентифікація і оптимізація нелінійних стохастичних систем.- М.: Енергія. 1995.- 440с.

18. Горский В.Г., Адлер Ю.П. Планування промислових експериментів.- М.: Металургія, 1994.- 264с.

19. Моцкус И.В. Достатні условія сходимості байесовских методів к абсолютному мінімуму непреривних функцій.- М.: Теорія оптимальних розв’язків, 1988, №4,-с.67-88.

20. Моцкус И.В. Іследованіе простого байесовского алгоритма для розв’язку багатоекстремальних задач.- Вільнюс, 1999.

21. Жилінский А.Г. Метод одномірной багатоекстремальної мінімізації.- М: Технічна кібернетика, 1986,№4,- с.71-74.

22. Эйкхофф П. Основі ідентифікації систем керування.- М.: Мир,1995.- 683с