Методы и программные средства анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей

На правах рукописи

МЕТОДЫ И ПРОГРАММНЫЕ СРЕДСТВА
АНАЛИЗА МУЛЬТИАГЕНТНЫХ СИСТЕМ НА ОСНОВЕ
НЕЧЕТКИХ КОГНИТИВНЫХ И ИГРОВЫХ МОДЕЛЕЙ

Специальность 05.13.11 – Математическое и программное
обеспечение вычислительных машин,
комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

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

Смоленск – 2010

Работа выполнена в филиале ГОУ ВПО «Московский энергетический
институт (технический университет)» в г. Смоленске на кафедре Вычислительной техники.

Научный руководитель: доктор технических наук, профессор

Официальные оппоненты: доктор технических наук, профессор

,

кандидат технических наук, доцент

Ведущая организация: Центр информационных технологий и
систем органов исполнительной власти (г. Москва)

Защита состоится «25» июня 2010 г. в 18 час. 00 мин. на заседании диссертационного совета Д 212.157.01 при Московском энергетическом институте (техническом университете) по адресу: Москва, Красноказарменная ул., ауд. М–704.

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (технического университета).

Отзывы в двух экземплярах, заверенные печатью, просим направлять Москва, Красноказарменная ул., Ученый совет МЭИ (ТУ).

Автореферат разослан «___» _________ 2010 г.

Ученый секретарь

диссертационного совета Д 212.157.01

кандидат технических наук, доцент М. В. Фомина

общая характеристика работы

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

Исследования данной области основываются на работах отечественных ученых Я. З. Цыпкина, Д. А. Поспелова, В. Б. Тарасова, А. Н. Аверкина, А. А. Баш­лы­ко­ва, В. Н. Вагина, В. В. Емельянова, А. П. Еремеева, О. П. Кузнецова, В. М. Ку­рей­чика, О. И. Ларичева, А. С. Нариньяни, Г. С. Осипова, А. Б. Петровского, Г. С. Плесневича, Э. В. Попова, Г. В. Рыбиной, В. Н. Финна, И. Б. Фоминых, В. Ф. Хорошевского; зарубежных ученых J. Allen, C. Demetresku, R. Detcher, A. Gereviny, G. Italiano, A. Krokhin, I. Meiri, L. Schubert, T. Van Allen.

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

На решение задач анализа конфликтных ситуаций и согласования целей ориентированы методы теории игр и когнитивного моделирования.

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

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

В то же время отсутствуют методики построения и анализа мультиагентных систем на основе нечетких игровых и когнитивных моделей, а также программные средства, реализующие эти методики. Кроме того, в настоящее время отсутствует подход к анализу мультиагентных систем, основанный на сочетании нечеткого когнитивного и игрового подходов.

Таким образом, задача исследования и разработки методов и программных средств анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей является актуальной и практически значимой.

Целью исследования является повышение эффективности процессов обработки знаний в компьютерных системах за счет создаваемых методов и программных средств анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей.

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

Для этого необходимо решить следующие задачи.

1. Исследование задач анализа мультиагентных систем и возможностей использования нечетких когнитивных и игровых моделей для их решения.

2. Обоснование показателей оценки взаимодействия агентов на основе свойств нечетких когнитивных моделей.

3. Построение нечетких когнитивных и игровых моделей для анализа мультиагентных систем.

4. Разработка модели динамики для анализа взаимодействия агентов в мультиагентных системах.

5. Создание метода анализа мультиагентных систем, включающего в себя решение основных задач анализа взаимодействия агентов и процедуру анализа коллективного поведения агентов в рамках совместной конкуренции за ресурсы.

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

7. Разработка и практическая реализация программных средств для анализа мультиагентных систем, основанных на нечетких когнитивных и игровых моделях.

8. Моделирование и оценка эффективности использования программных средств для анализа мультиагентных систем, основанных на создаваемых нечетких когнитивных и игровых моделях.

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

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

Достоверность научных положений подтверждена сравнением с данными из литературных источников, результатами экспериментов на основе компьютерного моделирования, а также результатами практического внедрения.

Объектом исследований являются программные средства для анализа мультиагентных систем.

Предметом исследований являются методы и программные средства для анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей.

Научная новизна работы заключается в следующем.

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

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

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

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

Практическую значимость работы составляют:

1. Методика построения программных средств для анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей.

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

3. Методическое обеспечение практического применения разработанных программных средств для анализа мультиагентных систем в различных предметных областях.

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

На защиту выносятся:

1. Нечеткая когнитивная модель для анализа взаимодействий в мультиагентных системах на основе предложенных системных характеристик и способа их вычислений.

2. Модель динамики для анализа взаимодействия агентов в мультиагентных системах.

3. Нечеткая коалиционная когнитивная модель для анализа типов взаимодействия агентов с использованием предложенных коалиционных показателей.

4. Метод и алгоритмы анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей.

5. Методика построения программных средств для анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей.

Реализация результатов работы. По результатам работы разработан прототип программной системы для анализа МАС. Теоретические и практические результаты работы использованы при выполнении следующих НИР: «Исследование, разработка и создание программно-технического комплекса мультиагентной региональной информационной системы межведомственного взаимодействия структур в системе управления охраной труда по вопросам обязательного социального страхования от несчастных случаев на производстве и профессиональных заболеваний» (Минздравсоцразвития РФ, Госконтракт № II – 2.17/05 от 01.01.2001 г.); «Исследование и разработка нейро-нечетких моделей в сложных организационно-технических системах» (Рособразование, ГОУВПО «МЭИ(ТУ)», Аналитическая ведомственная целевая программа «Развитие научного потенциала высшей школы (2006–2008 г. г.)», Рег. № проекта в программе 1.28.06, № гос. рег. ); «Исследование и разработка нечетких моделей и методов формирования и обработки знаний в интеллектуальных системах поддержки принятия решений» (Рособразование, ГОУВПО «МЭИ(ТУ)», Аналитическая ведомственная целевая программа «Развитие научного потенциала высшей школы (2009–2010 г. г.)», Рег. № проекта в программе 1.41.09, № гос. рег. ), а также используются в учебном процессе Филиала ГОУВПО «МЭИ(ТУ)» в г. Смоленске, что подтверждено соответствующими актами о внедрении.

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях: Межрегиональная научно-техническая конференция студентов и аспирантов «Информационные технологии, энергетика и экономика» (Смоленск, 2004); III Межвузовская научно-методическая конференция «Современные информационные технологии в научных исследованиях, образовании и управлении» (Смоленск, 2005); IX Международной конференции «Системы компьютерной математики и их приложения», СКМП–2008 (Смоленск, 2008).

Публикации. По результатам работы опубликовано 9 работ, в том числе 2 статьи в журналах из перечня ВАК. Результаты диссертации отражены в 4-х отчётах о НИР.

Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, списка литературы, включающего 118 наименований. Диссертация содержит 175 страниц машинописного текста, 27 рисунков, 20 таблиц, 4 приложения.

содержание работы

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

В первой главе рассмотрены существующие подходы к созданию методов и средств анализа мультиагентных систем, нечетких игровых и когнитивных моделей.

К числу основных проблем построения и анализа мультиагентных систем относятся следующие:

·  обеспечение взаимодействия, коммуникации агентов в МАС; построение языков и протоколов коммуникации;

·  согласование решений и координация действий агентов; планирование в МАС;

·  разрешение конфликтов между агентами из-за ресурсов;

·  описание представления агентами своих внутренних состояний, а также информации о знаниях, планах и действиях других агентов;

·  описание различных точек зрения, целей и предпочтений агентов в интересах представления их в МАС.

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

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

В результате анализа определены следующие особенности нечетких игровых моделей, с точки зрения их использования при создании программных средств для анализа мультиагентных систем:

·  существующие подходы ориентированы на построение и анализ однокритериальных игровых моделей, где проигрыш одного игрока другому задается одной величиной (например, денежными потерями); между тем, на практике, часто цели и ресурсы агентов описываются несколькими показателями;

·  отсутствие методик определения характеристик игровых моделей двух и более игроков, описывающих игровую модель как систему;

·  недостаточно разработан аппарат моделирования процесса развития конфликтных ситуаций в динамике;

·  недостаточно развит подход к анализу участия агентов в коалициях, в том числе, с учетом характеристик, определяющих согласованность действий игроков в рамках достижения общих и индивидуальных целей. Существующие модели не предоставляют достаточную гибкость в определении состава коалиций и возможности анализа индивидуальных действий участников коалиции.

Далее в первой главе рассмотрены существующие подходы к построению когнитивных моделей, определены задачи анализа мультиагентных систем, решаемых на их основе. Определены следующие особенности существующих когнитивных моделей с точки зрения их использования для анализа МАС:

·  отсутствуют подходы к вычислению показателей, позволяющих оценить согласованность действий агентов в МАС, опосредованного влияния агентов друг на друга, вклада агентов в действия коалиции и всей системы в целом;

·  отсутствуют свойств и характеристик, необходимых для моделирования и анализа действий агентов, таких как: ограничения на значения концептов; нормирование влияний для учета взаимодействия агентов с различным уровнем ресурсов; текущий выигрыш; задание стратегий агентов и способов их выбора;

·  не учитываются совместные действия агентов, имеющих сходные цели, в результате их объединения в коалиции.

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

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

Предложена нечеткая когнитивная модель, позволяющая на основе предлагаемых системных показателей осуществлять анализ взаимодействий в мультиагентных системах при преобладании индивидуальных действий над коалиционными. Для построения этой модели реализованы процедуры: описания состояний или значений концептов, характеризующие текущие уровни ресурсов агентов; взаимовлияния концептов друг на друга для представления движения ресурсов; аккумулирования непосредственного влияния нескольких концептов на один концепт с учетом процедуры выбора стратегии концепта (правил передачи ресурсов); опосредованного влияния концептов друг на друга; определения системных показателей модели для анализа взаимодействий в МАС.

Состояния/значения концептов предложенной нечеткой когнитивной модели и их взаимовлияние друг на друга описываются следующим образом:

G = (K, DK),

где K = {K1, K2, …, Kp} – множество концептов, каждому из которых соответствует множество стратегий ( – число стратегий концепта Ki; = {DKij} – множество связей между концептами; состояния концепта Ki (i Î I = {1, 2, …, P}) описывается соответствующей лингвистической переменной á, , ñ,  =  – терм-множество лингвистической переменной (набор лингвистических значений концепта, характеризующих его типовые состояния); mi – число типовых состояний данного концепта; – базовое множество ; влияния DKij (i, j Î I = {1, 2, …, P}) между типовыми состояниями каждой пары концептов задаются одним из значений терм-множества лингвистической переменной á, , ñ, где = – терм-множество лингвистической переменной ; z ´ l – число значений ; – базовое множество .

На рисунке 1 представлен пример структуры нечеткой когнитивной карты для анализа взаимодействий в мультиагентных системах.

Рисунок 1 – Пример структуры нечеткой когнитивной карты
для анализа взаимодействий в мультиагентных системах

Для аккумулирования непосредственного влияния нескольких концептов на один концепт предлагается использовать следующее выражение:

где – нечеткое множество, представляющее изменение значения концепта Ki в результате влияния концепта Kj, N – число входных концептов для концепта Ki; Å – операция нечеткого алгебраического сложения; , – текущие стратегии агентов, представленных концептами Ki и Kj соответственно; – нечеткий оператор, задающий нечеткое отображение типа «много входов – один выход», и представляющий передачу влияния от концепта Kj к концепту Ki.

Нечеткий оператор в выражении может быть реализован как в виде нечетких функций, так и в виде нечетких продукций, например:

Если Ki придерживается стратегии И Kj придерживается стратегии , То движение ресурсов от Ki к Kj составит .

Выбор же стратегии концептом Ki в общем случае зависит от его состояния и от текущих стратегий и предпочтений других концептов.

Опосредованное влияние одного концепта на другой характеризует совокупный причинный эффект всех «путей» между этими концептами. Определим m-й путь между концептами Ki и Kq нечеткой когнитивной карты следующим образом: Ki  Kq: dm = , m = 1, …, M, где M – возможное число путей между концептами Ki и Kq. Тогда опосредованное влияние концепта Ki на концепт Kq определится в соответствии с выражением:

где в качестве T-нормы берется операция минимума или произведения, а в качестве S-нормы – операция максимума.

В итоге формируется матрица опосредованных взаимовлияний концептов друг на друга:

Для определения опосредованных взаимовлияний концептов от исходной матрицы с положительно-отрицательными нечеткими связями выполняется переход к нечеткой матрице положительных связей , элементы которой определяются путем следующей замены:

Остальные элементы принимают нулевые значения.

Согласованные отношения опосредованного взаимовлияния концептов определяются в результате транзитивного замыкания :

Результат представляется в виде матрицы, состоящей из положительно-отрицательных пар элементов , образованных по правилу:

Предложены системные показатели нечеткой когнитивной модели, которые, в отличие от известных, рассчитываются на основе значений матрицы и ориентированы на решение задач анализа взаимодействия в МАС в динамике. Ниже представлены основные из них:

·  консонанс влияния концепта Ki на концепт K:

·  диссонанс влияния концепта Ki на концепт Kq:

·  воздействие (влияние) концепта Ki на концепт Kq:

·  консонанс влияния концепта Ki на систему (карту):

·  диссонанс влияния концепта Ki на систему (карту):

·  консонанс группы концептов p, включающей pn концептов на j-й концепт: ;

·  взаимный консонанс i-го концепта и группы концептов p:

Предложена модель динамики для анализа поведения агентов в МАС:

где t, t + 1 – дискретные моменты времени.

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

Нечеткий оператор в выражении может быть реализован как в виде нечетких функций, так и в виде нечетких продукций:

Если Ki в момент времени t придерживается стратегии И Kj в момент времени t придерживается стратегии , То движение ресурсов от Ki к Kj составит .

В наиболее общем виде, выбор для Ki текущей стратегии на следующем шаге осуществляется на основе нечеткого оператора , где I – индексы концептов, связанных с концептом Ki, J – индексы концептов, связанных с Kj. Оператор зависит от текущей стратегии для Ki, стратегий для Kj, непосредственно связанных с Ki, а также от влияний , оказываемых Kj на смежные с ними концепты. Эти влияния позволяют судить о целях и стратегиях Kj.

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

Пусть агенты, уровни ресурсов которых представлены значениями концептов Ki и Kj придерживаются только чистых стратегий, соответственно и . Агент Ki ничего не знает о стратегии, которую выберет агент Kj, но знает степени влияния агента Kj на других агентов МАС в текущий момент времени .

Игра отображается матрицей выигрышей агента Ki, представленных значениями терм-множеств лингвистических переменных (см. таблицу 1).

Таблица 1 – Матрица потерь агента Ki

		...		...
		...		...
...	...	...	...	...	...
		...		...
...	...	...	...	...	...
		...		...

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

П: Если есть И … И есть И … И есть ,

То есть ,

Затем определяется выигрыш агента Ki для каждой стратегии в момент времени (t + 1). Для этого, в рамках сформированной для каждой стратегии базы нечетких правил, применяется нечеткий вывод. И определяется значение потерь Qi агента Ki для всех стратегий (z = 1, … , Zi).

В результате в момент времени (t + 1) агент Ki выбирает стратегию , обеспечивающую наибольший выигрыш:

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

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

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

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

Введем понятие нечеткой коалиционной когнитивной модели, основанной на предложенной выше нечеткой продукционной когнитивной карте. Допустим, сформировано множество нечетких коалиций . Тогда – множество степеней принадлежности агентов к коалиции . На рисунке 2 приведен пример структуры нечеткой коалиционной когнитивной модели.

Рисунок 2 – Пример структуры нечеткой коалиционной когнитивной модели

Введение степеней принадлежности агентов к коалициям позволяет учесть то, что игрок может иметь разные цели и в различной степени участвовать в разных коалициях. Для каждой нечеткой коалиции Cm задается множество Gm, элементы которого Gmn Î [0 ,1] характеризуют степень участия (степень принадлежности) игроков к данной коалиции. Если Gmn = 1, то агент состоит только в коалиции Cm, если Gmn = 0, то он в этой коалиции не состоит. Если игрок состоит в нескольких коалициях, то степени принадлежности к этим коалициям будут числами от 0 до 1. При этом значение характеризует выигрыш, который получает агент Km от участия в коалиции Cm.

В соответствии с этим примером агент K1 относится к коалиции C1 со степенью принадлежности G11. Агент же K3 принимает участие в двух коалициях C1 и C2 степенями принадлежности G13 и G23 соответственно. Значение характеризует текущее влияние коалиции Cl на коалицию Cm и складывается из влияния участвующих в этих коалициях агентов с учетом степени их принадлежности к коалициям.

Для нечеткой коалиционной когнитивной модели, по аналогии с системными показателями, предложены следующие коалиционные показатели, позволяющие осуществить анализ различных типов взаимодействия агентов в динамике:

·  консонанс/диссонанс влияния агента (концепта) на коалицию;

·  консонанс/диссонанс влияния коалиции на агента;

·  воздействие (влияние) агента на коалицию;

·  воздействие (влияние) коалиции на агента;

·  взаимный консонанс/диссонанс влияния агента и коалиции.

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

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

·  построение модели взаимодействия агентов;

·  определение числа взаимодействующих агентов;

·  определение набора возможных стратегий агентов;

·  определение множества коммуникативных действий;

·  идентификация типов взаимодействия агентов;

·  выделение основных ролей агентов МАС и распределение их между агентами.

Предлагаемый метод состоит из следующих основных этапов.

Этап 1. Построение модели взаимодействия агентов на основе нечеткой когнитивной карты предложенного типа.

Шаг 1. Каждому агенту ставится в соответствие концепт Ki (i Î I = {1, …, P}) нечеткой когнитивной модели и задаются его состояния (значения ресурса) в виде á, , ñ.

Шаг 2. Задание взаимовлияний между агентами DKij (i, j Î I = {1, …, P}) в виде á, , ñ.

Шаг 3. Задание процедуры получения аккумулированного значения влияния агентов на одного агента .

Шаг 4. Задание процедуры выбора стратегии агентом Ki с учетом состояния этого агента, а также от текущих стратегий и предпочтений других агентов.

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

Этап 2. Моделирование динамики на основе предложенной нечеткой когнитивной модели.

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

Этап 3. Расчет системных показателей нечеткой когнитивной модели.

Системные показатели нечеткой когнитивной модели рассчитываются на основе полученной на предыдущем этапе матрицы .

Этап 4. Анализ согласованности действий агентов на основе рассчитанных системных показателей.

В качестве показателей согласованности действий агентов используются такие системные показатели, как , , , , , .

Этап 5. Анализ вклада агентов в деятельность системы.

В качестве показателей вклада каждого из агентов в деятельность всей системы используются такие системные показатели, как влияние концепта на систему и влияние системы на концепт .

Этап 6. Выявление типов взаимодействия и ролей агентов.

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

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

Значение характеризует выигрыш, который получает агент Km от участия в коалиции . Предполагается, что распределение текущих выигрышей между игроками идет пропорционально степеням их принадлежности к коалициям.

Этапы 1–7 повторяются до достижения одной из целей моделирования:

·  достижение заданного значения выигрыша для агента либо коалиции;

·  достижение устойчивого состояния отдельного агента либо коалиции;

·  выполнение заданного числа циклов моделирования

Этап 8. Мониторинг взаимодействия агентов.

·  анализ изменения состава коалиций с идентификацией причин такого изменения;

·  индикация и прогнозировании конфликтных ситуаций как внутри, так и между коалициями;

·  выработка превентивных управляющих решений по снижению рисков нежелательных ситуаций и их негативных последствий.

Далее предложена методика построения программных средств для анализа МАС. Определены требования к структурам и классам данных программных средств, предложена структура представления знаний (см. рисунок 3).

 

Рисунок 3 – Структура представления знаний о предметной области
в программных средствах для анализа МАС

Методика разработки программных средств для анализа МАС на основе нечетких когнитивных и игровых моделей включает в себя следующие этапы.

Этап 1. Разработка объектной модели знаний, включающей в себя объекты для хранения нечетких множеств, концептов, стратегий, влияний, а также характеристик модели, задание иерархических связей между объектами.

Этап 2. Разработка алгоритмов: управления объектной моделью; моделирования динамики системы; нечеткого вывода для получения значений текущих влияний; вычисления характеристик системы.

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

Этап 4. Создание системы управления знаниями.

Этап 5. Создание интерфейса пользователя, включающего модули отображения и редактирования знаний, модуль управления работой системы.

Структура программных средств для анализа МАС на основе нечетких когнитивных и игровых моделей представлена на рисунке 4.

Рисунок 4 – Структура программных средств для анализа МАС на основе
нечетких когнитивных и игровых моделей

В четвёртой главе рассмотрены вопросы практической реализации программных средств для анализа МАС. Приведены алгоритмы программ, предназначенных для моделирования и анализа МАС на основе предложенных моделей, а именно, алгоритм поиска наилучшей стратегии агента в рамках реализации игрового подхода и алгоритм моделирования динамики для анализа МАС.

Рассмотрены примеры использования разработанных программных средств для анализа МАС для выдачи рекомендаций по выбору стратегий агентами в рамках конкуренции за ограниченный набор ресурсов. Приведены результаты использования предложенных способа, моделей, алгоритмов и средств для обоснования характеристик программно-технического комплекса мультиагентной региональной информационной системы межведомственного взаимодействия в системе управления охраной труда, структура которой представлена на рисунке 5.

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

Рисунок 5 – Структура региональной мультиагентной системы охраны труда

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

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

В заключении приведены основные результаты диссертационной работы.

Основные результаты работы

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

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

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

4. Предложен метод и алгоритмы анализа мультиагентных систем на основе предложенных нечетких когнитивных и игровых моделей, позволяющие решать основные задачи анализа взаимодействия агентов.

5. Разработана методика построения программных средств для анализа мультиагентных систем на основе нечетких когнитивных и игровых моделей.

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

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

Список работ, опубликованных по теме диссертации

1.  Устиненков Е. С. Анализ динамики состояния сложных систем на основе обобщенных нечетких продукционных когнитивных карт/ В. В. Борисов, А. С. Федулов, Е. С. Устиненков // Нейрокомпьютеры: разработка, применение. – 2007. – № 1. – С. 21–30.

2.  Устиненков взаимодействий в сложных системах на основе нечетких когнитивных и игровых моделей / , // Нейрокомпьютеры: разработка и применение, № 8, 2009. – C. 4–12.

3.  Устиненков Е. С. Программная реализация нечеткой игровой модели/ Е. С. Устиненков// Актуальные вопросы управления в социальных и экономических системах: Материалы региональной науч.-практ. конф./ Смоленский филиал МЭИ (ТУ). – Смоленск, 2005. – С. 200.

4.  Устиненков Е. С. Анализ мультиагентных систем на основе игровых и когнитивных моделей/ В. В. Борисов, Е. С. Устиненков // Системы компьютерной математики и их приложения – СКМП-2008: Сб. трудов междунар. науч. конф./ СмолГУ.– Смоленск, 2008. – С. 107–108.

5.   С. Представление нечетких игровых моделей с коалициями на основе нечетких продукционных когнитивных карт/ Е. С. Устиненков // Системы компьютерной математики и их приложения – СКМП-2008: Сб. трудов междунар. науч. конф./ СмолГУ.– Смоленск, 2008. – С. 120–122.

6.  Устиненков системных показателей нечетких когнитивных моделей для выявления коалиций в мультиагентных системах/ , , // Информационные и телекоммуникационные технологии, №6 (т. 58) Воронеж: научная книга, 2009. – С. 779–785.

7.  Устиненков, Е. С. Методика построения программных средств для анализа мультиагентных систем/ Е. С. Устиненков// Компьютерные технологии и информационные системы: Сб. трудов межкафедральной конф. Военной академии войсковой ПВО ВС РФ. – Вып. 12 – Смоленск: Изд-во ВА ВПО ВС РФ, 2010. – С. 20–25.

8.  Устиненков анализа мультиагентных систем на основе нечетких когнитивных карт/// Информационный бюллетень Академии военных наук. – № 22. – Смоленск: Изд-во ВА ВПО ВС РФ, 2010. – С. 110–115.

9.  Устиненков когнитивные модели для выявления коалиций в мультиагентных системах// , // Математическая морфология. Электронный математический и медико-биологический журнал. – Т. 9. – Вып. 1. – 2010. – URL: Режим доступа к журн.: http://www. *****/user/sgma/MMORPH/N-25-html/TITL-25.htm

Подписано в печать __.__.10 Зак. Тир.___ п. л. 1

Полиграфический центр МЭИ (ТУ)

г. Москва, Красноказарменная ул., д. 13