Нечеткие модели мультиагентных систем в распределенной среде
Рассмотрены архитектурные нечеткие модели мультиагентных систем в распределенной среде, обладающие преимуществами
 как реактивных, так и мотивированных делиберативных агентов. Предложены средства спецификации поведения нечетких
 агентов на основе трансформаций нечетких графов с испол...
Saved in:
| Date: | 2010 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут програмних систем НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/14630 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Нечеткие модели мультиагентных систем в распределенной среде/ И.Н. Парасюк, С.В. Ершов// Пробл. програмув. — 2010. — № 2-3. — С. 330-339. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860090745202933760 |
|---|---|
| author | Парасюк, И.Н. Ершов, С.В. |
| author_facet | Парасюк, И.Н. Ершов, С.В. |
| citation_txt | Нечеткие модели мультиагентных систем в распределенной среде/ И.Н. Парасюк, С.В. Ершов// Пробл. програмув. — 2010. — № 2-3. — С. 330-339. — Бібліогр.: 15 назв. — рос. |
| collection | DSpace DC |
| description | Рассмотрены архитектурные нечеткие модели мультиагентных систем в распределенной среде, обладающие преимуществами
как реактивных, так и мотивированных делиберативных агентов. Предложены средства спецификации поведения нечетких
агентов на основе трансформаций нечетких графов с использованием нечеткого координатора и механизма адаптации нечетких
правил. Формализована процедура согласования поведения нечетких агентов в мультиагентных системах относительно нечетких
атрибутов, задающих свойства объектов. Предложена функция полезности, позволяющая получить оптимальное поведение
нечетких агентов в процессе многоатрибутного итеративного согласования в распределенной среде.
Architectural fuzzy models of multiagent systems in distributed environment that possesses advantages of both reactive and motivated
deliberative agents, are considered. Means of behavior specification of fuzzy agents are offered on the basis of fuzzy graphs transformations
using fuzzy coordinator and mechanism for adaptation of fuzzy rules. A negotiation procedure of fuzzy agents’ behavior in multiagent
systems is formalized in relation to fuzzy attributes that define properties of objects. A fitness function that allows to achieve an optimum
behavior of fuzzy agents in the process of multiattribute iterative concordance in distributed environment, is offered.
|
| first_indexed | 2025-12-07T17:22:54Z |
| format | Article |
| fulltext |
Формальні методи програмування
© И.Н. Парасюк, С.В. Ершов, 2010
330 ISSN 1727-4907. Проблеми програмування. 2010. № 2–3. Спеціальний випуск
УДК 681.3.06
НЕЧЕТКИЕ МОДЕЛИ МУЛЬТИАГЕНТНЫХ СИСТЕМ
В РАСПРЕДЕЛЕННОЙ СРЕДЕ
И.Н. Парасюк, С.В. Ершов
Институт кибернетики имени В.М. Глушкова НАН Украины,
03680, Киев-187, проспект Академика Глушкова, 40, тел. 526 6422, e-mail: ivpar1@i.com.ua
Рассмотрены архитектурные нечеткие модели мультиагентных систем в распределенной среде, обладающие преимуществами
как реактивных, так и мотивированных делиберативных агентов. Предложены средства спецификации поведения нечетких
агентов на основе трансформаций нечетких графов с использованием нечеткого координатора и механизма адаптации нечетких
правил. Формализована процедура согласования поведения нечетких агентов в мультиагентных системах относительно нечетких
атрибутов, задающих свойства объектов. Предложена функция полезности, позволяющая получить оптимальное поведение
нечетких агентов в процессе многоатрибутного итеративного согласования в распределенной среде.
Architectural fuzzy models of multiagent systems in distributed environment that possesses advantages of both reactive and motivated
deliberative agents, are considered. Means of behavior specification of fuzzy agents are offered on the basis of fuzzy graphs transformations
using fuzzy coordinator and mechanism for adaptation of fuzzy rules. A negotiation procedure of fuzzy agents’ behavior in multiagent
systems is formalized in relation to fuzzy attributes that define properties of objects. A fitness function that allows to achieve an optimum
behavior of fuzzy agents in the process of multiattribute iterative concordance in distributed environment, is offered.
Современная теория и практика программирования в настоящее время все чаще исследует модели
построения интеллектуальных мультиагентных систем, образованных взаимодействующими агентами [1, 2].
Оригинальные результаты получены, например, в работах [3,4] по инсерционной технологии
программирования и моделирования (с введением агентов, обладающих недетерминированным поведением
при погружении в среду, которую сами меняют).
Нечеткие модели по замыслу Л.А. Заде [5] должны использоваться при построении методов и средств
компьютеризации гуманистических систем, в основу которых положен принцип существенного
гранулирования информации. Значительному расширению области применения нечетких мультиагентных
систем препятствует недостаточный уровень формализации концептуальных нечетких моделей агентов,
отсутствие средств координации и согласования нечетких показателей при совместном решении задач агентами
в распределенной среде.
Целью данной работы является формализация поведения интеллектуальных агентов на основе нечетких
моделей и разработка процедуры согласования поведения агентов в нечетких мультиагентных системах. Данная
статья является дальнейшим развитием исследований в направлении становления моделеориентованных
архитектур программных систем в нечетком представлении [6-8].
Архитектура интеллектуальных агентов: общие положения
Под термином интеллектуальный агент понимаются программы, получающие информацию из
окружающей среды и выполняющие над ней соответствующие операции, при этом их поведение
рационально[9]. Архитектуры таких агентов делятся на четыре общих класса: дедуктивные агенты, реактивные
агенты (агенты, основанные на поведении), делиберативные (“разумные”) агенты и агенты, основанные на
побуждениях [1,10-13].
При дедуктивном подходе агент манипулирует символьным представлением среды, используя операции
логического вывода [1,10,11]. Агенты играют роль программ автоматического доказательства теорем,
непосредственно выполняя логические спецификации. Основные недостатки данного подхода: проблема
трансдукции, необходимость обеспечения непротиворечивых, надежных и “четких” знаний, невозможность
манипулировать описанием динамической и стохастической среды, чрезвычайная иерархичность,
необходимость построения полного агента для проведения испытаний, что не позволяет проводить
итерационные пошаговые процессы разработки.
Парадигма Убеждение-Желание-Намерение (Belief-Desire-Intention) воплощает один из основных видов
делиберативных (“разумных” агентов) и содержит явно представленную структуру данных, соответствует этим
трем указанным свойствам рассуждений, применяемых агентом при решении задач [1,10,11].
В агенте BDI [1,10], среда E начинается в специфическом состоянии в конечного множества дискретных
состояний: E = {e, e′, ...}. Агент Ag выбирает специфическое действие из доступного множества возможных
действий A на основе состояния среды и предыдущих выполненных действий: ,...},{ A . Запуск R -
последовательность чередующихся состояний и действий. Среда запускается в определенном состоянии и агент
выбирает действие, чтобы выполняться при этом состоянии. В результате этого действия, среда может перейти
в ряд возможных состояний:
Формальні методи програмування
331
ueeeR u 110 ...10
.
Функция Ag отображает запуски на действия, агент выбирает следующее действие, основываясь на
доступной истории запуска системы: ARAg : . Агент пробует найти и выполнить лучший план )(plan ,
который является серией действий, выполнимых в определенном порядке: },...,,{ 21 n .
BDI агент выполняет следующие функции:
1. Функция пересмотра убеждений агента (т.е. brf) модифицирует текущие убеждения агента на основе
множестве всех убеждений Bel и текущих результатов перцепции: )()(: BelPerBelbrf .
2. Желание, которое агент стремится достичь, считывается из стека намерений. Этот стек содержит все
желания (т. е. цели), которые агент обязался выполнить. Агент отыскивает планы, указывающие желание,
извлеченное из стека, в качестве постусловий. Из этих планов, только те, которые удовлетворяют своему
предусловию (на основе его текущих убеждений), становятся возможными вариантами или желаниями для
агента.
Делиберативный агент начинает размышлять, используя два функциональных компонента: функция
выбора )()()(: DesIntBeloptions , которая для текущего множества убеждений и намерений Int агента
и производит множество возможных желаний Des. Для того, чтобы выбрать между конкурирующими
вариантами, агент использует функцию фильтрации )()()()(: BelIntDesBelfilter . В процессе
рассуждений дальнейшие желаний помещаются в стек намерений, что в свою очередь запускает поиск
большего количества планов, чтобы достичь указанной цели, и так далее. Процесс заканчивается отдельными
действиями, которые могут быть непосредственно выполнены. Если специфический план достижения цели
терпит неудачу, то агент может выбрать другой план достижения желания из всех возможных планов.
Так как размер структуры намерений становится очень большим, ограничения, накладываемые на
вычислительные ресурсы для планирования, уточнения и оценки этих намерений, вызывают “познавательную
перегрузку” агента BDI. К сожалению, ранее упомянутые механизмы фильтрации, не помогают значительно
сократить “познавательную перегрузку” поскольку, со временем генерируется ряд действительных
альтернатив, которые все совместимы с текущими намерениями агента.
Другим возможным решением является использование реактивных (поведенческих) агентов [1,10-12]. В
таких агентах не рассматриваются планирующие действия, основанные на сложных внутренних
представлениях окружающей среды из-за их неотъемлемых ошибок их четкого представления и
ассоциированных с их обработкой временных затрат. Реактивный агент Agr производит ответ из множества
возможных ответов R = {r1, r2, ...}, на основе текущих стимулов S, что может быть представлено следующим
отображением: RSAgr )(: . Каждый индивидуальный стимул или результат перцепции si (где Ssi ) -
кортеж, состоящий из специфического типа или перцепционного класса p и значения силы : ),( psi . Агент
Agr выбирает текущий ответ r) из множества возможных доступных ответов R каждый раз когда больше, чем
порог . Функция поведения , ответственная за отображение входных стимулов на множество
последовательной действий, может быть дискретной или непрерывной. Реактивные агенты могут быть
разработаны с использованием итеративного процесса c использованием кооперативных или конкурентных
методов композиции отдельно задаваемых функций поведения i (где i ). Недостатком таких методов
композиции является их сложность. Так, в архитектуре реактивного агента если задано n уровней поведения, и
каждый уровень способен предложить m возможных действий, то это означает, что необходимо задать nm их
взаимодействий. Кроме того, стремясь упростить функцию поведения, такие агенты не учитывают возможного
состояния самого агента, его состояния и дальнейшей мотивации.
В качестве возможной альтернативы можно рассматривать мотивированные агенты [13] как подход,
совместимый с идеями делиберативных и поведенческих агентов. Различные побуждения (мотивации) -
ключевые определяющие факторы, с помощью которых агент может производить разнообразное поведение,
имеющее высшую степень выгоды (или полезности) как для агента, так и для мультиагентной системы в целом.
При таком подходе, мотив m – это отображение текущих убеждений bel агента о состоянии его среды во
множество активных побуждений )()(: mbelm . Такой агент будет иметь две функции: порождение цели
и активация цели обе из которых предназначены для генерирации активных целей в ответ на обнаруженные
изменения в его текущих убеждениях. Порожденные цели добавляются ко множеству активных целей агентов:
)()()(: mgbelmgen . Активация (вызов) цели происходит, когда интенсивность побуждения связанного
с целью превышает определенный th-порог: )()()()(: goalthbelmgact .
Привлекательность этого подхода по сравнению с реактивными агентами в том, что пользовательские
ожидания относительно поведения агента отображаются в профиль побуждений, который может затем быть
сопоставлен с реальным поведением агента и усовершенствован. Кроме того, в отличие от делиберативного
метода, такой тип агентов не использует сложную систему активации целей и с ней фильтры или триггеры.
Формальні методи програмування
332
Концептуальные основы построения нечетких мультиагентных систем
в распределенной среде
Наиболее простой тип нечетких агентов – реактивные агенты с простым поведением, модель которых
основана только на текущем состоянии среды. Их агентская функция основана на схеме условие-действие: IF
(условие) THEN действие.
Нечеткий логический вывод в таких агентах выполняется по нечеткой базе знаний:
j
p
jp
i
ijpi dwвесомcax
,
где nixi ,1,, – лингвистические переменные, а kpmjda jijp ,1,,1,, – лингвистические термы. Поскольку
для выполнения агентом действия часто необходима дефузификация нечетких значений, логический вывод
осуществляется как по алгоритму Мамдани, так и по алгоритму Сугено, либо с использованием иерархической
системы нечеткого вывода [14].
Рассмотрим спецификацию поведения нечетких агентов в мультиагентной системе, предназначенной для
закупки (продажи) товаров и услуг в распределенной среде. Система состоит из набора агентов-поставщиков,
агентов-потребителей, представляющих интересы участников рынка, и агента-диспетчера, предназначенного
для координации запросов.
Агенты вычисляют значения своих функций поставки и потребления, используяя знания,
представленные в форме нечетких правил. Например, цена товара является лингвистической переменной со
значениями низкая (A1) и высокая (A2), а потребность в товаре (его необходимое количество) – лингвистической
переменной со значениями малая (B1) та большая (B2) (рис.1).
1. Агент-потребитель содержит четыре (2*2) нечетких правила, позволяющих определить значение
лингвистической переменной спроса. Например:
ЕCЛИ Цена=A1 И Потребность=B1 ТО Количество=С2(среднее).
2. Агент-поставщик также включает четыре нечетких правила, на основе которых определяются
значения спроса.
0 p
1 A1 A2
Pmax
0
ix
1 B1 B2
Xmax
Рис. 1. Пример функций принадлежности термов: A1 (низкая), A2 (высокая); B1 (малая), B2 (большая)
При необходимости количество лингвистических термов, являющихся значениями лингвистических
переменных можно увеличить до 3–4. При этом количество правил также соответственно увеличится.
Операционная цена товара определяется агентом-диспетчером на основе дефузифицированных значений
потреблений и спроса каждого агента, которые передаются диспетчеру на каждом раунде работы системы. На
основе значения текущей цены и спроса (предложения) как агент-потребитель, так и агент-поставщик
вычисляют агентскую функцию действия. Поверхность отклика такой функции для агента с двумя
переменными показана на рис. 2.
Однако, для задания агентов которые могут оперировать со средой, лишь частично поддающейся
наблюдению, традиционных средств нечеткого вывода недостаточно. С этой целью в [9] вводится класс
агентов, основанных на модели. Внутри агента хранится представление о той части информации, что находится
вне границ его “обзора”. Поэтому для спецификации таких агентов целесообразно использовать моделе-
ориентированный подход.
Неточность и неопределенность при спецификация окружающей среды задаются нечеткими графами, а
преобразований модели с учетом внутреннего состояния агента - системами трансформаций нечетких графов
(СТНГ) [6]. Они являются обобщением последовательных систем трансформаций графов (графовых грамматик)
и учитывают основные виды нечеткости, которые возникают как при построении базовых категорий нечетких
объектов, так и при описании трансформаций нечетких графов, порождаемых нечеткими множествами.
Формальные модели СТНГ используется при проектировании нечетких агентов с двумя целями: 1) как
обобщение алгоритмов нечеткого логического вывода, в частности, таких, как системы Мамдани и Ларсена над
нечеткими графами; 2) с целью спецификации возможных преобразований между моделями, задающими
разные уровни абстракции нечетких агентов в подходе MDA (так называемая “вертикальные” трансформации
или преобразования “уточнения”).
Формальні методи програмування
333
Рис. 2. Пример поверхности отклика агента-потребителя
Каждая продукция СТНГ строится на основе нечетких графов, которые представляют собой антецедент и
граф-результат продукции. Такая продукция, может быть записана как указано далее.
ЕСЛИ нечеткий граф-антецедент ТО нечеткий граф-результат.
Возможность указанного представления продукций СТНГ основано на том факте, что нечеткий граф-
антецедент и нечеткий граф-результат (консеквент) могут быть записаны в виде
M21N21 E &E &E &N N &N
~~~~~~
,
где { N1, N2 ,…, NN} – множество вершин нечеткого графа, { E1, E2 ,…, EM} – множество ребер нечеткого графа,
а e~ – нечеткое множество соответствующей вершины или ребра нечеткого графа. Обозначим принадлежность
вершины и ребра графу-антецеденту и графу-консеквента соответственно верхним индексом A и С.
Таким образом, простая продукция, задающая соответствующее преобразование, может быть записана в
виде
ЕСЛИ A
M
A
M
AAA
N
A
N
AA EEEENNNN
~~
&...&
~~
&
~~
&...&
~~
1111
ТО
C
L
C
L
CCC
K
C
K
CC EEEENNNN
~~
&...&
~~
&
~~
&...&
~~
1111
где
A
iN
~
,
A
jE
~
,
A
iN
~
,
A
jE
~
,
C
kN
~
,
C
lE
~
,
C
kN
~
,
C
lE
~
– дискретные нечеткие множества или нечеткие числа, причем
A
iN
~
,
A
jE
~
,
C
kN
~
,
C
lE
~
– указанные в продукции нечеткие множества,
A
iN
~
,
A
jE
~
– значения истинности вершин и
ребер нечеткого графа к которому применяется продукция, обычно отличающееся от значений указанных в
продукции;
C
kN
~
,
C
lE
~
– исправленные значения истинности нечетких множеств графа получаемого в
результате применения продукции.
Пусть P – значение истинности антецедента продукции, NA – множество вершин, а EA – множество
ребер графа-антецедента. Тогда
))).,(),,(((max(minmin
))),,(),,(((max(minmin
min
xnxe
xnxn
P
xEAe
xNAn
Реализовано три типа вывода над нечеткими графами: монотонный, при котором последовательные
значения истинности вершин и ребер могут только возрастать; немонотонный, при котором последовательные
значения истинности могут как расти, так и уменьшаться; и нисходящий монотонный, при котором
последовательные значения истинности только уменьшаться. Адекватность применения определенного типа
вывода зависит от задачи и может отличаться для различных продукций, соответствующим определенным
этапам решения.
При монотонном выводе существующие значения истинности вершин и ребер графа, не могут быть
уменьшены при наличии дополнительных свидетельств. Пусть NС – множество вершин, а EС – множество
ребер графа-консеквента. Формула монотонного вывода для значений истинности вершин и ребер, которые
добавляются или остаются в соответствии с указанной продукцией:
)),(,(),(': xoPSxoECNCo ,
где функция S – так называемая S-норма, например )),(,max()),(,( xoPxoPS .
Формальні методи програмування
334
При немонотонном выводе, мы допускаем, что новые результаты, обеспечиваемые запуском указанной
продукцией, надежнее, чем любые существующие свидетельства:
.),(': PxoECNCo
Нисходящий монотонный вывод полезен, когда значения истинности ),(' xo представляет верхний
предел возможного значения:
)),(,(),(': xoPTxoECNCo ,
где функция T – любая T-норма, например, )),(,max()),(,( xoPxoPT , что соответствует оператору вывода
Мамдани.
Структура нечеткого агента, основанного на мотивации приведена на рис. 3. В данной реализации
используются системы СТНГ для того, чтобы непосредственно отображать стимулы X на ответы R. Выбор
этого способа был основан на простоте наличия единственной системы нечетких правил, обеспечивающей
функцию отображения , так как этот выбор не требует механизма координации. Отсутствие координатора
поведения внутри самого агента упрощает его реализацию и делает более очевидным эффект влияния нечетких
значений побуждения на результирующее поведение агента.
В случае четких значений входных стимулов },...,{ 1 nxxx фуззификатор приводит их к
соответствующим нечетким значениям. Блок нечеткого вывода осуществляет сопоставление нечетких правил
СТНГ не только с нечеткими стимулами }~,...,~{~
1 nxxx но и с нечеткими значениями мотивации
}~,...,~{~
1 Nmmm . Для этого задана проекция нечетких правил нечеткого графа предметной области (ПО)
нечеткое множество побуждений, то есть, отображение, определяющее какие из вершина графа ПО могут
рассматриваться в качестве мотивов (побуждений). Правила СТНГ, в левой части которых находятся нечеткие
значения мотивов рассматриваются как строго мотивированные. При использовании нисходящего нечеткого
вывода высота функции принадлежности мотивации в правой части правила может только уменьшаться, что
приведет к остановке выполнения СТНГ через несколько итерации ввиду отсутствия необходимых побуждений
(мера нечеткого совпадение меньше необходимого порога). Дефуззификатор j-го агента отображает множество
вершин нечеткого графа ПО, соответствующих нечетким значениям поведения во множество одновременных
действий },...,{ 1 jljj .
На рис. 4 показана архитектура нечеткой мультиагентной системы, состоящей из N мотивированных
агентов. Все агенты получают одинаковые стимулы }~,...,~{~
1 mxxx . Каждый агент осуществляет применение
правил СТНГ и вырабатывает решение относительно приемлемого поведения },...,{ 1 jljj . Выработка
окончательного решения осуществляется координатором, задачей которого также является также настройка
нечетких правил. C этой целью, модуль оценки предложений агентов на основе N ...,,, 21 , набора
соответствующих этим предложениям входных символов и набора мотиваций осуществляет настойку правил
СТНГ для каждого агента и передает полученный результат модулю вычисления результата. В результате
сопоставления с использованием индексов нечеткого ранжирования вырабатывается окончательное решение
мультиагентной системы, означающее “наилучшее” предложенное поведение },...,{ 1 ilii .
В нашей реализации координатора мультиагентной системы начальные установки побуждения
используются для того, чтобы на основе системы нечетких правил Такаги-Сугено определить нечеткую
пригодность поведения агента в различных средах (рис. 5). Множество побуждений M нечеткого агента для
закупки (продажи) товаров и услуг включает: отсутствие у агента необходимого количества товаров (услуг)
(m1), избыток товаров (m2), большой срок хранения товаров или пользования услугой (m3) и возможность
закупки/продажи у минимального количества поставщиков/потребителей (m4). Эти побуждения используются
как входные установки (нечеткие числа) до запуска каждого эксперимента.
Для возможности такой настройки пользователь выбирает значения побуждений (т.е. m1, ...,mN) которые
должны быть использованы в нечетком вычислении полезности (т. е. побуждения, которые помогают выбрать
лучшего агента в популяции) одну из допустимых сред обучения агента.
Модуль оценивания предложений агентов осуществляет следующие шаги:
– на основе генетического алгоритм генерирует популяцию различных мотивированных агентов;
– каждый агент популяции, в свою очередь, вырабатывает и выполняет последовательность набор
действий j в среде;
– на основе предложенного поведения каждого агента координатор производит набор N значений
полезности;
– результирующая нечеткая полезность F вычисляется на основе побуждений m1, ...,mN и отдельных
значений полезности Nff ,...1 .
Формальні методи програмування
335
Фуззификатор
Средства
нечеткого
вывода
Дефуззи-
фикатор
Четкие
значения
стимулов
Нечеткие
значения
стимулов
Система трансформаций
нечетких графов (СТНГ)
Нечеткие
значения
Четкие
значения
1x
nx
1
~
nx
mx
~
1
~
x
mx
~
1
~
j
jl
~
1j
jl
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1m
Nm
Рис. 3. Структура нечеткого мотивированного агента
Ag 1
Ag 2
Ag N
Модуль
Оценки
Предло-
жений
Агентов
Вычисли-
тель
Результата
Параллельные агенты Координатор
Лучший
вариант
поведения
Входные
стимулы
Результат
Ag1
Результат
Ag2
Результат
AgN
Предложение
первого
агента
Предложение
второго
агента
Предложение
агента N
1
~
x
mx
~
1
~
x
1
~
x
1
~
x
mx
~
mx
~
mx
~
1 1
l1
2 1
l2
1N
Nl
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1i
2i
il
Рис. 4. Структура нечеткой мультиагентной системы с координатором
Оценивание заканчивается, когда достигнуто число максимальных повторений генетического алгоритма.
Лучший агент в популяции сохраняется как заключительный вариант агента. Для определения нечеткого
значения полезности для специфического поведения, используется не требующая дефуззификации система
Такаги-Сугено. Результатом каждого правил являются четкие значения, суммируемые как взвешенная средняя
величина [14]. При определении значения полезности для каждого из четырех побуждений торгового агента
использованы треугольные функции принадлежности, показанные на рис. 6. Таким образом, использованы
четыре нечетких переменных с пятью функциями принадлежности каждая (5
4
= 625 различных нечетких
правила). Соответствующий алгоритм расчета значений нечеткой полезности показан на рис. 7.
Для торгового агента определены следующие переменные и соответствующие им критерии: надлежащее
окончание действий в состоянии, при котором значение ресурсов (имеющихся товаров или услуг).
Формальні методи програмування
336
Выбор N
побуждений
Выбор
среды для
обучения
агента
Генерация
популяции
агентов или
завершение
Выполнение
действий
в выбранной
среде
Вычисление
нечеткой
полезности на
основе
Nff ,...1
Вычисление N
значений
полезности
Nff ,...1
F
Рис. 5. Схема настройки нечетких правил на основе побуждений и функции полезности
0
0 0,25 0,75 0,5
1
1
х
μ(х)
среднее низкое высокое
очень
низкое
очень
высокое
Рис. 6. Нечеткие функции принадлежности
Входные значения: N : количество мотиваций;
M : количество функций принадлежности каждой из мотиваций;
X[N] : массив заданных мотиваций;
Y[N] : массив значений функций полезности;
C[N] : массив коэффициентов;
μ[N][M] : матрица функций принадлежности для мотиваций;
Переменные:
w[n] : оцениваемый вес каждого нечеткого правила; f[n] : определяемая полезность;
n, m0, m1, . . . , mN : целые значения;
Выходные значения:
F : нечеткое значение полезности;
НАЧАЛО
n := 1;
ДЛЯ m1, m2, . . . , mN ОТ 1 ШАГ 1 ДО M
НАЧАЛО
w[n] := min{μ[1][m1], μ[2][m2], . . . , μ[N][mN]};
f[n] :=
N
i 1
i ][i]C[m X[i]Y ;
n := n + 1;
КОНЕЦ;
F := (
NM
i 1
w[i]f[i] )/(
NM
i 1
w[i] );
КОНЕЦ
Рис. 7. Алгоритм вычисления нечеткого значения полезности
не меньше установленного для агента уровня (f1), не больше установленного для агента уровня (f2),
необходимость предпринимать дальнейшие операции из-за ограничения срока хранения или расходования
товаров или ресурсов (f3), количество поставщиков/потребителей, с которыми были проведены операции (f4).
Значения для этих критериев нормализованы (содержат нечеткие числа) и вычислены после того, как агент
завершает действия.
В процессе обучения, управляемая среда выбрана, и генетический алгоритм случайным образом
генерирует начальную популяцию агентов. После этого, каждый агент выполняет свое задание (покупка и
продажа) и вырабатывается набор значений полезности, соответствующих выполненному заданию. В резуль-
тате на основе значений побуждения (мотивации) и полученных значений полезности по отдельным критериям,
координатор вычисляет значение нечеткой полезности.
Формальні методи програмування
337
Процедура согласования поведения нечетких агентов в мультиагентных системах
В большинстве распределенных мультиагентных систем для выработки рационального поведения одних
нечетких моделей недостаточно. Любой агент должен вести себя так, чтобы максимизировать ожидаемое
значение функции полезности [9].
Процедура согласования поведения нечетких агентов основана на обмене информацией между агентами
относительно нечетких атрибутов для объектов поставки/потребления. Она включает в себя два основных
этапа: 1. Анализ и оценка имеющихся предложений средствами нечеткой логики. 2. Генерация дальнейших
запросов с учетом предпочтений обеих сторон.
Агент-потребитель анализирует предложение агента-поставщика на основе его собственной нечеткой
базы знаний. Первый шаг - загрузить правила базы знаний и получить нечеткие требования пользователя.
Пусть имеется n согласовываемых атрибутов (например, цена, время поставки, количество и т.д.), а
согласовываемый атрибут обозначим Ni, i = 1, 2, …, n. Каждый такой атрибут может принимать возможное
значение j (например, дешевый, дорогой), причем j = 1, 2, …., m. Трапециевидная нечеткая функция
принадлежности значения j согласовываемого атрибута i представляется на основе четырех параметров aNij, bNij,
cNij, dNij следующим образом:
1, если
( ) /( ), если ,
( )
( ) /( ), если ,
0, если или .
Nij Nij
Nij Nij Nij Nij Nij
Nij
Nij Nij Nij Nij Nij
Nij Nij
b x c
x a b a a x b
F x
d x d c c x d
x a x d
В некоторых случаях существует некоторые лингвистические значения, такие как, например, цена,
которые монотонно увеличиваются или уменьшаются. Например, если клиент, устанавливает в запросе атрибут
“как можно дешевле”, то агент потребует от пользователя, уточнить предполагаемые параметры aNij и bNij этого
запроса:
1, если
( ) ( ) /( ), если .
0, если .
Nij
Nij Nij Nij Nij Nij Nij
Nij
x a
F x b x b a a x b
x b
Агент генерирует экранную форму для того, чтобы выяснить требования пользователя. Запрос включает
требования относительно согласовываемых атрибутов Ni. Если пользователь требует их согласования с
лингвистическим значением j, чтобы проанализировать предложения агентов-поставщиков применяется
нечеткая функция принадлежности FNij(x). Вес требования (WNj) указывает оценку пользователем значимости
каждого атрибута в запросе:
1NjW , где j = 1, 2, …, n и )1,0{NjW .
Начальное значение D(t) представляет приемлемый уровень решения. Агент регулирует это значение
динамически в соответствии с действиями агента-поставщика. t =1, 2, .., Tmax указывает на t-й раунд
согласования. Для того, чтобы ускорить выполнение согласования, агент регулирует значение приемлемого
уровня для различных атрибутов. Приемлемое значение согласования атрибута Ni – DNi(t).
Принятие предложений агентом ограничивается теми случаями, когда все рассчитанные нечеткие
индикаторы выше опорного значения B для каждого атрибута.
Предположим, что предложение относительно согласовываемого атрибута Ni – ONi(t). Поэтому,
согласно требований пользователя, функция принадлежности FNij(x) используется для расчета нечеткой
тождественности требования пользователя предложению. Уравнение для вычисления нечеткой
тождественности i-го атрибута определяется на универсальном множестве X следующим образом:
dxxFtOtOxF
XCard
M
X
NijNiNiNiji )))]()(()),()([min((
)(
1
.
Обобщенный нечеткий индикатор M адекватности конкретного предложения будет вычислен как
взвешенное среднее значений Mi:
i
Ni
i
Nii
W
WM
M
*
Формальні методи програмування
338
Если M больше, чем приемлемый уровень D, и все нечеткие индикаторы по каждому индивидуальному
атрибуту выше, чем базовое значение, то агент принимает предложение немедленно.
Вариант 1: Принять предложение. Агент примет предложение O(t) если )(tDMBM ii .
Вариант 2: Проводить согласование далее. Агент будет далее вести переговоры с поставщиком, если
)(tDM .
Чтобы оценить предложение O(t), агент вычисляет значение “преимущества” GNi(O(t)) для
индивидуального атрибута согласования Ni по формуле:
)()())(( tDxFtOG NijNijNi .
В случае GNi(O(t)) > 0 предложение согласовываемого атрибута Ni выгодно агенту-потребителю.
Равенство GNi(O(t)) = 0 показывает, что предложение согласовываемого атрибута Ni точно соответствует
требованию потребителя в момент времени t (поскольку приемлемый уровень DNi(t) изменяется со временем).
Ситуация GNi(O(t)) < 0 показывает, что предложение атрибута Ni не удовлетворяет требованиям пользователя.
Поскольку процедура согласования включает n нечетких значений, то полное значение преимущества
или потерь определяются как взвешенное среднее преимуществ (потерь) по каждой проблеме согласования:
Nij
i
Ni WtOGtOG *))(())(( ,
где i = 1, 2, …, n. Это уравнение показывает, что потери по некоторым атрибутам могут быть компенсированы
получением преимуществ по другим атрибутам. Таким образом, задача опорного значения - предотвратить
чрезмерную потерю при специфическом результате согласования.
Задача вычисления нормы уступки следующая: (1) чтобы оценить соотношение согласования, которое
будет объяснено далее; (3) чтобы планировать стратегию. Норма средней уступки поставщика по проблеме
согласования Ni вычисляется следующим образом:
)1(
)()1(
Ni
NiNi
Ni
O
tOO
C
Это уравнение показывает, как вычислить норму уступки по атрибуту Ni на t-th раунде согласования.
Однако, цель вычисления этого значения - выяснить, насколько сильно стороны стремятся договориться
относительно значения данного атрибута. Поэтому, полная норма уступки по всем атрибутам должна быть
нормализована к 1. Другими словами, норма уступки атрибута Ni на t-м раунде согласования определяется как:
j
Nj
Ni
RNi
tC
tC
tC
)(
)(
)( .
где i = 1, 2, …, n.
Цель вычисления коэффициента согласия – оценить возможность урегулировать запрос по каждому
согласовываемому атрибуту для того, чтобы оценить потенциал для дальнейших переговоров между агентами.
Он включает: 1) норму уступки C(t) по атрибуту Ni; 2) вес атрибута Ni:
22)()( NiRNiNi WtCtK .
Вычисление чистого преимущества (дохода) агентов осуществляется как
.0))((,))(())(( tOGtOGtOG Ni
i
NiP
Этот шаг состоит в нахождении возможного объема уступки. Если агент обнаруживает, что чистое
преимущество значительное по некоторым атрибутам, он может уступить большее значение по другим
атрибутам в течение процедуры согласования. Изменение потери атрибута в соответствии с его весом, и
вычисление соотношения преимущества задается как
.0))((,
))((
))((
tOG
W
tOG
WtOP Ni
i
Ni
P
NiNi
Поскольку больший вес означает, что результат более важен для пользователя, агент выделяет большую
компенсацию для этого атрибута используя значения преимуществ по другим атрибутам (рис. 8). Как только
потери по отдельным атрибутам компенсированы, агент пытается уменьшить значение согласования по
каждому атрибуту, чтобы достичь консенсуса между поставщиком и потребителем:
B
W
tOP
tDtOtKtD
Ni
Ni
NiNiNi ,
))((
)(),(max)()1( .
Формальні методи програмування
339
B
D(t)
ONi(t)
1 2 3 4
……
i
Рис. 8. Компенсация значений атрибута агента
Общее значение согласования D(t + 1) на следующем раунде как средневзвешенное значений по каждому
атрибуту:
j
NJNJ tDWtD ),1(*)1( где j =1, 2,…,n.
Функция полезности взаимодействующих нечетких агентов основана на значениях получаемого
преимущества ))(( tOG и коэффициентах согласия по всем раундам согласования:
t
NiNiNi tOGtOKtU ))((*))(()( .
Выводы
Таким образом, нами предложены нечеткие архитектурные модели мультиагентных систем,
предназначенных для решения задач в распределенной среде. Такие гибридные модели обладают свойствами
как реактивных, так и мотивированных делиберативных агентов, что позволяет использовать преимущества
обеих подходов. Возможность применения таких моделей иллюстрируется, например, на задаче
распределенного управления ресурсами. Предложены средства спецификации поведения нечетких агентов на
основе трансформаций нечетких графов и средств адаптации нечетких правил координатором. Формализована
процедура согласования поведения нечетких агентов в мультиагентных системах относительно нечетких
атрибутов, задающих свойства объектов. Предложена функция полезности, позволяющая получить
оптимальное поведение нечетких агентов в процессе многоатрибутного итеративного согласования в
распределенной среде.
Уместно отметить, что в качестве платформы реализации данной нечеткой мультиагентной системы
используется кластерная система СКИТ-3 [15], в которой агенты взаимодействуют на основе асинхронного
обмена сообщениями средствами MPI. Вышеизложенные теоретические результаты в настоящее время
применяются для разработки архитектуры нечетких агентов на основе использования MDA (Model Driven
Architecture, Архитектуры, управляемой моделями).
1. Wooldridge M.J. An Introduction to Multiagent Systems. – Cambridge: MIT Press, 2002. – 366 p.
2. Основы инженерии качества программных систем / Ф.И. Андон, Г.И. Коваль, Т.М. Коротун, Е.М. Лаврищева, В.Ю. Суслов // 2-е изд.
– Киев: Академпериодика, 2007. – 672 с.
3. Інсерційне програмування / Летичевський О.А., Капітонова Ю.В., Волков В.А., Вишемирський В.В., Летичевський О.О. //
Кибернетика и системный анализ. - 2003. - № 1. - С. 19-32.
4. Летичевський О.А., Капітонова Ю.В., Летичевський О.О., Котляров В.П., Нікітченко М.С., Волков В.А., Вейгерт Т. Інсерційне
моделювання в проектуванні розподілених систем // Проблеми програмування 2008 (4). pp. 13-38.
5. Заде Л.А. Роль мягких вычислений и нечеткой логики в понимании, конструировании и развитии информационных/интеллектуальных
систем. - Новости Искусственного Интеллекта, №2-3, 2001, с. 7 - 11.
6. Парасюк І.М., Єршов С.В. Методи аналізу програмних архітектур, представлених нечіткими графовими моделями // Проблемы
программирования. – 2006. – № 1–2. – C. 101–110.
7. Ершов С.В. Нечеткие графы функциональных зависимостей как основа метамоделирования программных систем // Компьютерная
математика. – 2005. – № 3. – C.139–149.
8. Ершов С.В. К проблеме формализации объектно-ориентированных методов разработки программного обеспечения на основе
нечеткой логики // Там же. – 2003. – № 2. – C. 62–77.
9. Рассел С., Норвиг П. Искусственный интеллект. Современный подход. : Вильямс, 2007. – 1408 с.
10. Bussmann S., Jennings N., Jennings N.R., Wooldridge M.J. Multiagent systems for manufacturing control: a design methodology 2004 - 288 p.
11. Luck M.M., Ashri R., D'Inverno M. Agent-based software development, 2004 - 208 p.
12. Anumba C.J., Ugwu O. O., Ren Z. Agents and multi-agent systems in construction, 2005 - 329 p.
13. Plekhanova V. Intelligent agent software engineering. - 2003 - 240 p.
14. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. – М.: Горячая линия –
Телеком, 2004. – 452 с.
15. Суперкомпьютеры ИК НАН Украины. – http:// /icybcluster.org.ua.
|
| id | nasplib_isofts_kiev_ua-123456789-14630 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Russian |
| last_indexed | 2025-12-07T17:22:54Z |
| publishDate | 2010 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Парасюк, И.Н. Ершов, С.В. 2010-12-27T13:44:05Z 2010-12-27T13:44:05Z 2010 Нечеткие модели мультиагентных систем в распределенной среде/ И.Н. Парасюк, С.В. Ершов// Пробл. програмув. — 2010. — № 2-3. — С. 330-339. — Бібліогр.: 15 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/14630 681.3.06 Рассмотрены архитектурные нечеткие модели мультиагентных систем в распределенной среде, обладающие преимуществами
 как реактивных, так и мотивированных делиберативных агентов. Предложены средства спецификации поведения нечетких
 агентов на основе трансформаций нечетких графов с использованием нечеткого координатора и механизма адаптации нечетких
 правил. Формализована процедура согласования поведения нечетких агентов в мультиагентных системах относительно нечетких
 атрибутов, задающих свойства объектов. Предложена функция полезности, позволяющая получить оптимальное поведение
 нечетких агентов в процессе многоатрибутного итеративного согласования в распределенной среде. Architectural fuzzy models of multiagent systems in distributed environment that possesses advantages of both reactive and motivated
 deliberative agents, are considered. Means of behavior specification of fuzzy agents are offered on the basis of fuzzy graphs transformations
 using fuzzy coordinator and mechanism for adaptation of fuzzy rules. A negotiation procedure of fuzzy agents’ behavior in multiagent
 systems is formalized in relation to fuzzy attributes that define properties of objects. A fitness function that allows to achieve an optimum
 behavior of fuzzy agents in the process of multiattribute iterative concordance in distributed environment, is offered. ru Інститут програмних систем НАН України Формальні методи програмування Нечеткие модели мультиагентных систем в распределенной среде Fuzzy models of multiagent systems in distributed environment Article published earlier |
| spellingShingle | Нечеткие модели мультиагентных систем в распределенной среде Парасюк, И.Н. Ершов, С.В. Формальні методи програмування |
| title | Нечеткие модели мультиагентных систем в распределенной среде |
| title_alt | Fuzzy models of multiagent systems in distributed environment |
| title_full | Нечеткие модели мультиагентных систем в распределенной среде |
| title_fullStr | Нечеткие модели мультиагентных систем в распределенной среде |
| title_full_unstemmed | Нечеткие модели мультиагентных систем в распределенной среде |
| title_short | Нечеткие модели мультиагентных систем в распределенной среде |
| title_sort | нечеткие модели мультиагентных систем в распределенной среде |
| topic | Формальні методи програмування |
| topic_facet | Формальні методи програмування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/14630 |
| work_keys_str_mv | AT parasûkin nečetkiemodelimulʹtiagentnyhsistemvraspredelennoisrede AT eršovsv nečetkiemodelimulʹtiagentnyhsistemvraspredelennoisrede AT parasûkin fuzzymodelsofmultiagentsystemsindistributedenvironment AT eršovsv fuzzymodelsofmultiagentsystemsindistributedenvironment |