Лінійні дискретні ігрові задачі з розмитими множинами

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

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

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

Автореферат

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

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

ЛІНІЙНІ ДИСКРЕТНІ ІГРОВІ ЗАДАЧІ З РОЗМИТИМИ МНОЖИНАМИ

Виконала Онищенко Вікторія Валеріївна

Київ 2003

АНОТАЦІЯ

Онищенко В.В. Лінійні дискретні ігрові задачі з розмитими множинами. - Рукопис.

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

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

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

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

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

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

Виділено ситуацію, коли інформованість гравця, при виборі керування суперника, не грає ролі.

дискретність мінорантний мажорантний ігровий

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

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

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

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

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

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

Початок теоретичних досліджень теорії конфліктно керованих процесів веде з часу появи монографії Р. Айзекса. В основі досліджень Р. Айзекса покладено метод динамічного програмування, який приводить до основного рівняння теорії диференціальних ігор - рівняння Айзекса Беллмана для визначення ціни гри. Класична схема Айзекса докладно обгрунтована і посилена в роботах Л.С. Понтрягіна.

Побудові достатніх умов закінчення гри присвячені роботи Л.С. Понтрягіна, які були деталізовані для лінійного випадку і відомі як перший та другий прямі методи Понтрягіна. Зокрема, в другому методі використовується ідея поп'ятного руху від термінальної множини. Ідея другого методу Л.С. Понтрягіна - методу альтернованого інтегралу, була узагальнена для нелінійних диференціальних ігор Б.М. Пшеничним. Нижній альтернований інтеграл було введено М.С. Нікольським, а для дискретних систем аналог верхнього та нижнього альтернованих інтегралів Л.С. Понтрягіна були побудовані в роботах А.О. Чикрія.

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

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

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

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

Одним із перших кроків на шляху опису нечіткості можна вважати напрямок, пов'язаний з ім'ям американського математика Л.А. Заде, який отримав назву теорії розмитих (або нечітких) множин.

На протязі багатьох років дослідження в даній області були проведені не тільки Л. Заде, а і Р. Беллманом, Д. Гогеном, А. Кофманом, О.М. Аверкиним, О.М. Борисовим, О.В. Алексеевим, С.О.Орловським, Д.А. Поспеловим, І.В. Гайшуном, В.І. Ухоботовим, О.П. Ротштейном.

Зв'язок роботи з науковими програмами, планами, темами. Робота виконана у відповідності до завдань науково-дослідної роботи кафедри дослідження операцій факультету кібернетики Київського національного університету імені Тараса Шевченка: 97054 «Розробка статистичного аналізу марківських процесів. Вивчення топології на групах» (№ДР 0197U014611); 01БФ015-01 «Розвиток теорії і програмного забезпечення стохастичних та алгебраїчних систем із застосуванням в економіці, соціології, техніці та освіті» (№ДР 0101U002173); та відділу оптимізації керованих процесів Інституту кібернетики ім. В.М. Глушкова НАН України:

МФ 165.04 «Розробка, якісний аналіз та чисельна реалізація методів керування динамічними системами при наявності невизначеності та конфлікту» (№ДР 03014000635);

ВФ 165.02 «Аналітичні методи дослідження керованих процесів в умовах невизначеності» (№ДР 01984008067).

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

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

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

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

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

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

5. Виділити ситуацію коли інформованість гравця при виборі керування суперника не грає ролі.

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

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

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

Апробація результатів дисертації. Викладені в дисертації результати доповідались на ІІІ Всеукраїнській студентській науковій конференції з прикладної математики та інформатики (Львів, 10-12 травня 2000 р.), на Міжнародній конференції «Моделювання та оптимізація складних систем» (МОСС-2001), присвяченій 65-річчю від дня народження члена-кореспондента НАН України Б.М. Бублика (Київ, 25-28 січня 2001 р.), на Міжнародному симпозіумі (PDMU-2002) «Проблеми прийняття рішень та керування при нечіткості» (Київ-Канів, 14-20 травня 2002 р.).

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

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

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

={(x, _U(x)) },

де _U:[0,1] - називається функцією належності множини . Значення функції належності _U(x) для елементу хU будемо називати степенем належності.

Для множини А, АRⁿ розмита множина називається порожньою, якщо її функція належності дорівнює нулю.

Розмита множина Rⁿ нормальна, якщо верхня межа її функції належності дорівнює одиниці.

Якщо тоді розмиту множину називають субнормальною.

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

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

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

В підрозділі 2.1 подається загальна постановка нестаціонарної гри.

Вектори u(t), v(t) визначають керуючий вплив протидіючих сторін в t-й момент часу. Значення векторів x(t), u(t), v(t) в t-й момент часу визначають стан процесу в t+1-й момент часу.

Підрозділ 2.2 присвячений вивченню мажорантної гри, а в підрозділі 2.3 розглядається нестаціонарна лінійна дискретна мінорантна гра з розмитими по Заде множинами.

Отримані результати продемонструємо для мажорантної гри.

Отже розглянемо нестаціонарну лінійну дискретну мажорантну гру.

Введемо поняття множини досяжності. Нехай Z - довільна множина в Rⁿ. Множиною досяжності гравця Р за один крок з множини Z назвемо сукупність усіх таких точок, в кожну з яких гравець Р може забезпечити попадання із точок множини Z за один крок в силу системи при довільному керуванні гравця Е.

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

.

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

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

Нехай М, U(t), V(t) - опуклі замкнені обмежені носії розмитих множин з функціями належності. Тоді всі послідовності носіїв розмитих множин і опуклі замкнені обмежені.

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

Нехай носій розмитої множини повністю вимітає носії розмитих множин M і. Тоді носій розмитої множини повністю вимітає і всі носії розмитих множин , (t=0,1,…).

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

Третій розділ присвячений вивченню систем з пам'яттю.

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

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

Якщо носії розмитих множин М, U(t), V(t) з функціями належності - опуклі, замкнені та обмежені і носії послідовностей розмитих множин монотонні, то для їх аналітичного опису застосуємо опорні функції.

У четвертому розділі вивчаються системи з запізненням. Розглянемо диференціально-різнецеву ігрову задачу, як приклад гри з запізненням.

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

ВИСНОВКИ

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

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

2. Одержано розв'язок дискретного аналогу рівняння Вольтерра та диференціально-різницевого рівняння.

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

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

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

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

7. Виділено ситуацію коли інформованість гравця при виборі керування суперника не грає ролі.

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

1. Онищенко В.В. Линейная дискретная игра с нечеткими по Заде параметрами // Кибернетика и вычислительная техника. - Киев: 1999. - Вып. 125. C. 35-64.

2. Онищенко В.В. Лінійні дискретні ігри з областями керування та термінальною множиною, розмитими по Заде // Вісн. Київ. Ун-ту. Cерія: фіз.-мат. Науки. - 1999. -Вип. 3. - С.243-250.

3. Онищенко В.В. Применение размытых по Заде множеств для решения игровых задач // Теория оптимальных решений: Сб. науч. тр. НАН Украины. Ин-т кибернетики им. В.М.Глушкова. - Киев. - 2000. - С. 24-30.

4. Онищенко В.В. Лінійні дискретні ігрові задачі з розмитими по Заде множинами // Вісн. Київ. ун-ту. Серія: фіз.-мат. науки. - 2000. - Вип.4. - С. 275-284.

5. Онищенко В.В. Лінійні дискретні ігрові задачі з розмитими по Заде множинами. // Тез. доп. Міжнар. наук. конф. «Моделювання та оптимізація складних систем» (МОСС-2001), К.: Видавничо-поліграфічний центр «Київський університет» - 2001.-Т. 1. - С. 94-97.

6. Онищенко В.В. Диференціально-різницеві ігрові задачі з розмитими по Заде множинами // Тез. доп. Міжнар. симп. (PDMU-2002) «Проблеми приняття рішень та керування при нечіткості», К.: Видавничо-поліграфічний центр «Київський університет» - 2002. - С. 84.

7. Onyshchenko V. Game problems described by linear discrete Volterra equations with fuzzy sets. // Тез. доп. Міжнар. конф. з прикладної математики, присвяченої пам'яті Б.М.Пшеничного, К.: Видавництво НТУУ «КПІ» - 2002. - С. 107-108.

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