Національний університет “Львівська політехніка”

Литвин Василь Володимирович

УДК 51.001.57+004.855+004.832.38

Моделювання інтелектуальних інформаційних систем з індуктивною компонентою

01.05.02 – математичне моделювання та обчислювальні методи

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

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

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

Робота виконана у Національному університеті “Львівська політехніка”,

Міністерства освіти і науки України

Науковий керівник - доктор технічних наук, доцент Пасічник Володимир Володимирович, завідувач кафедри “Інформаційні системи та мережі” Національного університету “Львівська політехніка”

Офіційні опоненти - доктор технічних наук, доцент Матвійчук Ярослав Миколайович, професор кафедри “Теоретична радіотехніка та радіовимірювання” Національного університету “Львівська політехніка”

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

Провідна установа - Державний науково-дослідний інститут інформаційної інфраструктури Державного комітету зв'язку та інформатизації і НАН України (м. Львів)

Захист відбудеться 7 лютого 2003р. о 16 год. на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка” (79013, м. Львів-13, вул. С.Бандери, 12)

З дисертацією можна ознайомитися у бібліотеці Національного університету “Львівська політехніка” (79013, м. Львів, вул. Професорська, 1)

Автореферат розісланий “4” січня 2003 р.

Вчений секретар спеціалізованої

вченої ради, д.т.н., проф. Федасюк Д.В.

загальна характеристика роботи

Актуальність роботи. Технологія розробки інтелектуальних інформаційних систем (ІІС) є одним із напрямків штучного інтелекту. Дослідження у цій області полягають у створенні методів і засобів проектування автоматизованих інформаційних систем, які орієнтовані на ті області діяльності людини, що вимагають логічного міркування, певної майстерності та досвіду. До них належать задачі прийняття рішення у різноманітних предметних областях (ПО). Як відзначають провідні спеціалісти в області ІІС – “показником інтелектуальності системи є вміння системою використовувати у потрібний момент необхідні (релевантні) знання”. Системи, що не мають засобів для визначення і використання релевантних знань зіштовхуються із проблемою “комбінаторного вибуху”. Ця проблема є однією з основних причин, через яку обмежується сфера застосування ІІС. Розв'язання цієї проблеми полягає у підвищенні рівня інтелектуальності ІІС. Це веде до необхідності вирішення таких завдань: розширити сферу застосування ІІС; видавати ІІС точніші та надійніші розв'язки; узагальнити та модифікувати знання ІІС (індукція); підвищити ефективність функціонування ІІС.

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

За останні два десятиліття розроблено ряд математичних моделей інтелектуальних інформаційних систем. Значний внесок у розробку та дослідження таких моделей внесли вчені: Гладун В.П., Івахненко А.Г., Любарський Ю.Я., Одинцов Б.Е., Попов Є.В., Поспелов Г.С., Поспелов Д.А., Bratko I., Hayes-Roth F., Harmon P., Jackson P., Lenat D., Minsky M., Nillson N., Shapiro E., Walker R. та ін.

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

Зв'язок роботи з науковими програмами, планами, темами.

Робота виконана в рамках пріоритетного наукового напрямку Міністерства освіти і науки України “Перспективні інформаційні технології, прилади комплексної автоматизації, системи зв'язку” за темами: “Дослідження процесів проектування розподілених інтелектуальних інформаційних систем прийняття рішень для слабо-структурованих проблем на основі реляційних баз даних (на прикладі сфери фінансів, бізнесу та управління)”, шифр 0196U000179; “Розробка макетів та моделей для проектування розподілених інтелектуальних інформаційних систем, алгоритмів і програм виявлення та апробації систем переваг особи, що приймає рішення, методів відсіювання та відбору альтернатив в слабо-структурованому середовищі”, шифр 0198U002391. Участь автора полягала у розробці та дослідженні: структурної та функціональної моделей ІІСІК, алгоритмів підвищення ефективності функціонування ІІСІК, моделі подання знань за допомогою об'єктів та методів перетворення даної моделі у реляційну.

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

Мета дисертаційної роботи визначає необхідність розв'язання таких задач:

·

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

· розроблення процедур підвищення ефективності функціонування ІІС, які б враховували особливості ІІСІК, аналіз спеціальних випадків;

· визначення основних підходів до застосування об'єктно-орієнтованої парадигми аналізу та проектування ІІСІК;

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

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

Об'єктом досліджень виступають інтелектуальні інформаційні системи, що містять індуктивну компоненту.

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

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

·

· Розроблено нову модель керування пошуком розв'язку задачі, що містить індуктивну компоненту. Використання цієї моделі дозволяє зменшити розмірність простору пошуку станів ПО при розв'язуванні задачі.

· Вперше застосовано математичний апарат теорії координації до розв'язання задач підвищення ефективності функціонування ІІСІК. Розглянуто спеціальний випадок: багаторівневі ІІСІК.

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

Практичне значення одержаних результатів.

·

· Побудовано алгоритми координації ІІСІК та фільтрування інформації, які дозволяють зменшити розмірність простору пошуку розв'язку.

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

· Розроблено комплексну інформаційну систему керування навчальним процесом “Школа” з інтелектуальною компонентою побудови розкладу, в якій практично відображені результати наукових досліджень.

Впровадження результатів роботи. Розробки впроваджені у Фізико-механічному інституті ім. Г.В.Карпенка НАН України (м. Львів), міському споживчому товаристві (м. Львів), редакції тижневика НУ "Львівська політехніка" "Аудиторія", у двох школах міста Львова, а також в навчальному процесі НУ "Львівська політехніка", зокрема при викладанні дисциплін “Основи проектування систем штучного інтелекту”, “Теорія систем баз даних та знань”, “Математичні основи представлення даних та знань”, в яких використовувалися результати наукових досліджень як в окремих розділах лекційних курсів, так і в циклах лабораторних та практичних робіт.

Особистий внесок здобувача. Усі наукові результати, подані у дисертації, одержані здобувачем особисто. У друкованих працях, опублікованих у співавторстві, особистий внесок здобувача такий: [1] – належить системний аналіз діяльності служби працевлаштування, програмний код системи на мові Пролог; [4] – основні принципи побудови ІІСІК керування навчальним процесом; [5] – опис функціонування інтелектуальної компоненти опрацювання анкет для періодичних видань; [7] – фільтрування знань на початку та в процесі побудови розкладу; [8] – класифікація ІІС на основі методів пошуку розв'язку; [9] – моделювання основних компонент ІІСІК; [12] – розробка інтелектуального інтерфейсу між інформаційною системою та користувачем, [13] – основні принципи функціонування ІІС з кількома інтерпретаторами, [14] – класифікація ІІС на основі кількості змінних в моделі керування процесом пошуку розв'язку; [17] – координація багаторівневих ІІСІК, [18] – основні принципи видобування знань у ігрових видах спорту.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися на семінарах та конференціях: науковий семінар міжнародної комп'ютерної виставки “Комп'ютер і Офіс” – Львів, 1998, 1999, 2000, 2001; науковий семінар міжнародної комп'ютерної виставки “Комп'ютер+Бізнес” – Львів 1998, 1999, 2000, 2001; XV відкрита науково-технічна конференція молодих науковців і спеціалістів Фізико-механічного інституту ім. Г.В.Карпенка НАН України, Львів, 2000; Міжнародна науково-практична конференція “Сучасні технології в інформаційному суспільстві”, Київ, 2001; Міжнародна науково-практична конференція KDS-2001 “Знание-Диалог-Решение”, Санкт-Петербург, 2001, ІІ Всеукраїнська науково-практична конференція “Науково-методичні аспекти тренування футболістів”, Київ, 2001; щорічні (1998, 1999, 2000, 2001) наукові семінари кафедри "Інформаційні системи та мережі" та наукові конференції викладачів і науковців Національного університету “Львівська політехніка”.

Публікації. За темою дисертації опубліковано 18 наукових праць, із них 7 праць – одноосібні. 12 праць опубліковані у фахових виданнях ВАК України.

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

основний Зміст роботи

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

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

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

·

· володіє механізмами міркувань, якими виступають метапроцедури, що використовують знання з метою вироблення шляху розв'язку;

· володіє природно-мовним інтерфейсом, що забезпечує інтерактивну взаємодію користувача з ІІС.

Ці три компоненти і складають сутність розгляду ІІС як об'єкту моделювання.

Значна кількість ІІС ґрунтується на понятті “формальна продукційна система”. Продукційна система PS визначається як трійка елементів

PS = <E, B, I>,

де Е – база даних;

В – база знань, яка містить множину продукцій, тобто інформацію про можливі способи перетворення даних;

І – інтерпретатор, який реалізує процес виведення, що в циклі виконує наступні дії: визначає множину пар: (правило bi, набір біжучих даних Ei, на якій це правило задовольняється); виконує відповідні дії, тим самим проводячи зміни в базі даних.

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

,

де Q – вхідна сукупність інформації, що мінімально необхідна для початку функціонування ІІС;

V– вихідна інформація, яку генерує ІІС у відповідь на вхідну інформацію, яку надає клієнт; це є можливі відповіді, що видає ІІС;

D – індуктивна компонента (досвід);

St– стан інтелектуальної інформаційної системи: унікальний набір характеристик, який описує поточний стан ІІС. Стан ІІС визначається станом ПО та наявними знаннями в системі. Тобто

St = <E, B, H>,

де B – знання ПО, представлені у вигляді операторів; H – множина евристичних функцій (метазнань), визначених у заданій ПО; E – стан ПО.

де B – знання ПО, представлені у вигляді операторів; H – множина евристичних функцій (метазнань), визначених у заданій ПО; E – стан ПО.

Задачу модифікації знань та метазнань за допомогою D розбивається на дві окремі задачі, які стосуються окремо знань

D1 : A ® B

та метазнань

D2 : A ® B,

де A = E ґ B ґ H.

Для подальшого дослідження ІІС з індуктивною компонентою (ІІСІК) розглядається процес функціонування системи. Метою функціонування ІІС є задача переведення ПО з початкового стану E(0) в деякий кінцевий стан E(z).

Перехід з E(0) в E(z) здійснюється завдяки застосування операторів з множини B до стану ПО

P: E(0) ® E(z).

Оператори, які можна застосувати до деякого стану ПО, є допустимими і вони складають конфліктний набір. Основна задача функціонування ІІС полягає у виборі із конфліктного набору оператора, який буде використано системою до поточного стану ПО. Такий оператор називається релевантним, а процес його вибору – вирішенням конфліктів.

Для вибору релевантного оператора використовуються евристичні функції та досвід, набутий системою. Якщо B(i) – конфліктний набір операторів для стану ПО E(i), то процес вибору релевантного оператора виглядатиме як

u: B(i) ® bp.

Далі показано, що проблема вибору релевантного оператора еквівалентна системі булевих рівнянь (СБР). Якщо:

,

то вирішення конфліктів будемо розглядати як розв'язання такої СБР:

, (1)

де si – кількість евристичних функцій, які можна застосувати до стану ПО E(i).

Загалом функціональна модель ІІСІК має вигляд:

,

де E(t+1) – новий стан ПО; – множина станів, в яких перебувала ПО; i – модель керування процесом пошуку розв'язку; wОW – множина можливих факторів, що впливають на результат; g – функція оцінки роботи ІІС; t – функція допустимості розв'язку; xОX – множина ресурсів ІІС; y – функція оцінки витрат ресурсів.

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

Рис. 1. Ієрархія шарів вибору релевантного оператора

У кінці розділу наводиться порівняння основних характеристик продукційної системи із системою, запропонованою автором.

У другому розділі розглядається моделювання процесу керування пошуком розв'язку задачі на основі формальної структурної і функціональної моделей ІІСІК, побудованих у попередньому розділі. Відомі у літературі моделі повного перебору у практично важливих ПО зіштовхуються із проблемою комбінаторного вибуху. Використання індуктивної компоненти націлене на побудову моделі процесу керування розв'язком задачі, яка б дозволила мінімізувати використання зайвих операторів, тобто операторів, які не потрапляють у ланцюжок виведення. Маємо Lz Н BP. Якщо довжина Lz дорівнює dz, то цільова функція буде мати вигляд:

F = T - dz ® min.

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

Входом моделі керування розв'язком задачі є конфліктний набір операторів B(i), а виходом - релевантний оператор bp. Вибір bp зводиться до розв'язування СБР (1). Кількість можливих розв'язків (1) визначає простір пошуку розв'язку задачі. Тому модель керування розв'язку задачі повинна зменшити кількість можливих розв'язків (1), що можна здійснити за допомогою ІК. Цю проблему будемо розглядати у двох аспектах: якісному (за рахунок модифікації множин знань та метазнань) та кількісному (за рахунок відкидання непотрібних операторів із кофліктного набору, для чого використовується фільтрування інформації).

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

Рис. 2. Схема моделі керування пошуком розв'язку задачі.

Далі досліджується координація ІІСІК. Серед моментів втручання ІК виділяються три спеціальні випадки.

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

2. СБР (1) не має розв'язків. Тоді необхідно звернутись до верхнього шару з метою знаходження існування розв'язку СБР.

3. За бажанням користувача.

У багаторівневих ІІСІК розв'язок задачі розбивається на підзадачі P=p1Еp2Е…Еpm. Така декомпозиція також веде до проблеми координації. Тому далі у роботі розглядаються багаторівневі ІІСІК. Кожний рівень розв'язку підзадачі має ієрархічну структуру шарів вибору релевантного оператора.

Кожній підзадачі pk відповідає інтелектуальна підсистема Sk. Визначається керівна підсистема верхнього рівня S0. Множина операторів та евристичних функцій розбивається на три окремі підмножини. Перша підмножина містить знання та метазнання, визначені для окремої підсистеми; друга – для кількох підсистем, третя – для всієї системи. Підсистеми нижчих рівнів із керівною пов'язуються за допомогою даних та знань, визначених у підсистемі нижчого рівня. Координуючими сигналами керівної підсистеми є визначення стратегій вибору релевантних операторів. Між собою підсистеми нижчих рівнів пов'язуються за допомогою знань та метазнань другої та третьої підмножин, а також спільних даних, що містяться у поточному стані ПО.

У другому розділі дисертаційної роботи також розглядається питання фільтрування інформації як спосіб зменшення розмірності СБР. Фільтрування інформації здійснюється на початку роботи системи або під час її функціонування. Пропонуються такі методи фільтрування під час функціонування ІІСІК:

·

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

· у будь-який момент часу за допомогою діалогу між користувачем та ІІСІК за бажанням користувача.

Алгоритм фільтрування.

1. Побудувати відфільтровану множину даних та знань: .

2. Побудувати сумарну множину: .

3. Вибрати інформацію на основі деякого порогу: .

Для пошуку розв'язку пропонується двоетапний метод пошуку. Множину евристичних функцій H розбиваємо на дві підмножини H1 та H2, де підмножина H1 містить метазнання, за допомогою яких формується підмножина операторів Bў(i) конфліктного набору B(i) , а підмножина H2 – здійснює вибір релевантного оператора, але з підмножини Bў(i). Тобто . Тоді функція здійснює відображення: . Перевага в тому, що підмножина операторів Bў(i) формується один раз. При поверненні ПО назад у стан Е(і) конфліктним набором буде множина Bў(i) . Тобто заздалегідь відкидаються оператори, що не ведуть до розв'язку задачі.

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

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

Проаналізовано зв'язок об'єктно-орієнтованих методологій з пропонованою у дисертаційній роботі формальною моделлю ІІСІК. А саме

·

· джерела знань – множина операторів,

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

· індуктивна компонента задається утилітою класів,

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

Розглядається об'єктно-орієнтований метод подання знань. Показано взаємозв'язок об'єктно-орієнтованого методу подання знань з іншими неформальними методами подання знань, що дозволяє в одній ІІС використовувати декілька цих методів. Об'єкти різних класів співвідносяться між собою, утворюючи єдину структуру (схему Sch). Через z будемо позначати клас C або об'єкт o, а через Q – множину відношень між z. Тоді будь-яку схему можна подати як , де Fzi – підмножина елементів із Z, з якими елемент zi зв'язаний відношеннями із Q.

В загальному вигляді схему можна розглядати як пару Sch = (Z, F), де F – відображення Z в Z, зважене відношеннями із Q:

.

Щоб описати процедури функціонування ІІС, які базуються на поданні знань за допомогою об'єктів, у роботі розглядаються такі операції над схемами:

Об'єднання схем. Нехай задані схеми Sch1 = (Z1, F1), Sch2 = (Z2, F2),…, Schn = (Zn, Fn). Схема Sch = (Z, F) називається об'єднанням схем Schi, i = 1,2,…,n та позначається Sch = И Schi, якщо Z = И Zi та для .

Перетин схем. Нехай задані схеми Sch1 = (Z1, F1), Sch2 = (Z2, F2),…, Schn = (Zn, Fn). Схема Sch = (Z, F) називається перетином схем Schi, i = 1,2,…,n та позначається , якщо та для .

Схема Sch* = (Z*, F*) називається підсхемою Sch = (Z, F), якщо та , .

Доповнення схеми. Нехай задані схеми Sch1 = (Z1, F1) та Sch2 = (Z2, F2) такі, що Sch2 є підсхемою Sch1, тобто . Схема Sch3 = (Z3, F3) називається доповненням схеми до схеми Sch1, якщо , де , , та виконуються такі умови: ; , ; , де , , причому кожний елемент пов'язаний хоча б одним відношенням з об'єктами із ; , .

Конкретизація схем.

Нехай задана схема класів. є результатом конкретизації , якщо , , .

У четвертому розділі дисертаційної роботи описано ІІСІК автоматизації керування навчальним процесом “Школа”. Основною функціональною підсистемою є побудова розкладу відповідно до заданого навчального плану. Під час проектування та розроблення останньої було використано теоретичні результати дисертаційних досліджень.

Розклад R - це підмножина декартового добутку вхідних множин: викладачів (T), класів (S), предметів (L), КАБІНЕТІВ (А), днів (H), НОМЕРІВ УРОКУ (W) (RTSLAHWНT*S*L*A*H*W), тобто відношення, яке задовольняє такі умови:

·

· один викладач не може одночасно проводити кілька уроків;

· для одного класу не може одночасно проводитись кілька уроків;

· в одному кабінеті не може одночасно проводитись декілька уроків.

Початковим станом ПО E(0) є дані про навчальний план (рік навчання, предмет, кількість годин), викладачів, класи, дні та кабінети. Кінцевим станом ПО E(z) є готовий розклад, тобто E(z) = RTSLAHW. Подія – позначає один урок, передбачений навчальним планом. Множина B складається з наступних операторів: b1l - вибрати подію l; b2t – призначити події викладача t; b3h – призначити події день h; b4w – призначити події номер уроку w; b5a – призначити події кабінет a. Тоді початковий стан ІІС буде мати вигляд . Початкова множина евристичних функцій H є пустою, вона поповнюється та модифікується у процесі функціонування системи.

Рис. 3. Схема об'єктів кортежу РОЗКЛАД

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

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

·

· встановлення правил розкладу: правила складаються з предикатів – логічних висловлювань, які формально описують певну ситуацію в розкладі;

· встановлення вимог (обов'язково, за можливістю) у необхідності спеціалізованого кабінету;

· встановлення фіксованого часового обмеження;

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

Тим самим будуються нові евристичні функції, використання яких спрощує СБР (1). Так, для спеціалізованої середньої школи з вивчення іноземних мов було побудовано евристику: насамперед призначати події, що стосуються іноземних мов. Тобто, якщо всіх подій у навчальному плані є 1100 (на початку укладання розкладу СБР (1) має 1100 можливих розв'язків), то уроків з іноземною мовою є 134 (тим самим на початку укладання розкладу СБР (1) має 134 можливих розв'язки).

Кожний наступний процес укладання розкладу зменшує кількість зайвих призначень. Так для тестового прикладу під час першої реалізації процесу укладання було здійснено 581 зайве призначення, а для десятої – 212 (рис. 4а). Час укладання розкладу зменшився: з 20 хв. для першої реалізації процесу до 14 хв. для десятої його реалізації (рис. 4б). Для першої реалізації процесу було призначено 97% подій, починаючи з п'ятої реалізації – призначення відбулось для 100% подій (рис. 4в), тобто підвищилась ефективність побудови розкладу.

Рис. 4. Залежність зайвих призначень, часу та призначених подій від номера реалізації процесу укладання розкладу

Програмна реалізація ІІСІК “Школа” здійснювалась засобами Microsoft Access 2000. Ядром підсистеми є база даних. Під час її розроблення використовувалась стандартна реляційна модель, навколо якої будувалось програмне забезпечення. Таким чином, використано гібридне рішення: побудова об'єктно-орієнтованої оболонки над традиційною реляційною базою даних, що дозволило використати переваги обох підходів.

У роботі наведено правила, які необхідно враховувати, під час відображення класів і асоціацій (включаючи наслідування та агрегацію) у реляційну модель системи. У базі даних системи за допомогою мови SQL створено необхідні структури даних, засобами мови програмування VBA побудовано модулі системи, користувацькі форми та готові до друку звіти.

У додатках наведено програмний код модуля Shedule, який укладає розклад (1692 стрічки програмного коду), акти впровадження результатів роботи.

Основні результати та висновки.

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

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

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

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

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

5. Структурна та функціональна модель ІІСІК конструктивно реалізована засобами об'єктно-орієнтованого підходу. Розроблено об'єктно-орієнтовану модель подання знань, базовану на понятті схеми об'єктів. Показано взаємозв'язок цієї моделі подання знань з іншими неформальними методами подання знань, що дозволяє в одному проекті використовувати декілька таких методів.

6. Розроблено ІІСІК автоматизації керування навчальним процесом “Школа”, в якій практично відображені результати наукових досліджень.

список опублікованих праць за темою дисертації

1. Литвин В.В., Нікольський Ю.В. Застосування методів логічного програмування для автоматизації процедур прийняття рішень у діяльності служби працевлаштування. // Інформаційні системи та мережі. Вісник Національного Університету “Львівська політехніка”, №330. – Львів, 1998. – С. 153-163.

2. Литвин В.В. Об'єктно-орієнтований підхід до проектування баз даних. // Задачі та методи прикладної математики. Вісник Львівського Національного Університету ім. І.Франка, Випуск 50. – Львів, 1998. – С. 158-159.

3. Литвин В.В. Реалізація множинного наслідування в об'єктно-орієнтованих базах даних. // Інформаційні системи та мережі. Вісник Національного Університету “Львівська політехніка”, №383. – Львів, 1999. – С. 140-144.

4. Литвин В.В., Бакаїм Р.Б., Процовський О.Й., Садовий В.М., Шаховська Н.Б., Шаховський Р.В. Основні принципи та функціональне наповнення інформаційної системи "Школа" для автоматизації управління навчальним процесом. // Інформаційні системи та мережі. Вісник Національного Університету “Львівська політехніка”, № 383. – Львів, 1999. – С. 145-149.

5. Литвин В.В., Паров'як І.П., Пелещишин А.М., Процовський О.Й., Садовий В.М. Принципи реалізації інтегрованих комп'ютерних технологій для періодичних видань. //Інформаційні системи та мережі. Вісник Національного Університету "Львівська Політехніка", №383. – Львів, 1999. – С.149-154.

6. Литвин В.В. Формальна модель інтелектуальної інформаційної системи. // Комп'ютерна інженерія та інформаційні технології. Вісник Національного Університету “Львівська політехніка”, № 386. – Львів, 1999. – С. 104-108.

7. Литвин В.В., Назаров О.Ю., Чумаченко С.В. Інтелектуальна інформаційна система планування навчального процесу. // Інформаційні системи та мережі. Вісник Національного Університету “Львівська політехніка”, №406. – Львів 2000. – С. 179-184.

8. Івашків А.М., Литвин В.В. Проблема класифікації інтелектуальних інформаційних систем. // Інформаційні системи та мережі. Вісник Національного Університету “Львівська політехніка”, №406. – Львів, 2000. – С. 112-117.

9. Литвин В.В., Нікольський Ю.В. Моделювання компонент інтелектуальної інформаційної системи. // Труды международной научно-практической конференции KDS-2001 “Знание – диалог – решение”. – Санкт-Петербург, июнь, 2001. – т. ІІ. – С. 433-438.

10. Литвин В.В. Побудова інтелектуальних інформаційних систем на основі об'єктно-орієнтованої моделі представлення знань. // Комп'ютерна інженерія та інформаційні технології. Вісник Національного Університету “Львівська політехніка”, №433. – Львів, 2001. – С. 94-102.

11. Литвин В.В. Основні методи фільтрації інформації та їх використання при побудові інтелектуальних інформаційних систем. // Інформаційні системи та мережі. Вісник Національного Університету “Львівська політехніка”, №438. – Львів, 2001. – С. 94-99.

12. Литвин В.В., Григор'єв В.В. Застосування утилітарного підходу до реалізації природномовного інтерфейсу інтелектуальних інформаційних систем. // Інформаційні системи та мережі. Вісник Національного Університету “Львівська політехніка”, №438. – Львів, 2001. – С. 99-103.

13. Литвин В.В., Кравець Р.Б. Інтелектуальні інформаційні системи з кількома інтерпретаторами. // Інформаційні системи та мережі. Вісник Національного Університету “Львівська політехніка”, №438. – Львів, 2001. – С. 104-108.

14. Івашків А.М., Литвин В.В. Класифікація інтелектуальних інформаційних систем. // Тези доповідей сьомої всеукраїнської наукової конференції “Сучасні проблеми прикладної математики та інформатики”. – Львів, 2000. – С. 49-50

15. Литвин В.В. Двоетапний метод пошуку розв'язку в метаінтелектуальній інформаційній системі. // Тези доповідей сьомої всеукраїнської наукової конференції “Сучасні проблеми прикладної математики та інформатики”. – Львів, 2000. – С. 59-60.

16. Литвин В.В. Модель функціонування інтелектуальної інформаційної системи. // XV відкрита науково-технічна конференція молодих науковців і спеціалістів Фізико-механічного інституту ім. Г.В.Карпенка НАН України. Тези доповідей. – Львів, 2000. – С. 122-123.

17. Литвин В.В., Шаховська Н.Б. Проблема координації інтелектуальних інформаційних систем. // Тези доповідей ІІІ Міжнародної науково-практичної конференції “Системний аналіз та інформаційні технології” “Сучасні технології в інформаційному суспільстві”. – Київ, 2001. – С. 77-81.

18. Виноградський Б.А., Кравець Р.Б., Литвин В.В. Метод класифікації для підтримки прийняття рішень у ігрових видах спорту. // ІІ Всеукраїнська науково-практична конференція “Науково-методичні аспекти тренування футболістів”. – Київ, 2001. – С. 40-43.

Анотації

Литвин В.В. Моделювання інтелектуальних інформаційних систем з індуктивною компонентою. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 – “Математичне моделювання та обчислювальні методи”. – Національний університет “Львівська політехніка”, 2002.

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

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

Литвин В.В. Моделирование интеллектуальных информационных систем с индуктивной компонентой. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 – “Математическое моделирование и вычислительные методы”. – Национальный университет “Львовская политехника”, 2002.

Диссертация посвящена вопросам моделирования интеллектуальных информационных систем с индуктивной компонентой. Сформулированы концептуальное и математическое определения интеллектуальной информационной системы с индуктивной компонентой, построена ее структурная и функциональная модели. Сформулированы основные подходы к повышению эффективности функционирования интеллектуальной информационной системы с индуктивной компонентой. Применено математический аппарат теории координации и фильтрации информации к решению задач повышения эффективности функционирования интелектуальной информационной системы с индуктивной компонентой, что позволяет улучшить объективные характеристики таких систем. Разработан двухэтапный метод поиска решений на основе введенной модели. Сформулированы основные подходы к повышению эффективности та управляемости процесса проектирования и разработки интеллектуальных информационных систем с индуктивной компонентой путем использования объектно-ориентированных методологий. Разработана информационная система автоматизации управления учебным процессом “Школа”, которая отображает результаты научных исследований.

Ключевые слова: интеллектуальные информационные системы, продукционная модель, индуктивная модель, многоуровневые информационные системы.

Lytvyn V.V. Modelling of intelligent information systems with inductive component. – Manuscript.

Thesis for a Ph.D. science degree by specialty 01.05.02 – “Mathematical modeling and calculating methods”. – National university “Lvivska Polytechnika”, Lviv, 2002.

The thesis is dedicated to problem of intelligent information systems with inductive component modeling. Author has formulated conceptual and mathematical definition of intelligent information systems with inductive component. Author has proposed main approaches to efficiency increase of intelligent information systems with inductive component that allow objective characteristics improving of such systems. The two-stage solution search method was built based on developed models. Main approaches to intelligent information systems with inductive component design and development process efficiency and controllability increase using object-oriented methodology has been defined.

In the Chapter 1 we construct of intelligent information system with inductive component structural and functional models based on production system. The task of inductive component consists of productions and heuristic functions sets modification using acquired experience. Author pays the main attention to the relevant operator choose as a stage of such system functioning. Due to the inductive component the relevant operator choose process has a hierarchical nature, namely layer hierarchy. The main characteristics of system proposed by author and production system are compared in this chapter.

The Chapter 2 includes problem solving management process modeling based on intelligent information system with inductive component formal structural and functional models. Intelligent information system with inductive component performance increase problem is formulated and researched. This problem consists of redundant operators use minimization. It has been showed the problem is equivalent to the search space dimensionality reduction. Inductive component realize this task. The problem is considered from two points of view: qualitative (due to the knowledge and metaknowledge sets modification) and quantitative (due to the irrelevant operators reduction using information filtering). Intelligent information system functioning coordination is researched because of hierarchical nature of relevant operator choose. Also this chapter includes research of information filtering for search space dimensionality reduction and two-stage relevant operator choose method.

The Chapter 3 contains author's research of main approaches to intelligent information system with inductive component modeling based on facilities typical to the object-oriented methodology. The aspects of object-oriented methodology use on system analysis, design and development stages are analyzed. Relation