автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Исследование и алгоритмичная реализация нелинейной схемы компромиссов

ля Національна академія наук України

РГБ им

Інститут кібернетики імені В. М. Глушкова

Л

6 № 1^05

На правах рукопису

КОЗЛОВ Олександр Іванович

ДОСЛІДЖЕННЯ ТА АЛГОРИТМІЧНА РЕАЛІЗАЦІЯ НЕЛІНІЙНОЇ СХЕМИ КОМПРОМІСІВ

05.13.01 — системний аналіз та теорія оптимальних рішень

Автореферат дисертації на здобуття наукового ступеня кандидата технічних наук

Київ 1995

Дисертацією с рукопис.

Робота виконана в Інституті кібернетики імені В.М. Глуш кова НАН України.

Науковий керівник: доктор технічних наук

ВОРОНІН А. М.

Офіційні опоненти: член-кореспондент НАН України,

доктор технічних наук САМОЙЛЬНКО Ю. І.,

кандидат технічних наук РАДІЄВСЬКИЙ А. Є.

Провідна організація: Науково-виробнича корпорація

«Київський інститут автоматики» Міністерства машинобудування військово-промислового комплексу і конверсії України.

Захист відбудеться ------ 199<5~ р.

о ------ годині на засіданні спеціалізованої вченої ради

Д01.39.03 при Інституті кібернетики імені В. М. Глушкова НАН України за адресою:

252022 Київ 22, проспект Академіка Глушкова, 40.

З дисертацією молена ознайомитися у науково технічному архіві інституту.

Автореферат розісланий « — -» 199-^ р.

Учений секретар спеціалізованої вченої ради

А ЯКОВЛЄВ О. С.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

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

прийнятті рішення.

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

Мста.____дослідження: розроблення алгоритмічного та

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

Основі завдання .дослідження. 1. Розглянути властивості нелінійної схеми компромісів, що відображають загальні закономірності прийняття рішення ОПР. Дослідити можливість використання нелінійної схеми компромісів у системах керування без ОПР.

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

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

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

Методи___дослідження. Для дослідження нелінійної схеми

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

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

ОПР, так і конкретній ОПР, що здійснює навчання системи. Це дозволяє, при необхідності, виключити ОПР з системи керування.

Доведена унімодальність скалярної згортки за нелінійною схемою компромісів при деяких припущеннях про часткові критерії.

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

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

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

Розроблено алгоритми використання нелінійної схеми компромісів у програмному забезпеченні для розв'язування задач багатокритеріальної оптимізації. В тому числі розроблено алгоритм настроювання системи керування на переваги конкретної ОПР.

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

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

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

Основні положення, що виносяться на захист.

1. Доведено, що коли криторі.ільиі функції с строго опуклими

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

' 2. Для знаходження мінімуму узагальненого критерію,

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

3. Показано, що використання апроксимації узагальненого

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

4. Розроблено ефективний алгоритм ііггерактивного настроювання нелінійної схеми компромісів на переваги конкретної ОПР, який легко реалізується сучасними засобами розроблення програмного забезпечення.

Особистий шієшк дисертанта

1. Доведені теореми про унііМодальність скалярної згортки за нелінійною схемою компромісі».

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

3. Алгоритмізовано метод більш точних моделей. Для вибору початкових точок методу розроблено п-вимірне узагальнення "правила свастики". Розроблено алгоритм покоординатного спуску з використанням методу більш точних моделей.

4. Доведено надквадратичну швидкість локальної збіжності методу біліли точних моделей.

5. Модифіковано алгоритм інтерактивного настроювання нелінійної схеми компромісів на переваги конкретної ОПР.

6. Створено програмне забезпечення, що дозволяє розв'язувати широкий спектр задач багатокритеріальної опгимізації.

Апробація _робо-гц. За матеріалами дисертації були зроблені повідомлення та доповіді на Всесоюзному семінарі ''Кибернетика

электроэнергетическнх систем" (м. Челябінськ, 1990 р.), Всесоюзній конференції "Интеграция АСУ ТП и тренажерных устронстп" (м. Українка, 1931 р.), на школі-семінарі ''Системотехническое

моделирование и оптимизация. Проблемы многокрнтериальности" (м. Київ, 1992 р.), на семінарах "Проблемы создания

интеллектуальных систем поддержки принятия решений" (м. Київ, 1993 р.) та "Нейробионика" (м. Київ, 1994 р.) наукової ради АН України з проблеми "Кібернетика", на міжнародній школі-семінарі "Многокритериальные задачи в условиях неопределенности" (м.

Орєхово-Зуєво, 1994 р.).

Структура та обсяг дисертації. Дисертація складається з вступу, п'яти глав, висновків та списку літератури з 116 найменувань. Робота має загальний обсяг 134 сторінки

машинописного тексту, включає 3 таблиці та 8 рисунків.

ЗМІСТ РОБОТИ

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

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

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

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

володіє нелінійна схема компромісів.

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

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

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

Другу-Главу присвячено дослідженню всластивостей нелінійної схеми компромісів. На основі леми Карліна та визначення парето-оптимального розв'язку показується, що нелінійна схема компромісів у вигляді

!П ,

Ф(х) = £ а* (1 -уок(х)) , хєГх, (1)

к=1

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

Показано, що коли у,(х), і = 1, т, - неперервні та строго опуклі на паралелепіпеді П» =■ {х є Е" І а, 5 х,'2 Ь„ і = І.п} функції, то скалярна згортка за нелінійною схемою компромісів

Ф(х) = І (1 -уокОО)Л хєГх, (2)

к«І

при нормуванні, часткових критеріїв за допомогою виразів

Уо. = А, =Биру,(х), і=1,ш, (3)

А| хе!'.

має єдиний мінімум на парсілелепіпеді Г1„, тобто є унімодальною.

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

У третій . _ главі розглядаються питання, пов'язані з алгоритмічною реалізацією нелінійної схеми компромісів.

Розробляються обчислювальні методи пошуку екстремуму

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

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

міиімаксу, в спокійних ситуаціях - принцип інтегральної

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

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

Основним методом пошуку мінімуму уаагальненого критерію (2) в роботі є модифікований метод Нелдера • Міда (метод симплекс-планування).

Розглянемо метод симплекс-планування в задачі пошуку мінімуму деякої функції Р{х), заданої на паралелепіпеді П, = {х є Еп І а, < х, 5 Ь„ і = 1, п} при наявності обмежень тину нерівностей дк(х)50, к = 1,1. 1 Іеобхідьо 'знайти точку х'еГІц.тдку, що Р(х’) < Г(х) та дк(х")<0, к =1,1. Коротко алгоритм, методу симплекс-планування можна представити так.

, КРОК 1. Перехід у простір нормованих незалежних змінних х. Задамо початкову точку хм с II*. С]к(хц)50, к = 1,1, та перейдемо від паралелепіпеда- П, до кубу К,/ = {х' є Е" І 0 5 х' і 1. і = ЇГп}. викопавши нормування нез<клелних аііпііих чідпоиїдно до ниразу

x'=Fr- (4>

t>j Q.j

Пошук мінімуму функції F(x) зводиться тепер до пошуку точки Хл є кх/, яка відповідає точці х' при перетворенні (4). Точці хн відповідатиме точка хн'. В подальшому будемо працювати з нормованими незалежними змінними і для. зручності будемо опускати штрих. .

КРОК 2. Вибір початкового симплексу. Назв.емо п-вимірним симплексом в п-вимірному євклідовому просторі многогранник з п+1 вершиною. Якщо многогранник правильний, то симплекс називається регулярним. Побудуємо всередені кубу К* регулярний симплекс, одна з вершин якого збігається з точкою х„. Координати векторів, відповідних вершинам симплексу, будемо зберігати в таблиці X розміром п + 1 на п. 1-й рядок таблиці буде відповідати і-й вершині симплексу, а j-й стовпчик - j-fi компоненті і-ї вершини. Таким чином, перший рядок цієї таблиці буде містили компоненти вектора х„. Елементи цієї таблиці визначаються виразами:

„ v .. і -1 + УпТТ

Л|| = X|J +S’ —=-----:---,

J2 n-k

V Г---------------------- (5)

v Y .. 1 n-l + Vn+1

XhM-X«+8.—-------------—^---------------------.

Тут k - величина, що визнач'? розмір симплексу. Вона впливає на кількість ітерацій, необхідних для досягненн- точки мінімуму, і її вибір може визначатися апріорними відомостями про функцію, що мінімізується. В більшості випадків на цьому кроці k береться рівним 0.2. Величина s визначає спрямованість симплексу всередині кубу К„. Якщо Хі) <, 0,5, то s = 1, в противному випадку s = -1.

Після того як таблиця X створена, побудуємо вектор Fv, компонентами якого с значення функції F(x) для відповідних рядків таблиці, тобто значення функції, відповідні вершинам .симплексу.

КРОК 3. Побудова наступного симплексу. Обираємо в таблиці X рядок, якому відповідає максимальна компонента вектора Fv. Нехай цей рядок має номер М. Відкидаємо цю вершину, як найгіршу, і будуємо новий симплекс, який містить усі залишені порішиш і що одну нову вершину, яка одержується відображенням підкинуті' вершини відносно центра ваги протилежної грані симплексу. Побудова нового симплексу може здійснюватись або за

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

XjH = 2-f-XM].

XjH= 1,5-f+ 0.5-XMJ- (6)

XjH = 0,5 • ^ + 0,5 • xMj

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

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

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

Поставимо задачу пошуку глобального мінімуму в' найбільш загальному вигляді. Нехай U - деяка непуста множина із Е",'а F(x) -функція, визначена на цій множині. Без втрати загальності можна розглядати задачу мінімізації цієї функції на цій множині. Нехай тоді F’ - точна нижня грань функції F(x) на множині U. Нехай також множина U* = {х є U I F(x) = F'} - це множина точок глобального' мінімуму функції F(x). Необхідно знайти точку х' із множини U, яка достатньо близька до множини U* або належить їй. Якщо функція F(x) - неперервна, а множина U - замкнута та обмежена, то знак нижньої грані можна замінити знаком мінімуму.

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

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

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

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

Розроблено тахі допоміжні алгоритми: алгоритм апроксимації невідомих критеріальних функцій поліномами другого ■ порядку, алгоритм планування експерименту з використанням ЛПт-послідовностей, алгоритм покоординатного спуску при використанні методу більш точних моделей для задач великого виміру.

Уведення в нелінійну схему компромісів (2) вектора переваг дозволяє врахувати переваги конкретної ОПР, внаслідок чого парето-оптимальний розв'язок, отриманий за нелінійною схемою компромісів (1). відповідатиме рішенню, іцо приймає ОПР. Однак ОПР може усвідомити та сформулюватитвої/переваги, тобто ту схему компромісів, на підставі якої приймається рішення, лише внаслідок виконання кількох пробних кроків,- оцінки .усієї ситуації в цілому та поступового поліпшення багатокритеріального роз'вязку. В зв'язку з, цим у програмі багатокритеріальної ■'оптимі'зації була реалізована' інтерактивна процедура вибору компонент вектора переваг, заснована на модифікованому методі Нелдера - Міда.

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

У четвертії: глааі описується програма багатокритеріальної

оптимізації TURBO-OPT1M. Програма виконана мовою Borland Pascal with Objects 7.0 з використанням бібліотеки Turbo Vision, що забезпечує ефективне використання ресурсів ЕОМ, стандартизоване та досить зручне середовище для користувача, а також простоту модифікації та налагодження. -

Розглянемо постановку задачі, на яку орієнтована розроблена програма. Нехай задана множина можливих рішень Ґх, що складається із векторів х n-вимірного євклідова простору Е" і являє собою n-виміриий паралелепіпед, тобто на вектори х накладені обмеження вигляду ai^x,£bi, і = ї7ії. На вектори х можуть бути накладені також обмеження типу нерівностей вигляду д,(х)^0, і = 1, п. Якість рішення, що приймається, оцінюється за

сукупністю часткових критеріїв fk(x), k = 1........ш, що утворюють

вектор f, який повинен лежати в області допустимих значень D. Усі часткові критерії повинні бути додатні та потребувати мінімізації. Крім того, для кожного часткового критерію f, повинно бути задано максимально допустиме значення А.,. Задача векторної оптимізації полягає в тому, щоб знайти розв’язок х', іцо оптимізує вектор часткових критеріїв ирн заданих обмеженнях.

Програма дозволяє розв'язувати задачі оптимізації для таких випадків зв'язку часткових критеріїв з керуючими параметрами:

а) критерії виражаються через параметри. явно і є деякими

функціями від параметрів, тобто відомі аналітичні залежності критеріїв від параметрів, якими можна скористуватись в явному вигляді; •

б) критерії с деякими функціоналами, або для розрахунку їх

значень потрібно розв'язання системи диференціальних рівнянь або запровадження яких-небудь інших обчислень; •

в) залежності критеріїв від параметрів невідомі, і для ■ визначення параметрів необхідно провести один або кілька експериментів;

г) значення критеріїв можна одержати, виконавши написану користувачем програму;

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

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

У п'ятій главі обговорюються результати практичного застосування програми багатокритеріальної оптимізації ТІДІВО-ОРТІМ. Показано, що розроблені методи дозволяють розв'язувати різні задачі багатокритеріальної оптимізації. Розглядаються результати моделювання збуреного бічного руху літака та побудови відповідної системи керування літаком. Описується програма моделювання та оцінки операторської діяльності, наводяться результати розв'язування задачі оптимального проектування лавинно-прольотного діоду.

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

у = -М • Мг - 0,25 ■ р,

V = -0,1 • у - Мз - 0, 31 • р, (7)

Р = 0,03 ■ у-Мз-0,45-р,

де у - кут крену, іу - курсовий кут, р * кут ковзання, а

-зо, м, <-30

м,= С|2 V |М, іЗО , (8)

зо, Мі V о

-10, м2<-10

Мі = С„ (У + м,). |Ма| £ Ю , (9)

,0> М2> 10

-10, Мі < -10

Мз “ Саз V. ІМзІ з ;іо . (10)

10. Мз > 10

Величина М обирається в залежності від режиму польоту і може бути або сталою, або являти собою деяку функцію, значення якої змінюються в невеликих межах. Коефіцієнти зворотного зв'язку С,,, Сіа, С2І та С2І задаються виразами

й-к,ь

100 • к 12 • -ч/^ 12 • к?2 1

<-12 =----------

м2 М' (її)

С2і = 0,

Сг2 = к22-

М2

Вибір коефіцієнтів к„, к,2 і к2_, у виразах (11), а також коефіцієнт функції Ляпунова Ь повинні підпорядковуватись умовам зв'язку, які для розглянутого літака мали вигляд

СІЗ = ^-{0.03-Ь-0,025 + к,2-(0,31 + Ь-Сг2)-+

[(і, 18 • Ь • С22 - Ь2 • С|2 - 0,096і) -(і-к?г) -кп +кіз . ___ } . о.

(12)

Г гі т і 50 ■ Ь ■ кгі 5,3 • /ь ■ кгг

С23 = -0,31+—--------------- -----к23 = 0 . (13)

Вибір чільних параметрів відповідно до формули (13) повинен забезпечиш додатнісгь підкореневого виразу в формулі (12). Однак в розглянутому випадку неповної інформації, коли Сп — 0, умову зв’язку (13) можна замінити безпосередньою вимогою додати ості цього підкореневого виразу, тобто

1,18 • Ь -С22 -Ь2 • С|2- 0,0901 > 0 . (!■!}

Розв’язуючи нерівність (14), одержуємо обмеження па діапазон значень функції Сп: ■

' 0,09 <Ь-С2< 1,0 . (15)

Задача параметричної оитимізації полягає у виборі коефіцієнтів кп, к,„ к_,_, та Ь, які задовольняють норіниості (1і) т<> умові зв'язку (12), яка повинна задовольнятися при значеннях коефіцієнта к,., в межах -1 < кп < 1.

Критеріями, що мінімізувались, були:

1) час перехідного процесу, які пі визначається як період зменшення величини курсового кута під деякого початкового значення до’ полошиш градуса, тобто Тп.,, = Ц|'у| ;; 0,5"1.

2) максимальне абсолютне значення величини кута ковзання за час перехідного процесу;

\ , 3) максимальне абсолютне значення величини кута крену |у|тм

за час перехідного процесу;

4) величина перерегулювання за курсовим кутом ч/тм:

5) коливальність ,М„, яка визначається як відношення величини двох суміжних піків при коливальному процесі за курсовим кутом.

При оптимізації використовувались такі максимальні значення цих величин:

Тир £ 15 с,

ІРІ»и^2«,

Іти ^ 31»

Му/іО, 1°.

(16)

Оскільки величина та швидкість відхилення органів керування обмежені, то в закон керування були введені нелінійності типу насичення, (8), (9), (10). Величина М в першому наближенні взята М= 1. Початкові умови були такими:

\)/(0) = -20, у(0) = Р(0) = 0.

(17)

Значення Ь вибирались із діапазону 1 + 10. Ь = їв першому варіаіггі. Оптимізація проводилась по параметрах 1с,,, к,2, к22. Показники перехідного процесу, одержані в результаті оптимізації при Ь == 1, задовольняли технічним вимогам (16), але були близькими до обмежень. Тому подальша оптимізація проводилась за рахунок перебору величини Ь. Результати оптимізації для різних значень Ь в діапазоні 1 + 5 показано в табл. 1 та 2.

Таблиця 1

Оптимальні значення параметрів для Ь в діапазоні 1 5

ь к|3 ки .

1 0,95339 -0,28695 0,00190

2 0,13910 -0,43180 0,00168

3 0,07427 -0,23232 0,00153

4 0,07943 -0,36908 0,00133

5 0,62105 -0,39235 0,00141

.Таблиця 2 '

Оптимальні значення критеріїв для Ь в діапазоні 1 * 5

ь Т * пер іРітах Мтах М V

1 13,90000 1,79490 28,56437 0,00000 0,00000

2 12,50000 1,56131 21,72989 0,01286 0,00000

3 13,60000 1,61286 15,79842 0,37072 0,00000

4 12,60000 1,28399 17,52178 0,43383 0,00000

5 13,70000 1,255597 28,69303 0,00000 0,00000

На рисунку 1 показано перехідні процеси для отриманих значень керуючих параметрів для Ь = 1.

ВИСНОВКИ

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

2. Доведена парето-оптимальність вектора рішень, що отримується при мінімізації нелінійної схеми компромісів.

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

4. На випадок одної змінної доведено, що коли часткові критерії - двічі диференційовані, строго унімодальні на відрізку

функції, то для унімодальності нелінійної схеми компромісів досить, щоб друга похідна иеліиійно'ї схеми була додатна на відрізку 1х,,х2],

де х, - найлівіша точка, в якій досягається мінімум одного з

часткових критеріїв, а х2 - найправіша така точка.

5. Метод Нелдера - Міда модифіковано для врахування

обмежень типу нерівностей. .

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

7. Розроблено інтерактивну процедуру вибору компонент

вектору переваг, яка заснована на модифікованому методі Нелдера -Міда.

8. Запропоновано об'єднати процес пошуку мінімуму узагальненого критерію модифікованим методом Нелдера - Міда та апроксимацію часткових критеріїв поліномами другого порядку.

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

Основні положення дисертації опубліковано в таких працях:

1. Воронин А.Н., Козлов А.И. Многокритериальная

оптимизация сложных динамических систем // Управление и автоматизация проектирования в электроэнергетических системах. -Челябинск, 1990. - С. 134. .

2. Козлов А.И. Применение нелинейной схемы компромиссов при моделировании операторской деятельности // Интеграция АСУТП и тренажерных устройств. - М., 1991. - С. 46.

3. Воронин А.Н., Козлов А.И. Численный метод решения вариационных задач управления // Проблемы построения кибернетических систем. - Киев: Ин-v кибернетики им В.М. Глушкова АН Украины, 1993. - С. 35.

4. Козлов А.И. Об унимодальности нелинейной схемы компромиссов // Автоматика. - 1993. - N 4. - С. 81-85.

5. Voronin A.N., Koziov A.i. Multiobjective problems solution

under uncertainty // Multiple criteria problems under uncertainty. Abstracts of Tiie Third International Workshop - Orekhovo-Zuevo, 1994.-P. 0\>. .

Козлов Л. К. Исследоплиие п алгоритмическая реализация нелинейной схемы компромиссов.

Диссертация на сопсканле ученой степени кандидата технических наук по специальности 05.13.01—системный анализ и теория оптимальных решений, Институт кибернетики им. В. М. Глушкова НАН Украины, Киев, 1995.

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

Kozlov A. I. The Investigation and the Algorithm Realisation of the Non-linear Trade-off Scheme.

Dissertation for the candidate of technical sciences scientific degree on a speciality 05.13.01—the system analysis and the theory of optimal decisions, V. M. Glushkov’s Institute of Cybernetics of National Academy of Sciences of Ukraine, Kiev, 1995.

The manuscript and five publicaiions are defended containing theoretical and practical results on research of use of nonlinear trade-off scheme in the software for multicriteria optimisation problems solving. Numerical methods and algorithms accounting peculiarities of use of non-linear trade-off scheme are offered. Developed algorithms are realised in the software.

Ключові слова: оптимізація багатокритеріальна, згортка скалярна, критерій векторний, розв’язок ефективний, методи чисельні, алгоритмізація, програмне забезпечення.

Підп. до друку 05.09.95. Формат 60X84/16. Папір для розм. апарат. Офс. друк. Ум. друк. арк. 0,93. Ум. фарб>відб. 1,16. Обл. вид. арк. 1,0.. Зам. 712. Тираж 100 прим.

Редакційио-видавиичнй відділ з поліграфічною дільницею Інституту кібернетики імені В. М. Глушкора ПАН України 252022 Київ 22, проспект Академ,иа Глу-лкова, 40