Моделі, алгоритми і програми інженерії знань для прийняття рішень в умовах імовірнісних даних

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

Національний аерокосмічний університет

імені М.Є. Жуковського

“Харківський авіаційний інститут”

БАР Борис

УДК 519.816

МОДЕЛІ, АЛГОРИТМИ І ПРОГРАМИ ІНЖЕНЕРІЇ ЗНАНЬ ДЛЯ ПРИЙНЯТТЯ РІШЕНЬ В УМОВАХ ІМОВІРНІСНИХ ДАНИХ

01.05.04 - Системний аналіз і теорія оптимальних рішень

Автореферат

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

Харків 2000

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

Робота виконана в Національному аерокосмічному університеті імені

М.Є. Жуковського “Харківський авіаційний інститут” Міністерства освіти і науки України.

Науковий керівник - доктор технічних наук, професор, Сіроджа Ігор Борисович, Національний аерокосмічний університет імені М.Є. Жуковського “ХАІ”, завідувач кафедри Програмного забезпечення.

Офіційні опоненти:

- доктор технічних наук, професор Петров Едуард Георгійович, Харківський державний технічний університет радіоелектроніки, завідувач кафедри системотехніки;

- кандидат технічних наук Подоляка Оксана Олександрівна, Харківський державний автомобільно-дорожній технічний університет, доцент кафедри інформатики.

Провідна установа

Національний технічний університет України “КПІ”, кафедра Автоматизованих систем обробки інформації та управління, Міністерство освіти і науки України, м. Київ.

Захист відбудеться 26.01.2001 р. о 14 годині на засіданні спеціалізованої вченої ради Д 64.062.01 у Національному аерокосмічному університеті ім. М.Є. Жуковського “Харківський авіаційний інститут” за адресою: 61070, Харків-70, вул. Чкалова, 17.

З дисертацією можна ознайомитись у бібліотеці Національного аерокосмічного університету імені М.Є. Жуковського “ХАІ” за адресою 61070, Харків - 70, вул. Чкалова, 17.

Автореферат розісланий 22.12. 200 р.

Вчений секретар

спеціалізованої вченої ради Соколов Ю.М.

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

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

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

Суттєвий вклад в розвиток методів інженерії знань для прийняття рішень внесли зарубіжні та вітчизняні вчені. Наприклад, Е. Фейгенбаум, Е. Попов, Д. Поспєлов (продукційні моделі уявлення знань); М. Мінський, Ю. Нільсон (фреймові моделі); Ф. Уоссерман, Е. Гудман, Дж. Холланд, А. Івахненко (перцентрони, нейронні мережі, генетичні алгоритми); А. Тейз, П. Грибомон, А. Закрєвський (логічні та скінченно-предикатні моделі); В. Захаров, С. Ульянов (моделі fuzzy logic); І. Сіроджа (квантові моделі) та інші.

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

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

Зв'язок роботи з науковими програмами, планами і темами грунтується на виконанні автором дисертаційних досліджень в 1999-2000 р.р. на кафедрі програмного забезпечення Національного аерокосмічного університету імені М.Є. Жуковського “ХАІ” у межах державної науково-технічної програми №7 “Перспективні інформаційні технології, прилади комплексної автоматизації, системи зв'язку” ДКНТПП України (постанова Верховної Ради України від 16.10.1992 року 27-05-ХІІ про приоритетні напрямки розвитку науки і техніки) відповідно до плану науково-дослідних робіт з держбюджетної теми: Г603-41/2000 “Створення методології штучного інтелекту для ідентифікації та управління складними системами аерокосмічного призначення” (ДР №0198U002228).

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

1. Розвиток концептуальних і теоретичних основ синтезу ІАКЗ-моделей шляхом розробки класу математичних моделей уявлення та маніпулювання vk-знаннями для прийняття імовірних рішень в умовах введеної a-невизначеності.

1.1. Постановка і розв'язок задачі формалізації та синтезу vk-знань (Av-задачі) шляхом множинного, векторно-матричного і скінченно-предикатного представлення.

1.2. Визначення, обгрунтування і синтез формальних процедур та операторів машинного маніпулювання vk-знаннями.

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

2. Алгоритмізація навчання vk-знанням, автоматичного квантування і оптимізації прийняття рішень з допомогою v-КМВР.

2.1. Розробка та обгрунтування загальної методики алгоритмічного розв'язування базових задачі розпізнавання (ідентифікації) ситуацій (Bv-задачі) і прогнозування ситуацій (Cv-задачі) засобами vk-знань.

2.2. Алгоритмізація виводу ідентифікаційних та прогнозних рішень з допомогою v-КМВР шляхом використання оператора дедукції з точним обчисленням показників достовірності цільових заключень.

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

3.1. Розробка, реалізація і впровадження у виробництво інтелектуального інтерактивного програмного комплексу (ІПК) “V-КВАНТ” для підтримки прийняття імовірних рішень на базі примінення ПЕОМ.

3.2. Постановка, розв'язок і експериментальні дослідження з допомогою ІПК “V-КВАНТ” тестових та реальних виробничих задач оперативного планування і управління завданнями авіаційного виробництва та управління запасами в маркетингу при умовах a-невизначеності.

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

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

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

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

1. Визначено клас K(a) неструктуризованих задач прийняття рішень в умовах a-невизначеності, які характеризуються п'ятьма виділеними особливостями і розв'язуються ІАКЗ-методом за принципом логічного виводу імовірних vk-знань-висновків із відомих vk-знань-засновків (вперше одержано).

2. Теоретично обгрунтовано і розвинуто концепцію реалізації вказанного принципу шляхом моделювання причинно-наслідкових міркувань людини при пошуку висновків на основі застосування комп'ютерної моделі логічної мережі імовірних міркувань (ЛМІМ), що навчається експертами на ситуаційних прикладах і трансформується в оптимальну v-квантову мережу виводу рішень (v-КМВР) з точним обчисленням достовірності заключень (удосконалено).

3. Розроблено клас Mv векторно-матричних і скінченно-предикатних ІАКЗ-моделей уявлення та маніпулювання знаннями для виводу імовірих рішень з допомогою v-КМВР, що дало суттєве збільшення ефективності і швидкодії прийняття рішень (вперше одержано).

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

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

Практичне значення одержаних результатів полягає в доведенні автором теоретичних розробок до конкретних алгоритмів, інженерних методик прогнозування і розпізнавання виробничих ситуацій в умовах a-невизначеності, а також в розробці діючого ІПК “V-КВАНТ” на базі ПЕОМ. Ці засоби можна безпосередньо застосувати в проектних, науково-дослідних та промислових організаціях для автоматизації підтримки прийняття виробничих рішень. При цьому можна досягти збільшення ефективності застосування ПЕОМ в 4-5 разів за рахунок зниження працезатрат на усіх етапах прийняття рішень, а також підвищення їх якості в 2-4 рази. Розроблені в дисертації ВАКЗ-моделі, алгоритми та програмні модулі ІПК “V-КВАНТ” впроваджені в 2000р. на АНТК “АНТОНОВ” у планово-виробничому відділі (акт впровадження від 23 жовтня 2000р.) і у відділі автоматизованих систем управління (акт впровадження від 27 жовтня 2000р.), а також в учбовий процес Національного аерокосмічного університету ім. М.Є. Жуковського на кафедрі № 603 ПЗ факультету економіки і менеджменту (акт впровадження від 3 листопада 2000р.).

Особистий внесок здобувача. Всі результати дисертації отримані автором самостійно.

В роботі [2] автору належить концепція та системний синтез блоку підтримки прийняття рішень ВАКЗ-методом в електронній торгівлі через Internet; в [3] - метод експериментального дослідження ефективності прийняття знанняорієнтованих рішень на основі використання оцінок емпіричного ризику та методика і алгоритми їх визначення і аналізу. В роботі [4] автор розробив принципи та запропонував відповідну функціональну схему інтелектуальної інформаційної технології для прийняття рішень в електронній торгівлі через мережу Internet на основі використання ВАКЗ-моделей.

В роботах [5,6] автором розроблено моделі трансформації логічної мережі імовірних міркувань в v-квантову мережу виводу рішень з їх оптимізацією для синтезу інтелектуальних систем оперативного управління та побудови алгоритмів розпізнавання образів ВАКЗ-методом. Особисто в роботі [6] автор запропонував ідею навчання розпізнавальної системи на прикладах сценарних ситуацій, що описуються vk-знаннями, та розробив конкретний алгоритм її реалізації.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідались та обговорювались на: IV Міжнародній конференції “Проблеми створення і використання науково-технічної інформації на сучасному етапі”, м. Київ, УкрІНТЕІ, 1999 р.; Міжнародній конференції “АВТОМАТИКА-2000”, м. Львів, 2000р.; V Всеукраїнській міжнародній конференції “Оброблення сигналів і зображень та розпізнавання образів. УкрОБРАЗ-2000”, м. Київ, 2000р., а також на науково-технічних семінарах кафедри програмного забезпечення Національного аерокосмічного університету ім. М.Є. Жуковського “ХАІ” та кафедри автоматизованих систем обробки інформації та управління Національного технічного університету України “КПІ”.

Публікації: За темою дисертації з викладенням її основних результатів опубліковано 6 друкованих праць, з яких 3 статті у наукових фахових виданнях згідно з переліком ВАК України та три публікації в матеріалах і тезах наукових конференцій.

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

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

У першому розділі висвітлено стан проблеми прийняття рішень в умовах невизначеності та її загальну постановку на основі огляду і порівняльного аналізу публікацій. Задачу Z знанняорієнтованого прийняття рішень формально поставимо так: Z=(Q, U, L, Ф), де Q - множина імовірних ситуацій на множині результатів спостережень X={X1,X1,...,Xn}, , j=1,n; U={u} - множина допустимих рішень u=u(x), xОX L:QґU®R - обмежена дійсна функція втрат L(q, u), qОQ; Ф - множина закономірностей на Q при відповідних умовах a-невизначеності. Множини X,U і Ф представлені формалізмами запропонованих моделей vk-знань. Застосовуючи відповідно визначений функціонал F, одержуємо функцію ризику R(u)=FL(q,u). Необхідно знайти оптимальне рішення u*ОU, що мінімізує ризик при відомих закономірностях Ф. Множина Ф в дисертації належить до класу функціональних логічних закономірностей, що підлягають визначенню в режимі навчання за результатами спостережень та прикладами сценарних ситуацій-знань експертів відповідно конкретної предметної галузі з урахуванням умов неповноти даних і a-невизначеності. Ці умови, як було вказано раніше, пов'язані з малими об'ємами вибіркових навчаючих знань та їх імовірнісним характером. При цьому показано можливість і доцільність розробки в рамках штучного інтелекту знанняорієнтованих систем прийняття рішень (ЗСПР) в умовах a-невизначеності для виділеного класу K(a) об'єктів прийняття рішень (ОПР), які можна описати скінченим набором характеристик (ознак), виміряних в кількісних та якісних шкалах. Встановлено недостатню ефективність існуючих методів і моделей уявлення знань і маніпулювання ними, а також відсутність українських розробок ЗСПР виробничого призначення та недоцільність використання складних і дорогих закордонних експертних систем. Посилаючись на такі висновки, визначено мету дисертаційної роботи і сформульовано завдання досліджень. Вони полягають в розробці математичних моделей різнорівневих імовірних алгоритмічних квантів знань (ІАКЗ-моделей) алгоритмів маніпулювання ними за допомогою ПЕОМ та створенню простого і недорогого інтерактивного програмного комплексу (ІПК) “V-КВАНТ” для підтримки прийняття виробничих рішень в умовах a-невизначеності.

Обгрунтована концепція знанняорієнтованого прийняття імовірних рішень на базі використання запропонованої v-квантової мережі виводу рішень (v-КМВР) як бази знань (БvkЗ) і одночасно механізму виводу vk-знань-наслідків із vk-знань-засновків.

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

(Av-задача); ідентифікація (розпізнавання) ситуацій (Bv-задача) і прогнозування ситуацій

(Cv-задача) в умовах a-невизначеності.

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

, (1)

де Sv - символьна мова v-квантів знань, що є скінченною множиною букв, цифр та символів операцій теорії алгоритмів; Kv - скінченна множина термінальних v-квантів знань, що задана априорі; - імовірна множина, яка породжує значення деякої функції pv(·) достовірності подій, що описуються різнорівневими v-квантами, тобто множина показників достовірності (ПД) vk-знань в інтервалі [0, 1]; Пv - правила побудови різнорівневих vk-знань; Qv - множина семантичних кодів і спеціальних структур даних, що визначають рівень та зміст v-квантових структур знань.

Таким чином, для Av-задачі створено формальний механізм побудови класу Mv різнорівневих vk-знань на мові Sv з ПД із відповідного Qv рівня та змісту на основі застосування правил побудови з Пv до термінальних v-квантів множини Kv.

Визначення 1. Імовірною множиною на універсальній множині U={u} називається сукупність пар виду

, (2)

оператор машинний маніпулювання розпізнавання

де pv(u):U®[0,1] є функція достовірності імовірної множини , а значення p(u) для конкретного uОU називається ПД величини u. Проміжні значення ПД на відрізку [0, 1] відображають ступінь довіри чи недовіри до відповідних знань.

Нехай об'єкти прийняття рішень wОW мають скінченну множину різнотипових ознак x1,x2,...,xn (в тому числі і цільових), які приймають значення із скінченних імовірних множин:

(3)

де - показник достовірності (ПД) i-го значення j-ї ознаки xj Кожній із множин Xj поставимо у відповідність одновимірні числові масиви (домени) [d1 : d2 : ... : dn ], що розділяються символом “:” з відповідними компонентами доменів . Інформацію про ОПР w будемо уявляти змістовно (з семантикою) структурованою у вигляді імовірних часток-квантів знань (vk-знань) різних рівнів з визначеними чи не відомими ПД p(·). Нехай число змістовно відповідає знанням 0-го рівня, функція чи вектор - знанням 1-го рівня, а функціональна структура чи матриця - знанням 2-го рівня і т.д. з довільним ускладненням, шо непринципово. Тоді деякі ОПР wОW, що характеризуються ознаками зі значеннями з імовірних множин (3), можна описати v-квантовими конструкціями виду

(4)

де код vk1ОQv, ім'я yОSv, .

Вираз (4) назвемо термінальним векторним v-квантом знань 1-го рівня з семантикою : “ОПР w характеризується n різнотиповими ознаками xj, (j=1,n), значення яких з відповідними ПД ”

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

(5)

де , з семантикою: “Із - вимірної сукупності імовірнісних значень ознак вибрати значеня ak з ПД p(ak)О[0,1]”.

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

(6)

де - зафіксована множина імовірнісних значень ознак, з семантикою: “зафіксоване значення j-ї ознаки ОПР в данний момент спостережень враховується з ПД , якщо значення характеристичної функції ; при значення не враховується”. Множину Kv сформуємо на основі термінальних vk-знань (4), (5) і (6):

(7)

До складу множини Пv правил побудови різнорівневих vk-знань включимо відомі в теорії алгоритмів оператор суперпозиції (П-оператор), оператор рядкової конкатенації (CON<·>- оператор), оператор стовбцевої конкатенації (CON[·]-оператор) та алгоритми точного обчислення ПД (ТОПД) v-квантових заключень.

Визначення 2. Алгоритмічні структури, побудовані з термінальних v-квантів множини Kv (7) шляхом скінченого числа застосувань П-оператора, CON<·> - оператора і CON[·] - оператора при наявності алгоритмів ТОПД v-квантових заключень і правил Пv (1), називаються різнорівневими імовірними квантами знань (vk-знання) що утворюють клас Мv ІАКЗ-моделей уявлення імовірних знань. При повністю достовірних знаннях узагальнений клас Мv вироджується в клас Мt точних БАКЗ-моделей, запропонованих професором Сіроджа І.Б.

На відміну від існуючих моделей знань (продукції, фрейми, та ін.) клас Мv ІАКЗ-моделей забезпечує множинне, векторно-матричне та аналітичне (предикатне) представлення імовірних ситуацій, фактів і закономірностей в скінченному імовірному просторі v-квантових моделей:

, (8)

де , - число компонентів j-го домена.

В загальному випадку v-квант з ім'ям Y описує стан ОПР як закономірність або факт і містить логічну комбінацію засновків з ПД відносно значень ознак, від яких залежить обчислюваний вихідний ПД висновку відносно цільової ознаки xц. При цьому символ “,”, що разділяє компоненти в домені, виконує роль диз'юнкції (АБО), а символ “:”, що розділяє самі домени, - роль кон'юнкції (I). Наприклад, гіпотетичний факт з деякої предметної галузі, описаний інтервальним v-квантом 1-го рівня у просторі (8) з ім'ям Y:

(9)

має таку семантику: “ЯКЩО ОПР характеризується 2-м значенням з ПД АБО 4-м значенням з ПД ознаки x1, якій відповідає імовірна множина І 1-м значенням з ПД АБО 2-м значенням з ПД ознаки x2 з відповідної множини , ТО 1-ше значення цільової ознаки x3= xц з ПД з відповідної множин визначає умовну подію-наслідок (®Y); інформація про ознаку x4 неоднозначна, бо спостерігаються 1-е АБО 2-е її значення з двох можливих у відповідній множини ; заключний ПД p(Y) v-квантової події Y обчислюється з допомогою вбудованого в v-квант алгоритму A(Y) і урахуванням умовної імовірності p(®Y), про що свідчить вихідний домен”. ІАКЗ-моделі vk1 (9) відповідає інтервал I простору (8), який можна описати аналітично предикатом у вигляді кон'юнкта , що складається з імовірних виразів виду з семантикою: “ознака xj ОПР приймає значення з імовірної підмножини імовірної множини ”. Виходячи з цього ІАКЗ-модель vk1Y (9) описаного факту можна подати в наступній аналітичній формі предикатного рівняння:

(10)

Аналогічно виразам (9) і (10) з ускладненнями у вигляді матричних структур описують v-кванти 2-го рівня. В роботі показана алгоритмічна достатність vk-знань 0-го, 1-го та 2-го рівнів для розв'язування усіх практично існуючих базових Bv-, Cv-задач прийняття рішень на основі використання v-КМВР як БvkЗ у формі системи функціональних закономірностей. Логічну мережу імовірних міркувань (ЛМІМ) знаходять за розробленою методикою в режимі навчання за сценарними прикладами обучаючих знань (СПОЗ) і трансформують в v-КМВР.

Визначення 3. Обученою ЛМІМ називається орієнтований граф G=(E,Г), що побудований за відомими від експертів СПОЗ з використанням алгоритму АЛОБУЧ, має порядкову функцію П(Xi)"XiОE, яка визначена на підмножинах-рівнях N1,N2,…,Nk М E вершин, і що має такі властивості:

1) усі вершини (вузли мережі) XiОE, (1Ј i Ј n) відповідають висловленням із СПОЗ конкретної предметної галузі, а дуги із Г:Е®E вказують на причинно-наслідкові зв'язки між вузлами з логічними зв'язками “І”, “АБО”, “НІ”;

2) всі вузли XiОN1МE при Г-1=Ж відповідають вхідній інформації засновків ei,(1Ј i Ј nп) відносно деяких висновків cj,(Ј j Ј mB) з відомими ПД p(ei) і p(®cj);

3) всі вузли XsОNkМE при ГNk=Ж є цільовими (вихідними) вузлами-заключеннями

Cs,(1Ј s Ј S) з обчислюваними ПД p(Cs), а всі вершини проміжних рівнів між N1 і Nk відповідають частковим висновкам cj.

Формально СПОЗ описуються як фрагменти сценарію прийняття рішень у вигляді висловлювань продукційного типу:

ЯКЩО (логічна комбінація засновків ei з відповідними ПД p(ei) та p(®Cj), ТО Cj (висновок) з ПД p(Cj)=?,

що задаються пронумерованими пропозиціональними формулами в базисі {Щ, Ъ, щ ®} і називаються продукційними рядками СПОЗ.

Символ “?” вказує на необхідність обчислення ПД висновку C1, тобто p(C1) за відомими імовірнісними даними.

Далі розроблена методика синтезу обучаємої v-КМВР, яка визначається формально як результат трансформації ЛМІМ з допомогою послідовної дії запропонованих алгоритмів автоматичного квантування (АЛАКВА) та оптимізації v-КМВР (АЛОПТ) за критерієм позбавлення надмірності.

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

Особливістю моделі v-КМВР є здатність її до перенавчання та донавчання за новими СПОЗ, а також точне обчислення імовірностей v-квантових подій шляхом ортогоналізації диз'юнктивної нормальної форми (ДНФ) логіки висловлювань в мережі. Оскільки ортогональна ДНФ (ОДНФ) містить лише всі попарно ортогональні елементарні кон'юнкції (тобто незалежні події), то вказані обчислення за доведеною теоремою виконуються шляхом підстановки замість змінних ОДНФ, що є іменами v-квантів, відповідних відомих імовірностей з заміною логічних операцій “Щ” і “Ъ” на арифметичні “ґ” і “+”.

У третьому розділі на основі використання викладеної в 2-му розділі теорії ІАКЗ-моделей здійснено алгоритмізацію машинного навчання vk-знанням, автоматичного квантування та оптимізації прийняття рішень за допомогою v-КМВР. Вперше поставлена і розв'язана задача комплексної алгоритмізації засобами ІАКЗ-методу запропонованої моделі v-КМВР і причинно-наслідкових міркувань і прийняття рішень людиною. Для цього розроблено загальну методику алгоритмізації розв'язування базових Bv-задачі (ідентифікація ситуацій) і Cv-задачі (прогнозування ситуацій), а також синтезовано комплекс оригінальних функціонально пов'язаних алгоритмів: машинного навчання vk-знанням (АЛОБУЧ), автоматичного квантування інформації (АЛАКВА), оптимізації (АЛОПТ) і управління (АЛУПР) v-КМВР, а також алгоритмів дедуктивного виводу ідентифікаційних та прогнозних рішень і обчислення їх показників достовірності. Формально загальна методика алгоритмізації зводиться до реалізації індуктивного оператора (IND-оператора) та дедуктивного (DED-оператора) виводу vk-знань. Нехай при розв'язуванні Bv-задачі використані ідентифікаційні СПОЗ (Bv) і в результаті навчання одержана відповідна v-КМВР як функціональна БvkЗ(Bv) для розпізновання ситуацій в умовах a-невизначеності алгоритмічними засобами IND-оператора:

(12)

Тоді алгоритмічний розв'язок Bv-задачі полягає в знаходженні ідентифікаційних цільових vk-знань vksRBw засобами DED-оператора:

 (13)

Аналогічно на основі використання прогнозних СПОЗ (Cv) в результаті навчання шляхом IND-оператора отримується відповідна БvkЗ(Cv) і розв'язується Cv -задача знаходження прогнозних цільових vk-знань vksRCw алгоритмічними засобами DED-оператора:

.(14)

У виразах (13) і (14) використано відповідні результати (vk-знання) спостережень vk1YBw і vk1YCw та алгоритми розпізнавання АЛ(Bv) і прогнозування АЛ(Cv), що виконуються під управлінням алгоритму АЛУПР.

Алгоритм АЛОБУЧ забезпечує автоматичну побудову ЛМІМ в діалоговому режимі навчання з допомогою експертів на СПОЗ. На рис. 1 показана блок-схема загального алгоритму трансформації ЛМІМ в v-КМВР за допомогою алгоритмів АЛАКВА і АЛОПТ. Оптимізація v-КМВР здійснена алгоритмом АЛОПТ (див. рис. 2) за критерієм позбавлення надмірності за згорткою v-квантів та наслідком, що пов'язані з надлишковими vk-знаннями в мережі.

Функціонування та управління v-КМВР в режимах R1 (штатний), R2 (донавчання), R3 (перенавчання) і R4 (так тримати) здійснюється з допомогою алгоритму АЛУПР, блок-схема якого подана на рис. 3.

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

У четвертому розділі викладено прикладну частину дисертаційних досліджень на основі розробки інтерактивного програмного комплексу (ІПК) “V-КВАНТ”, а також результати його використання для розв'язування практичних Bv-задачі (ідентифікації) та Cv-задачі (прогнозування) як базових задач прийняття знанняорієнтованих рішень при імовірних данних. На рис. 4 показана загальна архітектура ІПК “V-КВАНТ”, створеного засобами об'єктно-орієнтованого середовища Borland Pascal 7.0 і Delphi 3.0. з використанням ПЕОМ.

Автором розроблено програмне забезпечення ІПК, виконані експериментальна перевірка та практичне використання ІАКЗ-моделей прийняття рішень, що підтвердило правомірність і працездатність дисертаційних результатів. Зокрема, це проілюстровано при розв'язуванні спрощеної задачі інвестиційного менеджменту (ІМ) в який знаходять правила прийняття інвестиційних рішень за обчисленими показниками інвестиційних проектів: e1 - чистий грошовий потік; e2 - період окупності інвестицій; e3 - чиста вартість; e4 - норма прибутку; e5 - індекс прибутковості; e6 - оцінка чутливості. Цільові заключення C5 - (клас1-“прийняти проект”) і C6 - (“клас2-відхилити проект”) приймаються в залежності від обчислених ПД p(C5) і p(C6). На рис. 5 наведені продукційні рядки СПОЗ(ІМ), що спричинили в результаті навчання побудову ЛМІМ, яка показана на рис. 6.

1.

2.

3.

4.

5.

6.

Рис. 5. Продукційні рядки СПОЗ (“Ж” є “?”)

В результаті трансформації ЛМІМ (рис. 6) з допомогою АЛАКВА і АЛОПТ одержано оптимальну v-КМВР(ІМ) (див. рис. 7), яка задає найдену БvkЗ(ІМ) і водночас правило прийняття інвестиційних рішень, описане системою vk-знань (див. рис. 8).

Обчислені р(С5)=0.81 з рівнем ризику 19% і р(С6)=0.62 (ризик 38%) свідчать про те, що при допустимому рівні ризику 0.80 інвестиційний проект слід прийняти в даному випадку.

Поставлені і розв'язані з використанням ІПК ”V-КВАНТ” реальні задачі прийняття рішень у сфері оперативного планування і управління авіаційним виробництвом при невизначеності термінів операцій і розподілу ресурсів, а також при управлінні запасами в бізнесі при невизначеності терміну поставок та попиту. Одержані результати експериментального оцінювання розв'язків показали високу адекватність, та ефективність ВАКЗ-методу прийняття рішень.

ВИСНОВКИ

У дисертації наведено теоретичне узагальнення і нове вирішення наукової задачі, що виявляється в розробці математичних моделей, алгоритмів і програмних засобів інженерії знань для прийняття рішень в умовах імовірнісних даних. Задача розв'язана засобами коректно побудованого класу Mv моделей імовірних алгоритмічних квантів знань (ІАКЗ-моделей) з використанням ПЕОМ і синтезованої v-квантової мережі виводу імовірних рішень, що навчається за сценарними прикладами ситуацій конкретної предметної галузі. Отримані результати можуть бути використані для якісного і ефективного розв'язування неструктуризованих задач прийняття знанняорієнтованих рішень в індустріальному, соціально-економічному і екологічному моніторингу; в інвестиційному менеджменті, управлінні ризиками, бізнес-процесами і промисловими об'єктами, а також в криміналістиці і військовій справі при умовах означеної a-невизначеності.

Головні наукові і практичні результати роботи полягають в наступному.

1. Виділено клас мало досліджених об'єктів прийняття рішень в умовах a-невизначеності, яка зумовлена імовірнісним характером і неповнотою інформації, та змістовно сформульовані відповідні базові задачі: формалізація v-квантів знань (Av-задача), знанняорієнтоване прийняття ідентифікаційних рішень (Bv-задача) і прогнозних рішень (Cv-задача) методом імовірних алгоритмічних квантів знань (ІАКЗ-метод).

2. Вперше поставлена і розв'язана базова Av-задача формалізації та синтезу vk-знань як ІАКЗ-моделей в аксіоматично визначеному класі Mv алгоритмічних структур, які на відміну від існуючих моделей знань забезпечують множинне, векторно-матричне і аналітичне скінченно-предикатне уявлення фактів, ситуацій і функціональних закономірностей та машинне маніпулювання ними для прийняття рішень.

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

4. Розроблена загальна методика синтезу графової моделі v-КМВР має особливу здатність до навчання за сценарними прикладами ситуацій з відтворенням не тільки параметрів

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

5. На основі розвинутої в роботі теорії ІАКЗ-моделей розроблена загальна методика алгоритмічного розв'язування базових Bv-задачі (ідентифікація) і Cv-задачі (прогнозування) прийняття рішень в умовах -невизначеності, на базі комп'ютерного застосування векторно-матричних IND- і DED операторів виводу імовірних рішень як vk-знань, що реалізовані з допомогою синтезованих оригінальних алгоритмів навчання v-КМВР, автоматичного квантування інформації і оптимізації мережі, обчислення ПД її v-квантів та упрвавління режимами її функціонування.

6. Засобами об'єктно-орієнтованого середовища Borland Pascal 7.0 і Delphi 5.0 створено і впроваджено в навчальний процес ХАІ та у авіаційне виробництво на АНТК “АНТОНОВ” (м. Київ) інтерактивний програмний комплекс (ІПК) “V-КВАНТ” на базі використання ПЕОМ середньої потужності. Застосовуючи ІПК “V-КВАНТ”, експериментально доведено вірогідність та ефективність дисертаційних розробок і висновків, про що свідчать успішні розв'язки багатьох тестових та реальних задач прийняття рішень при:

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

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

7. Розроблене програмне забезпечення ІПК “V-КВАНТ” складає ядро нової інформаційної технології інженерії знань, що на відміну від застосування відомих нейромереж, базується на використанні логічної мережі імовірних міркувань (ЛМІМ), яка навчається за сценарними прикладами ситуацій і трансформується в v-квантову мережу виводу рішень

(v-КМВР) із заздалегідь невідомою структурою.

8. Результати експериментального порівняння ІАКЗ-моделей з найбільш відомими засобами інженерії знань показали високу адекватність, ефективність та переваги ІАКЗ-методу прийняття рішень, що полягають в зменшенні середнього ризику на порядок, збільшенні швидкодії процесу навчання в 2,5 рази та скороченні об'єму пам'яті БvkЗ у 1,5 рази.

9. Створені ІАКЗ-моделі, алгоритми, інженерні методики і програми можуть бути використані в науково-дослідних, проектно-конструкторських, навчальних і промислових організаціях для автоматизації прийняття рішень при імовірнісних і неповних даних.

СПИСОК ОПУБЛІКОВАНИХ АВТОРОМ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Сироджа И.Б., Бар Б. Система поддержки принятия решений в электронной торговле через Интернет // Вестник ХГПУ. - 2000. -Вып.94. -С.71-76.

2. Бар Б. Моделювання і синтез інтелектуальної v-квантової мережі прийняття рішень в інженерії нечітких знань // Вісник Державного університету “Львівська політехніка” Комп'ютерна інженерія та інформаційні технології. - 2000. -№.392. -С.60-64.

3. Сироджа И.И., Бар Б. Экспериментальное оценивание адекватности и эффективности принятия знаниеориентированных решений методом вероятных квантов знаний // Радиоэлектроника и информатика. - 2000. -№.3. -С.39-44.

4. Сироджа И.Б., Сироджа И.И., Бар Б. Модели и формальные процедуры машинного манипулирования вероятными квантами знаний // Проблемы бионики. - Харьков, 2000. -№.52. -С.36-42.

5. Сироджа И.Б., Бар Б., Голобродский О.Ю. Интеллектуальная информационная технология принятия решений для электронной торговли в сети INTERNET // Тези доповідей та повідомлень ІV Міжнародної конф. “Проблеми створення, інтеграції і використання науково-технічної інформації на сучасному етапі”. - Киев: УкрІНТЕІ.-1999. -С.34-37.

6. Сироджа И.Б., Бар Б., Сироджа И.И. Принятие решений методом вероятных алгоритмических квантов знаний в интеллектуальных системах управления // Праці міжнародної конференції “АВТОМАТИКА-2000”, - Львів, -2000. -т.1. -С.18-25.

7. Sirodzha I.B., Bar B., Sirodzha I.I. Pattern recognition by method of probable algorithm quantums of knowledge (PAQK-method) // The fifth All-Ukrainian International Conference “UkrOBRAZ'2000”, - Київ, -2000. -P.18-25.

АНОТАЦІЯ

Бар Борис. Моделі, алгоритми і програми інженерії знань для прийняття рішнь в умовах імовірнісних даних. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.0.5.04 - Системний аналіз і теорія оптимальних рішень. - Національний аерокосмічний університет імені М.Є. Жуковського “ХАІ”, Харків, 2000.

Запропонована нова системна алгоритмічна формалізація моделей знань в рамках методу імовірних алгоритмічних квантів знань (ІАКЗ-метод) прийняття рішень в умовах -невизначеності, пов'язаної з неповними різнотипними та імовірнісними даними. Розроблені ІАКЗ-моделі забезпечують єдине уявлення та алгоритмічне маніпулювання числовою і лінгвістичною інформацією у вигляді різнорівневих за складністю структур імовірних квантів знань (vk-знань) засобами скінченних предикатів і векторно-матричних операторів. На відміну від існуючих засобів інженерії знань ІАКЗ-моделі дозволяють будувати автоматично в режимі навчання на зразках сценарних ситуацій логічну мережу імовірних міркувань (ЛМІМ), яка трансформується у v-квантову мережу виводу рішень (v-КМВР) з точним обчисленням достовірності висновків шляхом ортогональних перетворень функцій алгебри логіки. На базі використання ІАКЗ-моделей сворено інтерактивний програмний комплекс (ІПК) “V-КВАНТ” для автоматизації підтримки прийняття виробничих рішень на базі використання ПЕОМ, який відрізняється прийнятною вартістю та достатньо високим ступенем “інтелектуальності” за рахунок можливості дообучатися і переобучатися за допомогою експертів і за інформацією спостережень.

На основі використання ІПК “V-КВАНТ” розв'язано низку задач прийняття виробничих рішень, зокрема в оперативному плануванні та управлінні авіаційним виробництвом, а також в управлінні запасами в бізнесі.

Ключові слова: імовірні алгоритмічні кванти знань, vk-знання, база імовірних квантів знань, знанняорієнтоване прийняття рішень, v-квантова мережа виводу рішень (v-КМВР).

АННОТАЦИЯ

Бар Борис. Модели, алгоритмы и программы инженерии знаний для принятия решений в условиях вероятностных данных. - Рукопись.

Диссертация на соискание учёной степени кандидата технических наук по специальности 01.05.04 - Системный анализ и теория оптимальных решений. - Национальный аэрокосмический университет им. Н.Е. Жуковского “ХАИ”, Харьков, 2000.

Предложена новая системная алгоритмическая формализация моделей знаний и усовершенствован метод вероятных алгоритмических квантов знаний (ВАКЗ-метод) принятия решений в условиях -неопределённости, связанной с неполными, разнотипными и вероятностными данными. Усовершенствованные ВАКЗ-модели обеспечивают единое представление и алгоритмическое манипулирование числовой и лингвистической информацией в виде разноуровневых по сложности структур вероятных квантов знаний (vk-знаний) средствами конечных предикатов и векторно-матричных операторов. В отличие от существующих средств инженерии знаний ВАКЗ-модели позволяют автоматически строить в режиме обучения на примерах сценарных ситуаций логическую сеть вероятных рассуждений (ЛСВР), которая трансформируется в v-квантовую сеть вывода решений (v-КСВР) как vk-знаний-следствий из vk-знаний-посылок. Процесс логического вывода vk-знаний сопровождается точными вычислениями достоверности следствий путём ортогональных преобразований функций алгебры логики. Построенная в результате обучения v-КСВР одновременно выполняет роль базы vk-знаний (БvkЗ) из конкретной предметной области и задаёт механизм вывода искомых решений с вычислением их показателей достоверности по наблюдаемым данным и логике рассуждений.

Впервые поставлены и решены три базовые задачи а рамках ВАКЗ-метода принятия решений: формализация ВАКЗ-моделей в определенном классе Mv (Av-задача); идентификация вероятных ситуаций (-задача) и прогнозирование вероятных ситуаций (Cv-задача). В Av-задаче строго определены и обоснованы множественное, векторно-матричное и аналитическое (конечно-предикатное) представления vk-знаний в классе Mv ВАКЗ-моделей 0-го, 1-го и 2-го уровней.

Предложены и обоснованы модели и формальные процедуры машинного манипулирования vk-знаниями. Разработаны методики синтеза модели v-КСВР, обучаемой на сценарных примерах и оптимизируемой по избыточности, а также вычисления вероятностных оценок принятия решений посредством vk-знаний.

Созданы методы алгоритмизации обучения vk-знаниям, автоматического квантования и оптимизации принятия вероятных решений посредством v-КСВР в Bv- и Cv-задачах. Синтезированы и обоснованы соответствующие алгоритмы, а также алгоритм управления режимами функционирования v-КСВР.

Разработано программное обеспечение синтеза ВАКЗ-моделей, проведена экспериментальная проверка и выполнено практическое использование ВАКЗ-моделей принятия решений.

На основе использования ВАКЗ-моделей создан интерактивный программный комплекс (ИПК) “V-КВАНТ” для автоматизации поддержки принятия производственных решений на базе использования ПЭВМ, который отличается приемлемой стоимостью и достаточно высокой степенью “интеллектуальности” за счет возможности дообучаться и переобучаться с помощью экспертов либо без них по информации наблюдений.

На базе использования ИПК “V-КВАНТ” решен ряд задач принятия производственных решений, в частности в оперативном планировании и управлении авиационным производством, а также в управлении запасами в бизнесе.

Базовые модули программного обеспечения ИПК внедрены на АНТК “АНТОНОВ” г. Киев. ИПК “v-КВАНТ” может быть использован в промышленных научно-исследовательских и проектно-конструкторских организациях для автоматизации принятия решений в условиях нечетких и вероятностных данных.

Ключевые слова: вероятностные алгоритмические кванты знаний, vk-знания, знаниеориентированное принятие решений, v-квантовая сеть вывода решений (v-КСВР).

ABSTRACT

Bar Boris. Models, algorithms and programs of knowledge engineering for decision making in probabilistic data conditions - Manuscript.

Dissertation for a degree of Candidate of Technical Sciences in specialization field 01.05.04 - System analysis and theory of optimal decisions. - National Aerospace University named after N.E. Zhukovsky “KhAI”, Kharkov, 2000.

New system algorithm formalization of knowledge models was offered and method of probable algorithmical knowledge quanta (PAQK-method) for a decision making under -uncertain conditions, connected with lack of data, variety of types and probable data was improved. In the difference from existed means of knowledge engineering PAQK-models let automatically to build in the mode of teaching on examples of scenario situations the logical net of probable reasoning (LNPR), that is transformed to v-quantum net of decision's output (v-QNDO) as vk-knowledge-consequences from vk-knowledge-precedents.

The process of logical output of vk-knowledge is accompanied by exact calculation of consequences' reliability by means of orthogonal transformations of functions of logical algebra.

On the base of using PAQK-models interactive program complex (IPC) “V-KVANT” was created for industrial decision support based on PC usage. The method differs from others by acceptable price and high level of “intellectual abilities”, i.e. by capability of teaching and re-teaching with the help of experts or without them using information about known facts.

Key words: probabilistic algorithms, knowledge quanta, vk-knowledge, knowledge-oriented decision making, v-quantum net of decision conclusion drawing.

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

...