Методи структурно-параметричної компараторної ідентифікації моделей багатофакторного оцінювання і вибору рішень

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Вступ

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

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

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

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

Для досягнення поставленої мети необхідно:

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

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

- підвищити ефективність існуючих методів компараторної параметричної ідентифікації моделей багатофакторного оцінювання;

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

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

- провести аналіз ефективності й апробацію розроблених математичних моделей і методів при розв'язанні практичних задач.

1. Аналіз предметної області, постановці мети і задач дослідження

У ньому наведені результати системологічного аналізу проблеми прийняття рішень і задач ідентифікації МБФО, виконаний огляд публікацій з досліджуваної проблеми, сформульовані постановки мети і задач дослідження.

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

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

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

Наведений огляд літературних джерел показав, що основні результати отримані для окремих задач: виділення підмножин ефективних альтернатив ; формування функції корисності часткових критеріїв (ФКЧК); параметричної ідентифікації адитивних і адитивно-мультиплікативних моделей оцінювання. З урахуванням цього, актуальними стають загальні задачі структурно-параметричної ідентифікації МБФО на множині адитивних, мультиплікативних і змішаних ФУК, які припускають сумісне визначення векторів параметрів ФКЧК і векторів вагових коефіцієнтів часткових критеріїв.

2. Обґрунтування і розробка теоретико-методологічних основ ідентифікації моделей багатофакторного оцінювання

Для розв'язання задачі структурно-параметричної ідентифікації обрані адитивна, мультиплікативна і адитивно-мультиплікативні МБФО:

; (1)

; (2)

; (3)

, (4)

де Р(х) - значення ФУК для варіанту х; = - значення функції корисності і-го часткового критерію; - ваговий коефіцієнт і-го часткового критерію, ; ; - вагові коефіцієнти добутку ФКЧК і , ; - адаптаційний коефіцієнт, що визначає конкретний вид схеми, . Як ФКЧК пропонується використовувати функції:

; (5)

(6)

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

Для вибору рішень в умовах невизначеності цілей, вихідних даних і ризику запропоновано використовувати відомі моделі: універсальну адаптивну, інтервального аналізу, Лапласа, максимаксу, Вальда, Гурвиця, Севіджа.

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

Сформульована загальна задача структурно-параметричної ідентифікації МБФО у такій постановці.

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

; (7)

; (8)

. (9)

Необхідно для встановленого ОПР порядку (7), (8) або (9) вибрати вид МБФО на множині структур (1) - (4), визначити найкраще значення вектору параметрів (де - множина допустимих векторів параметрів моделі).

Вектор параметрів складається з трьох векторів , де - вектор параметрів ФКЧК; - вектор параметрів ФУК; - вектор адаптаційних параметрів ФУК.

Після декомпозиції загальної задачі , у ній виділені комплекси задач: структурної (вибір виду моделі ) і параметричної ідентифікації ФКЧК (визначення ) і ФУК (визначення та/або ).

Значення мінімізують похибку відновлення переваг ОПР: , де ; - відповідно порядкові номери альтернативи xj у перевазі ОПР і отриманій на підставі значень ФУК із вектором параметрів .

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

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

– для переваги виду (7) на основі відношення :

–

; (10)

, (11)

де ; - значення ФУК виду із значеннями параметрів для альтернативи ;

- для переваги у вигляді відношення :

. (12)

На перевазі ОПР виду (8) необхідно заздалегідь виділити відношення и , а як критерій пропонується використовувати:

, (13)

де:

;

.

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

На основі сформованих відношень з урахуванням виду ФУК (1) - (4) можуть бути сформовані системи рівнянь і (або) нерівностей (СРН):

, ; (14)

, ; (15)

, . (16)

Отримані СРН доповнюються обмеженнями на значення параметрів . Для зниження розмірності СРН (обчислювальних витрат на її розв'язання) пропонується заздалегідь виділяти підмножину .

У процесі структурно-параметричної ідентифікації значення і використовуються для обчислення ФУК для всіх моделей-претендентів (1) - (4). Для кожної з моделей , на основі відношень (14) - (16) і обмежень формуються відповідні СРН. У результаті їх розв'язання знаходяться найкращі значення параметрів для всіх класів моделей (1) - (4) і відповідні їм значення критеріїв , (11) - (13) та визначається найкраща з моделей .Для спрощення задачі формування підмножин ефективних альтернатив (на опуклих множинах Х) заздалегідь виділяється наближена область компромісів (НОК) , . З цією метою на множині Х знайдемо найкращі за кожним критерієм варіанти і відповідні їм значення інших критеріїв kj(), . Визначимо межі <, >, відображення підмножини ХP у простір критеріїв К: , , якщо min і , якщо max.

Для знайдених меж НОК <, >, знайдемо r опорних варіантів , ,…, , координати яких у просторі критеріїв , визначають точки, якомога більш рівномірно розподілені на . Побудуємо площини, які проходять через різні набори з т точок, що включають граничні точки , і точки , ,…, та відсікають від Х область .

Запропонована модифікація методу для кругової області Х з рівномірним розподілом рішень з r = 1 дозволяє скоротити НОК: щодо вихідної області у 40,1 разу; щодо методу сектора - у 10 разів; щодо базового методу - у 3,6 рази.

3. Розробка математичних моделей і методів ідентифікації моделей багатофакторного оцінювання

При розв'язанні задачі параметричної ідентифікація адитивних моделей оцінювання (1) для сформованих відношень , або отримаємо підсистеми рівнянь і нерівностей (14), (15) або (16). Для визначення єдиного розв'язку перейдемо до регуляризованих задач (10) - (11). Для переваги на основі відношення еквівалентності перейдемо до регуляризованої задачі (12).

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

При заданих значеннях параметрів ФКЧК приходимо до задачі ідентифікації вагових коефіцієнтів часткових критеріїв . Системи лінійних рівнянь і нерівностей (14) - (16) матимуть вигляд:

, (17)

(18)

(19)

, (20)

де m - кількість часткових критеріїв; nЕ, nS, nNS - відповідно потужності відношень , , у вихідному порядку ; .

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

Як альтернативу рішенням у вигляді чебишевської точки пропонується використовувати узагальнені розв'язки систем (17) - (20), що враховують віддалення (або ухилення) від усієї множини обмежень:

,

де - норма вектора відхилу; - матриця коефіцієнтів для об'єднаної СРН (17) - (20).

При розв'язанні загальної задачі параметричної ідентифікації мультиплікативних моделей (2) для сформованих відношень , або отримаємо підсистеми нелінійних рівнянь і нерівностей (14) - (16). Для них можуть бути знайдені тільки наближені розв'язки. При заданих параметрах ФКЧК , (5) або (6) отримані СРН пропонується лінеаризувати шляхом логарифмування, що дозволить розв'язувати їх за допомогою методів ідентифікації адитивних ФУК.

Загальна задача параметричної ідентифікації змішаних адитивно-мультиплікативних моделей (3) - (4) належить до задач нелінійного математичного програмування. Для неї можуть бути знайдені тільки наближені розв'язки. При заданих значеннях параметрів ФКЧК (5) або (6) СРН задачі ідентифікації вагових коефіцієнтів для моделі на основі полінома Колмогорова-Габора (3) можуть бути приведені до адитивного вигляду. Позначимо: , , , , ... . З урахуванням цього, модель (3) прийме адитивну форму:

, (21)

де - вектор параметрів (вагових коефіцієнтів) моделі (3), поданої у вигляді (21); - кількість доданків у ФУК на основі полінома Колмогорова-Габора n-го ступеня; - кількість часткових критеріїв.

У задачі параметричної ідентифікації універсальної ФКЧК для ряду з значень i-го критерію , і заданих значень їх корисності необхідно визначити найкращі значення параметрів ФКЧК виду (6) .

Після нормування часткового критерію , за схемою (5) при отримаємо , .

Вибір найкращих значень параметрів ФКЧК може бути проведений за показниками мінімуму: суми квадратів відхилень; максимальної похибки; суми модулів похибок.

Якщо характер даних , , , свідчить про опуклість (увігнутість) ФКЧК, то з цього виходить, що = 0 і = 0 (або = 1 і =1). У цьому випадку задача зводиться до визначення значення тільки одного параметру або .

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

Суть першої із запропонованих модифікацій методу MN-1 полягає у зменшенні області пошуку параметрів на основі виявлених властивостей ФКЧК. ФКЧК завжди проходить між заданими точками (), або через них, тобто вона відхиляється від лінійної ФКЧК на кожному з відрізків , не більше, ніж функція, побудована для самої віддаленої точки відрізку , .

Для кожної точки відрізків , значення параметрів вибираються за умов:

;

;

;

,

а найкращі значення параметрів нелінійності знаходяться у діапазонах: : , і : ; , де - кількість точок, для яких (точки впорядковані за збільшенням критерію).

Точка перегину функції (6) не може бути віддалена від лінійної ФКЧК далі, ніж максимально віддалена точка вихідних даних , . З урахуванням цього, область раціональних значень її координат обмежується лініями, що проходять через максимально віддалені від лінійної ФКЧК точки.

У другій модифікації методу MN-2 за найкращі координати пропонується вибирати середні значення координат сусідніх точок і , (при и ), а у визначеній області знаходити тільки і .

Часова складність складає: базового методу сіток MN - (де - кількість значень, що апроксимуються, ; - відносний розмір кроку сітки); модифікації MN-1 - ; модифікації MN-2 - .

Задача ідентифікації вагових коефіцієнтів часткових критеріїв розглядалася у такій постановці. Задані: множина альтернатив , кожна з яких оцінюється за множиною часткових критеріїв , ; вигляд і параметри ФКЧК; вид ФУК; якісна корисність альтернатив у вигляді . Потрібно визначити найкращі значення коефіцієнтів , що задовольняють встановленій перевазі ОПР (7), (8) або (9).

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

Для вирішення цієї задачі були використані методи сіток MN, випадкового пошуку, генетичної селекції, а також запропонований метод на основі схеми оптимізації за парами координат MOPC. Суть його може бути подана наступним чином. Формується вихідне значення координат вектора, що задовольняє умові , . Для заданого значення кроку на площині виконується екстремізація за парами координат ; ; …; при фіксованих значеннях інших координат. Процедура повторюється до тих пір, поки послідовних спроб поліпшити значення критерію за парами координат , не стануть безуспішними. Для підвищення точності методу можуть бути використані зменшення кроку зміни координат і багатократні розв'язання задачі (модифікація MOPC-М).

Проведено експериментальне дослідження запропонованих методів. Завдання розв'язувалися на ПЕОМ з процесором 2 ГГц для і . Результати дослідження показують, що метод MOPC має поліноміальну часову складність та .

Суть запропонованих методів для вирішення загальної задачі параметричної ідентифікації МБФО полягає у реалізації схем екстремізації по парах координат MOPC, випадкового пошуку MRS, еволюційного пошуку MES з вибором на кожному кроці значень параметрів ФКЧК , модифікованим методом сіток.

4. Експериментальне дослідження розроблених методів шляхом розв'язання тестових задач

Експерименти проводились на ПЕОМ з процесором 2 ГГц.

Задача виділення підмножини ефективних альтернатив розв'язувалась для і запропонованим модифікованим методом парних порівнянь, що передбачає попереднє виділення наближеної області компромісів. Одержаний розв'язок збігається з розв'язком, одержаним базовим методом парних порівнянь. Час розв'язання склав: запропонованим методом - менше за 1 мс; методами Карліна і Гермейера для значень кроку - відповідно: 1.043 і 1.196 с.

Розв'язання задачі параметричної ідентифікація ФКЧК (6) проводилося для з використанням базового методу сіток MN, його модифікацій MN-1, MN-2 а також методу випадкового пошуку MRS. Час розв'язання методом MN (50 кроків по кожній координаті) склав 7.793 с. За той же час методом MRS було проаналізовано 5117698 варіантів, кращий з яких поступається розв'язку, отриманому методом сіток MN, за різними критеріями від 37.3 % до 89.5 %. Зменшення часу розв'язання методом MN-1 склало 68.8 %.

Задача ідентифікації вагових коефіцієнтів часткових критеріїв розв'язувалася для і методами випадкового пошуку MRS, оптимізації за парами координат МОРС і еволюційного пошуку MES. Всіма методами вдалося відновити вихідний порядок альтернатив . Кращим за комплексним показником "точність - час розв'язання" виявився модифікований метод оптимізації за парами координат MOPC-М.

При розв'язанні задачі структурно-параметричної ідентифікації МБФО вибір здійснювався для і між адитивною, мультиплікативною і змішаними ФУК (1) - (4). Усі моделі виявилися адекватними. Мінімальну складність виявила адитивна модель (1), максимальне значення критерію сили переваги отримано для моделі на основі полінома Колмогорова-Габора (3). Проте, вона значно перевершує всі інші моделі за складністю. Кращою за комплексним показником "точність - складність" виявилась адитивно-мультиплікативна модель (4). Вона поступилася моделі на основі полінома Колмогорова-Габора (3) за критерієм сили переваг на 2.78 %, проте потребує у 7.79 рази менше часу на розв'язання задачі ідентифікації.

Висновки

компараторний адитивний параметричний ідентифікація

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

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

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

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

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

5. Сформульовано постановку задачі і розроблено метод структурно-параметричної ідентифікації МБФО у класі адитивних, мультиплікативних і комбінованих адитивно-мультиплікативних ФУК. Це дозволяє підвищити точність (адекватність) МБФО і використовувати для вирішення практичних завдань моделі мінімальної складності.

6. Удосконалено у напрямі зниження часової складності метод формування підмножин ефективних варіантів для опуклої множини альтернатив на основі виділення наближеної області компромісів. Його практичне застосування дозволяє знижувати складність процедур ідентифікації МБФО і вибору рішень.

7. Показана можливість і доцільність використання отриманих результатів для розв'язання задач ідентифікації МБФО. Наведені результати розв'язання задач виділення підмножини ефективних альтернатив, параметричної ідентифікації ФКЧК, ідентифікації вагових коефіцієнтів часткових критеріїв, параметричної і структурно-параметричної ідентифікації МБФО. Застосування розроблених моделей і методів при розв'язанні контрольних задач дозволило зменшити час пошуку розв'язків на 61.2 - 68.8 % і (або) отримати варіанти з кращими на 18.9 - 25.8 % значеннями критеріїв.

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

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

Література

Бескоровайный В.В., Трофименко И.В. Структурный синтез территориально распределенных объектов в условиях неопределенности исходных данных // Вестник Херсонского государственного технического университета. - 2004. - № 1 (19). - С. 245 - 249.

Бескоровайный В.В., Трофименко И.В. Параметрическая идентификация аддитивно-мультипликативных моделей многофакторного оценивания // Радиоэлектроника и информатика. - 2005. - № 4. - С. 41 - 46.

Бескоровайный В.В., Трофименко И.В. Структурно-параметрична ідентифікація моделей багатофакторного оцінювання // Системи озброєння і військова техніка. - 2006. - № 3 (7). - С. 56 - 59.

Бескоровайный В.В., Петров Э.Г., Трофименко И.В. Метод решения общей задачи компараторной идентификации моделей многофакторного оценивания // Бионика интеллекта. - 2006. - № 2 (65). - С. 3 - 7.

Бескоровайный В.В., Трофименко И.В. Параметрическая идентификация мультипликативных моделей для многофакторного выбора решений // Збірник наукових праць Харківського університету повітряних сил. - Харків: ХУ ПС, 2005. - Вип. 5 (5). - С. 74 - 77.

Бескоровайный В.В., Трофименко И.В. Определение подмножеств эффективных вариантов в задачах многофакторного выбора решений // Автоматизированные системы управления и приборы автоматики. - 2005. - Вып. 132. - С. 4 - 11.

Бескоровайный В.В., Трофименко И.В. Параметрическая идентификация функции общей полезности для многофакторного оценивания и выбора решений // Збірник наукових праць Харківського університету повітряних сил. - Харків: ХУ ПС, 2006. - Вип. 6 (12). - С. 63 - 66.

Размещено на Allbest.ru