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

Національна академія наук України

Інститут кібернетики імені В.М. Глушкова

УДК 519.8

Автореферат

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

кандидата фізико-математичних наук

СИНТЕЗ ДИСКРЕТНИХ МОДЕЛЕЙВИБОРУ РІШЕНЬ НА ОСНОВІ ЗНАНЬ

01.05.01 - теоретичні основи інформатики та кібернетики

КОЗЛОВА Маргарита Геннадіївна

Київ - 2002

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

Роботу виконано в Таврійському національному університеті імені В.І. Вернадського, Міністерство освіти і науки України.

Науковий керівник: доктор фізико-математичних наук, професор

ДонськОй Володимир Йосипович,

Таврійський національний університет імені В.І. Вернадського, завідувач кафедри інформатики.

Офіційні опоненти:доктор фізико-математичних наук, професор

ГУПАЛ Анатолій Михайлович

доктор фізико-математичних наук

ПОЛУМІЄНКО Сергій Костянтинович

Провідна установа:Київський національний університет імені Т. Шевченка, факультет кібернетики, Міністерство освіти і науки України, м. Київ.

Захист відбудеться 22 лютого 2002 р. об 11.00 годині на засіданні спеціалізованої вченої ради Д_26.194.02 при Інституті кібернетики імені В.М. Глушкова НАН України за адресою: м. Київ, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитись в науково-технічному архіві інституту.

Відгук на автореферат просимо надсилати за адресою: м. Київ, проспект Академіка Глушкова, 40, Інститут кібернетики імені В.М. Глушкова НАН України, вченому секретарю спеціалізованої вченої ради Д 26.194.02.

Автореферат розісланий 17 січня 2002 р.

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

спеціалізованої вченої радиСинявський В.Ф.

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

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

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

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

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

Зв'язок із науковими програмами і планами. Дисертаційну роботу виконано відповідно до плану науково-дослідної роботи кафедри інформатики Таврійського національного університету ім. В.І. Вернадського по держбюджетній тематиці на 1996-2000 р. “Розробка математичних моделей і методів інтелектуалізації прийняття рішень в інформаційних системах”, № реєстрації 0197U001968

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

Для досягнення поставленої мети в роботі вирішуються такі основні задачі:

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

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

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

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

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

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

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

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

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

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

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

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

У статті [2] Донському В.Й. належить вибір напряму роботи і постановка задачі. Особистий внесок здобувача полягає в побудові процедури витягу інформації: розроблено алгоритм, наведено приклади. У статті [5] самостійно на підставі канонічної моделі прийняття рішень із диз'юнктивним обмеженням введено поняття множини П(А) паретівського типу, що є описанням області невизначенності, а також розроблено алгоритм його синтезу на основі доведених теорем. У статтях [7, 9] опубліковані самостійно отримані результати, крім результатів, що відносяться до неперервних моделей оптимізації з неповною інформацією, які належать співавторам.

Апробація результатів роботи. Результати роботи доповідалися й обговорювалися на

- VI Міжнародній конференції “Знания - Диалог - Решения” (Ялта, вересень 1997 р.);

- II і III Міжнародних наукових конференціях “Интеллектуализация обработки информации” (Алушта, 1996, 2000 р.);

- Міжнародній науковій конференції “Штучний інтелект” (Кацівелі, 2000 р.);

- на Кримському науковому семінарі при кафедрі інформатики (керівник професор Донський В.Й.),

- на наукових професорсько-викладацьких конференціях математичного факультету Таврійського національного університету ім. В.І. Вернадського (1999, 2000 р.);

- на засіданні наукового семінару “Програмологія та ії застосування” факультету кібернетики Київського національного університету ім. Т. Шевченка (19 квітня 2001 р., Київ).

Публікації. За темою дисертації опубліковано 10 робіт [1-10], серед яких 3 статті - в наукових виданнях із списку наукових кваліфікаційних видань України, затверджених ВАК України; 3 статті - в наукових журналах і збірниках наукових праць; 4 публікації - у тезах наукових конференцій.

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

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

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

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

Поряд із цим приводяться необхідні результати робіт Н. Нільсона по І/АБО графах і В.Й._Донського по логічним продукційним системам, які є підкласом дедуктивних систем (підрозділ 1.2), що використовуються при побудові орієнтованих на знання моделей при моделюванні і розв'язанні дискретних задач оптимізації.

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

Розділ 2 дисертаційної роботи присвячено питанню синтезу моделей дискретної оптимізації на основі продукційних баз знань. Сформульовано вимогу до бази знань (БЗ) системи прийняття рішень. Запропоновано схему рішення орієнтованих на знання задач із неповною інформацією. Отримано методи витягу додаткової інформації та оцінки складності задач синтезу області припустимих рішень.

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

У загальному виді однокритеріальні псевдобулеві моделі.

Будь-яку задачу скалярної псевдобулевої умовної оптимізації можна подати в канонічній формі з диз'юнктивним обмеженням. Ліва частина єдиного обмеження є диз'юнктивною нормальною формою (ДНФ) характеристичної функції множини W?. Канонічна модель існує для будь-якої задачі у формі (1) і в цьому значені є повною. Показано, що якщо існує логічна система продукцій (ЛСП), що дозволяє виводити цільовий факт - припустиме рішення”, тоді обмеження канонічної моделі еквівалентно ЛСП (3) і І/АБО графу Нільсона спеціального вигляду.

Сформульовано вимогу до БЗ системи прийняття рішень. Якщо рішення повинні задовольняти деяким обмеженням, то ЛСП повинна забезпечувати можливість виводу цільових предикатів, що відповідають цим обмеженням. Група обмежень, що повинні виконуватися одночасно, “описується” вершиною типу “І”, “що пов'язує” ці обмеження (відповідні цільові предикати) в одне ціле. Питання повноти знань про обмеження в БЗ є важливим, і воно виділяється окремо в теорії орієнтованих на знання систем.

Для синтезу ДНФ по заданим ЛСП запропоновано використовувати D- і DS-алгоритми, що реалізують, відповідно стратегії “зверху вниз” і “знизу вверх”, що потребує додаткового дослідження їхньої складності та інших властивостей.

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

У підрозділі 2.4. роботи уточнені оцінки складності D- і DS- алгоритмів синтезу області припустимих рішень. Розглянута задача з диз'юнктивним обмеженням в каноничній формі.

У розділі 3 дисертаційної роботи досліджується синтез критеріїв вибору рішень задач, орієнтованих на знання. У підрозділі 3.1. розглянуті питання подання знань про псевдобулеві функції в базі знань системи прийняття рішень. Оскільки кожну псевдобулеву функцію можна подати у вигляді полінома над полем дійсних чисел, тоді будь-яка цільова функція в канонічній моделі “улаштована” “не складніше” за поліном, тому можна використовувати такі знання про неї: лінійність (нелінійність); знаки коефіцієнтів цільової функції (додатність, від'ємність або нуль-важливий випадок, що вказує на невходження змінної в цільову функцію); значення функції в деяких точках. Цю інформацію можна вважати знаннями, які мають вигляд фактів - початкових істинних предикатів. Таким чином, порівняно “невелика кількість знань” про цільову функцію канонічної моделі в деяких випадках дозволяє одержати точне рішення (екстремальний набір).

Алгоритми прийняття рішень у випадку з початковою інформацією про лінійність і знаки коефіцієнтів цільової функції розглянуто в підрозділі 3.2.

Будемо вважати, що інформація про цільову функцію F у канонічній моделі (6) подана лише наступними достовірними знаннями: F - лінійна функція, і для кожного є істинним тільки один із трьох предикатів: “”, “”, “”. Без обмеження загальності, вважаємо, що відшукується максимум функції F. Позначимо N_j - інтервал, що складається з усіх булевих наборів, на яких j-та кон'юнкція ДНФ-обмеження канонічної моделі перетворюється на одиницю. Область припустимих рішень задачі має вигляд . Екстремальне рішення в кожному інтервалі досягається в будь-якій точці , що задовільнює наступній умові. Якщо то для кожного :

(7)

де - довільне значення.

Далі введено визначення 3.1 мажорування точок за критерієм F.

Припустимо, знайдено множини екстремальних точок у кожному інтервалі. Позначимо їх . Будь-яка точка задовільнює умові (7). Усі точки множин за критерієм F рівноцінні (значення однакові для ).

Далі введено визначення 3.2 A-паретівською підмножини.

A-паретівська множина легко обчислюється шляхом попарних порівнянь точок із A з урахуванням очевидної транзитивності відношення . Позначимо A-паретівську множину П(A).

Теорема 3.2. Якщо A-паретівська множина цілком міститься в деякому інтервалі , що відповідає j-ій кон'юнкції достовірного ДНФ-обмеження, то точки, які належать до неї, вичерпують всі екстремальні рішення задачі (6), незважаючи на неповноту початкової інформації.

Умова теореми 3.2 є достатньою для точного знаходження рішення задачі (6) із зазначеною вище початковою інформацією (знаннями) про цільову функцію. Але воно, взагалі, може не виконуватися. На основі початкової інформації віддати перевагу одній із двох точок із A-паретівської множини неможливо, тому що вони не задовільнюють відношенню . Необхідно залучення додаткової “звужуючої” інформації (додаткових знань).

Алгоритм рішення розглянутих задач у загальному випадку буде таким:

1^о. Відшукується множина П(A).

2^о. Перевіряється достатня умова можливості розв'язання з теореми 3.2.

3^о. Якщо ця умова виконується, то всі екстремальні рішення вичерпуються множиною точок П(A), і рішення закінчується.

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

5^о. Якщо додаткових знань досить для вибору екстремальних рішень, то видається точна відповідь, інакше видається A-паретівська множина як набір альтернатив для остаточного вибору ОПР.

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

Для моделей, описаних вище, порівняння пар точок із П(A) приводить до нерівностей . Нерівність такого виду можна використовувати для видачі еквівалентних запитів. Для прийняття рішення досить відповіді експертів на будь-який із цих запитів по k-ому порівнянню. Такі запити будемо називати “звужуючими”.

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

Початкову інформацію подано у вигляді частково заданої характеристичної граничної функції , що перелічує m булевих наборів, для яких відомо: значення () більше або не більше нуля ( - деяке число).

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

Визначення 3.3. Псевдобулева функція f називається додатною за змінною , якщо для будь-яких булевих наборів і таких, що хеммінгова відстань між ними і , виконується: .

Лінійна псевдобулева функція додатна (від'ємна) за змінною тоді і тільки тоді, коли ().

Далі введено визначення 3.4 та 3.5 для характеристичної граничної функцією лінійної псевдобулевої функції f та характеристичної граничної функції довільної псевдобулевої функції f.

Теорема 3.3. Лінійна псевдобулева функція f додатня (від'ємна) за змінною тоді і тільки тоді, коли змінна є істотною для характеристичної функції , але не входить ні в яку просту імпліканту булевої функції з інверсіями (без інверсій).

Теорема 3.4. Нехай f - довільна псевдобулева функція і - її характеристична гранична функція. Якщо знайдеться пара простих імплікант функції таких, що деяка змінна входить до однієї з них з інверсією, а до другої - без інверсії, тоді f - нелінійна функція.

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

Ця інформація представляється булевою таблицею з m рядків і n+1 стовпців; останній стовпець містить значення цільового предиката “ - вище за середнє”. Таблиця задає часткову функцію , що збігається зі значеннями істинної (але невідомої) характеристичної граничної функції в точках.

1⁰. Побудувати всі максимальні для інтервали поза “нулями” функції і відповідні їм прості імпліканти.

2⁰. Перевірити умови теореми 3.3 для всіх . Якщо для деякої змінної ця умова виконується, то встановлюється, що невідома цільова функція лінійна за цією змінною і з'ясовується знак відповідного коефіцієнта . Якщо виконується умова теореми 3.4, то досліджувана цільова функція - нелінійна.

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

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

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

У таких випадках їхнє приведення до форми з диз'юнктивним обмеженням може виявитися складною і навіть поліноміально нерозв'язною задачею.

Розглянемо таку задачу

(9)

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

Запропонований метод використовує необхідну умову належності точки множині Парето і принципу гілок і межей.

Позначимо множину номерів змінних, які мають додатний, а - множина номерів змінних, які мають від'ємний коефіцієнт у лінійній функції . Нехай і .

Далі доведена лема 3.1. Якщо для задачі безумовної багатокритеріальної оптимізації

(10)

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

(11)

Зауваження 3.1. Якщо і , то необхідними умовами ефективності точки в задачі (10) є і . Якщо і , то необхідною умовою ефективності точки в задачі (10) є . Якщо і , то необхідною умовою ефективності точки в задачі (10) є .

Умова (11) не є достатньою. Це підтверджують наведені в роботі приклади.

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

Введено визначення 3.6 нижньою (верхньою) векторною оцінкою припустимої множини X та визначення 3.7 мажорування векторів

Введено визначення 3.8 рекорда.

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

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

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

Далі в роботі досліджуються задачі з диз'юнктивним обмеженням і метод гілок і межей.

Терема 3.5. Нехай у задачі (10) існує непуста множина Парето Р, і до даної задачі додається обмеження . Для отриманої задачі множина Р, якщо вона не пуста, буде складатися тільки з паретівських точок.

Зауваження 3.2. Умова {Р}, яка виходить з теореми 3.5, є достатньою для того, щоб точка була паретівською в задачі з обмеженням при {Р} . Однак ця умова не є необхідною.

Використовуючи теорему 3.5 і маючи множину Р для багатокритеріальної задачі безумовної оптимізації, можна знайти підмножину {Р} паретівської множини Р для задачі з умовою . Однак для пошуку всієї множини Р потрібне дослідження множини {\ Р}. Якщо множина Р знайдена і має логічне описання у вигляді ДНФ, то побудова множини Р для задачі з диз'юнктивним обмеженням зводиться до перемноження двох ДНФ.

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

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

Далі розглянуто питання вибору інтервалів і змінних для розгалуження.

У розділі 4 подано приклади практичного застосування методів прийняття рішень на основі знань, зокрема в п. 4.1 наведено структуру програмного комплексу “Таврида” прийняття оптимальних рішень на основі знань.

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

ВИСНОВКИ

Основні результати даної дисертації:

1. Отримано нові алгоритми синтезу цільових псевдобулевих функцій на основі знань.

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

3. Введено поняття множини П(А) паретівського типу, що є описом області невизначеності задачі.

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

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

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

7. Розроблено нові підходи до розв'язання багатокритеріальних задач псевдобулевої оптимізації з ДНФ-обмеженням.

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ

1. Козлова М.Г. Многокритериальные модели принятия решений с линейными псевдобулевыми функциями и дизъюнктивным ограничением // Искусственный интеллект. - 2000. - №2. - С. 67-73.

2. Донской В.И., Козлова М.Г. Извлечение знаний о свойствах целевой функции в логических системах поддержки принятия решений // Искусственный интеллект. - 2000. - №3. - С. 230-234.

3. Козлова М.Г. Синтез сужающих запросов // Динамические системы. Вып.16. - Симферополь: КФТ. - 2000. - С.208-211.

4. Козлова М.Г. Системы поддержки принятия решений в современной информатике // Программы, системы, модели. - Симферополь. - 1996. - № 2. - С. 40-45.

5. Донской В.И., Козлова М.Г. Модели принятия решений на основе знаний // Труды VI Международной конференции “Знание - Диалог - Решение”. - Киев: ИК НАНУ. - 1997. - С.336-343.

6. Козлова М.Г. Знаниеориентированные модели принятия оптимальных решений // Ученые записки Симферопольского государственного университета. - 1998. - № 7 (46). - С.76-83.

7. Лукьяненко В.А., Козлова М.Г. Системы поддержи принятия решений: представление и преобразование информации, оптимизационный подход // Тезисы докладов II Крымской Международной математической школы “Метод функций Ляпунова и его приложения”. - Сімферополь. - 1995. - С.29-30.

8. Козлова М.Г. Синтез дискретных моделей выбора решений на основе знаний // Тезисы докладов Международной научной конференции “Интеллектуализация обработки информации”. - Сімферополь. - 1996. - С.13-14.

9. Козлова М.Г., Руденко Л.И. О развитии подходов к принятию решений при неполной информации // Тезисы докладов IV Крымской Международной математической школы “Метод функций Ляпунова и его приложения”. - Сімферополь. - 1998. - С.57-58.

10. Козлова М.Г. Дискретные модели выбора решений на основе знаний // Тезисы докладов Международной научной конференции “Интеллектуализация обработки информации”. - Симферополь: Кр.НЦ НАНУ. - 2000. - С.36-37.

АНОТАНІЯ

Козлова М.Г. Синтез діскретних моделей вибора рішень на основі знань. - Рукопис.

Дисертація на здобуття наукового ступения кандидата фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики. - Інстітут кібернетики ім. В.М. Глушкова НАН України, Київ, 2001.

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

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

АННОТАЦИЯ

Козлова М.Г. Синтез дискретных моделей выбора решений на основе знаний. - Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики. - Институт кибернетики им. В.М. Глушкова НАН Украины, Киев, 2001.

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

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

ANNOTATION

Kozlova M.G. Synthesis of Discrete Models of Knowledge-Based Decision Choice. - The manuscript.

The dissertation for the Candidate of physical and mathematical science degree by speciality 01.05.01 - theoretical fundamentals of computer science and cybernetics - Institute of Computer Science named after V.M. Glushkov of National Academy of Science of Ukraine, Kyiv, 2001.

Investigation of decision-making (DM) problems with incomplete initial information represented in the form of knowledge, design of algorithms of DM discrete models synthesis on the base of knowledge and their representation in DM support systems as special subsystems were considered in the dissertation. New results were obtained in the dissertation. The notion of Pareto Type Set to be the description of uncertainty domain was introduced on the base of canonical DM model with disjunctive restrictions for the first time and the algorithm of its synthesis was worked out. The Method of Active Restricting Inquiries for Pseudo-Boolean optimization problem solving in canonical form was suggested and detailed. General basic principles of Restricting Inquiries Theory for construction of DM systems with incomplete information were developed studying the special case of Restricting Inquiries Method application. Methods of extraction of knowledge on the properties of Pseudo-Boolean objective function in the DM problems with incomplete information and algorithms of extracting such properties were worked out. Approach to solving of multicriteria Pseudo-Boolean problems with disjunctive restrictions was developed for usage in knowledge-based DM systems.

Key words: decision making, disjunctive restriction, canonical model, Pseudo-Boolean function, discrete optimization, extraction of knowledge, incompleteness, reliable information, models synthesis, algorithms, logical system of productions, Restricting Inquiry.

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

...