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

Кравець Петро Олексійович

УДК 518.90:519.95

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

В УМОВАХ НЕВИЗНАЧЕНОСТІ

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

АВТОРЕФЕРАТ

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

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

Львів-2000

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

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

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

Науковий керівник: доктор технічних наук

Пасічник Володимир Володимирович,

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

завідувач кафедри “Інформаційні системи та мережі”

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

Грінченко Тамара Олексіївна,

Інститут прикладної інформатики,

завідувач лабораторії гіпертекстових систем

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

Яцимірський Михайло Миколайович,

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

доцент кафедри “Електронні обчислювальні машини”

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

Захист відбудеться 19 травня 2000 р. о 1600 год.

на засіданні спеціалізованої вченої ради Д 35.052.05 у Державному університеті “Львівська політехніка” (79013, м. Львів, вул. С. Бандери, 12).

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

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

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

спеціалізованої вченої ради

кандидат технічних наук, доцент ____________ Ткаченко С.П.

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

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

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

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

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

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

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

Для досягнення поставленої мети необхідно розв’язати такі задачі:

·

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

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

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

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

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

·

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

· визначено умови асимптотичної збiжностi побудованих алгоритмiв до станiв рівноваги та встановлено порядки гранично можливих швидкостей збiжностi;

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

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

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

·

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

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

Впровадження результатiв роботи. Результати роботи використанi та впроваджені в наступних організаціях: Львівська філія ЗАТ “Утел” - адаптивні ігрові алгоритми керування потоками інформації цифрових мереж телекомунікації; науково-виробнича фірма “РОЛА”, м. Львів - інформаційне, методичне та алгоритмічне забезпечення керування потоками інформації в комп’ютерних мережах; науково-виробнича фірма “ТЕХНОЕКС”, м. Львів - ігрові алгоритми та програми маршрутизації пакетів повідомлень в комп’ютерних мережах; Державний університет “Львівська політехніка” - результати дисертаційної роботи використані при виконанні ряду госпдоговорів в НДЛ-62 (номери державної реєстрації 01830049929, 01870001864, 01870096331, 01880079669, 01890074586) для розв’язування задач організаційної та інформаційної підтримки розподіленого вибору варіантів рішень в умовах невизначеності та впроваджені в навчальний процес на факультеті комп’ютерної техніки та інформаційних технологій.

Особистий внесок. Особистий внесок автора в отриманих наукових результатах полягає в тому, що всі положення, які становлять суть дисертації, були сформульовані та вирішені ним самостійно. З 22 наукових робіт 20 праць написані без співавторів. У публікаціях, які написані у співавторстві, здобувачу належить: [2] - математична та програмна модель людино-машинної системи прийняття рішень; [12] - математична та програмна модель синтезу томографічних зображень за допомогою самонавчальних ігрових алгоритмів.

Апробацiя роботи. Основнi результати роботи доповiдались та обговорювались на конференцiях, школах та семінарах: науково-технiчнi конференцiї Державного університету "Львiвська полiтехнiка" з 1991 по 1999 р.; 5-а Республіканська школа-семінар "Преобразование параметров электрической энергии в энергетических и технологических установках", Алушта, 1990; 5-й Ленінградський симпозіум по теорії адаптивних систем “Адаптивные и экспертные системы в управлении” (ТАС’91), Ленінград, 1991; XIV-а Всесоюзна школа по адаптивних системах, Іркутськ, 1991; 2-а Всесоюзна конференція "Повышение эффективности средств обработки информации на базе математического и машинного моделирования", Тамбов, 1991; 3-я Українська конференцiя з автоматичного керування "Автоматика-96", Севастополь, 1996; Міжнародна конференція "Биокстрасенсорика и научне основ культур здоровья на рубеже веков", Москва, 1996; 3-я Всеукраїнська мiжнародна конференцiя з опрацювання сигналiв і зображень та розпiзнавання образiв "УкрОБРАЗ-96", Київ, 1996; 4-та Мiжнародна науково-технiчна конференцiя "Досвiд розробки та застосування приладо-технологiчних САПР”, Львiв, 1997; 4-та Українська конференцiя з автоматичного управлiння "Автоматика-97", Черкаси, 1997; 3-я Міжнародна науково-практична конференція "Сучаснi технологiї в аерокосмiчному комплексi", Житомир, 1997; Мiжнародна науково-технiчна конференцiя "Сучаснi проблеми засобiв телекомунiкацiї, комп’ютерної iнженерiї та пiдготовки спецiалiстiв", Львів, 1998; Мiжнародна наукова конференцiя "Сучаснi проблеми механiки і математики", Львiв, 1998; Науково-технічний семінар Міжнародної виставки “Комп’ютер плюс бізнес 98”, Львів, 1998.

Публiкацiї. По темі дисертації опубліковано 22 наукові роботи, з них 12 статей у періодичних фахових виданнях.

Структура та обсяг роботи. Дисертацiя складається з вступу, 4-х розділів, висновкiв, списку лiтератури (175 найменувань), додаткiв. Повний обсяг роботи - 210 с., ілюстрацій - 54, таблиць - 11, додаткiв - 4.

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

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

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

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

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

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

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

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

З врахуванням відмов гравців послідовності обраних варіантів оцінюються поточними середніми виграшами

. (1)

Метою кожного гравця є максимізація функції середніх виграшів

. (2)

Пошук розв’язків задачі векторної оптимізації (2) здійснюється у множині

точок рівноваги за Нешем (для гри без обміну інформацією)

, (3)

або оптимальності за Парето (для гри з обміном інформацією)

(4)

де нерівності (3) та (4) виконуються з ймовірністю 1, а ; ; .

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

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

,

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

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

, ,, (5)

де - градієнт функції ; - вектор, що складається з одиниць.

Умова (5) визначає вирівнювальні за Нешем стратегії для коаліцій гравців . У загальному випадку ці стратегії є локальними (-оптимальними) розв’язками за Парето базової безкоаліційної гри. Вирівнювальні за Нешем стратегії безкоаліційної гри отримуються з (5) при .

Розділ завершено оглядом літературних джерел та аналізом інформації з комп’ютерної мережі Internet про напрямки сучасних досліджень стохастичних ігор. У роботі запропоновано використання адаптивних ігрових алгоритмів для розв’язування ряду практичних задач в умовах невизначеності: маршрутизація пакетів повідомлень у комп’ютерних мережах [11, 21], синтез зображення комп’ютерного томографічного експерименту [12, 15], фільтрування статистично стійких зображень [17], синтез інформації на семантичних мережах [7], оцінювання розв’язків задач теорії стохастичних полів [5, 8, 18, 20].

У другому розділі на основі виконаних у розділі 1 формулювань ігрової задачі в умовах невизначеності та детермінованої матричної ігрової задачі, методом стохастичної апроксимації умови доповняльної нежорсткості (5) побудовано наступні марківські рекурентні ігрові алгоритми:

, (6)

, (7)

де - оператор проектування на -симплекс ; - параметр, що регулює величину кроку алгоритму; ; - одиничний вектор-індикатор вибору варіанту .

На відміну від (7), алгоритм (6) отримано на основі покомпонентного зважування векторів умови (5)

,

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

Отримано [3, 4, 6, 9, 10, 13, 14, 16, 19, 22] ряд модифікацій алгоритмів (6) та (7): безпроекційний алгоритм (6) при обмеженнях ; градієнтний алгоритм (7) при ; алгоритми без обміну інформацією при ; з обміном інформацією при ; без відмов гравців при ; з відмовами гравців при ; регуляризовані алгоритми при , .

Визначено достатні умови збіжності ігрових алгоритмів (6) та (7) до асимптотично оптимальних розв’язків у знаковизначених середовищах та середовищах загального виду. На основі верхніх оцінок умовного математичного сподівання поточної похибки виконання умови доповняльної нежорсткості при фіксованій передісторії подій та наслідків теореми Роббінса-Сігмунда отримано умови збіжності з ймовірністю 1. На основі усереднення отриманих оцінок по реалізаціях подій та результатів теореми про рекурентні числові нерівності отримано умови збіжності у середньоквадратичному.

Оцінювання асимптотичного порядку швидкості збіжності виконано для послідовностей ; ; методом моментів Чжуна:

, (8)

де - параметр порядку, - величина швидкості збіжності. Більшому та меншому відповідає більша швидкість збіжності ігрового алгоритму.

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

У середовищі загального виду алгоритм (6) забезпечує максимальний асимптотичний порядок швидкості збіжності рівний , що досягається при , . Для алгоритму (7) максимальний порядок дорівнює , що досягається при , .

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

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

У третьому розділі виконано планування комп’ютерного експерименту, описано інструментальні програмні засоби та результати моделювання адаптивних ігрових алгоритмів (без обміну та з обміном інформацією, без відмов та з відмовами гравців) у знакододатних середовищах та середовищах загального виду. Програмний комплекс розроблено на мові С++ з використанням засобів графічного проектування інтерактивних середовищ Borland Builder C++ для операційної системи Windows 98.

Результати комп’ютерного моделювання, подані у вигляді графіків зміни усередненої у часі похибки доповняльної нежорсткості , підтверджують основні теоретичні положення дисертації. Кількість ітерацій моделювання однієї реалізації ігрового алгоритму прийнята рівною 10 тис. кроків. Узагальнення результатів отримано усередненням 50 реалізацій кожного алгоритму для фіксованих початкових даних. Залежність часу моделювання однієї реалізації алгоритму від розмірності ігрової задачі для ПК з процесором Intel Pentium MMX 200 MHz наведена на рис. 1.

Рис. 1. Залежність часу моделювання від розмірності ігрової задачі.

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

Порядок швидкості збіжності ігрових алгоритмів визначався на основі логарифмування виразу (8) та оцінки , де - кут нахилу прямої лінійної апроксимації функції з координатним напрямком часу на відрізку [103,104].

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

а) |

б)

Рис. 2. Поведінка ігрових алгоритмів з параметрами , у середовищі : а) алгоритми без обміну інформацією: 1 - алгоритм (6), 2 - алгоритм (7); б) алгоритм (6): 1 - без обміну інформацією, 2 - з обміном інформацією.

а) |

б)

Рис. 3. Вплив ймовірностей відмов гравців на збіжність ігрового алгоритму (6) з параметрами,, , : а) для стаціонарних відмов: 1 - , 2 - , 3 - , 4 - , 5 - , 6 - ; б) для нестаціонарних відмов: 1 - без відмов гравців, 2 - з лінійно зростаючими ймовірностями відмов , 3 - з лінійно спадними ймовірностями відмов , 4 - з періодичною зміною ймовірностей відмов .

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

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

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

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

Рис. 4. Ефективність ігрової маршрутизації для стаціонарних ймовірностей генерування пакетів mi=const: 1 - середня кількість транзитних передавань пакета; 2 - середня довжина черги; 3 - поточне значення усередненої у часі функції програшів.

а) |

б)

Рис. 5. Ефективність ігрової маршрутизації: а) для нестаціонарних ймовірностей генерування пакетів з періодом зміни 100 кроків; б) для відновлювальних відмов вузлів з ймовірностями hi=0.5 та джерелами пакетів mi=0.1. Графіки: 1 - середня кількість транзитних передавань пакета; 2 - середня довжина черги; 3 - поточне значення усередненої у часі функції програшів.

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

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

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

ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ

У роботі розроблено математичні, алгоритмічні та програмні засоби для моделювання ігрових задач вибору варіантів рішень в умовах апріорної невизначеності. Основні результати роботи полягають у наступному.

1.

1.

1.

1.

1.

1.

1.

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

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

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

АНОТАЦІЯ

Кравець П.О. Математичні та програмно-алгоритмічні засоби моделювання ігрових задач вибору варіантів рішень в умовах невизначеності. - Рукопис.

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

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

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

Кравец П.А. Математические и программно-алгоритмические средства моделирования игровх задач вбора вариантов решений в условиях неопределенности. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 - Математическое моделирование и вчислительне метод. - Государственнй университет “Львівська політехніка”, Львов, 2000.

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

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

Kravets P.A. Mathematical and program-algorithmic resources for variants choice game tasks solutions simulation in conditions of uncertainty. - Manuscript.

Thesis for a Ph.D. science degree by speciality 01.05.02 - Mathematical modeling and computing methods. - State university "Lvivska Polytechnika", Lviv, 2000.

The thesis treats the game patterns and adaptive variants choice game solutions in uncertain conditions and their application for technical problems solutions.

The criteria of an asymptotic optimality of the game in conditions of uncertainty are formulated. On the basis of a condition of an adding slackness the method of stochastic approximating executes synthesis of new recurrent game algorithms for the patterns of games without an exchange and with local information exchange between the players, without refusals and with refusals of the players. The estimations of synthesized game algorithms convergence speed to equilibrium states are received. The game algorithms software simulation tools and their practical implementations are developed. Is formulated and the problem of game packets routing is solved, that allows to improve performances of computer networks.

The first chapter contains the formulas of base definitions of a game problem in conditions of prior uncertainty, description of the patterns of the game without an exchange and with information exchange between the players, without refusals and with refusals of the players. The criteria of an asymptotic equilibrium on Nash and Pareto optimality for the game in conditions of uncertainty are formulated. To obtain the conditions of decidability of a game problem in conditions of uncertainty is executed matrix setting of the determined game problem. The condition of an adding slackness is formulated and the paths of solution of a game problem in the class of Markovian recurrent algorithms are scheduled. The study of the references was executed and the analysis of the information from the computer network Internet on a problem of stochastic games was conducted. The application of game algorithms for solution of a number of practical problems is offered.

The second chapter contains synthesis and analysis of Markovian recurrent game algorithms constructed on the basis of a condition of an adding slackness and a method of stochastic approximating. The recurrent game algorithms without an exchange and with information exchange, without refusals and with refusals of the players are synthesized. The conditions of asymptotic convergence of game algorithms with probability 1 and in average to a point set of an equilibrium on Nash and Pareto optimality in the of fixed sign environments and environments of a general type are determined. The estimations of the orders of designed game algorithms convergence speed are executed.

Is showed, that the game algorithms, offered by the author constructed on the basis of a condition of an adding slackness, have the greater speed of convergence to the leveling strategies, than known game algorithms of gradient type.

The third chapter is devoted to planning of computer experiment and contains the description by the author designed simulation software tool of adaptive game algorithms. The program complex is written on the language C++ for an operating system Windows 98. The simulation of game algorithms conduct without information exchange, with information exchange, without refusals of the players, with refusals of the players in the of fixed sign environments and environments of a general type is executed. The influence of parameters of algorithms, distribution laws and dispersion of scorings, dimension of a game problem, refusals of the players, information exchange on speed of convergence of game algorithms is researched. The results of computer simulation are received by the way of schedules of a time variation of an error of fulfillment of a condition of an adding slackness. The quantity of iterations of simulation of one realization of game algorithm is equal of 10 thousand steps. The generalization of results is executed by averaging 50 realizations of each algorithm. The results of computer simulation basically correspond to theoretical estimations of speed of convergence of game algorithms.

Is showed, that the game algorithms with information exchange about significance of current scorings have greater speed of convergence, than game algorithms without information exchange. The restored refusals of the players result to decrease of speed of convergence of game algorithms.

In the fourth chapter the problem of messages routing in global computer networks is formulated, which solution is executed with the help of adaptive game algorithms. The research of routing algorithms efficiency is executed with the help of the simulation model of operation of the computer network consisting of five sites of packet switching, for different intensities unpriority and priority input streams, modes of addressing, failures of switches, with or without limitations of queues length. The results of