| Головна |
| « Попередня | Наступна » | |
2.6.2.6 МЕТОДИ ВИРІШЕННЯ ЗАВДАНЬ ВЕКТОРНОЇ ОПТИМІЗАЦІЇ НОРМАЛІЗАЦІЯ КРИТЕРІЇВ | ||
|
Тому в більшості випадків у вирішення багатокритеріальної задачі потрібно включення попереднього етапу - нормалізації критеріїв. Нормалізація критеріїв являє собою однозначне відображення функції fk (X), Vk е K, з RN в RN. Для нормалізації критеріїв у векторних завданнях використовується лінійне перетворення: fk (X) = af '(X) + c, Vk еk (54) або fk (X) = (fk (X) + c) / a, Vk е K, (55) де f'k (X), Vk е K - первісне значення критерію; fk (X), Vk е K - нормалізоване значення. Така нормалізація критеріїв у оптимізаційної задачі не впливає на результат рішення. У разі, якщо вирішується опукла оптимізаційна задача: max F (X), X е 5, (56) X то в точці оптимуму X * е5, dF (X *) / dX = 0. (57) Якщо ж вирішується оптимізаційна задача: max (aF (X) + c), X е 5, (58) то в точці оптимуму X * е5, d (aF (X *) + c) / dX = 0, (59) т.е . результат ідентичний. До нормалізації критеріїв у векторних завданнях пред'являються дві основні вимоги: нормалізовані критерії повинні бути виміряні в одних і тих же величинах; в точках оптимуму Xk, Vk е K величини всіх критеріїв повинні мати однакову величину. При виконанні цих вимог представляється можливим порівняти критерії щодо їх чисельним значенням. У нашому випадку - вирішенні задачі багатокритеріальної оптимізації з максимумом векторної цільової функції застосовується наступна нормалізація критеріїв: Xk (X) = (fk (X) - frw; - fkmn). (60) При цьому відносна оцінка Xk (X), k = 1, K на всій безлічі допустимих точок лежить в межах 0 Слід зауважити, що при всіх достоїнствах попередньої нормалізації критеріїв у неї є важливий недолік (загальний для всіх відносних величин) - нормалізований критерій не завжди має настільки однозначну економічну інтерпретацію, як звичайний. Наприклад, якщо відносна оцінка критерію f9 - норматив поточної ліквідності - дорівнює 0,9 (тобто 90% від максимально можливої), то важко сказати, чи достатній це показник для банку. Якщо ж знати, що в абсолютних величинах дана величина становить 94% (при максимумі в 106%), а необхідне інструкцією мінімальне значення становить 70%, то на підставі цього можна зробити більш певні висновки. Тому в ході рішення задачі багатокритеріальної оптимізації необхідно користуватися паралельно звичайними і нормалізованими критеріями. Методика побудови безлічі Парето-оптимальних рішень Виділення Парето-оптимального підмножини - досить важке завдання, для якої поки не відомий універсальний алгоритм. Однак для деяких окремих випадків такі алгоритми відомі, наприклад, для випадку лінійної задачі векторної оптимізації існує узагальнений варіант симплекс-методу, який дозволяє виділити всі Парето-оптимальні крайні точки і необмежені ефективні ребра. Однак у нашому випадку він не підходить, так як деякі з цільових функцій є нелінійними. У цьому випадку напрошується рішення, яке використовує ідею повного перегляду всіх можливих варіантів рішень і вибору з них найкращого. Однак, природно, що такий повний перегляд неможливий, так як кількість точок перегляду нескінченно. Для того, щоб зменшити кількість переглядаються точок можна (звичайно, на шкоду одержуваного обсягу інформації)-яким розумним способом організувати процедуру перегляду. На цій ідеї і заснований метод вирішення проектно-конструкторських завдань із суперечливими критеріями, запропонований І. М. Соболем і Р. Б. Статніковим і заснований на твердженні, що максимальне число переглядаються точок при мінімумі обчислень досягається, якщо точки вибираються з так званої ЛПТ- послідовності. Назва ЛПТ-послідовність з'явилося як скорочення фрази "нескінченні послідовності точок, будь двійковий ділянку яких є Пт-сітка". Таким чином, переглядаючи варіанти в точках, відповідних ЛПТ-послідовності і, обчислюючи значення критеріїв у цих точках, можна приймати обгрунтовані рішення. Для виділення серед отриманих точок Парето-оптимальних використовується метод, заснований на застосуванні алгоритмів сортування. Перевагою даного методу є відсутність необхідності вирішення скалярних задач оптимізації, які в деяких випадках (складні нелінійні функції з великою кількістю розривів і т. д.) вимагають значних витрат машинного часу. У нашому випадку це не настільки актуально, як в інженерних задачах, так як екстремуми всіх використаних функцій легко обчислюються. Тому в якості методу побудови множини Парето був обраний наближений графоаналітичний метод Н. М. Моїсеєва, який полягає в послідовному итеративном процесі вирішення найпростіших оптимізаційних задач. У разі двох критеріїв він застосовується такий спосіб: спочатку задаються початковими довільними значеннями критеріїв: f1 = с1; f2 = с2. Потім вирішуються дві оптимізаційні завдань: 1) max f1, f = С2; 2) max f2, f = cb (62) Вирішивши ці два завдання знаходять точки a і b. Пряма, що з'єднує ці дві точки є областю Парето в першому наближенні. Далі вирішуються дві аналогічні завдання. При цьому задаються значеннями критеріїв: f = c3; f2 = c4. Потім вирішуються дві оптимізаційні завдання: 1) max f1, f = C4; 2) max f>, f = C3. (63) Через отримані точки знову проводять прямі. Після з'єднання точок c і d отримують ламану acdb, яка є областю Парето другого наближення. У більшості випадків друге наближення є достатнім. У разі більшого числа критеріїв метод втрачає наочність, але може виконуватися за допомогою ЕОМ. Важливою проблемою є візуальне подання безлічі Парето. У разі двох критеріїв воно відображається лінією на площині. У разі трьох критеріїв безліч Парето можна візуалізувати поверхнею в просторі, проте, на відміну від лінії на площині зробити вибір на підставі тривимірного графіка досить важко. Тому можливе застосування альтернативного методу ліній рівня, який можна узагальнити на більше число критеріїв. Скалярні методи розв'язання задачі багатокритеріальної оптимізації Методика побудови безлічі Парето дозволяє представити найбільш повну інформацію про багатокритеріальної задачі оптимізації особі, що приймає рішення, без будь-яких передумов про відносну важливість критеріїв. Однак даний метод досить громіздкий і важко застосуємо у разі великого числа критеріїв (більше трьох). Тому на практиці більш широко застосовуються методи, що дозволяють тим або іншим способом привести рішення задачі векторної оптимізації до скалярної. Метод головного критерію Найбільш простим і часто применяющимся методом є виділення одного критерію в якості головного і переклад інших критеріїв в розряд обмежень шляхом формулювання додаткових обмежень на значення цих критеріїв. Конкретні значення даних додаткових обмежень можуть бути встановлені, наприклад, за допомогою статистичних методів, або експертним шляхом на підставі неформальних міркувань. Ймовірно, у більшості ситуацій для банку основним критерієм, підметом максимізації, буде показник прибутковості (рентабельності), а на критерії, що відображають різні аспекти надійності, будуть накладатися обмеження, так як кінцевою метою діяльності якої комерційної організації є отримання прибутку, а збільшення надійності шляхом , наприклад, надмірного підвищення ліквідності вище розумних меж не тільки не збільшить довіру клієнтів і партнерів, але й може поставити під загрозу майбутнє стан банку зважаючи на зниження прибутковості. Проте в деяких ситуаціях виправдано зосередження зусиль на максимізації якого іншого критерію, крім прибутковості. Так, в передбаченні кризи довіри до банківської системи розумною є максимізація ліквідності з метою задоволення масових вимог щодо повернення вкладів. У разі, якщо банк бажає розширити свою ресурсну базу шляхом залучення вкладів такої групи населення і господарських агентів, яка при виборі банку орієнтується на його місце в популярних банківських рейтингах, то слід максимізувати підсумковий рейтинг банку за моделлю Кромонова, як найбільш популярною. В цілому, метод приведення багатокритеріальної задачі до однокритерійним шляхом накладення додаткових обмежень на менш важливі критерії є широко поширеним зважаючи на свою зрозумілості, простоти інтерпретації результатів і невисоких вимог до математичної підготовки експерта, програмному забезпеченню та швидкодії ЕОМ. Проте даному методу притаманний ряд фундаментальних недоліків. Перш за все, даний метод значно спрощує структуру вихідної задачі, не враховує різницю в значеннях критеріїв, переведених в розряд обмежень. Крім того, досить важким завданням є формулювання обмежень на значення менш важливих критеріїв. Якщо задати занадто низькі обмеження, то отримана точка не обов'язково буде Парето-оптимальної (у разі, якщо цільова функція має декілька екстремумів), а якщо занадто високі, то значення цільової функції (головного критерію) в отриманій точці буде занадто низьким порівняно з його абсолютно досяжним максимумом (без врахування обмежень на інші критерії). Однак даний метод використовується при побудові Парето-оптимального безлічі за методикою академіка Мойсеєва. Метод поступок Покращуваній різновидом методу перекладу менш важливих критеріїв у обмеження є метод послідовних поступок (званий також методом оптимізації за послідовно застосовуваним критеріям), пропонований насамперед В. В . Подиновский в ряді робіт. Його суть полягає в наступному. Проводиться аналіз відносної важливості критеріїв і критерії розташовуються і нумеруються в порядку убування важливості. Виробляється оптимізація за першим критерієм і визначається його найбільше значення f *. Далі експерт оцінює величину допустимого зниження (поступки) даного критерію (f1 - А / 1) і шукається оптимум другого за важливістю критерію і т.д. Після оптимізації останнього за важливістю критерію за умови, що значення кожного критерію k = 1, K повинно бути не менше (fl - Afk), k = 1, K, одержувані рішення вважаються оптимальними. Переваги цього методу в його простоті і наочності. Важливою перевагою є можливість цілеспрямованого участі особи, що приймає рішення в процесі оптимізації з урахуванням раніше отриманих (на попередньому етапі оптимізації) даних шляхом вибору величини поступки по кожному критерію. Основним теоретичним недоліком даного методу є те, що на кожному кроці відбувається усічення безлічі точок, оптимальних за Парето, звідси в загальному випадку вийшло рішення не оптимально за Парето, тобто потрібне додаткове доказ оптимальності по Парето даного рішення, що є дуже складною процедурою. Інакше доведеться змиритися з тим, що дане рішення, хоча і задовольняє особа, яка приймає рішення значеннями всіх критеріїв, але не обов'язково є оптимальним. Однак на практиці це не настільки важливо, так як в реальній ситуації шукають, як правило, не оптимальне, але «досить хороше» рішення. Другим недоліком є складність вибору та обгрунтування величин поступок за окремими критеріями, так як величини поступок не співмірні між собою зважаючи різної економічної сутності різних критеріїв. Однак від другого недоліку можна позбутися застосуванням нормалізації критеріїв. Згортка критеріїв Інша дуже поширена група методів скаляризації векторної задачі математичного програмування - згортка критеріїв. Існує велика кількість різних видів згорток [11, 12]. Теоретично всі вони базуються на підході, пов'язаному з поняттям функції корисності особи, що приймає рішення. При цьому підході передбачається, що особа, яка приймає рішення, завжди має функцію корисності, незалежно від того, чи може особа, яка приймає рішення задати її в явному вигляді (тобто дати її математичний опис). Ця функція відображає вектори критеріїв на дійсну пряму так, що більше значення на цій прямій відповідає більш кращого вектору критеріїв. Сенс різних згорток полягає в тому, щоб з кількох критеріїв отримати один «коефіцієнт якості» (зведений критерій), наближено моделюючи таким чином невідому (не задано в явному вигляді) функцію корисності особи, що приймає рішення. Найбільш популярною сверткой є метод зважених сум з точковим оцінюванням ваг. При цьому задається вектор вагових коефіцієнтів критеріїв, що характеризує відносну важливість того чи іншого критерію: Вагові коефіцієнти зазвичай використовуються в нормованому вигляді і задовольняють рівності: K X ak = 1, ak> 0, Vk е K, (65) k = 1 тобто передбачається, що вагові коефіцієнти ненегативні. Кожен критерій множиться на свій ваговий коефіцієнт, а потім все зважені критерії сумуються і утворюють зважену цільову функцію, значення якої інтерпретуються як «коефіцієнт якості» отриманого рішення. Отримана скалярізованная функція максимізується на допустимої області обмежень. Виходить однокритеріальних (скалярна) задача математичного програмування: F0 = max X af (X). (66) k = 1 У результаті рішення даної задачі виходить точка оптимуму X0. Основною перевагою даної згортки є те, що з нею пов'язані класичні достатні і необхідні умови оптимальності по Парето (теореми Карліна). Теорема Карліна 1. У опуклою завданню багатокритеріальної оптимізації точка X0 е 5 оптимальна по Парето, якщо існує вектор вагових коефіцієнтів A0 = {a °> 0, k = 1, K}, для якого виконується співвідношення: Xа0 / ь (Х0) = тахX / (X). (67) о, к = 1 а = 1 Теорема Карліна 2. Якщо в опуклою завданню багатокритеріальної оптимізації точка X0 е 5 Парето-оптимальна, то існує вектор вагових коефіцієнтів А0 = {а °> 0, к = 1, К}, для якого виконується співвідношення: Xа0 / к ° (Х °) = тахXа0 / (X). (68) , Ак! До (х) =! Хах ^ ак. / К ' к = 1 ^ к = 1 а = 1 Згідно з даними теоремам, дану згортку можна використовувати для отримання Парето-оптимальних точок. Прикладом даної згортки може служити підсумковий рейтинг надійності банку Кромонова, отриманий як адитивна згортка ряду коефіцієнтів. Перевагою даного методу є те, що він згідно теоремі Карліна генерує Парето-оптимальні точки. Однак йому притаманний цілий ряд фундаментальних недоліків. По-перше, неявна функція корисності особи, що приймає рішення, як правило, нелінійна, тому «істинні» ваги критеріїв (тобто такі ваги, при яких градієнт зважене цільової функції збігається за напрямком в градієнтом функції корисності) будуть змінюватися від точки до точці, тому можна говорити лише про локально відповідних вагах, крім того, часто особа, яка приймає рішення взагалі не може задати вагові коефіцієнти. По-друге, далеко не завжди втрата якості по одному з критеріїв компенсується приростом якості по іншому. Тому отримане рішення, оптимальне в сенсі єдиного сумарного критерію, може характеризуватися низькою якістю по ряду приватних критеріїв і бути тому абсолютно неприйнятним. По-третє, отримане рішення часто буває нестійкий, тобто малим приращениям вагових коефіцієнтів відповідають великі прирости цільових функцій. По-четверте, згортка критеріїв різної фізичної природи не дозволяє інтерпретувати значення зваженої цільової функції. По-п'яте, значні труднощі можуть виникнути в разі сильної кореляції між критеріями. Деякі з перерахованих вище недоліків можуть бути скориговані. Так, у разі різної фізичної (економічної) природи критеріїв можлива їх нормалізація і подальша згортка нормалізованих критеріїв. Щоб виключити неприйнятно низькі значення окремих критеріїв, можна накласти додаткові обмеження на ці критерії. Іншим методом боротьби з даним недоліком - неприйнятно низькими значеннями окремих критеріїв при хорошому значенні сумарного критерію - є застосування згорток НЕ адитивного, а мультиплікативного виду: Г0 = тах П (ак / к (X)) Рк. (69) Кек Однак дана згортка не набула великого поширення з огляду на те, що існують аналогічні, але більш перспективні види згорток. (7О) Так, існує згортка види: ТІП ^ = Х | / к - / к (Х) / К Найбільш широке застосування дана згортка отримала при р = 2, яка трактується як мінімізація суми квадратів відносних відхилень функціоналів від своїх досяжних оптимальних значень. Дана точка в разі рівноцінності критеріїв показує рішення, найбільш близьке до недосяжною «ідеальної» точці (в якій всі критерії приймають своє максимальне значення). Однак даної згортку також властивий наступний поширений недолік: «хороше» значення зведеного критерію досягається ціною низьких значень деяких приватних критеріїв. Методики, засновані на гарантованому результаті Даний недолік відсутній в методиках, заснованих на гарантованому результаті (максимина, мінімакс). Даний принцип вперше був запропонований Карліним [19] в наступній постановці: тахтіп ^ (X) = {/ к, к = 1К}. (71) X до Дана задача називається максимізацією мінімальної компоненти. Але, так як критерії часто вимірюються в різних одиницях, то не представляється можливим порівнювати критерії між собою і вести спільну оптимізацію. к = 1 Машуніним був запропонований вдосконалений варіант даної методики, заснований на використанні нормалізації критеріїв. Машунін вводить поняття рівня Х-нижній з відносних оцінок: Х = ТІП Х до (X) (72) і перетворює максимина задачу Х0 = тахтіп Х до (X) (73) в екстремальну задачу Х0 = тах Х, Х <Хк (X), к = 1, К. (74) Дана задача є формалізованим поданням принципу максимальної ефективності. Методика, заснована на принципі максимина, дозволяє оцінити розташування умовного центру багатовимірного безлічі Парето. Застосування даного методу корисно навіть в умовах завдання з двома або трьома критеріями, коли можлива візуалізація безлічі Парето, так як вона дає додаткову інформацію про можливості компромісу між критеріями. | ||
| « Попередня | Наступна » | |
|
| ||