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

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

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ ІНСТИТУТ КІБЕРНЕТИКИ ім. В.М.Глушкова

БЛИЩИК Володимир Федорович

УДК 519.83

ПСЕВДОБУЛЕВІ ТЕОРЕТИКО-ІГРОВІ МОДЕЛІ З ПРЕЦЕДЕНТНОЮ ПОЧАТКОВОЮ ІНФОРМАЦІЄЮ І ЇХ ЗАСТОСУВАННЯ У СИСТЕМАХ ПІДТРИМКИ ПРИЙНЯТТЯ РІШЕНЬ

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

Автореферат

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

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

Київ - 2007

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

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

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

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

ДОНСЬКОЙ Володимир Йосипович,

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

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

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

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

в.о. зав. Відділу Інституту телекомунікацій та глобального інформаційного простору НАН України, м. Київ,

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

ГОРБАЧУК Василь Михайлович

старший науковий співробітник Інституту кібернетики ім. В.М.Глушкова НАН України, м. Київ.

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

З дисертацією можна ознайомитись в науково-технічному архіві Інституту кібернетики ім. В.М. Глушкова НАН України, 03187, м.Київ, просп.академіка Глушкова, 40.

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

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

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

Актуальність теми.

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

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

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

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

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

Дисертаційна робота виконана відповідно до плану науково-дослідної роботи кафедри інформатики Таврійського національного університету ім.В.І.Вернадського по держбюджетній тематиці на 2001-2004 pp. "Розробка гібридної універсальної програмної оболонки для побудови експертних систем й логічних систем підтримки прийняття рішень", номер державної реєстрації роботи 0102U001575. А також на 2005-2007 pp. "Створення гібридних математичних моделей й алгоритмів для рішення задач оптимізації на основі неповної інформації", номер державної реєстрації роботи 0105U002407.

Мета дисертаційної роботи

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

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

Розробити методи розв'язання зазначеного класу антагоністичних ігор,заданих в умовах часткового(прецедентного) задания платіжної функції;

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

Розробити й реалізувати підхід до використання зазначених вище класівтеоретико-ігрових моделей у комп'ютерних системах підтримки й прийняттярішень (ППР).

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

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

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

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

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

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

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

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

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

Наукова новизна отриманих результатів.

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

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

Методи редукції матричних ігор з булевими стратегіями (побудова LQ-iгop)і їх розв'язання.

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

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

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

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

Принципи використання псевдобулевих теоретико-ігрових методів вінформаційних системах підтримки прийняття рішень та їхня реалізація прирозробці програмних комплексів "ТриОЛь" й "IntMan".

Практичне значення отриманих результатів дисертаційної роботи складається з можливості застосування розроблених у ній алгоритмів синтезу й прийняття рішень у рамках теоретико-ігрового підходу для побудови інтелектуалізованих інформаційних систем, виявлення схованих структурних закономірностей у даних, побудови логічних описів класів об'єктів у вигляді диз'юнктивних нормальних форм. Зокрема, як результат розв'язання практичної задачі, в дисертації побудована теоретико-ігрова модель, що описує міжнаціональні відносини і дозволяє шукати компромісні рішення. Ця задача виграла конкурсний грант АРК №1191-4/05 в 2005 р. і була вирішена автором.

Особистий внесок

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

Апробація результатів дисертації

Результати роботи доповідалися й обговорювалися на Міжнародній науковій конференції "Інтелектуалізація обробки інформації" (Алушта, 2000, 2002, 2004, 2006 pp.); Міжнародній науковій конференції "On Problems of Decision Making and Control under Uncertainties" (Алушта, вересень, 2003, 2006 pp.); на Ломоносовських читаннях (Севастополь, 2005); на конференції молодих учених й фахівців (Кримський науковий центр, НАН України, 2005, Сімферополь); на наукових конференціях професорсько-викладацького складу факультету математики й інформатики Таврійського національного університету ім. В.І. Вернадського (2002-2006 pp.).

Публікації

Наведені результати відбиті в 10 публікаціях, серед яких 4 статті в наукових виданнях зі списку наукових кваліфікаційних видань України, затверджених ВАК України; 5 публікації в тезах наукових конференцій, 1 стаття в міжнародному науковому журналі "Економічна кібернетика".

Структура й об'єм роботи

Зміст роботи викладений у рукопису, що складається з 114 сторінок, 18 малюнків, 7 таблиць. Дисертаційна робота містить у собі вступ, чотири розділи, висновок і список використаних джерел з 104 найменувань.

ОСНОВНИЙ ЗМІСТ ДИСЕРТАЦІЇ

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

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

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

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

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

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

Позначимо f₁,…,f_l набір функцій алгебри логіки:

Означення 1.8. Функції (1) називаються логічними описами класів (ЛОК) значень функції виграшу для ігор

Означення 1.9. Ситуації у грі

називаються еквівалентними, якщо вони обидві належать тій самій множині із сукупності

Означення 1.10. Контролюючою стратегією першого (другого) гравця в грі для класуназивається такий набір значеньзмінних x₁,…,x_m( y₁,…y_n), що

Теорема 1.2. У грідва гравці одночасно можуть мати контролюючі стратегії тільки для одного й того ж єдиного класу.

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

Наслідок 1.1. Якщо інтервал N_K рангувідповідний кон'юнкції

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

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

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

Теорема 1.4. Будь-яка проста імпліканта ЛОК f_j є мінімальною контролюючою кон'юнкцією першого (другого) гравця тоді й тільки тоді, коли в ній не утримуються змінні y₁,…y_n(x₁,…,x_m).

Теорема 1.5. Для того, щоб гра мала сідлову точку, досить, щоб обоє гравців мали контролюючу стратегію.

Зауваження 1.2. Умова теореми 1.6 не є необхідною.

Приводиться приклад до зауваження 1.2.

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

Звертається увага на проблеми розмірності вихідної гри, вводиться поняття LQ-гри.

Функція ЛОК може бути подана у вигляді ортогональної ДНФ а кожна кон'юнкція в цієї ДНФ в загальному випадку у вигляді добутку двох елементарних кон'юнкцій

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

В отриманому списку міститься по d кон'юнкцій видуЯкщо в

зазначеному списку містяться однакові кон'юнкції, то з однакових треба залишити тільки одну. У підсумку залишиться d₁ кон'юнкцій видуй d₂ кон'юнкцій виду

Перейдемо до матричної гри d₁xd₂ в якій рядки будуть відповідати стратегіям першого гравця, які визначають кон'юнкції Стовпці в матричній грі будуть відповідати стратегіям другого гравця, обумовленим кон'юнкціями Побудована матрична гра називається LQ-грою.

Означення 1.14. Перехід до LQ-irop називається редукцією ігор з булевими стратегіями.

Розробляється редукція вихідної гри методом зведення до LQ-гри.

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

Вибір числа l класів еквівалентності значень функції виграшу.

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

Виявлення контролюючих стратегій.

Перехід до матричної LQ-гри, якщо рішення на основі контролюючихстратегій одержати не вдається.

Перехід до змішаного розширення матричної LQ-гри, якщо вона не маєрішення в чистих стратегіях.

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

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

Позначимо T_k - множину наборів з B^m+n для яких задані значення (невідомої повністю) платіжної функції H. Потрібно знайти розбивку множини T_k на заздалегідь невідоме числопідмножин M₁,…M_l щоб для заданоговиконувалась наступна властивість: якщоі то значеннявідрізняються не більше, ніж; на Будемо називати таку властивість розбивкивластивістю -діаметрів класів.

Алгоритмпобудови розбивки множини T_k, який задовольняє властивості -діаметрів класів

Вхід: Множина T_k, значеннячисло

Вихід: Розбивка T_k на деяке число l підмножин (класів)

Упорядкувати елементи множини

Покласти число класів

3. t := t+1; якщо t>k, то перейти до п.6.

Нехай вже побудовані класи M₁,…,M_l. Вибрати черговий булев набірЯкщо знайдеться клас M_j такий, що для всіхвиконуєтьсянерівність то у протилежному випадкучисло класів збільшується:

Перейти до п.2.

Кінець.

Зазначимо ряд властивостей алгоритму

забезпечує розбивку множини T_k на заздалегідь невідоме, але залежне від заданої точностічисло класів l.

Для будь-яких двох елементівз того самого класу виконуєтьсянерівність

Алгоритм не визначає властивості булевих векторів, поєднуваних в одинклас, у термінах логічних змінних x₁,…,x_m,y₁,…,y_n а здійснює розбивкутільки за властивістю близькості значень платіжної функції.

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

1. Якщо для ситуаціїто ця ситуація одержує оцінкуплатіжної функції

2. Елементи множини апроксимуючих значень платіжної функції взаємнооднозначно відповідаютьелементам розбивки множини вершин-мірного куба класів в просторі змінних гри;

3. За побудованим деревом DT шляхом виконання алгоритму переглядугалузей знизу нагору від листів до кореня з оцінкою тимчасової складності легко знаходяться ДНФ, що описують побудовані класи значень платіжної функції в просторі змінних гри. Ці ДНФ являють собою ЛОК, використовуючи які виписується гра

Умова побудови бінарного дерева рішень із мінімальним числом листівприводить до мінімізації сумарного числа LQ кон'юнкцій, тобто розмірностіLQ-гри

По заданому дереву матриця LQ-гри може бути побудована зполіноміальною часовою складністю

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

Наслідок 2.1. Обумовлене алгоритмом DT значенняплатіжної функції з імовірністю більшої 1 -- 5 не буде відрізнятися від істинного значенняна величину

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

1. Задати початкову інформацію про груу вигляді множини пар (ситуація,значення платіжної функції). Задати числовий параметрдля визначення-діаметрів класів. Задати оцінки таких, щодля всіх

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

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

Сформувати навчальну вибірку дляподальшого синтезу алгоритму розпізнавання властивості

Синтезувати алгоритм, що розпізнає, - бінарне розв'язуюче дерево DT,використовуючи навчальну вибірку

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

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

Якщо в п.7 рішення гри не знайдено, побудувати LQ-rpy.

Якщо LQ-rpa має рішення в чистих стратегіях, видати це рішення якостаточну відповідь.

10. Якщо LQ-rpa не має рішення в чистих стратегіях - перейти до змішаного розширення LQ-гри й знайти рішення цієї гри в змішаних стратегіях.

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

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

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

Визначимо багатокрокову грузі стратегіями послідовного вибору гравцями по одній ЕС по черзі, вважаючи, що длявідома платіжна LQ-матриця.

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

Означення 3.1. Операцією видалення елементарної складової називається підстановка значення якої-небудь однієї змінної в усі ЛОК

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

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

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

Означення 3.3. Кон'юнкція К першого (другого) гравця в-грі називається умовно-контролюючої, якщо в матриці цієї-гри всі значення у відповідному цієї кон'юнкції К рядку (стовпцю) однакові й рівні h(K)] величина h(K) називається ціною умовно-контролюючої кон'юнкції.

Означення 3.4. Умовно-контролююча кон'юнкція першого (другого) гравця з найбільшої (найменшої) ціною називається найкращої.

Теорема 3.2.

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

Якщо у вихідній LQ-грі обидва гравці мають умовно-контролюючікон'юнкції й L* і Q* найкращі з них, то в грі гравці можутьзабезпечити собі виграш, рівний h(L*,Q*); при цьому пара (L*,Q*) єсідловою точкою вихідної LQ-гри.

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

Наслідок 3.1. Якщо вихідна LQ-rpa має сідлову точку й ціну h* і перший (другий) гравець має найкращу умовно-контролюючу кон'юнкцію з ціною

то він забезпечує собі виграш не менший (не більший) значення h* ціни вихідної LQ-гри.

Алгоритмрішення багатокрокової гри

1. Якщо вихідна LQ-rpа, має сідлову точку, знайти її й визначити ціну гри h*.

2. Якщо існують найкращі умовно-контролюючі кон'юнкції першого (другого)гравця з ціною то виконувати операцію

: привласнюючи елементарним складовим своєї найкращої умовно-контролюючої кон'юнкції послідовно (і в будь-якому порядку) значення:При цьому кроки супротивника можуть бути будь-якими.

3. Якщо сідлової точки у вихідної LQ-rpi немає, але умовно-контролюючікон'юнкції є в одного гравця з найкращою ціною /іук, ухвалити рішеннящодо достатності виграшу /іу_К і реалізувати стратегію, яка відповідаєнайкращій умовно-контролюючій кон'юнкції.

4. Якщо умовно-контролюючих кон'юнкціі немає в обох гравців, то виконуватиоптимальні кроки у такий спосіб. Оскільки кожен крок, відповідно дотеореми 3.1, приводить до викреслювання деяких рядків або стовпцівплатіжної матриці, то розглянути всі можливі кроки (їх число буде небільше, ніж; подвоєна сума рангів L або Q кон'юнкцій). При виборі кожногокроку оцінюється гарантований виграш і реалізується оптимальний крок.

Розглядається антагоністична гра: в якій булеві вектори, що складаються з набору змінних, доступних тільки першому гравцеві, наступного видувизначають 2ⁿ стратегії, а булеві вектори визначають 2^m стратегії другого гравця, при цьому в грі задана множина змінних які можуть бути обрані обома гравцями. Значення змінноїбудемо називати незафіксованим і позначатиякщо воно не обрано жодним із гравців. Якщо гравець вибирає одну зі зміннихто він фіксує її значення рівним 0 або 1, і воно стає недоступним другому гравцеві. Функція називається платіжною функцією в грі і її значення відповідає виграшу першого гравця або програшу другого. Визначену в такий спосіб гру назвемо грою з перехопленням.

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

У розділі 4 дисертаційної роботи розглядаються алгоритмічні питання реалізації теоретико-ігрових моделей у системах підтримки прийняття рішень і експертних систем; наводиться базова ієрархія класів (рис. 1), що є батьківською при об'єктно-орієнтованому програмуванні всіх теоретико-ігрових моделей, використовуваних у програмних комплексах IntMan (Intelligent Management) і ТриОЛь (комплекс використовує оптимізаційно-логічну (ОЛ) схему прийняття рішень, засновану на побудові областей дедуктивної виводимості, індуктивної виводимості й виводимості за аналогією (ТРИ)).

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

У висновку наводяться підсумки дисертаційної роботи.

ВИСНОВКИ

В роботі отримані наступні основні результати.

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

Розроблені методи редукції (скорочення розмірності) матричних ігор збулевими стратегіями на основі поняття LQ -ігор, побудованих након'юнкціях, які містять керуючі змінні тільки першого (L-кон'юнкції) ітільки другого (Q-кон'юнкції) гравців. Наведено алгоритм переходу доLQ-irop й їхнього розв'язання.

Розроблений підхід до визначення класів значень платіжної функції приїї частковому заданні прецедентною інформацією на основі нового алгоритму розбивки за властивістю-діаметрів. Цей алгоритм покладенийв основу довизначення частково невідомої псевдобулевої платіжної функціїна всю галузь BⁿxB^m можливих ігрових ситуацій.

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

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

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

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

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

Розроблене програмне забезпечення для теоретико-ігрових підсистем упрограмних комплексах Intman й ТриОль.

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

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

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

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

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

[1 ] Блищик В.Ф. Решение игр с булевыми стратегиями и неполной информацией на основе синтеза ДНФ// Искусственный интеллект. - 2000. -№ 2. - С.9-12.

[2 ] Блищик В.Ф. Решение игр с булевыми стратегиями и неполной информацией на основе синтеза ДНФ// Международная научная конференция. Интеллектуализация обработки информации. ИОИ'2000. Тезисы докладов. - Симферополь: ТНУ им. В.И.Вернадского, 2000. -С.13-14.

[З ] Блыщик В. Ф. Принятие и визуализация решений при последовательном выборе действий в матричной игре с булевыми стратегиями// Interna-tional Conference. Problems of Decision Making under Uncertainties (PDMU-2003).Abstracts. - Alushta (Ukraine). 2003. - C.74-76.

[4 ] Блыщик В. Ф. Игры двух лиц с булевыми стратегиями и множеством переменных перехвата// Таврический вестник информатики и математики. - 2004. - № 1. - С.40-47.

[5 ] Блыщик В.Ф. Методы построения классов значений платежной функции по прецедентной начальной информации// International Conference. Prob-lems of Decision Making under Uncertainties (PDMU-2003).Abstracts. - Alushta (Ukraine) 2006. - C.74-76.

[6 ] Блыщик В. Ф. Алгоритм построения классов значений платежной функции по прецедентной начальной информации// Искусственный интеллект. -2006. - № 2. - С.10-13.

[7 ] Блыщик В.Ф. Классификация матричных игр с частично-заданной платежной функцией// Международная научная конференция. Интеллектуализация обработки информации. ИОИ'2006. Тезисы докладов. - Симферополь: ТНУ им. В.И.Вернадского, 2006. - С.24-26.

[8 ] Блыщик В.Ф., Донской В.И., Минин А., Махина Г.А. Интеллектуализированная программная система intman поддержки принятия решений в задачах планирования и управления// Искусственный интеллект. - 2002. - С.406-415.

[9 ] Блыщик В.Ф., Донской В.И., Минин А., Махина Г.А. Программная реализация моделей поддержки принятия решений при неполной информации// Международная научная конференция. Интеллектуализация обработки информации. ИОИ'2002. Тезисы докладов. - Симферополь: ТНУ им. В.И.Вернадского, 2002. - С.109.

[10 ] Блищик В.Ф., Сигал А.В. Антагонистическая игра, заданная в условиях частичной неопределенности// Економічна кібернетика. Міжнародний науковий журнал. - 2005. - №5-6(35-36). - С.47-53.

АНОТАЦІЇ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Blyschik V.F. Pseudo-Boolean game theoretical models with the precedent initial information and their usage in decision making systems. - Manuscript.

Thesis for a candidate degree by specialty 01.05.01 - Theoretical bases of informatics and cybernetics. Glushkov Institute of Cybernetics NAS Ukraine, Kiev, 2007.

The dissertation is devoted to the exploration of Pseudo-Boolean game theoretical models with Partial information about payoff function and their usage in decision making systems.

The Methods of analysis, reduction and general scheme of decision of Zero-Sum games with Boolean strategies and payoff function on the basis of logic algebra and disjunctive normal forms theory were developed. The way of empirical generalization of the precedent initial information about payoff function based on decision tree learn-ing algorithms was proposed. The method of the probability error was developed. The new statement of Pseudo-Boolean game decision method with consecutive choice of player actions was proposed. The class hierarchy, which allows embed the game the-oretical models with Boolean strategies in decision making computer systems of was described. On the basis of given basic class hierarchy game theoretical subsystems were developed in software, allowing to choose optimal solutions when exists undefined and contradictory factors in cases of partial initial information. Experiments with real data were held.

Key words: Zero-Sum Game with Boolean strategies, partially given payoff func-tion, payoff function values classes, Logical class description, LQ-game, elementary component, multi-step game, decision making systems.

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

...