Математическая морфология.

Электронный математический и медико-биологический журнал. - Т. 9. -

Вып. 1. - 2010. - URL:

http://www.smolensk.ru/user/sgma/MMORPH/TITL.HTM

http://www.smolensk.ru/user/sgma/MMORPH/N-25-html/TITL-25.htm

http://www.smolensk.ru/user/sgma/MMORPH/N-25-html/cont.htm

УДК 519.8

НЕЧЕТКИЕ КОГНИТИВНЫЕ МОДЕЛИ ДЛЯ ВЫЯВЛЕНИЯ КОАЛИЦИЙ В МУЛЬТИАГЕНТНЫХ СИСТЕМАХ

Ó 2010 г. Борисов В. В., Устиненков Е. С.

(borisov.doc)

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

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

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

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

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

Ключевые слова: нечеткие когнитивные и игровые модели, многоагентные системы, интеллектуальный агент

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

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

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

В данной статье описываются использование системных показателей нечетких когнитивных моделей для оценки согласованности действий агентов МАС и формирования коалиций.

Нечеткая когнитивная модель для анализа МАС описывается как:

G = (K, DK),

где K = {K₁, K₂, …, K_p} – множество концептов, каждому из которых соответствует множество стратегий

,

– число стратегий коалиции K_i;

= {DK_ij} – множество связей между концептами;

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

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

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

Для описанной выше модели можно ввести набор системных статических и динамических показателей, как это делается в работе [4].

Пусть H = v_ij – матрица транзитивных замыканий, вычисленная, как предлагается в работе [2].

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

· консонанс влияния концепта K_i на концепт K_q

· взаимный консонанс влияния концептов K_i и K_j:

;

· консонанс влияния системы на j-й концепт

		(2.12)
· консонанс группы концептов p, включающей pn концептов на j-й концепт .			(2.18)

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

.

2. Оценка согласованности действия агентов и выявление коалиций

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

Можно предложить следующее решение описанной выше задачи.

Построение множества L возможных партнеров по коалиции. При этом предполагается, что агент K_m принадлежит множеству L лишь в том случае, когда агенты K_m и K_i не взаимодействуют напрямую, т.е. когда не задано влияние , либо оно всегда нулевое, т.к. агенты, между которыми имеется соперничество, не могут быть партнерами по коалиции. На рис. 2 для концепта K₁ это – множество L={K₃, K₄}.

Определение набора возможных коалиций Fp для агента K_i. Во множество Fp включаются все возможные коалиции, которые могут быть сформированы агентами из множества L с агентом K_i. Для приведенного выше примера Fp={{K₁, K₃},{K₁, K₄},{K₁, K₃, K₄}}.

Рис. 2. Структура исходной нечеткой когнитивной модели

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

Агент K_i, имея в своем распоряжении список возможных коалиций, ранжированных по уровню согласованности целей, может договориться с другими агентами о сотрудничестве. Например, пусть в приведенном примере наиболее согласованной с целями игрока K₁ оказалась коалиция Fp₃={K₁, K₃, K₄} и агенты K₃, K₄ готовы к созданию такой коалиции.

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

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

Первый из них включает в себя:

· изменение участниками коалиций правил выбора текущей стратегии. При этом правила выбора текущей стратегии агента могут быть оптимизированы не с точки зрения получения максимального выигрыша этим агентом, а с точки зрения максимизации общего выигрыша игроков, участников коалиции;

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

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

Новая модель для приведенного выше примера будет иметь следующий вид (рис. 3).

Рис. 3. Структура нечеткой когнитивной модели с коалицией

,

где f – нечеткий оператор, задающий нечеткое отображение типа «много входов – один выход»;

– суммарный выигрыш агентов, составляющих коалицию;

– суммарные выигрыши агентов i,j, получаемые ими от агентов, не входящих в коалицию.

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

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

Рис. 4. Структура нечеткой когнитивной модели с коалицией

Получается новая когнитивная модель вида:

,

где K – множество агентов; С – множество нечетких коалиций; G – множество степеней принадлежности игроков к коалициям; S – множество коалиционных стратегий; – множество коалиционных выигрышей; П – множество продукционных правил, описывающих распределения выигрышей между коалициями; ПП – множество продукционных правил; описывающих распределения коалиционных выигрышей между игроками; V – множество переменных, описывающие текущие выигрыши игроков.

Итак, пусть задано K – конечное множество игроков, N – количество игроков, F – множество всех нечетких коалиций. Для каждой j-й нечеткой коалиции задан вектор . Уровнем участия игрока i в нечеткой коалиции C_j называется i-я координата V_ij вектора V.

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

Примем, что для нечеткой коалиции уровень участия равен 1, если игрок целиком состоит в ней и нулю, если игрок целиком не состоит в коалиции.

На рис. 5 представлен пример структуры когнитивной с нечеткими коалициями. На нем представлены 7 игроков и 3 коалиции.

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

В примере игрок K₁ принадлежит лишь к коалиции C₁ со степенью принадлежности V₁₁. Игрок же K₃ принадлежит к двум коалициям – к C₁ и C₂ со степенями принадлежности V₃₁ и V₃₂ соответственно.

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

.

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

Кроме того, задаются потери (нечеткие), которые несет i-я коалиция от j-ой коалиции, при учете, что i-я коалиция придерживается стратегии , а j-я коалиция придерживается стратегии . Потери могут быть заданы в виде нечетких продукционных правил. Для каждой пары коалиций они задается в виде:

Пij: Если коалиция C_i придерживается стратегии , а коалиция C_j придерживается стратегии , то выигрыш коалиции C_i равен .

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

.

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

Так, выигрыш m-го игрока от участия в i-ой коалиции определяется как произведение степени участия игрока в этой коалиции и выигрыша коалиции:

.

Для представления распределения выигрыша в модели, основанной на НПКК, вместо последнего выражения удобнее использовать задание выигрыша в виде нечетких продукционных правил вида

ПП_ij: Если выигрыш коалиции C_i равен и степень участия m-го игрока в i-й коалиции равна V_i, то выигрыш m-го игрока равен .

Переменная представляет текущий (накопленный) выигрыш игрока i.

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

Заключение

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

литература

1. Тарасов В. Б. От многоагентных систем к интеллектуальным организациям. – М.: УРСС, 2002.

2. Борисов В. В., Федулов А. С. Обобщенные нечеткие когнитивные карты. – Нейрокомпьютеры: разработка, применение, № 4, 2004.

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

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

FUZZY COGNITIVE MODELS FOR REVEALING COALITIONS IN MULTI-AGENTS SYSTEMS

V. V. Borisov, E. S. Ustinenkov

The fuzzy cognitive model intended for the analysis of interactions in complex systems is offered. This model takes into account an opportunity of a choice of strategy of agents due to realization of the fuzzy game approach. The components and procedures for development of the given model are considered. The method of the analysis of interactions in complex systems is developed on the basis of the offered fuzzy cognitive model.

The fuzzy coalition cognitive model being development of the offered fuzzy cognitive map is developed. This model allows to carry out the monitoring of interactions of agents, including:

· the analysis of change of structure of coalitions with definition of the reasons of such change;

· prediction and indication of conflict situations as inside, and between coalitions;

· decision-making on reduction of risks of undesirable situations and their negative consequences (including, an estimation of realization of these decisions).

Key words: fuzzy cognitive and game models, multi-agent systems, intelligent agent.

Филиал ГОУВПО «Московский энергетический институт

(технический университет)» в г. Смоленске

vborisov@etna-it.ru, admin@softorbits.com

Поступила в редакцию 12.03.2010.