Современные информационные технологии

2. Вычислительная техника и програмирование

Д.т.н. Гриша С.М., Гнатенко Н.С.

Національний Технічний Університет України «КПІ»

Ідентифікація функції корисності в типових задачах прийняття рішень

Запропоновано підхід до прийняття рішень в експерно-критеріальних задачах [1] на основі ідентифікації вирішувального правила у вигляді функції корисності в ході вирішення типових задач (підхід ПРІФК), що дозволяє підвищити ефективність роботи експертів шляхом переходу у деяких випадках від розв’язку слабоструктурованої задачі прийняття рішень (ЗПР) до розв’язку задачі оптимізації.

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

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

Рисунок. Схема реалізації підходу ПРІФК

По результатах аналізу ступеню визначеності експертам також може бути запропоновано вирішити спрощену ЗПР, що дозволить отримати необхідне прирощення інформації [2] про вигляд ФК.

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

На будь-якому етапі ідентифікації ФК СППР може бути переведена у режим активного навчання [3], коли ідентифікація ФК здійснюється в ході вирішення експертами типових ЗПР, або проведена перевірка отриманої ФК шляхом розв’язку експертами серії ЗПР з альтернативами з визначеної області ФК. Формування тестової вибірки також відбувається з урахуванням інформативності тестових ЗПР, але в сенсі можливості перевірки певних гіпотез про апроксимовану структуру переваг. Такий режим також дозволяє виявити протиріччя у перевагах експертів в контексті попереднього досвіду.

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

Підхід до ідентифікації ФК

Проблема ідентифікації функції корисності має ряд особливостей.

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

При цьому ФК апроксимує переваги ОПР, тобто де - відношення переваги, задане на множині векторів, що представляють альтернативні рішення. ФК можна побудувати лише у випадку, коли є зв'язним квазіпорядком [4].

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

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

З урахуванням розглянутих особливостей прийняття рішень на базі ФК і з метою забезпечення належної якості процесу прийняття рішень до методу ідентифікації функції корисності висуваються наступні вимоги:

1) в ході навчання необхідно ідентифікувати ФК максимально простого вигляду,

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

3) результуюча модель має враховувати тільки істотні фактори в мінімальній кількості;

4) у процесі ідентифікації мають бути усунені можливі протиріччя у вхідних даних;

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

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

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

Таким чином, запропоновано структуру підходу ПРІФК, що дозволяє здійснити ідентифікацію функції корисності у широкому спектрі випадків, та, виявлено доцільність використання для рішення задачі ідентифікації функції корисності алгоритмів МГОА.

ЛІТЕРАТУРА:

1. Емельянов С.В., Ларичев О.И. Многокритериальные методы принятия решений. - М.: Знание., 1985. – 32 c. – (Новое в жизни, науке и технике. Сер. «Математика, Кибернетика»; №10).

2. Рассел С., Норвиг П. Искусственный интеллект: современный подход: Пер. с англ. – М.: Издательский дом «Вильямс», 2006. – 1408 с.

3. Воронцов К.В. Комбинаторные обоснования обучаемых алгоритмов // ЖВМиМФ. — 2004. — Т.44, №11. — С. 2099–2112.

4. О. И. Ларичев. Теория и методы принятия решений, а также Хроника событий в Волшебных странах. –М.: Издательство «Логос», 2003. – 392 с.