Содержание к диссертации
Введение
1 Анализ существующих методов, моделей и программных средств для анализа мультиагентных систем
1.1 Основные задачи и методы анализа мультиагентных систем 11
1.2 Когнитивные модели для анализа мультиагентных систем 14
1.2.1 Традиционные знаковые когнитивные карты и их развитие 15
1.2.2 Нечеткие когнитивные карты Коско и их развитие 16
1.2.3 Нечеткие когнитивные карты Силова 17
1.2.4 Нечеткие продукционные когнитивные карты 18
1.3 Нечеткие игровые модели для построения и анализа мультиагентных систем 21
1.3.1 Нечеткие игровые модели с нечеткими стратегиями и целями игроков 22
1.3.2 Нечеткие игровые модели с информацией о предпочтении игроков в использовании стратегий и о степени уверенности в выборе противником стратегии 24
1.3.3 Лингвистические нечеткие игровые модели 26
1.3.4 Несовместные нечеткие игровые модели с критерием Нэша 29
1.3.5 Нечеткие игровые модели нескольких игроков 31
1.4 Совместное использование игровых и когнитивных моделей для описания сложных систем 39
1.5 Средства построения и анализа мультиагентных систем 42
1.6 Требования к нечетким когнитивным и игровым моделям для построения и анализа мультиагентных систем 43
1.7 Постановка задачи исследования 45
1.8 Выводы 47
2 Разработка нечетких когнитивных и игровых моделей для анализа мультиагентных систем 48
2.1 Разработка нечеткой игровой модели для анализа мультиагентных систем 51
2.1.1 Постановка задачи 52
2.1.2 Алгоритм решения нечеткой игровой модели 53
2.1.3 Нечеткие игры с несколькими критериями 55
2.2 Разработка нечетких когнитивных моделей для анализа мультиагентных систем 56
2.2.1 Описание состояний и значений концептов 57
2.2.2 Опосредованное влияние одного концепта на другой 59
2.3 Модель динамики для анализа взаимодействия агентов в мультиагентных системах 62
2.3.1 Анализ тенденций взаимодействия агентов 65
2.3.2 Нормирование влияний концептов 67
2.4 Разработка нечеткой коалиционной когнитивной модели для оценки ситуаций взаимодействия агентов 70
2.5 Выводы 72
3 Разработка метода и средств анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей 73
3.1 Метод анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей 73
3.1.1 Моделирование динамики в мультиагентных системах 76
3.1.2 Определение числа взаимодействующих агентов 76
3.1.3 Определение множества коммуникативных действий 77
3.1.4 Определение набора возможных стратегий агентов и способов их выбора 78
3.1.5 Выработка рекомендаций по использованию выделенных ситуаций взаимодействия - выявление коалиций агентов 80
3.1.6 Выявление видов взаимодействия агентов 86
3.1.7 Выявление ситуации взаимодействия агентов 87
3.1.8 Идентификация ролей агентов 88
3.2 Средства анализа мультиагентных систем 88
3.2.1 Методика построения программных средств для анализа мультиагентных систем 88
3.2.2 Функциональность и основные особенности программных средств для построения и анализа мультиагентных систем 90
3.2.3 Функциональность и основные особенности программных средств для построения и анализа нечетких когнитивных моделей 91
3.2.5 Алгоритм поиска решения нечеткой игровой модели 96
3.2.6 Алгоритм шага моделирования динамики когнитивной модели 98
3.3 Выводы 100
4 Оценка эффективности использования разработанных программных средств анализ а мультиагентных систем 101
4.1 Методика анализа мультиагентных систем с использованием разработанных программных средств 101
4.2 Оценка адекватности разработанных программных средств анализа мультиагентных систем 108
4.3 Практическое применение разработанных программных средств 112
4.3.1 Анализ мультиагентной региональной информационной системы межведомственного взаимодействия структур в системе управления охраной труда 112
4.3.2 Ранжирование и продвижение Web ресурсов 126
4.3.3 Анализ торговых сетей 129
4.4 Выводы 139
Заключение 140
Список литературы 141
Приложение
- Нечеткие игровые модели для построения и анализа мультиагентных систем
- Разработка нечетких когнитивных моделей для анализа мультиагентных систем
- Функциональность и основные особенности программных средств для построения и анализа мультиагентных систем
- Оценка адекватности разработанных программных средств анализа мультиагентных систем
Введение к работе
Актуальность темы исследований. В настоящее время проводятся интенсивные исследования, связанные с расширением интеллектуальных возмолшостеи современных компьютерных систем. При этом одним из наиболее активно развивающихся направлений в этой области является создание методов и программных средств для решения задач создания и анализа мультиагентных систем (МАС), основными из которых являются следующие: формализация агентов и МАС; описание моделей среды и поведения агентов в среде; описание, декомпозиция и распределение задач мел<цу агентами в МАС; синтез (композиция) решений в МАС; взаимодействие (коммуникация) агентов.
Исследования данной области основываются на работах отечественных ученых Я. 3. Цыпкина, Д. А. Поспелова, В. Б. Тарасова, А. Н. Аверкина, А. А. Башлы-кова, В. Н. Вагина, В. В. Емельянова, А. П. Еремеева, О. П. Кузнецова, В. М. Ку-
рСїШПСа, ч-». п. ./іарИЧСБа, А. *-. нарИКЬЯНй, 1 . V-. Ч^СИЙОий, A. D. ПефОВСКОШ,
Г. С. Плесневича, Э. В. Попова, Г. В. Рыбиной, В. Н. Финна, И. Б. Фоминых, В. Ф. Хорошевского; зарубежных ученых J. Allen, С. Demetresku, R. Detcher, A. Gereviny, G. Italiano, A. Krokhin, I. Meiri, L. Schubert, T. Van Allen.
Вместе с тем, существующие методы и модели не обеспечивают развитые возможности анализа взаимодействия мультиагентных систем при решении следующих задач: построение модели взаимодействия агентов; определение числа и стратегий взаимодействующих агентов; идентификация ситуаций взаимодействия; планирование в MAC с выделением и распределением ролей агентов; согласование решений и координация действий агентов; разрешение конфликтов между агентами из-за ресурсов.
На решение задач анализа конфликтных ситуаций и согласования целей ориентированы методы теории игр и когнитивного моделирования.
Предметом теории игр являются методы формализации и принятия решений в конфликтных ситуациях, в которых сталкиваются интересы игроков, преследующих зачастую противоположные цели. Данные типы взаимодействия сложны для непосредственного анализа из-за необходимости учета множества факторов, которые, к тому же, могут быть разнокачественными, оцениваться с помощью различных шкал. Часто знания агентов о действиях друг друга либо о состоянии системы могут быть противоречивыми, неполными. Для формализации таких факторов и построения игровых моделей целесообразно использовать методы теории нечетких множеств и нечеткой логики.
Аппарат нечетких когнитивных карт, основанный на соединении когнитивного моделирования и теории нечетких множеств в рамках концепции «мягких» вычислений (Soft Computing), позволяет адекватно представлять и анализировать широкий класс систем и процессов с учетом неопределенности, неточности и неполноты исходных данных. Данный класс моделей может быть эффективно использован для анализа конфликтных ситуаций, в которых присутствует неполная или противоречивая информация, в качестве основы для анализа мультиагентных систем, существенно расширяя их свойства. Вместе с тем, несмотря на активные исследования в данной области, вопросы анализа нечетких когнитивных карт с учетом как индивидуальных, так и коалиционных действий агентов при столкно-
вении их интересов развиты недостаточно. А именно, отсутствует научно-методический аппарат (обоснованные показатели, модели, способы) оценки согласованности действий агентов, существующие модели динамики не позволяют учесть коалиционные действия агентов.
В то же время отсутствуют методики построения и анализа мультиагентных систем на основе нечетких игровых и когнитивных моделей, а также программные средства, реализующие эти методики. Кроме того, в настоящее время отсутствует подход к анализу мультиагентных систем, основанный на сочетании нечеткого когнитивного и игрового подходов.
Таким образом, задача исследования и разработки методов и программных средств анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей является актуальной и практически значимой.
Целью исследования является повышение эффективности процессов обработки знаний в компьютерных системах за счет создаваемых методов и программных средств анализа мультиагентных систем ня основе нечетких когнитивных к игровых моделей.
Научной задачей диссертационной работы является создание и исследование методов и программных средств для анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей.
Для этого необходимо решить следующие задачи.
-
Исследование задач анализа мультиагентных систем и возможностей использования нечетких когнитивных и игровых моделей для их решения.
-
Обоснование показателей оценки взаимодействия агентов на основе свойств нечетких когнитивных моделей.
-
Построение нечетких когнитивных и игровых моделей для анализа мультиагентных систем.
-
Разработка модели динамики для анализа взаимодействия агентов в мультиагентных системах.
-
Создание метода анализа мультиагентных систем, включающего в себя решение основных задач анализа взаимодействия агентов и процедуру анализа коллективного поведения агентов в рамках совместной конкуренции за ресурсы.
-
Создание методики построения программных средств для анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей, позволяющих проводить практические исследования процессов обработки знаний о предметной области в компьютерных системах.
-
Разработка и практическая реализация программных средств для анализа мультиагентных систем, основанных на нечетких когнитивных и игровых моделях.
-
Моделирование и оценка эффективности использования программных средств для анализа мультиагентных систем, основанных на создаваемых нечетких когнитивных и игровых моделях.
В ходе работы над диссертацией были использованы следующие методы исследований: методы теории принятия решений, теории игр и когнитивного моделирования, мультиагентных систем, нечетких множеств, нечеткого вывода и нечетких систем, анализа и проектирования алгоритмов и программ.
Обоснованность научных результатов, выводов и рекомендаций, сформулированных в работе, определяется корректным применением методов исследования.
Достоверность научных положений подтверждена сравнением с данными из литературных источников, результатами экспериментов на основе компьютерного моделирования, а таюке результатами практического внедрения.
Объектом исследований являются программные средства для анализа мультиагентных систем.
Предметом исследований являются методы и программные средства для анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей.
Научная новизна работы заключается в следующем.
1. Предложена нечеткая когнитивная модель для создания программных
средств анализа мультиагентных систем, отличающиеся наличием системных по
казателей, позволяющих осуществлять оценку взаимодействия агентов при преоб
ладании индивидуальных действий над коалиционными.
-
Разработана модель динамики для создания программных средств анализа мультиагентных систем, и отличающаяся учетом взаимодействия агентов с различными уровнями ресурсоь, а і шике реализацией игрового подхода путем задания стратегий поведения агентов и способов их выбора.
-
Разработаны коалиционные когнитивные модели, предназначенные для создания программных средств анализа мультиагентных систем, на основе нечетких продукционных когнитивных карт, позволяющие учитывать как совместные, так и индивидуальные действия агентов в рамках общей конкуренции за ограниченные разнородные ресурсы.
-
Созданы метод и алгоритмы анализа мультиагентных систем на основе нечетких игровых и когнитивных моделей, позволяющие анализировать поведение агентов в конфликтных ситуациях, а также осуществлять решение основных задач анализа взаимодействия агентов.
Практическую значимость работы составляют:
-
Методика построения программных средств для анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей.
-
Программные средства анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей, позволяющие проводить практические исследования процессов представления и обработки знаний о предметной области в компьютерных системах.
-
Методическое обеспечение практического применения разработанных программных средств для анализа мультиагентных систем в различных предметных областях.
-
Описанные практические применения разработанных метода, моделей, алгоритмов и средств для анализа мультиагентных систем при решении задач: создания программно-технического комплекса региональной информационной системы управления охраной труда; учета, ранжирования и оптимизации Web ресурсов; анализа торговых сетей.
На защиту выносятся:
-
Нечеткая когнитивная модель для анализа взаимодействий в мультиагентных системах на основе предложенных системных характеристик и способа их вычислений.
-
Модель динамики для анализа взаимодействия агентов в мультиагентных системах.
-
Нечеткая коалиционная когнитивная модель для анализа типов взаимодействия агентов с использованием предложенных коалиционных показателей.
-
Метод и алгоритмы анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей.
-
Методика построения программных средств для анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей.
Реализация результатов работы. По результатам работы разработан прототип программной системы для анализа MAC. Теоретические и практические результаты работы использованы при выполнении следующих НИР: «Исследование, разработка и создание программно-технического комплекса мультиагентной региональной информационной системы межведомственного взаимодействия структур в системе управления охраной труда по вопросам обязательного социального страхования от несчастных случаев на производстве и профессиональных заболеваний» (Минздравсоцразвития РФ, Госконгракт №11-2.17/05 от 18.11.2005г.); «Исследование И разработка НсйрО-НбЧЄїКйХ мОДсЛсЙ в СЛОжНых Оріанизацишшо-
технических системах» (Рособразование, ГОУВПО «МЭИ(ТУ)», Аналитическая ведомственная целевая программа «Развитие научного потенциала высшей школы (2006-2008 г.г.)», Per. № проекта в программе 1.28.06, №гос. per. 01200605938); «Исследование и разработка нечетких моделей и методов формирования и обработки знаний в интеллектуальных системах поддержки принятия решений» (Рособразование, ГОУВПО «МЭИ(ТУ)», Аналитическая ведомственная целевая программа «Развитие научного потенциала высшей школы (2009-2010 г.г.)», Per. № проекта в программе 1.41.09, № гос. per. 01200950521), а также используются в учебном процессе Филиала ГОУВПО «МЭИ(ТУ)>> в г. Смоленске, что подтверждено соответствующими актами о внедрении.
Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях: Межрегиональная научно-техническая конференция студентов и аспирантов «Информационные технологии, энергетика и экономика» (Смоленск, 2004); III Межвузовская научно-методическая конференция «Современные информационные технологии в научных исследованиях, образовании и управлении» (Смоленск, 2005); IX Международной конференции «Системы компьютерной математики и их приложения», СКМП-2008 (Смоленск, 2008).
Публикации. По результатам работы опубликовано 9 работ, в том числе 2 статьи в журналах из перечня ВАК. Результаты диссертации отражены в 4-х отчётах о НИР.
Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, списка литературы, включающего 118 наименований. Диссертация содержит 176 страниц машинописного текста, 27 рисунков, 20 таблиц, 4 приложения.
Нечеткие игровые модели для построения и анализа мультиагентных систем
На решение задач анализа конкуренции, возникающих между агентами МАС в условиях ограниченных ресурсов, ориентирован аппарат нечетких игровых моделей.
Исторически первыми появились модели, в которых рассматривалось взаимодействие двух противоборствующих сторон. Часто они задавались в виде игровых матриц. Использование игровых моделей, в которых принимают участие более двух игроков, предоставляет дополнительные возможности анализа взаимоотношения сторон. Так игроки со сходными интересами могут образовывать коалиции, в рамках которых они могут действовать совместно. В несовместных играх игроки, как правило, имеют различные интересы и в них не рассматривается формирование коалиций [98].
Игровые модели также можно классифицировать по следующим свойствам: « выпуклость; характеристики ядра; расширяемость; линейность; определенность для подыгр; точность.
Как для игр двух игроков, так и для несовместных и кооперативных игр, нечеткость может быть введена в различные компоненты игровой модели. В зависимости от этого, можно выделить следующие классы нечетких игровых моделей: с нечеткими выигрышами игроков; в с нечеткими стратегиями игроков; с нечеткими целями игроков; с нечеткими предпочтениями игроков в выборе стратегий; с нечеткой информацией о предполагаемых действиях противника; с нечетким составом коалиций.
Часто нечеткость вводится сразу в несколько компонентов модели. Подробнее эти и другие классы нечетких игровых моделей будут рассмотрены далее.
В [91] рассматривается подход к задачам анализа игровых ситуаций в нечетко определенной обстановке, в котором как стратегии игроков, так и их цели задаются в виде нечетких множеств. Целью анализа данной модели является поиск наилучшей стратегии игрока, а также поиск множества стратегий игрока, гарантирующих ему достижение его цели со степенью, не меньшей некоторого заданного числа. Формулируется такая игра следующим образом.
Пусть X и Y - множества некоторых элементов, которые могут выбирать игроки 1 и 2 соответственно. Допустимые выборы (стратегии) игроков 1 и 2 описываются нечеткими множествами S\ и .% в X и Y соответственно с функциями принадлежности ps\ и jusi. Заданы также функции/J,/2 :XxY— R, причем значение fx(x9y) есть оценка игроком / ситуации (х, у) без учета допустимости выборов х и у. Цель игрока / описывается нечетким множеством G,г в R с функцией принадлежности
Следует заметить, что цель, поставленная игроком, может оказаться плохо или вообще несовместимой с его возможностями, т.е. с множеством его стратегий 5,.
Целью игрока / можно считать нечеткое множество в1 7с функцией принадлежности (1.1).
Для данной модели решаются задачи нахождения следующих характеристик: наилучшая стратегия игрока при известной стратегии противника; стратегия игрока, обеспечивающая ему наибольший гарантированный выигрыш при неизвестной стратегии противника; множество стратегий игрока, гарантирующее ему достижение цели со степенью, не меньшей некоторого заданного числа а.
Введем нечеткие множества D\ и Di в X Y, определив их функции принадлежности следующим образом:
Смысл нечетких множеств D\ и Di можно пояснить следующим обра-зом. Если, например, игроку 1, известен конкретный выбор у игроком 2, то перед ним стоит задача достижения нечеткой цели ju-(x,y ) при множестве допустимых альтернатив juSi (х). В соответствии с используемым здесь подходом Беллмана-Заде решение D\ такой задачи определяется как пересечение нечетких множеств цели и ограничения:
Таким образом, нечеткое множество D\ можно рассматривать как семейство (по параметру у) решений задач достижения нечетких цел ей//-(х,,)/). Аналогичный смысл придается и множеству Д .
Далее будем считать, что при каждом фиксированном выборе одного игрока второй выбирает стратегию, которая максимизирует соответствующую ему функцию //д.
Если игрок полагается целиком лишь на свои возможности, то естественной является его ориентация на получение наибольшего гарантированного выигрыша, т.е. рациональным считается такой способ оценки игроком 1 своих выборов, при котором он рассчитывает на наихудшую для него реакцию игрока 2 из множества возможных реакций последнего.
При этом важную роль играет имеющаяся в его распоряжении информация об интересах и ограничениях игрока 2. Если, например, игрок 1 имеет возможность первым выбрать свою стратегию, а игроку 2 становится известным этот выбор, то наибольший гарантированный выигрыш игрока 1 равен
Присутствующее в этом выражении множества Y(x), зависящее от х, есть множество возможных реакций (ответов) игрока 2 на выбор х игрока 1. В этом смысле зависимость Y(x) отражает степень информированности игрока 1 об интересах и ограничениях игрока 2.
Если Н\ слишком мал, то это означает, что цель, к выполнению которой стремится игрок 1, слишком завышена (с учетом его возможностей). В связи с этим естественным образом возникает следующая задача. Каково должно быть нечеткое множество стратегий игрока 1, которое гарантировало бы ему (при заданной информированности об игроке 2) достижение цели со степенью, не меньшей некоторого заданного числа а?
Разработка нечетких когнитивных моделей для анализа мультиагентных систем
В данной работе предполагается использовать когнитивную модель как средство представления, моделирования динамики и анализа показателей в рамках анализа действий агентов при наличии соперничества за ограниченный набор ресурсов, а также совместных действий агентов в рамках достижения общих целей. Поэтому было проведено исследование существующих типов когнитивных карт, а также подходов к их построению, анализу и динамическому моделированию, освященным в работах [7, 8].
Когнитивные карты представляют собой разновидность математических моделей для формализации проблемы, сложной системы в виде множества концептов, отображающих ее системные факторы (переменные), и выявления причинно-следственных отношений (отношений влияния) между ними с учетом воздействия на эти факторы или изменения характера отношений.
В ходе анализа выделен ряд ограничений существующих когнитивных моделей с точки зрения их использования для анализа мультиагентных систем, а именно: отсутствие подходов к вычислению показателей, позволяющих оценить согласованность действий агентов в MAC, опосредованного влияния агентов друг на друга, вклада агентов в действия коалиции и всей системы в целом; о отсутствие свойств и характеристик, необходимых для моделирования и анализа действий агентов, таких как: ограничения на значения концептов; нормирование влияний для учета взаимодействия аген тов с различным уровнем ресурсов; текущий выигрыш; задание стратегий агентов и способов их выбора; о отсутствие подхода к представлению совместных действий агентов, имеющих сходные цели, формируемых в результате их объединения в коалиции. Для снятия указанных выше ограничений при анализе мультиагентных систем создана нечеткая когнитивная модель, позволяющая на основе предложенных системных показателей осуществлять анализ взаимодействий в мультиагентных системах.
Для построения предложенной модели реализованы следующие процедуры: описания состояний или значений концептов; взаимовлияния концептов друг на друга; аккумулирования непосредственного влияния нескольких концептов на один концепт с учетом процедуры выбора стратегии концепта (агента); опосредованного влияния концептов; определения системных показателей модели.
Состояния/значения концептов предложенной нечеткой когнитивной модели и их взаимовлияние друг на друга описываются следующим образом:
Проблема совместного учета положительного и отрицательного влияния концептов и аккумулирования влияний в нечеткой когнитивной карте решается путем расширения базовых множеств состояний концептов, их приращений и весов влияния на область отрицательных значений и использованием для задания нечетких отображений нечетких продукционных систем типа Мамдани и нечетких алгебраических операций на всем диапазоне базовых множеств.
Для аккумулирования непосредственного влияния нескольких концептов на один концепт используется следующее выражение: где ЬКЬ - нечеткое множество, представляющее изменение значения концепта КІ в результате влияния концепта Kj, N- число входных концептов для выходного концепта К,-; - операция нечеткого алгебраического сложения; S-f , SyJ - текущие стратегии агентов, представленных концептами К{ и Kj соответственно; / - нечеткий оператор, задающий нечеткое отображение типа «много входов - один выход» (Multi Input - Single Output: MISO), и представляющий передачу влияния от концепта Kj к концепту К{. При этом нечеткий оператор / в выражении AK,j = f(Sp ,S{ J) может быть реализован как в виде нечетких функций, так и в виде нечетких продукций, например:
Если КІ придерживается стратегии 5 И Kj придерживается стратегии SfJ, То движение ресурсов AK;J от Kt к Kj составит Tzl ,J.
Выбор же стратегии Stf1 агентом АГ,- в общем случае зависит от состояния этого агента и от текущих стратегий и предпочтений других агентов.
Задача нахождения опосредованного влияния концепта АГ,- на концепт К}- заключается в определении совокупного причинного эффекта или «веса» того пути между этими концептами, который характеризуется максимальным совокупным значением влияния ЛАГ.
В некоторый момент времени влияние одного концепта на другой определяется как типовыми состояниями (значениями) этих концептов, так и мерой влияния в предыдущий момент времени.
Найдем стационарное значение опосредованного влияния концепта AT,-на концепт Kj. Определим т-и путь между концептами КІ И Kq нечеткой когнитивной карты следующим образом: где M - возможное число путей между концептами КІ и Kq. Тогда опосредованное влияние концепта АГ;- на концепт Kq определится в соответствии с выражением: где в качестве Т-нормы берется операция минимума или произведения, а в качестве S-нормы - операция максимума. Для определения опосредованного влияния всех концептов карты друг на друга в некоторый момент времени, можно использовать, как это описано в [57] операцию транзитивного замыкания квадратной матрицы нечетких весов. В работе [57] предложено описание операции транзитивного замыкания квадратной матрицы с четкими числовыми значениями в виде Можно предложить аналогичную операцию в случае, если нечетких элементов матрицы с использованием операций Т нормы и объединения над нечеткими числами. Однако в силу большого числа вычислительных операций над нечеткими числами для модели, будет наблюдаться слишком сильное увеличение нечеткости. Поэтому необходимо провести предварительную дефаззификацию значений АКтц и искать транзитивное замыкание матрицы четких значений АК у, полученных после дефаззификации и нормировки к промежутку [-1. 1]. В итоге формируется матрица опосредованных взаимовлияний концептов друг на друга
Функциональность и основные особенности программных средств для построения и анализа мультиагентных систем
Создание системы управления знаниями. На этом этапе создаются основные процедуры и классы для доступа к знаниям, изменения состояний, сохранения и загрузки знаний. Этап 5. Создание интерфейса пользователя, включающего в себя модули отображения состояния, модуля редактирования знаний, модуля управления, модуля сохранения и загрузки знаний. Разработка прототипа программной системы Разработанные алгоритмы и модели были реализованы в виде двух программных продуктов: в FuzzyGame 1.0 - реализует алгоритм решение матричной нечеткой игры двух игроков с использованием алгоритма, описанного в разделе 2.2 [78]. CognitiveMaps 1.1 - реализует создание, моделирование динамики и расчет системных показателей НПКК, а также создание, моделирование и анализ нечетких игровых моделей на основе НПКК, в том числе при анализе MAC. Далее описаны функциональность и основные особенности этих программ (рисунок 3.3). В идею программных средств анализа MAC заложено предположение о том, что агент может использовать ограниченное число стратегий, полный список которых известен другой стороне, при этом некоторую информацию о действительной его стратегии дает набор числовых факторов. Исходные данные модели игровой ситуации: Степени уверенности в выборе агентами каждой из его возможных стратегий. Игровая матрица, представляющая собой набор произвольного числа значений числовых критериев для каждой пары стратегий игроков. в Настройки алгоритма поиска решения, а именно, режим анализа игровых критериев (по минимуму и по медиане) и пороговое значение уверенности в найденном критерии. Если уверенность в найденном решении будет меньше порогового, оно будет отброшено.
В разработанных программных средствах используется описанный ранее алгоритм, дающий рекомендацшо одной из сторон в выборе наиболее целесообразной стратегии, с указанием степени уверенности в этом решении. Программные средства позволяет задавать произвольное число стратегий противоборствующих сторон, при этом игровая ситуация описывается путем указания для каждой пары стратегий игроков набора числовых критериев, характеризующих исход игры при условии, что игроки придерживаются этих стратегий, т. е. реализован учет многокритериальности потерь. В реализованном алгоритме поиска решения имеется возможность использования различных режимов анализа значений критериев, а именно, учет лишь минимального значения среди всех критериев для каждой пары стратегий двух игроков или же использование медианы множества критериев. Экранные формы подсистемы FuzzyGame 1.0 приведены в Приложении 1. Существует также возможность задания минимального значения степени уверенности в выдаваемой рекомендации по поводу наиболее целесообразной стратегии. При этом решения, степень уверенности в которых меньше заданной «отсекаются» и, в общем случае, задача может не иметь решения. В предложенной реализации игровой модели существует возможность сохранения введенных игровых ситуаций в файл с возможностью последующей его загрузки, а также имеется справочная система. Программа выполнена на языке С# с использованием платформы .Net и средства разработки Microsoft Visual С# .NET 7.1.
Приложение CognitiveMaps 1.1 реализует создание, моделирование динамики и расчет системных показателей НПКК, а также создание, моделирование и анализ МАС на основе НПКК. Подсистема предназначена для построения нечетких когнитивных карт, их графического отображения, анализа статических и динамических показателей модели, моделирования динамики НПКК. Основные функции системы: о задание и редактирование нечетких множеств, используемых при описании концептов и влияний концептов друг на друга; задание и редактирование множества концептов, входящих в состав НПКК; задание и редактирование влияний концептов друг на друга в виде нечетких продукционных правил; визуальное отображение НПКК в виде графа; реализация модели динамики НПКК путем получения на каждом шаге значений влияний концептов с помощью нечеткого логического вывода и агрегации влияний нескольких концептов; моделирование динамики НПКК с возможностью указания условий завершения моделирования; вычисление динамических и статических показателей НПКК. Структура подсистемы представлена на рисунке 3.4.
Оценка адекватности разработанных программных средств анализа мультиагентных систем
Пусть задана нечеткая конфликтная ситуация ./V игроков, т.е. заданы: множество игроков - К= {К\, Кг,... , К }; для каждого /-го игрока задано множество смешанных стратегий заданы потери (нечеткие), которые несет /-й игроку-му противнику, при учете, что /-й игрок придерживается стратегии S x, a у"-й игрок придерживается стратегии SJy. Потери могут быть заданы в виде нечеткого отношения. Для каждой пары игроков оно задается как это показано в таблице 4.6
Описанная игровая ситуация может быть задана в виде НПКК следующим образом: множеству концептов соответствует множество игроков (агентов). Терм множеству набора лингвистических значений каждого концепта соответствует множество возможных нечетких стратегий этого игрока; влиянию концепта на другой соответствует выигрыш. Влияние описывается продукциями вида «Если j-й игрок придерживается стратегии S x, ау -й придерживается стратегии SJV, то потери равны WJi». На рисунке 4.5 приведен пример представления игровой ситуации в виде НПКК: Рассмотрим простейшую четкую матричную игру двух игроков А и В. Пусть у каждого из игроков имеются 2 стратегии: AI,A2VLBI, В2.Игровая модель задана матрицей выигрышей/ (таблица 4.7). Воспользовавшись минимаксным принципом (условием минимальности возможных потерь), можно найти равновесное решение игры, это (А\, В\). Если оба игрока будут придерживаться этим стратегиям, то на каждом шаге игры выигрыш у игрока А у игрока В будет равен 1. Между тем, если игрок В знает, что игроке придерживается стратегии Лі, то он может выбрать стратегию #2, увеличив тем самым свой выигрыш. Здесь встает вопрос о осведомленности игрока В в стратегии, выбранной игроком А. Наличие этих сведений, возможно нечетких, можно учесть используя подход, описанный в разделе 2.2.
Здесь же мы рассмотрим построение нечеткой модели. Основанной на НПКК, аналогичной приведенной модели и адекватность ее использования. Нечеткая модель будет задана следующим образом (рисунок 4.6). Концепты А и В соответствуют игрокам. У каждого игрока имеются 2 стратегии (Стратегия 1 и Стратегия 2). Стратегии являются нечеткими значениями, заданными с функцией принадлежности Singleton. Выигрыши игроков зададим нечеткими множествами типа singleton со значениями, соответствующими значениям из таблицы 3.1 (обозначим эти функции +1,+2,+3,+4,-1,-2,-3,-4, в соответствии с деффазифицированными значениями). Продукционные правила, описывающие влияния концептов друг на друга будут иметь вид: Если стратегияу!=Стретегия1, и стратегия 2?=Стратегия 1 то влияние на В равно +1. Если стратегия Л=Стретегия1, и стратегия =Стратегия 2 то влияние А на В равно -2. Если стратегия у4=Стретегия2, и стратегия ІЗ=Стратегия 1 то влияние .Л на В равно -3. Если стратегия Л=Стретегия2, и стратегия Л=Стратегия 2 то влияние А на В равно +4. Если стратегия =Стретегия1, и стратегия 4=Стратегия 1 то влияние В на А равно -1. Если стратегия =Стретегия1, и стратегия Л=Стратегия 2 то влияние В па. А равно +3. Если стратегия 5=Стретегия2, и стратегия Л=Стратегия 1 то влияние В иг. А равно+2. Если стратегия 2?=Стретегия2, и стратегия #=Стратегия 2 то влияние В на А равно -4. Разработанные программные средства, реализующие представление нечеткой игровой модели в виде НПКК, позволяют задавать частоты использования игроками стратегий, что позволяет исследовать как чистые так и смешенные стратегии игроков. Задавая значения частот использования одной из стратегий равной 1, а всех прочих 0, получим ситуацию, когда игроки придерживаются заданной стратегии. Задавая различные частоты и проводя моделирование можно оценить адекватность данной модели исходной четкой модели, а также эффективность использования нечетких стратегий. Пусть р\, рг- частоты использования игроком А его стратегий. q\, qi-частоты использования игроком В его стратеги. N - количество шагов моделирования. Ма - выигрыш игрока А, Мь выигрыш игрока В. Za, Zb - средние выигрыши игроков А и В за 1 шаг. Из результатов следует, что при использовании чистых стратегий (одна из вероятностей равна 1, остальные - 0), значения выигрышей в нечеткой модели соответствует выигрышем четкой модели, задаваемой таблице 4.8. Незначительные отклонения (1,985 и 2) появились вследствие дефаззификации.
