Метод формирования коалиций в мультиагентных системах на основе нечетких правил
Предложен метод выявления коалиций в мультиагентных системах на основе системы нечетких правил, который позволяет определить величину вознаграждения и продолжительность нахождения в коалиции для каждого потенциального агента. Разработанный метод формирует коалиции в условиях неполноты информации и д...
Saved in:
| Date: | 2011 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Series: | Компьютерная математика |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/84659 |
| 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: | Метод формирования коалиций в мультиагентных системах на основе нечетких правил / С.В. Ершов // Компьютерная математика: сб. науч. тр. — 2011. — № 2. — С. 51-58. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84659 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-846592015-07-12T03:02:23Z Метод формирования коалиций в мультиагентных системах на основе нечетких правил Ершов, С.В. Информационные технологии в экологии Предложен метод выявления коалиций в мультиагентных системах на основе системы нечетких правил, который позволяет определить величину вознаграждения и продолжительность нахождения в коалиции для каждого потенциального агента. Разработанный метод формирует коалиции в условиях неполноты информации и дает возможность адаптировать нечеткие правила, на основании которых принимается решение относительно включения агента. Розглядається метод виявлення коаліцій у мультиагентних системах на основі системи нечітких правил, який дозволяє визначити величину винагороди і тривалість перебування в коаліції для кожного потенційного агента. Розроблений метод формує коаліції в умовах неповноти інформації і дає можливість адаптувати нечіткі правила, на підставі яких приймається рішення щодо включення агента. Method to identify coalitions in multi-agent systems based on a system of fuzzy rules, which allows to determine the awards and duration of staying in the coalition for each potential agent is investigated. The method developed forms a coalition under incomplete information and allows to adapt the fuzzy rules, based on which a decision on the inclusion of the agent is taken. 2011 Article Метод формирования коалиций в мультиагентных системах на основе нечетких правил / С.В. Ершов // Компьютерная математика: сб. науч. тр. — 2011. — № 2. — С. 51-58. — Бібліогр.: 7 назв. — рос. ХХХХ-0003 http://dspace.nbuv.gov.ua/handle/123456789/84659 681.3.06 ru Компьютерная математика Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Информационные технологии в экологии Информационные технологии в экологии |
| spellingShingle |
Информационные технологии в экологии Информационные технологии в экологии Ершов, С.В. Метод формирования коалиций в мультиагентных системах на основе нечетких правил Компьютерная математика |
| description |
Предложен метод выявления коалиций в мультиагентных системах на основе системы нечетких правил, который позволяет определить величину вознаграждения и продолжительность нахождения в коалиции для каждого потенциального агента. Разработанный метод формирует коалиции в условиях неполноты информации и дает возможность адаптировать нечеткие правила, на основании которых принимается решение относительно включения агента. |
| format |
Article |
| author |
Ершов, С.В. |
| author_facet |
Ершов, С.В. |
| author_sort |
Ершов, С.В. |
| title |
Метод формирования коалиций в мультиагентных системах на основе нечетких правил |
| title_short |
Метод формирования коалиций в мультиагентных системах на основе нечетких правил |
| title_full |
Метод формирования коалиций в мультиагентных системах на основе нечетких правил |
| title_fullStr |
Метод формирования коалиций в мультиагентных системах на основе нечетких правил |
| title_full_unstemmed |
Метод формирования коалиций в мультиагентных системах на основе нечетких правил |
| title_sort |
метод формирования коалиций в мультиагентных системах на основе нечетких правил |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2011 |
| topic_facet |
Информационные технологии в экологии |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84659 |
| citation_txt |
Метод формирования коалиций в мультиагентных системах на основе нечетких правил / С.В. Ершов // Компьютерная математика: сб. науч. тр. — 2011. — № 2. — С. 51-58. — Бібліогр.: 7 назв. — рос. |
| series |
Компьютерная математика |
| work_keys_str_mv |
AT eršovsv metodformirovaniâkoalicijvmulʹtiagentnyhsistemahnaosnovenečetkihpravil |
| first_indexed |
2025-07-06T11:43:35Z |
| last_indexed |
2025-07-06T11:43:35Z |
| _version_ |
1836897760487407616 |
| fulltext |
Компьютерная математика. 2011, № 2 51
Инструментальные
средства
информационных
технологий
Предложен метод выявления коа-
лиций в мультиагентных систе-
мах на основе системы нечетких
правил, который позволяет опре-
делить величину вознаграждения
и продолжительность нахожде-
ния в коалиции для каждого по-
тенциального агента. Разрабо-
танный метод формирует коали-
ции в условиях неполноты инфор-
мации и дает возможность
адаптировать нечеткие правила,
на основании которых прини-
мается решение относительно
включения агента.
С.В. Ершов, 2011
С.В. ЕРШОВ
Компьютерная математика. 2011, № 2 52
УДК 681.3.06
С.В. ЕРШОВ
МЕТОД
ФОРМИРОВАНИЯ
КОАЛИЦИЙ В
МУЛЬТИАГЕНТНЫХ
СИСТЕМАХ
НА ОСНОВЕ
НЕЧЕТКИХ ПРАВИЛ
Введение. В настоящее время
при разработке интеллекту-
альных мультиагентных сис-
тем большой интерес вызы-
вает исследование способов
организации эффективных
отношений в виде коалиции
на основе контракта о найме,
а именно, отношений между
агентами-исполнителями и
агентами-принципала-ми
(лидерами коалиции). Значи-
тельное множество работ бы-
ло посвящено исследованию
коллективного поведения и
коалиций агентов в процессе
совместного решения задач в
рамках Belief-Desire-Intention
(BDI)-архи-тектур [1, 2], од-
нако способы формирования
коалиций, основанные на
правилах, фактически не рас-
сматривались. В частности,
проблема формирования коа-
лиции может возникнуть на
основе неполной информа-
ции, поскольку новый лидер коалиции может
не иметь достоверной информации об ус-
пешности решения задач отдельными аген-
тами и о наличии необходимых ресурсов у
других агентов (например, когда агенты вы-
полняют функции лидера по очереди).
Цель настоящей работы – построение и
обоснование метода формирования коалиций
в мультиагентных системах на основе систем
нечетких правил. Данная цель тематически
вписывается в дальнейшее развитие исследо-
ваний в направлении становления моделе-
ориентированных архитектур программных
систем в нечетком представлении [3–5].
С.В. ЕРШОВ
Компьютерная математика. 2011, № 2 54
Определим задачу как ,i i it w R′=< > , где iw – награда полученная агентом
или коалицией, если задача it выполнена агентом/коалицией; iR′ – набор необ-
ходимых ресурсов, которыми должны обладать агенты для решения задачи it .
Агент формально определяется как , ,i i i ia g R s′=< > , где ig представляет собой
набор отдельных целей агента ia ; iR′ – ресурсы, которыми обладает агент ia ;
, ,i a ps v v t=< > – статус агента, включающий такие характеристики как доступ-
ность агента (занят ли он решением задачи), должность агента (независимый
агент, член коалиции, лидер коалиции) и время завершения контракта (соглаше-
ния между членом коалиции и лидером о выполнении задачи). 0,0,0is =< > оз-
начает, что агент не входит в коалицию и не занят решением задачи; с таким
агентом можно заключить контракт на выполнение необходимой коалиции за-
дачи.
Коалиция – это набор агентов, определенный как ,i i iAT MS TR=< > , где
iMS – множество агентов, являющихся членами коалиции, включая лидера, iTR
– суммарный объем ресурсов всех агентов коалиции. Подразумевается, что агент
может находиться только в одной коалиции: : i ji j MS MS∀ ≠ ∩ = ∅ . Множество
участников ( )ij ij iCS CS MS⊆ в коалиции iAT – множество агентов, участвую-
щих в решении задачи it .
В общей ситуации, агенты, которые всегда содействуют выполнению зада-
ний и могут принести больше пользы коалиции – самые ценные, их нужно со-
хранить в коалиции надолго. С другой стороны, коалиция агентов не должна
включать агенты, приносящие ей мало пользы. В данном методе используются
два фактора – коэффициент использования и коэффициент содействия, чтобы
оценить значимость отдельных потенциальных членов коалиции для решения
отдельной задачи.
Коэффициент использования [0,1]Α ∈ – это частота, с которой член коали-
ции ka успешно участвовал в последних M задачах коалиции iAT , задаваемая
соотношением
1
1
( ).
M
k ij
j
k a CS
M=
Α = ∈∑ (1)
Значение параметра М определяется лидером коалиции или задается пользова-
телем.
Коэффициент содействия [0,1]Β∈ – это степень, в которой член коалиции
ka содействовал коалиции iAT в решении последних M задач, задаваемая
следующим выражением ( jkc – количество агентов, участвовавших в решении
j-й задачи):
МЕТОД ФОРМИРОВАНИЯ КОАЛИЦИЙ …
Компьютерная математика. 2011, № 2 55
1
1
/ ( )
.
M
j jk k ij
j
M
j
j
w c k a CS
w
=
=
∈
Β =
∑
∑
(2)
Например, предположим, что три последние задачи, выполненные коалици-
ей iAT , включающей агенты , , ,p r q sa a a a – это 1 140,t R′=< > , 2 250,t R′=< >
и 2 360,t R′=< > . Члены коалиции участвуют в трех задачах – { , }p qa a , { , }p ra a и
{ , }p qa a . В соответствии с (1) и (2) получаем следующие значения коэффициен-
тов использования и содействия для каждого из агентов:
:pa 1,pΑ =
(40 / 2 50 / 2 60 / 2)
0,5
(40 50 60)p
+ +Β = =
+ +
;
:qa 0,67,qΑ =
(40 / 2 60 / 2)
0,33
(40 50 60)q
+Β = =
+ +
;
:ra 0,33,rΑ =
50 / 2
0,17
(40 50 60)rΒ = =
+ +
;
:sa 0,sΑ = 0sΒ = .
Очевидно, что pa – наиболее важный член коалиции iAT , чаще всего
участвовавший в решении задач и принесший наибольшую пользу коалиции.
C другой стороны, sa не принимал участия в решении задач и не принес ника-
кой пользы.
Чтобы заключить обоснованные контракты с членами коалиции, агент-
лидер должен оценить, насколько легко найти аналогичные агенты (обладающие
аналогичными ресурсами и опытом) во всей мультиагентной системе, для чего
определяется параметр доступности ресурсов.
Степень доступности ресурсов агента Γ – величина обратная количеству
доступных агентов, не входящих в коалицию и не решающих задачу и обла-
дающих как минимум тем же количеством ресурсов, что и агент ka . Она опре-
деляется следующим выражением:
(0,0,0)
1Rk Ri
si
N
⊆
=
Γ = ∑ ,
где N – количество доступных агентов, обладающих необходимыми ресурсами
во всей мультиагентной системе.
Например, пусть 10 из 20 имеющихся в системе агентов, обладают теми же
или большими ресурсами, что и ka . Тогда значение доступности ресурсов для
члена коалиции ka составляет 0,5.Γ =
С.В. ЕРШОВ
Компьютерная математика. 2011, № 2 56
Согласно значений коэффициента использования, коэффициента содействия
и степени доступности ресурсов агента, лидеры используют систему нечетких
правил для определения длительности и вознаграждения за сотрудничество с
членами своей коалиции.
В данном методе коэффициент использования, коэффициента содействия и
степени доступности ресурсов агента являются входными параметрами. Выход-
ные параметры – срок контракта и cумма вознаграждения.
Срок действия контракта k∆ – это параметр, который обозначает желатель-
ную продолжительность нахождения агента ka в коалиции. Это выходной па-
раметр, который необходимо определить с помощью нечетких правил. Диапазон
срока действия контракта – [0, MAX ∆ ], где значение MAX ∆ – константа, опре-
деленная в мультиагентной системе и обозначающая максимальный период
времени, в течение которого агент может находиться в коалиции.
Параметр kΝ обозначает максимальное вознаграждение агенту – издержки
которые коалиция понесет с тем, чтобы содержать агента ka в коалиции. Рабо-
чий диапазон вознаграждения – [0, MAXΝ ], где значение параметра MAXΝ , обо-
значающее максимальное значение величины издержек, устанавливает лидер.
Для коэффициента использования выбраны следующие четыре лингвисти-
ческих терма, которые выражены соответствующими нечеткими множествами:
Никогда (Н), Редко (Р), Время от времени (В) и Часто (Ч). Другой входной па-
раметр – коэффициент содействия также имеет четыре лингвистических терма,
а именно: Отсутствует (О), Незначительная (Н), Средняя (С) и Большая (Б).
Трапециевидные нечеткие функции принадлежности принимаются здесь, чтобы
определить нечеткую степень принадлежности этих четырех нечетких мно-
жеств. Функции принадлежности для этих четырех нечетких множеств опреде-
лены в выражениях и показаны на рисунке, а.
1 5 , [0, 0,2],
( )Никогда/Отсутствует 0, [0, 0,2]
x x
x
x
− ∈
µ = ∉
(3)
10 1, [0.1, 0,2],
1, (0.2, 0,3),
( )Редко/Незначительная 4 10 , [0.3, 0,4],
0, [0,1, 0,4]
x x
x
x
x x
x
− ∈
∈µ = − ∈
∉
(4)
10 3, [0.3, 0,4],
1, (0.4, 0,6),
( )Время от времени/Средняя 7 10 , [0.6, 0,7],
0, [0,3, 0,7]
x x
x
x
x x
x
− ∈
∈µ = − ∈
∉
(5)
МЕТОД ФОРМИРОВАНИЯ КОАЛИЦИЙ …
Компьютерная математика. 2011, № 2 57
10 6, [0.6, 0,7],
( ) 1, (0.7,1], .Часто/Большая
0, [0,6,1]
x x
x x
x
− ∈
µ = ∈
∉
(6)
Для Γ задано три лингвистических терма, а именно Незначительная (Н), Сред-
няя (С) и Большая (Б). Функции принадлежности для Γ показаны на рисунке, б.
Для выходного параметра ∆ выбраны следующие четыре лингвистических
терма: Большой (Б), Средний (С), Небольшой (Н) и Отсутствует (О). Для Ν –
в качестве термов выбраны Значительная (З), Средняя (С), Незначительная (Н) и
Отсутствует (О). Нечеткие функции принадлежности этих нечетких множеств
определены выражениями и показаны на рисунке, в.
1 5 , [0, 0,2],
( )Отсутствует/Отсутствует 0, [0, 0,2]
x x
x
x
− ∈
µ = ∉
(7)
10 1, [0.1, 0,2],
1, (0.2, 0,3),
( )Небольшой/Незначительная 4 10 , [0.3, 0,4],
0, [0,1, 0,4]
x x
x
x
x x
x
− ∈
∈µ = − ∈
∉
(8)
10 3, [0.3, 0,4],
1, (0.4, 0,6),
( )Средний/Средняя 7 10 , [0.6, 0,7],
0, [0,3, 0,7]
x x
x
x
x x
x
− ∈
∈µ = − ∈
∉
(9)
10 6, [0.6, 0,7],
( ) 1, (0.7,1] , .Большой/Значительная
0, [0,6,1]
x x
x x
x
− ∈
µ = ∈
∉
(10)
Система нечетких правил может быть представлена в виде таблицы, в кото-
рой представлены все возможные комбинации каждого из входных лингвисти-
ческих параметров и соответствующие им выходные параметры (см. таблицу).
Каждый элемент системы правил определяется операцией AND двух лин-
гвистических входных параметров для получения выходной комбинации, в сле-
дуюшем виде: IF (F( Α ) = α AND F( Β ) = β AND F( Γ ) = γ ) THEN (F( ∆ ) = δ)
AND F(N) = η), где α ∈ {Никогда, Редко, Время от времени, Часто}, β ∈ {От-
сутствует, Незначительная, Средняя, Большая}, γ ∈ {Незначительная, Сред-
няя, Большая}, δ ∈ {Большой, Средний, Небольшой, Отсутствует}, и η ∈ {Зна-
чительная, Средняя, Незначительная, Отсутствует} . При этом оператор AND
используется для объединения значений принадлежности, т. е. наименьшая сте-
пень принадлежности операндов определяет степень принадлежности пере-
сечения нечетких множеств [6, 7]. Результирующее значение принадлежности
µδ/η(V) может быть рассчитано следующим образом: / min( ( ),δ η αµ = µ Α
( ), ( )).β γµ Χ µ Γ
С.В. ЕРШОВ
Компьютерная математика. 2011, № 2 58
а
1
0,5
0
0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1
A, B
б
1
0,5
0
0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1
Г
в
1
0,5
0
0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1
Степень
принадлежности
,N
Степень
принадлежности
Степень
принадлежности
НО РН ВС ЧБ
Н С Б
БЗ СС НН
ОО
РИСУНОК. Нечеткие множества лингвистических термов: a – коэффициенты использования
и содействия; б – степени доступности ресурсов; в – сроки действия контракта и
величины вознаграждения
МЕТОД ФОРМИРОВАНИЯ КОАЛИЦИЙ …
Компьютерная математика. 2011, № 2 59
Результирующие значения системы правил могут быть определены путем
отслеживания значения принадлежности для каждого правила через выходные
функции принадлежности. Наконец, для дефуззификации результирующего зна-
чения используется метод центра тяжести [6, 7]. Выходное значение рассчиты-
вается следующим образом:
( )
1 1
( ) / ( ),
k k
i i i
i i
DF v v v
= =
= ⋅µ µ∑ ∑
где ( )ivµ – степень принадлежности значения iv , а k – количество использован-
ных нечетких правил.
ТАБЛИЦА. Система нечетких правил для выбора агентов в коалицию,
представленная с использованием лингвистических термов
Степень доступности ресурсов агента Н С Б
Коэффициент
использования
Коэффициент содействия Получаемые значения: ∆ , N
Н О ∆ =О, N=О ∆ =О, N =О ∆ =О, N =О
Н Н ∆ =С, N =Н ∆ =О, N =О ∆ =О, N =О
Н С --- --- ---
Н Б --- --- ---
Р О ∆ =С, N =Н ∆ =О, N =О ∆ =О, N =О
Р Н ∆ =Б, N =Н ∆ =Н, N =Н ∆ =О, N =О
Р С ∆ =Б, N =Н ∆ =С, N =С ∆ =Н, N =С
Р Б ∆ =Б, N =С ∆ =Н, N =С ∆ =О, N =С
В О --- --- ---
В Н ∆ =Б, N =С ∆ =С, N =Н ∆ =Н, N =Н
В С ∆ =Б, N =С ∆ =С, N =С ∆ =С, N =Н
В Б ∆ =Б, N =З ∆ =Б, N =С ∆ =С, N =С
Ч О --- --- ---
Ч Н ∆ =Б, N =С ∆ =С, N =С ∆ =Б, N =Н
Ч С ∆ =Б, N =З ∆ =Б, N =С ∆ =Б, N =Н
Ч Б ∆ =Б, N =З ∆ =Б, N =З ∆ =Б, N =С
Выводы. Таким образом, разработан метод выявления коалиций в мультиа-
гентных системах на основе системы нечетких правил, который позволяет опре-
делить величину вознаграждения и желательную продолжительность нахожде-
ния в коалиции для каждого потенциального агента. Такой метод формирует
коалиции в условиях неполноты информации и дает возможность адаптировать
систему нечетких правил, на основе которых принимается решение относитель-
но включения данного агента. Кроме того, он обеспечивает расширение модели
нечетких интеллектуальных агентов средствами формирования коллективного
поведения в рамках единого концептуального подхода.
С.В. ЕРШОВ
Компьютерная математика. 2011, № 2 60
С.В. Єршов
МЕТОД ФОРМУВАННЯ КОАЛІЦІЙ В МУЛЬТИАГЕНТНИХ СИСТЕМАХ
НА ОСНОВІ НЕЧІТКИХ ПРАВИЛ
Розглядається метод виявлення коаліцій у мультиагентних системах на основі системи нечіт-
ких правил, який дозволяє визначити величину винагороди і тривалість перебування в коалі-
ції для кожного потенційного агента. Розроблений метод формує коаліції в умовах неповноти
інформації і дає можливість адаптувати нечіткі правила, на підставі яких приймається рішен-
ня щодо включення агента.
S.V. Yershov
METHOD OF COALITION FORMING IN MULTI-AGENT SYSTEMS BASED ON FUZZY
RULES
Method to identify coalitions in multi-agent systems based on a system of fuzzy rules, which allows
to determine the awards and duration of staying in the coalition for each potential agent is investi-
gated. The method developed forms a coalition under incomplete information and allows to adapt
the fuzzy rules, based on which a decision on the inclusion of the agent is taken.
1. Wooldridge M.J. An Introduction to Multi-agent Systems. – Cambridge: MIT Press, 2002. – 366 p.
2. Городецкий В.И., Грушинский М.С., Хабалов А.В. Многоагентные системы (обзор) // Новости
искусственного интеллекта. – 1998. – № 2. – C. 8–38.
3. Парасюк И.Н., Ершов С.В. Нечеткие модели мультиагентных систем в распределенной среде
// Проблеми програмування. – 2010. – № 2–3. – C. 330–339.
4. Парасюк И.Н., Ершов С.В. Моделе-ориентированная архитектура нечетких мультиагентных
систем // Компьютерная математика. – 2010. – № 2. – C. 139–149.
5. Ершов С.В. Принципы построения нечетких мультиагентных систем в распределенной среде
// Там же. – 2009. – № 2. – C. 54–61.
6. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и
нечеткие системы. – М.: Горячая линия – Телеком, 2004. – 452 с.
7. Леоненков А.В. Нечеткое моделирование в среде MATLAB и fuzzyTECH. – СПб.: БХВ, 2005. –
736 с.
Получено 05.04.2011
Об авторе:
Ершов Сергей Владимирович,
кандидат физико-математических наук, старший научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины.
sershv@ukr.net
|