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

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

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

БАР Борис

УДК 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), (11)

ТО 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.

Рис. 3. Блок-схема алгоритму АЛУПР

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

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

Рис.4 Загальна архітектура ІПК “V-КВАНТ”

Автором розроблено програмне забезпечення ІПК, виконані експериментальна перевірка та практичне використання ІАКЗ-моделей прийняття рішень, що підтвердило правомірність і працездатність дисертаційних результатів. Зокрема, це проілюстровано при розв'язуванні спрощеної задачі інвестиційного менеджменту (ІМ) в який знаходять правила прийняття інвестиційних рішень за обчисленими показниками інвестиційних проектів: 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