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

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ АЕРОКОСМІЧНИЙ УНІВЕРСИТЕТ

ІМ. М.Є. ЖУКОВСЬКОГО

"ХАРКІВСЬКИЙ АВІАЦІЙНИЙ ІНСТИТУТ"

УДК 004.891:378.145

Автореферат

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

кандидата технічних наук

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

05.13.06 - автоматизовані системи управління та прогресивні інформаційні технології

РОЗСОХА СЕРГІЙ ВОЛОДИМИРОВИЧ

Харків - 2007

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

Роботу виконано у Національному аерокосмічному університеті ім. М.Є. Жуковського "Харківський авіаційний інститут", Міністерство освіти і науки України.

Науковий керівник:

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

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

Безкоровайний Володимир Валентинович, доктор технічних наук, професор, Харківський національний університет радіоелектроніки; професор кафедри системотехніки;

Чухрай Андрій Григорович, кандидат технічних наук, Національний аерокосмічний університет ім. М.Є. Жуковського "Харківський авіаційний інститут", доцент кафедри систем управління літальних апаратів.

Провідна установа: Національний технічний університет "Харківський політехнічний інститут", кафедра системного аналізу і управління, Міністерство освіти і науки України, м. Харків.

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

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

Автореферат розісланий "27" лютого 2007 р.

Вчений секретар спеціалізованої вченої ради М.О. Латкін.

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

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

Сучасна автоматизація складання розкладів базується в основному на використанні класичних методів, що спираються на точні математичні моделі з неявним використанням знань. Між тим дуже важко побудувати таку математичну модель, яка б враховувала лінгвістичний і нечіткий характер даних, обмежень, вимог і побажань. Будь-які спроби спрощення математичної моделі призводять до отримання неадекватного результату. Таким чином, вирішення задачі автоматизації складання розкладів занять за допомогою існуючих засобів виявляється неможливим внаслідок її неструктурованості, великої розмірності та NP-складності, наявності нечітких кількісних і якісних даних та необхідності явно використовувати знання експертів про особливості конкретного ВНЗ. Надалі такі умови обмежень в задачі будемо скорочено називати ц_невизначеністю.

Саме диспетчер ВНЗ здатний ефективно вирішити задачу складання розкладу за умов ц_невизначеності, завдяки своїм знанням і досвіду, але йому необхідна автоматизація як рутинної, так і творчої праці. Тому актуальності набуває розробка нових моделей, методів та інтелектуальних інформаційних технологій підтримки знання орієнтованого прийняття диспетчерських рішень у ВНЗ.

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

У дисертації автор розвиває РАКЗ-метод, створюючи цРАКЗ-метод прийняття рішень за умов ц_невизначеності з використанням заздалегідь синтезованої бази нечітких квантів знань (БцkЗ) як системи імплікативних і функціональних закономірностей відносно предметної галузі.

Зв`язок роботи з науковими програмами, планами, темами ґрунтується на проведенні автором дисертаційних досліджень у 2003-2006 роках відповідно до плану науково-дослідних робіт за держбюджетними темами "Теорія створення квантових систем штучного інтелекту для прийняття технологічних рішень у виробництві аерокосмічної техніки" (ДР № 0103U004081) і "Методологія створення інтегрованих інформаційних технологій знанняорієнтованої підтримки рішень при виробництві аерокосмічної техніки" (ДР №0106U001039), а також згідно з договором між "ХАІ" та НВП "ХАРТРОН-Плант" Лтд про науково-технічну співпрацю. У межах цих тем і договору дисертант розробляв цРАКЗ-моделі, методи та програмні засоби для дедуктивного виводу диспетчерських і технологічних рішень за умов лінгвістичної невизначеності, тобто ц_невизначеності.

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

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

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

3. Розробити методику дедуктивного виводу рішень як цk-знань для комп'ютерної підтримки диспетчерських рішень при складанні розкладів занять, спираючись на заздалегідь синтезовану БцkЗ.

4. Розробити алгоритми, які реалізують цРАКЗ-моделі та методи знанняорієнтованої підтримки прийняття ідентифікаційних (Bц-задача) та прогнозних (Cц-задача) рішень при складанні розкладів занять у ВНЗ.

5. На базі запропанованих цРАКЗ-моделей, методів та алгоритмів розробити дослідницький прототип у вигляді експертної системи для підтримки прийняття диспетчерських рішень при складанні розкладів занять на прикладі Національного аерокосмічного університету ім. М.Є. Жуковського "ХАІ".

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

Об`єктом дисертаційного дослідження є процеси прийняття рішень при складанні розкладу занять у ВНЗ.

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

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

Наукова новизна одержаних результатів. У процесі вирішення поставлених задач автором особисто одержано такі результати:

вперше розроблено цРАКЗ-метод дедуктивного виводу рішень за умов ц-невизначеності при складанні розкладів, який на відміну від існуючих використовує заздалегідь побудовану базу нечітких квантів знань і ґрунтується на застосуванні цk-знань з нечіткою логікою Заде, що дозволяє підвищити оперативність прийняття рішень і знизити ймовірність помилкового рішення на контрольних даних.

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

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

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

Зокрема одержано такі основні практичні результати:

1. Синтезовано методику знанняорієнтованої підтримки прийняття диспетчерських рішень при складанні розкладів занять з метою імітації інтелектуальних дій диспетчера ВНЗ та автоматичного формування відповідних адміністративно-нормативних документів.

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

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

4. На базі використання об'єктно-орієнтованого інструментального засобу Microsoft Visual Studio 2003 створено ЕС "ШТУРМАН-Розклад", з використанням якої успішно вирішені тестові та реальні задачі складання розкладів занять та іспитів при управлінні навчальним процесом в "ХАІ" та експериментально доведено достовірність і ефективність дисертаційних результатів.

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

Результати дисертаційної роботи у вигляді моделей, методів і програмних засобів впроваджено в навчально-методичному відділі та у навчальний процес Національного аерокосмічного університету ім. М.Є. Жуковського (акт впровадження від 02.11 2006 р.) та у Науково-виробничому підприємстві "Хартрон-Плант" ЛТД при розробці знанняорієнтованої системи формування технологічних маршрутів (акт реалізації від 10.10 2006 р.).

Особистий внесок здобувача. Усі положення, винесені до захисту, отримані автором особисто. У публікаціях, виконаних у співавторстві, дисертанту належать (відповідно до списку публікацій): [1, 6] - дослідження проблеми прийняття рішень диспетчером ВНЗ та обґрунтування вибору відповідних засобів інженерії квантів знань; [4] - розробка цРАКЗ-методу і алгоритмів нечіткого дедуктивного виводу для підтримки прийняття диспетчерських рішень; [5] розробка класифікації вимог до розкладу занять та архітектури ЕС "ШТУРМАН-Розклад"; [7, 9] - розробка ЕС "ШТУРМАН-Розклад" і складової підсистеми підтримки прийняття рішень за умов ц_невизначеності при складанні навчальних розкладів.

Апробація результатів дисертації. Результати досліджень доповідалися на таких наукових конференціях: "Штучний інтелект" - 2003 р., м. Геленджик, Краснодарській край, Росія; "ІКТМ 2003"- 2003 г., Національний аерокосмічний університет ім. М.Є. Жуковського "ХАІ", м. Харків; "ІКТМ 2004" 2004 р., Національний аерокосмічний університет ім. М.Є. Жуковського "ХАІ" м. Харків; "Автоматика 2004" - 2004 р., Національний університет харчових технологій, м. Київ; "ІКТМ 2005" - 2005 р., Національний аерокосмічний університет ім. М.Є. Жуковського "ХАІ", м. Харків.

Публікації. Результати досліджень опубліковані в 9 друкованих працях, з яких 1 стаття у науково-технічному журналі, 4 статті у збірках наукових праць, що включені до переліку фахових видань ВАК України, 4 у матеріалах конференцій.

Структура і обсяг дисертації. Дисертація складається зі вступу, 4 розділів, висновків та 5 додатків. Повний обсяг дисертації складає 177 сторінки, у тому числі: 21 рисунок, 2 таблиці, список використаних джерел зі 120 найменувань на 12 сторінках і 4 додатків на 29 сторінках.

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

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

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

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

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

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

У цьому розділі також проведено аналіз існуючих підходів інженерії знань до маніпулювання знаннями, наведено їх переваги та недоліки, обґрунтовано використання РАКЗ_методу інженерії квантів знань (ІКЗ) для розв`язання задач прийняття диспетчерських рішень при складанні розкладів занять.

У другому розділі наведено теоретичні основи підтримки прийняття диспетчерських рішень на основі створення цРАКЗ-методу ІКЗ, які є фундаментом подальших розділів. Синтезовано цРАКЗ-моделі дедуктивного виводу як розвиток РАКЗ-моделі на випадок ц-невизначеності. Розроблено методику виводу дедуктивних рішень з використанням нечіткої бази квантів знань (БцkЗ) і методику інтегральної оцінки якості розкладу занять.

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

Згідно з РАКЗ-методом об`єкти прийняття рішень (ОПР) характеризуються скінченною кількістю різнотипних характеристик , які приймають значення з кінцевих множин:

(1)

Множинам значень характеристик ставляться у відповідність одновимірні масиви , які називають доменами. Інформація, що деякий клас спостережувальних об`єктів характеризується n ознаками із значеннями з множин , подається доменизованим вектором який називається векторним квантом знань 1-го рівня:

(2)

Для реалізації схеми нечіткого логічного виводу рішень (рис. 1) необхідно вирішити такі задачі: фазифікація, тобто інтерпретація чіткого значення у вигляді нечіткого, обчислення нечіткої імплікації (прийняття рішень) та дефазифікація. Методики вирішення перелічених задач задає інваріантність схеми нечіткого виводу.

Рис. 1. Схема нечіткого логічного виводу

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

,

.

Для оцінки лінгвістичних ознак будемо використовувати якісні терми з терм-множин . Потужності терм-множин можуть буди різними, тобто . Лінгвістичні терми будемо розглядати як нечіткі множини, задані на універсальних множинах і визначимо їх як:

,

де - ступінь приналежності елемента терму .

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

,

.

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

,

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

;

база нечітких квантів знань .

Нечітким дедуктивним виводом -знань згідно з РАКЗ-методом називається алгоритмічний процес знаходження логічних -квантових наслідків спираючись на базу -знань за допомогою алгоритмів :

, , ,

за принципом від загального до часткового.

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

,

де - база -знань; - база функцій приналежності нечітким ознакам; - квант спостережень про ОПР w відносно якого за допомогою алгоритму виводиться рішення у вигляді -знань -го рівня ().

Спираючись на удосконалену модель нечіткого дедуктивного виводу рішень, необхідно розробити новий метод нечіткого дедуктивного виводу рішень.

Розглянемо інформаційну частину нечіткого кванта знань першого рівня

. (3)

Їй відповідає наступне логічне висловлювання:

(4)

де , , універсальні множини. Вираз (4) можна подати у вигляді системи елементарних висловлювань:

(5)

Система (5) відповідає система нечітких відношень:

(6)

де декартовий добуток звичайних множин та , тобто

, , , ;

декартовий добуток нечітких множин та , обумовлене співвідношенням:

,

де ступінь приналежності.

Відповідно до композиційного правила виводу кожне відношення (6) дозволяє оцінювати нечітку множину , що інтерпретуємо в термінах рішень :

(7)

де операція нечіткої композиції.

Об'єднуючи згідно з (5) всі відношення з (7) операцією(), отримаємо:

або більш компактно:

(8)

Формула (8) отримана для ц-кванта першого рівня. Для нечіткого виводу у кванті другого рівня всі рядки, які відповідають рішенню , об'єднуємо логічним складанням:

(9)

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

(10)

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

Таким чином, одержані співвідношення (9) и (10) дозволяють на основі інформації, що міститься в , виводити нечітке рішення для поточних лінгвістичних оцінок параметрів вектора спостережень.

Згідно з РАКЗ-методом загальна методика алгоритмічного рішення базових задач ідентифікації (B_ц-задача) та прогнозування (C_ц-задача) зводиться до реалізації DED-оператора.

Вирішення Bц-задачі полягає в одержані цільових цk-знань цk_sRB за рахунок DED-оператора у вигляді:

цk_sRB = DED(БцkЗ(B_ц),цk₁YB;АЛ(B_ц),цАЛУПР; цk_sRB) =

= БцkЗ(B_ц),

а вирішення Сц-задачі полягає у виводі цільових цk-знань цk_sRС за рахунок DED-оператора у вигляді:

цk_sRС = DED(БцkЗ(С_ц),цk₁YC;АЛ(С_ц),цАЛУПР; цk_sRС) =

= БцkЗ(С_ц).

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

.

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

1. Вирахувати відстань між та :

для усіх .

2. Вибрати таке , для якого:

.

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

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

У загальному випадку радіальна метрична діаграма (РМД) задає n-мірний простір, в якому виконується оцінювання однієї з характеристик розкладу, де n кількість показників (метрик) , за якими оцінюється задана характеристика.

Оскільки різні показники (метрики) можуть мати різні вимірювальні шкали, то для зручності їхнього спільного використання при побудові РМД показники, що входять до однієї діаграми, можуть мати єдині метричні шкали. При цьому значення всіх Р_i, що мають метричну шкалу, мають бути унормовані, тобто зведені до діапазону від 0 до 1, чим ближче до 1, тим краще.

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

,

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

Ступінь виконання зазначених вимог вираховується таким чином:

; ;

; .

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

; ;;,

де - кількість методичних основних, методичних додаткових, організаційних основних, організаційних додаткових вимог відповідних видів.

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

; ;

;.

Розклад навчальних занять вважається сформованим, якщо критерій якості , де - довірчий інтервал критерія якості розкладу.

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

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

Вхід: фіксований квант спостережень - .

Вихід: нечітке рішення .

Крок 1: організувати перегляд нечітких квантів знань (); i індекс поточного кванта знань першого рівня.

Крок 2: організувати перегляд ознак i го нечіткого кванта знань; j індекс поточної ознаки i го кванта знань.

Крок 3: визначити нечітке відношення між цільовою та j ою ознакою i-го кванта знань.

Крок 4: обрахувати нечітке проміжне рішення як нечітку композицію відношення та j-ї ознаки.

Крок 5: визначити нечітке рішення за квантом знань першого рівня за формулою:

.

Крок 6: визначити нечітке рішення як об'єднання всіх рішень .

Крок 7: якщо розглянуті не всі ознаки, то збільшити індекс поточної ознаки j на одиницю та перейти до кроку 3.

Крок 8: якщо розглянуто не всі -кванти знань, то збільшити індекс поточного кванта знань i на одиницю та перейти до кроку 2;

Кінець.

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

Вхід: - граф, що відповідає ц-КМВР, усі вершини якого розподілені по рівнях , - квант спостережень розпізнаваємого об'єкту , - допустимий рівень ризику прийняття рішення.

Вихід: - вектор значень коефіцієнта впевненості класів, що розпізнаються .

Крок 1: організувати активізацію рівней графа , i поточний рівень графа.

Крок 2: активізувати вершини i-го рівня ц-КМВР.

Крок 3: якщо не всі вершини i-го рівня ц-КМВР не активовані, то зупинити процес активації ц-КМВР і всім значенням вектора присвоїти нуль.

Крок 4: якщо активовані не всі вершини i-го рівня , то перейти до кроку 2, інакше перейти до кроку 5.

Крок 5: якщо активовані не всі рівні графа , то збільшити значення i на одиницю та перейти до кроку 2, інакше перейти до кроку 6.

Крок 6: присвоїти змінній w максимальне значення вектора , j - індекс елемента з максимальним значенням .

Крок 7: превірити число w на відповідність такій умові:.

Крок 8: якщо нерівність задовольняється, то об'єкт , інакше об'єкт не може бути розпізнаний.

Кінець.

У четвертому розділі проводиться експериментальна перевірка отриманих в попередніх розділах результатів. Аналіз якості складеного розкладу занять за запропонованою методикою показав підвищення якості в середньому на 18-20 % у порівнянно з розкладом, який був складений диспетчером, що графічно відображено у вигляді радіальної діаграми (рис. 2).

Рис. 2. Оцінка якості розкладу занять у вигляді радіальної діаграми

Експериментальне оцінювання адекватності та ефективності розроблених цРАКЗ-моделей і методів проведено на базі одержаних результатів рішення тестових і реальних задач прийняття диспетчерських рішень при складанні розкладів занять для Національного аерокосмічного університету ім. М.Є. Жуковського "ХАІ" з використанням ЕС "ШТУРМАН-Розклад". Вирішення 2500 контрольних завдань дало такі результати: кількість вірних відповідей - 2431; машина не дала відповіді - 69 рази. Таким чином, ризик прийняття помилкового рішення з допомогою ЕС "ШТУРМАН-Розклад" складає 2,7 %. Вирішення цих же контрольних завдань без використання "ШТУРМАН-Розклад" диспетчером дало такі результати: кількість вірних рішень - 2143; кількість невірних рішень - 357. Таким чином, ризик складає біля 14,2 %.

Отже, використання ЕС "ШТУРМАН-Розклад" дозволяє знизити ризик прийняття помилкових рішень у два рази.

Надається опис архітектури (рис. 3), режимів і функцій розробленої системи "Штурман_Розклад" для знанняорієнтованого складання розкладу занять.

Рис. 3. Архітектура ЕС "ШТУРМАН-Розклад"

Сформульовано та вирішено засобами експертної системи "ШТУРМАН-Розклад" задачі знанняорієнтованої підтримки прийняття рішень при складанні розкладів занять і при формуванні технологічних маршрутів, що засвідчує адекватність розроблених квантових моделей.

У висновках сформульовано основні положення, що виносяться на захист.

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

ВИСНОВКИ

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

Проведене дослідження підтверджує актуальність всіх аспектів порушених в дисертаційній темі, відповідає поставленим меті та задачам, окреслює шляхи практичної реалізації одержаних результатів. Розроблені в дисертації моделі, методи і алгоритми реалізовані у вигляді ЕС "ШТУРМАН-Розклад" для підтримки прийняття диспетчерських рішень при складанні розкладів занять у ВНЗ.

У рамках дисертаційної роботи досягнуто таких основних результатів:

1. Проведено огляд і аналіз методів і засобів комп'ютерної підтримки прийняття диспетчерських рішень при складанні розкладів занять у ВНЗ і сформульвано задачі дисертаційної роботи.

2. Розроблено цРАКЗ-метод дедуктивного виводу рішень за умов ц-невизначеності при складанні розкладів, який на відміну від існуючих використовує заздалегідь побудовану базу нечітких квантів знань і ґрунтується на застосуванні цk-знань з нечіткою логікою Заде, що дозволяє підвищити оперативність прийняття рішень і знизити ймовірність помилкового рішення на контрольних даних.

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

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

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

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

7. З використанням об'єктно-орієнтованого інструментального засобу Microsoft Visual Studio 2003 на базі розроблених моделей, методів і алгоритмів створено ЕС "ШТУРМАН_Розклад", за допомогою якої успішно вирішені тестові та реальні задачі складання розкладів занять та іспитів для Національного аерокосмічного університету ім. М.Є. Жуковського, а також експериментально доведено достовірність і ефективність дисертаційних розробок.

8. Результати дисертаційної роботи впроваджені та використовуються в роботі навчально-методичного відділу Національного аерокосмічного університету ім. М.Є. Жуковського для створення розкладів занять на денній і заочній формах навчання та іспитів всього університету.

Результати експериментальних досліджень показали, що розклади занять складенні з використанням запропонованих у дисертації моделей та методів є кращими, ніж розклади, що складаються традиційними засобами, за такими показниками: з розкладу виключено ситуації, що не допускаються і заважають проведенню занять (накладки викладачів, аудиторій, груп); у розкладі відсутні "вікна" у студентів; зростає ефективність використання аудиторного фонду і викладацького складу ВНЗ.

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

1. Россоха С.В., Соханюк И.Е. Проблема поддержки принятия диспетчерских решений при планировании расписаний учебных занятий в техническом университете // Искусственный интеллект. 2003. №4. С. 349 355.

2. Россоха С.В. Знаниеориентированный метод автоматизированного синтеза расписаний учебных занятий // Открытые информационные и компьютерные интегрированные технологии. - Х.: Нац. аэрокосм. ун-т "ХАИ", 2005. Вып. 29. - С. 149 154.

3. Россоха С.В. Поддержка принятия решений при синтезе учебных расписаний // Вестник НТУ "ХПИ". Тематический выпуск: Системный анализ, управление и информационные технологии. - Х.: НТУ "ХПИ", 2005. - №59. - С. 177 182.

4. Сироджа И.Б., Россоха С.В. Нечеткий дедуктивный вывод в системе квантов знаний для поддержки принятия решений в условиях ц-неопределенности // Открытые информационные и компьютерные интегрированные технологии - Х.: Нац. аэрокосм. ун-т "ХАИ", 2006. Вып. 30. - С. 50-56.

5. Сироджа И.Б., Россоха И.Е. Россоха С.В. Интеллектуальная информационная технология поддержки принятия диспетчерских решений // Открытые информационные и компьютерные интегрированные технологии. - Харьков: Нац. аэрокосм. ун-т "ХАИ", 2006. Вып. 32. - С. 114-118.

6. Россоха С. В., Россоха И.Е. Модели и методы поддержки принятия решений диспетчером технического университета // Международная научно-техническая конференция "Интегрированные компьютерные технологии в машиностроении", ИКТМ`2003. Х: Нац. аэрокосм. ун-т им. "ХАИ", 2003. С. 265.

7. Россоха С.В., Россоха И.Е. Система рационального планирования расписания учебных занятий в ВУЗе // Международная конференция по автоматическому управлению "Автоматика-2004". К.: Нац. ун-т пищевых технологий, 2004. - С. 78.

8. Россоха С.В. Методы вывода в знаниеориентированных системах поддержки принятия решений // Международная научно-техническая конференция "Интегрированные компьютерные технологии в машиностроении", ИКТМ`2004. Х.: Нац. аэрокосм. ун-т "ХАИ", 2004. - С. 380.

9. Россоха С.В., Россоха И.Е. Поддержка принятия решений в многокритериальной задаче планирования учебных расписаний // Международная научно-техническая конференция ИКТМ`2005. - Х.: Нац. аэрокосм. ун-т "ХАИ", 2005. - С. 413.

АНОТАЦІЯ

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - автоматизовані системи управління та прогресивні інформаційні технології. Національний аерокосмічний університет ім. М.Є. Жуковського "ХАІ", Харків, 2006.

Дисертацію присвячено питанням автоматизації підтримки прийняття рішень при складанні розкладів занять в умовах ц-невизначеності. Для вирішення задачі підтримки прийняття диспетчерських рішень було використано РАКЗ-метод подання знань та маніпулювання ними. У цілях підвищення ефективності прийняття рішень РАКЗ-методом в умовах ц-невизначеності запропоновано метод нечіткого дедуктивного виводу, що спирається на заздалегідь побудовану базу нечітких квантів знань та математичний і логічний апарат теорії нечітких множин. Модифіковано РАКЗ-моделі дедуктивного виводу диспетчерських рішень за рахунок введення алгоритмічних операторів фазифікації та дефазифікаціі та запропоновані оригінальні алгоритми, що дозволяють моделювати причинно-наслідкові міркування диспетчерів для комп'ютеризації прийняття рішень. Розроблено метод оцінки якості розкладів занять за ступенем виконання оптимізуючих вимог, що дозволяє найточніше оцінити якість розкладу занять. В дисертації запропоновано моделі, методи і алгоритми, реалізовані у вигляді прототипу ЕС "ШТУРМАН-Розклад".

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

АННОТАЦИЯ

Россоха С.В. Модели и методы инженерии нечетких квантов знаний для дедуктивного вывода решений в экспертной системе при составлении расписаний в ВУЗе. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - автоматизированные системы управления и прогрессивные информационные технологии. Национальный аэрокосмический университет им. Н.Е. Жуковского "ХАИ", Харков, 2006.

Работа посвящена вопросам автоматизации знаниеориентированной поддержки принятия решений при составлении расписаний занятий в условиях так называемой ц-неопределенности, связанной преимущественно с нечетким и лингвистическим описанием характеристик объектов принятия решений (ОПР).

В первом разделе проведен анализ методов, средств и технологий составления расписаний занятий, а также моделей, методов, технологий и инструментальных средств, необходимых для решения задачи дедуктивного вывода знаниеориентированных решений для поддержки принятия решений при составлении расписаний занятий.

Определено, что при управлении учебным процессом составления расписаний является наиболее трудоемким этапом, решения, принятые на данном этапе, существенным образом влияют на качество учебного процесса. Несмотря на большое количество систем, направленных на автоматизацию рутинного, а не творческого процесса составления расписаний занятий, большинство из них не может эффективно функционировать в реальных условиях работы вузов из-за отсутствия способности подстраиваться к изменяющимся среде и исходным данным, как следствие использование жесткой стратегии составления расписания занятий, а также пренебрежение диспетчерским опытом и знаниями.

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

Третий раздел посвящен разработке комплекса алгоритмов необходимых для нечеткого дедуктивного вывода решений по ранее синтезированной базе нечетких квантов знаний. Описаны основные алгоритмы работы операторов фаззификации, дефаззификации, нечеткого дедуктивного вывода решений. Разработан алгоритм вычисления коэффициента уверенности следствия, основываясь на методике расчета предложенной во второй главе. Разработаны алгоритмы определения степеней выполнения методических и организационных требований различных видов для последующего их использования при оценке качества составленного расписания занятий в вузе.

В четвертом разделе проведен анализ адекватности разработанных моделей, выполнена экспериментальная проверка полученных теоретических результатов на базе разработанной экспертной системы "ШТУРМАН-Розклад" для составления расписаний занятий в вузе.

Выполнено объектно-ориентированное моделирование проблемной области и построена объектная модель предметной области.

Проведено оценивание качества расписания занятий на основании разработанной во второй главе методики, выявила 18 20 % улучшение качества расписания занятий в сравнении с расписанием составленным диспетчером вручную.

Сформулированы и решены с помощью экспертной системы типичные задачи принятия диспетчерских решений. Анализ качества принимаемых решений, выраженный величиной риска принятия ошибочного решения, показал, что риск принятия ошибочного решения экспертной системой "ШТУРМАН-Розклад" составляет около 2,7 %, тогда как для опытного диспетчера он составляет 14,2 %.

Предложенные в диссертации модели, методы и алгоритмы реализованы в виде прототипа ЕС "ШТУРМАН-Розклад".

Таким образом, применение системы "ШТУРМАН-Розклад" позволит сократить временные затраты на составление расписаний занятий, снизить трудоемкость составления расписания занятий и повысить его качество.

Ключевые слова: экспертная система, поддержка принятия решений, расписание занятий, инженерия квантов знаний, автоматизация составления расписания занятий, нечеткая логика, многокритериальная оптимизация.

ABSTRACT

Rozsokha S. Models and methods of engineering of fuzzy quantums of knowledge for a deductive conclusion of decisions in expert system at drawing up of schedules in high school. the Manuscript.

The dissertation on reception of a scientific degree of Cand. Tech. Sci. on a specialty 05.13.06 the automated control systems and progressive information technologies. - National Aerospace University "Kharkiv Aviation Institute", Kharkov, 2006.

The dissertation is devoted to questions of automation of support of decision-making at drawing up of schedules of occupations in conditions ц-Uncertainty. For the decision of a problem of support of acceptance of dispatching decisions the DAQK method of representation and a manipulation has been used by knowledge. With a view of increase of efficiency of decision-making by the DAQK method in ц-conditions. The method of an indistinct deductive conclusion which bases on beforehand constructed base of fuzzy quantum's of knowledge is offered to uncertainty, and is based on the mathematical and logic device of the theory of fuzzy sets. Modified DAQK models of a deductive conclusion of dispatching decisions, due to introduction of algorithmic operators fuzzyfication and defuzzyfication. The developed original algorithms for knowledge based supports of acceptance of dispatching decisions at drawing up of schedules of occupations in high school which allow to model cause and effect reasoning's of the dispatcher for a computerization of acceptance of dispatching decisions. The method of an estimation of quality of schedules of occupations on a degree of performance optimizing requirements which allows to estimate quality of the schedule of occupations more precisely. The models suggested in the dissertation, methods and algorithms are realized as the prototype of expert system " Navigator schedule".

Key words: expert system, support of acceptance knowledge based decisions, the schedule of occupations, engineering of quantums of knowledge, automation of formation of the schedule of occupations, fuzzy logic, a lot criteria optimization.

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