Mathematical methods of planning in systems consisted of rational agents
The paper is devoted to mathematical methods of planning in systems consisting of rational agents. An agent is an autonomous object that has sources of information about the environment and influences this environment. A rational agent is an agent who has a goal and uses optimal behavioral strategie...
Gespeichert in:
| Datum: | 2024 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
PROBLEMS IN PROGRAMMING
2024
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/641 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-641 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/9b/be5ede29745cf29c90657dd2e5c4529b.pdf |
| spelling |
pp_isofts_kiev_ua-article-6412025-02-15T13:22:25Z Mathematical methods of planning in systems consisted of rational agents Математичні методи планування в системах, що складаються з раціональних агентів Sinitsyn, I.P. Doroshenko, A.Yu. Pashko, S.V. method; planning; rational agent; system; multi-criteria optimization; neural network UDC 004.8 метод; планування; раціональний агент; система; багатокритеріальна оптимізація; нейронна мережа УДК 004.8 The paper is devoted to mathematical methods of planning in systems consisting of rational agents. An agent is an autonomous object that has sources of information about the environment and influences this environment. A rational agent is an agent who has a goal and uses optimal behavioral strategies to achieve it. It is assumed that there is a utility function, which is defined on the set of possible sequences of actions of the agent and takes values in the set of real numbers. A rational agent acts to maximize the utility function. If rational agents form a system, then they have a common goal and act in an optimal way to achieve it. Agents use the optimal solution of the extreme problem, which corresponds to the goal of the system. The problem of linear programming is considered, in which the number of product sets produced by the system is maximized. To solve the nonlinear problem of optimizing the production plan, the conditional gradient method is used, which at each iteration allows a posteriori estimation of the error of the solution and allows stopping the calculation process after reaching the required accuracy. Since the rational agents that are part of the system can have separate optimality criteria, multi-criteria optimization problems appear. The article considers a humanmachine procedure for solving such problems, which is connected with the conditional gradient method and uses information from the decision-maker (DM) at each iteration. The difficulties of this approach are that the DM is not able to make decisions many times under the condition of a significant number of iterations of the nonlinear programming method. The article proposes to replace OPR with an artificial neural network. Nonlinear and stochastic programming methods are used to find optimal parameters of this network.Prombles in programming 2024; 2-3: 231-238 Робота присвячена математичним методам планування в системах, що складаються з раціональних агентів. Агентом вважається автономний об’єкт, який має джерела інформації про навколишнє середовище та впливає на це середовище. Раціональним агентом вважається агент, який має мету і заради її досягнення використовує оптимальні стратегії поведінки. Вважається, що існує функція корисності, яка визначена на множині можливих послідовностей дій агента і приймає значення в множині дійсних чисел. Раціональний агент діє так, щоб максимізувати функцію корисності. Якщо раціональні агенти утворюють систему, то вони мають спільну мету і діють оптимальним способом для її досягнення. Агенти використовують оптимальний розв’язок екстремальної задачі, який відповідає меті системи. Розглянуто задачу лінійного програмування, в якій максимізується кількість виготовлених системою комплектів продукції. Для розв’язування нелінійної задачі оптимізації плану виготовлення продукції застосовується метод умовного градієнта, який на кожній ітерації допускає апостеріорну оцінку похибки ортиманого розв’язку та дозволяє зупинити процес обчислень після досягнення потрібної точності. Оскільки раціональні агенти, що входять до складу системи, можуть мати окремі критерії оптимальності, виникають задачі багатокритеріальної оптимізації. В статті розглядається людино-машинна процедура розв’язування таких задач, яка пов’язана з методом умовного градієнта і на кожній ітерації використовує інформацію від особи, що приймає рішення (ОПР). Труднощі такого підходу полягають у тому, що ОПР не в змозі багаторазово приймати рішення за умови значної кількості ітерацій метода нелінійного програмування. В статті запропоновано замінити ОПР штучною нейронною мережею. Для пошуку оптимальних значень параметрів цієї мережі застосовуються методи нелінійного та стохастичного програмування.Prombles in programming 2024; 2-3: 231-238 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2024-12-17 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/641 10.15407/pp2024.02-03.231 PROBLEMS IN PROGRAMMING; No 2-3 (2024); 231-238 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2024); 231-238 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2024); 231-238 1727-4907 10.15407/pp2024.02-03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/641/693 Copyright (c) 2024 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2025-02-15T13:22:25Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
method planning rational agent system multi-criteria optimization neural network UDC 004.8 |
| spellingShingle |
method planning rational agent system multi-criteria optimization neural network UDC 004.8 Sinitsyn, I.P. Doroshenko, A.Yu. Pashko, S.V. Mathematical methods of planning in systems consisted of rational agents |
| topic_facet |
method planning rational agent system multi-criteria optimization neural network UDC 004.8 метод планування раціональний агент система багатокритеріальна оптимізація нейронна мережа УДК 004.8 |
| format |
Article |
| author |
Sinitsyn, I.P. Doroshenko, A.Yu. Pashko, S.V. |
| author_facet |
Sinitsyn, I.P. Doroshenko, A.Yu. Pashko, S.V. |
| author_sort |
Sinitsyn, I.P. |
| title |
Mathematical methods of planning in systems consisted of rational agents |
| title_short |
Mathematical methods of planning in systems consisted of rational agents |
| title_full |
Mathematical methods of planning in systems consisted of rational agents |
| title_fullStr |
Mathematical methods of planning in systems consisted of rational agents |
| title_full_unstemmed |
Mathematical methods of planning in systems consisted of rational agents |
| title_sort |
mathematical methods of planning in systems consisted of rational agents |
| title_alt |
Математичні методи планування в системах, що складаються з раціональних агентів |
| description |
The paper is devoted to mathematical methods of planning in systems consisting of rational agents. An agent is an autonomous object that has sources of information about the environment and influences this environment. A rational agent is an agent who has a goal and uses optimal behavioral strategies to achieve it. It is assumed that there is a utility function, which is defined on the set of possible sequences of actions of the agent and takes values in the set of real numbers. A rational agent acts to maximize the utility function. If rational agents form a system, then they have a common goal and act in an optimal way to achieve it. Agents use the optimal solution of the extreme problem, which corresponds to the goal of the system. The problem of linear programming is considered, in which the number of product sets produced by the system is maximized. To solve the nonlinear problem of optimizing the production plan, the conditional gradient method is used, which at each iteration allows a posteriori estimation of the error of the solution and allows stopping the calculation process after reaching the required accuracy. Since the rational agents that are part of the system can have separate optimality criteria, multi-criteria optimization problems appear. The article considers a humanmachine procedure for solving such problems, which is connected with the conditional gradient method and uses information from the decision-maker (DM) at each iteration. The difficulties of this approach are that the DM is not able to make decisions many times under the condition of a significant number of iterations of the nonlinear programming method. The article proposes to replace OPR with an artificial neural network. Nonlinear and stochastic programming methods are used to find optimal parameters of this network.Prombles in programming 2024; 2-3: 231-238 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2024 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/641 |
| work_keys_str_mv |
AT sinitsynip mathematicalmethodsofplanninginsystemsconsistedofrationalagents AT doroshenkoayu mathematicalmethodsofplanninginsystemsconsistedofrationalagents AT pashkosv mathematicalmethodsofplanninginsystemsconsistedofrationalagents AT sinitsynip matematičnímetodiplanuvannâvsistemahŝoskladaûtʹsâzracíonalʹnihagentív AT doroshenkoayu matematičnímetodiplanuvannâvsistemahŝoskladaûtʹsâzracíonalʹnihagentív AT pashkosv matematičnímetodiplanuvannâvsistemahŝoskladaûtʹsâzracíonalʹnihagentív |
| first_indexed |
2025-07-17T10:07:58Z |
| last_indexed |
2025-07-17T10:07:58Z |
| _version_ |
1850411315186630656 |
| fulltext |
231
Агентно-орієнтовані інформаційні системи
УДК 004.8 http://doi.org/10.15407/pp2024.02-03.231
І.П. Сініцин, А.Ю. Дорошенко, С.В. Пашко
МАТЕМАТИЧНІ МЕТОДИ ПЛАНУВАННЯ В СИСТЕМАХ,
ЩО СКЛАДАЮТЬСЯ З РАЦІОНАЛЬНИХ АГЕНТІВ
Робота присвячена математичним методам планування в системах, що складаються з раціональних аге-
нтів. Агентом вважається автономний об’єкт, який має джерела інформації про навколишнє середови-
ще та впливає на це середовище. Раціональним агентом вважається агент, який має мету і заради її до-
сягнення використовує оптимальні стратегії поведінки. Вважається, що існує функція корисності, яка
визначена на множині можливих послідовностей дій агента і приймає значення в множині дійсних чи-
сел. Раціональний агент діє так, щоб максимізувати функцію корисності. Якщо раціональні агенти ут-
ворюють систему, то вони мають спільну мету і діють оптимальним способом для її досягнення. Аген-
ти використовують оптимальний розв’язок екстремальної задачі, який відповідає меті системи. Розгля-
нуто задачу лінійного програмування, в якій максимізується кількість виготовлених системою компле-
ктів продукції. Для розв’язування нелінійної задачі оптимізації плану виготовлення продукції застосо-
вується метод умовного градієнта, який на кожній ітерації допускає апостеріорну оцінку похибки ор-
тиманого розв’язку та дозволяє зупинити процес обчислень після досягнення потрібної точності. Оскі-
льки раціональні агенти, що входять до складу системи, можуть мати окремі критерії оптимальності,
виникають задачі багатокритеріальної оптимізації. В статті розглядається людино-машинна процедура
розв’язування таких задач, яка пов’язана з методом умовного градієнта і на кожній ітерації використо-
вує інформацію від особи, що приймає рішення (ОПР). Труднощі такого підходу полягають у тому, що
ОПР не в змозі багаторазово приймати рішення за умови значної кількості ітерацій метода нелінійного
програмування. В статті запропоновано замінити ОПР штучною нейронною мережею. Для пошуку оп-
тимальних значень параметрів цієї мережі застосовуються методи нелінійного та стохастичного про-
грамування.
Ключові слова: метод, планування, раціональний агент, система, багатокритеріальна оптимізація, ней-
ронна мережа.
I. Sinitsyn, A. Doroshenko, S. Pashko
MATHEMATICAL METHODS OF PLANNING IN SYSTEMS
CONSISTED OF RATIONAL AGENTS
The paper is devoted to mathematical methods of planning in systems consisting of rational agents. An agent is
an autonomous object that has sources of information about the environment and influences this environment.
A rational agent is an agent who has a goal and uses optimal behavioral strategies to achieve it. It is assumed
that there is a utility function, which is defined on the set of possible sequences of actions of the agent and
takes values in the set of real numbers. A rational agent acts to maximize the utility function. If rational agents
form a system, then they have a common goal and act in an optimal way to achieve it. Agents use the optimal
solution of the extreme problem, which corresponds to the goal of the system. The problem of linear
programming is considered, in which the number of product sets produced by the system is maximized. To
solve the nonlinear problem of optimizing the production plan, the conditional gradient method is used, which
at each iteration allows a posteriori estimation of the error of the solution and allows stopping the calculation
process after reaching the required accuracy. Since the rational agents that are part of the system can have
separate optimality criteria, multi-criteria optimization problems appear. The article considers a human-
machine procedure for solving such problems, which is connected with the conditional gradient method and
uses information from the decision-maker (DM) at each iteration. The difficulties of this approach are that the
DM is not able to make decisions many times under the condition of a significant number of iterations of the
nonlinear programming method. The article proposes to replace OPR with an artificial neural network. Non-
linear and stochastic programming methods are used to find optimal parameters of this network.
Keywords: method, planning, rational agent, system, multi-criteria optimization, neural network.
© І.П. Сініцин, А.Ю. Дорошенко, С.В. Пашко, 2024
ISSN 1727-4907. Проблеми програмування. 2024. №2-3
232
Агентно-орієнтовані інформаційні системи
Вступ
В останні роки в рамках теорії
штучного інтелекту успішно розвивається
агентно-орієнтований підхід. Агенти вва-
жаються раціональними або інтелектуа-
льними та можуть утворювати багатоаге-
нтні системи і діяти заради досягнення
спільної мети. Системи агентів вивчають-
ся з різних точок зору: з позиції теорії
конфліктних процесів, теорії інформації,
соціальної психології, програмної інжене-
рії, в контексті понять електроніки. В за-
пропонованій роботі розглядається аспект
оптимізації дій агентів у складі багатоа-
гентної системи.
В роботі [1] показано, що основни-
ми видами діяльності, які пов’язані з керу-
ванням системами раціональних агентів та
окремими агентами, є кооперування (утво-
рення систем агентів), планування та ко-
ординація дій агентів, розміщування сис-
тем та розпізнавання. Проблеми коопера-
ції, планування і координації дій агентів
детально вивчаються в монографії [2]. За-
дачі розпізнавання досліджуються в робо-
тах [3, 4], задачі розміщування – в роботах
[5, 6]. В роботі [7] визначається та викори-
стовується поняття раціонального агента.
Для розв'язування екстремальних
задач планування, тобто для пошуку оп-
тимальних планів дій у багатоагентних
системах, що складаються з раціональних
агентів, застосовуються методи матема-
тичного програмування, зокрема, методи
лінійного, нелінійного, стохастичного,
дискретного програмування [8 – 12]. Для
багатоагентних систем важливе значення
мають задачі багатокритеріальної оптимі-
зації та відповідні математичні методи
[13, 14]. В роботі [14] для розв’язання ба-
гатокритеріальних задач застосовуються
людино-машинні процедури, в яких метод
нелінійного програмування поєднується з
роботою особи, що приймає рішення
(ОПР). Труднощі такого підходу поляга-
ють у тому, що ОПР не в змозі багатора-
зово приймати рішення за умови значної
кількості ітерацій методу нелінійного
програмування.
В даній роботі розглядається про-
блема оптимального планування дій бага-
тоагентної системи, що складається з раці-
ональних агентів. Описуються екстрема-
льні задачі планування та відповідні мате-
матичні методи їх розв’язування. В зада-
чах багатокритеріальної оптимізації про-
понується замість ОПР використовувати
штучну нейронну мережу та запропонова-
но способи визначення оптимальних зна-
чень параметрів такої мережі.
1. Агенти та багатоагентні
системи
Поняття раціонального агента ши-
роко використовується в теорії штучного
інтелекту, економіці, теорії ігор та має
об’єднуюче значення, дозволяючи визна-
чити основні задачі, що стоять перед аген-
тами та багатоагентними системами, взає-
мозв’язки між цими задачами тощо. В ро-
боті [7] агентом вважається автономний
об’єкт, який сприймає навколишнє середо-
вище за допомогою датчиків та впливає на
це середовище за допомогою виконавчих
механізмів. Вважається, шо програма аген-
та працює в обчислювальному пристрої та
приймає дані від датчиків, розпізнає і ана-
лізує дані, обчислює оптимальну стратегію
поведінки агента, подає команди виконав-
чим механізмам. Агентом може бути
комп’ютерна програма, робот, людина. В
[7] наведено наступне визначення раціона-
льного агента: “Для будь-якої послідовно-
сті актів сприйняття раціональний агент
повинен обрати дію, яка, як очікується,
максимізує його показники продуктивнос-
ті, з врахуванням факторів, наданих даною
послідовністю актів сприйняття та всіх
вбудованих знань, що ними володіє агент”.
Зазвичай існують різні допустимі
послідовності дій агента, які ведуть до ме-
ти. В такому разі доцільно вважати, що іс-
нує функція корисності, визначена на
множині послідовностей дій агента (або
системи агентів), яка приймає значення з
множини дійсних чисел. В [7] обгрунто-
вується таке твердження: “раціональний
агент повинен діяти так, щоб максимізува-
233
Агентно-орієнтовані інформаційні системи
ти функцію корисності”. Раціональним
агентом назвемо агент, який заради досяг-
нення мети використовує оптимальну
стратегію поведінки, максимізуючи функ-
цію корисності. Багатоагентною системою
назвемо систему, що складається з раціо-
нальних агентів, які мають спільну мету і
використовують оптимальну стратегію для
її досягнення. Можна вважати, що для сис-
теми сформульована екстремальна задача і
агенти формують стратегію поведінки,
використовуючи оптимальний розв’язок
цієї задачі. Наведемо приклади систем, що
складаються з раціональних агентів:
– система органів державного уп-
равління, підприємств, установ і організа-
цій оборонно-промислового комплексу
(ОПК) країни;
– система економік різних країн, що
розвиваються у взаємодії;
– група дронів, що переслідують
ціль.
Зауважимо, що до системи агентів
може входити центральний агент, який ви-
конує деякі з керівних функцій.
В літературі існують визначення
агентів інших типів, які відрізняються від
раціональних агентів. В роботі [2] визна-
чається поняття інтелектуального агента,
який повинен мати такі властивості: реак-
тивність, тобто здатність сприймати стан
оточуючого середовища та діяти відповід-
но; проактивність, тобто здатність до ви-
явлення власної ініціативи; соціальну ак-
тивність, тобто здатність до взаємодії з
іншими агентами для досягнення мети.
Агенти вважаються автономними.
Автономність означає, що поведінка аген-
та визначається не тільки навколишнім се-
редовищем, а й значною мірою властивос-
тями агента.
Визначення агента називається
“слабким”, якщо воно містить тільки опи-
сані ознаки, тобто автономність, реактив-
ність, проактивність, соціальну активність
[15]. Якщо крім наведених ознак у визна-
ченні агента присутні додаткові, то визна-
чення називається “сильним”. Серед дода-
ткових можуть бути такі властивості: ба-
жання – ситуації, бажані для агента; намі-
ри – те, що потрібно зробити для задово-
лення бажань або для виконання
обов’язків перед іншими агентами; цілі –
множина проміжних та кінцевих цілей
агента; знання – частина знань, що не змі-
нюється протягом існування агента; пере-
конання – частина знань агента, що може
змінюватися.
Вважаємо, що агенти володіють на-
веденими вище та, можливо, іншими влас-
тивостями тією мірою, якою це необхідно
для розв’язання задач і використання
отриманих розв’язків.
Плануванням вважається розроб-
лення способу дій багатоагентної системи
та окремих агентів у майбутньому залеж-
но від ситуацій, які можуть виникнути, ви-
бір ефективного способу дій, оптимальний
розподіл ресурсів. Існують наступні мож-
ливості планування дій системи [16]:
централізоване планування, розподілене
розроблення централізованого плану, роз-
поділене розроблення розподіленого пла-
ну. Приклади включають групи автоном-
них транспортних засобів, мобільні сенсо-
рні мережі, маршрутизацію в мережах да-
них, системи транспортування, багатопро-
цесорні обчислення, енергетичні системи
[17].
Далі зосередимося на централізова-
ному плануванні.
2. Оптимізаційні моделі
планування в багатоагентних
системах і відповідні числові
методи
Розглянемо оптимізаційні (екстре-
мальні) задачі планування в багатоагент-
них системах. Такі задачі можуть бути за-
стосовані, зокрема, в процесі планування
діяльності ОПК України. ОПК являє со-
бою систему, що складається з науково-
дослідних центрів, державних організацій,
взаємопов'язаних промислових підпри-
ємств, які виробляють товари військового
призначення. Кожний елемент цієї системи
вважаємо раціональним агентом. Припус-
тимо, існує виділений агент (наприклад,
міністерство), що володіє потрібною для
планування інформацією.
Нехай система містить m раціона-
льних агентів, кожний з яких виробляє кі-
лька видів продукції. Деякі агенти можуть
234
Агентно-орієнтовані інформаційні системи
не виробляти кінцеві продукти, виконуючи
керуючі функції. Позначимо n кількість
видів продукції, нехай −ijx вартість j -ї
продукції, що виробляється i -м агентом,
−j питома вага j -ї продукції у складі
комплекту кінцевої продукції. Позначимо
).,...,,( 1211 mnxxxx = Потрібно максимізува-
ти кількість вироблених комплектів кінце-
вої продукції
max/min
1,...,1 xj
m
i
ijnj
x →
=
=
(1)
за умов
,,...,1,,...,1,
1
lkmibxa
n
j
ikijijk ==
=
(2)
.,...,1,,..,1,maxmin njmixxx ijijij == (3)
Тут −ijka витрати k -го ресурсу на
вироблення j -ї продукції одиничної вар-
тості на i -му підприємстві, −ikb запас k -
го ресурсу на i -му підприємстві, l – кіль-
кість видів ресурсів, −maxmin , ijij xx задані чи-
сла, maxmin0 ijij xx .
Позначимо X множину векторів ,x
які задовольняють умови (2), (3). Викорис-
товуючи додаткову змінну ,y задачу (1) –
(3) запишемо так:
max,
, yx
y → (4)
,,...,1,/
1
njyx j
m
i
ij =
=
(5)
.Xx (6)
Задача (4) – (6) являє собою задачу ліній-
ного програмування. Зауважимо, що числа,
які фігурують в задачах (1) – (3) та (4) –
(6), являють собою частину знань та пере-
конань агентів, а цільова функція виражає
наміри системи.
Припустимо, в задачі (1) – (3) за-
мість цільової функції (1) використовуєть-
ся деяка цільова функція ),(xf тобто
розв’язується задача
.max)(
Xx
xf
→ (7)
Функцію )(xf вважаємо увігнутою на
множині X та гладкою на деякій околиці
множини X . Гладкість означає, що функ-
ція )(xf має неперервні частинні похідні
за всіма змінними, а околицею X назива-
ється відкрита множина, що містить X .
Для розв’язання цієї задачі доцільно вико-
ристати метод умовного градієнта [8], який
полягає в наступному. Виберемо .0 Xx
На s -му кроці ( ,...2,1,0=s ) обчислюємо
,),(maxarg xxfx s
Xx
s =
(8)
)),((maxarg
10
sss
t
s xxtxft −+=
(9)
).(1 ss
s
ss xxtxx −+=+ (10)
Тут f означає градієнт функції ,f
−ba, скалярний добуток векторів
),...,( 1 naaa = та ),,...,( 1 nbbb = тобто
.,
1
=
=
n
j
jjbaba
Позначимо x оптимальний
розв’язок задачі (7). Cправедливі співвід-
ношення [8]
,),()()( ssss xxxfxfxf −− (11)
)./1()()( sOxfxf s =− (12)
Оцінку (12) неможливо покращити. З ре-
зультатів роботи [10] та з (12) випливає,
що метод умовного градієнта не субопти-
мальний. Цей метод доцільно використо-
вувати для розв’язання задачі (7) через
можливість застосування оцінки (11), яка
дозволяє зупинити обчислювальний про-
цес після досягнення потрібної точності, та
через його простоту і задовільну швид-
кість збіжності на практиці. Метод умов-
ного градієнта використовується в наступ-
ному розділі як складова частина багаток-
ритеріальної оптимізації.
Якщо функція f не є гладкою або
замість градієнта (узагальненого градієнта)
функції f відомий його стохастичний
аналог, для розв’язання задачі (7) викорис-
товуються методи негладкої оптимізації та
стохастичного програмування [9 – 11].
Якщо замість задачі (7) розглядається за-
дача дискретного програмування, можна
використовувати методи гілок та меж, ев-
ристичні алгоритми, методи випадкового
пошуку з локальною оптимізацією, полі-
номіальні наближені схеми [12].
235
Агентно-орієнтовані інформаційні системи
3. Багатокритеріальна оптимізація
та людино-машинні процедури
Окрім спільної мети, кожний раціо-
нальний агент багатоагентної системи мо-
же мати свій критерій оптимальності.
Проблема полягає в тому, щоб знайти які-
сний розв'язок, який підходить для всіх
агентів. Вважаємо, що екстремальна задача
для i -го агента має вигляд
max,)(
Xxi xf
→ (13)
де },,...,1{ mi ),,...,( 1 nxxx = X – опукла
замкнута обмежена множина n -вимірного
евклідового простору. В [13] описані ме-
тоди розв’язання багатокритеріальних за-
дач: метод згортки, тобто заміни множини
критеріїв (13) одним критерієм; метод го-
ловного критерію; метод цільового про-
грамування; метод поступок.
Розглянемо людино-машинний ме-
тод багатокритеріальної оптимізації [14].
Цей метод використовує метод нелінійно-
го програмування, в якому напрямки руху
та величини кроків визначаються за допо-
могою ОПР. Задачу багатокритеріальної
оптимізації будемо розглядати в такому
вигляді:
.max))(),...,(()( 1 Xxm xfxfuxf
→= (14)
Тут u – функція корисності, X – опукла
замкнута обмежена множина n -вимірного
евклідового простору. Вважаємо, шо фун-
кція )(xf увігнута на X . Наступні умови
[14] є достатніми для увігнутості функції
f на множині X :
1) функція u увігнута, а функції
,,...,1, mifi = лінійні;
2) функції u та ,,...,1, mifi = увігнуті,
і функція u є неспадною за кожною
змінною.
Припустимо, що виконуються умови, які
гарантують існування неперервних час-
тинних похідних складної функції
))(),...,(( 1 xfxfu m та справедливість прави-
ла їх обчислення [18].
Для розв’язання задачі (14) викори-
стаємо метод умовного градієнта (8) – (10).
Згідно з правилом обчислення частинних
похідних від складної функції, маємо
== ))(),...,(()( 1
s
m
ss xfxfuxf
.)(
1
=
=
m
i
s
i
s
i
xf
f
u
Тут ( ) − s
ifu i -а частинна похідна від u ,
обчислена в точці )),(),...,(( 1
s
m
s xfxf а
− )( s
i xf градієнт функції ,if обчислений
в точці .sx Лінійна функція ,),( xxf s що
входить до співвідношення (8), відома не
повністю, оскільки не відомі величини
( ) .s
ifu Зауважимо, що у співвідношенні
(8) вираз xxf s ),( можна помножити на
додатнє число. Зокрема, його можна розді-
лити на будь-який додатній коефіцієнт
( ) .s
ifu (Можна також вибрати від’ємний
коефіцієнт, такий випадок розглядається
аналогічно). Без втрати загальності вважа-
ємо, що за дільника обрано перший коефі-
цієнт ( ) .1
sfu Співвідношення (8) запи-
шемо так:
,,)(maxarg
1
xxfwx
m
i
s
i
s
i
Xx
s
=
= (15)
де ( ) ( ) ./ 1
ss
i
s
i fufuw =
В (15) усі величини, крім ,s
iw вва-
жаються відомими. Величини ,s
iw що по-
казують відносну важливість 1-го та i -го
критеріїв, визначаються за допомогою
ОПР, після чого виконується оптимізація
(15). В роботі [14] запропоновано такий
спосіб визначення .s
iw
Припустимо, функція u задоволь-
няє умови, що гарантують справедливість
теореми про повний приріст функції бага-
тьох змінних [18]. Нехай у точці
))(),...,(( 1
s
m
s xfxf критерій 1f отримав
приріст ,1 критерій −if приріст ,i зна-
чення інших критеріїв не змінилися. Має-
мо
),(),...,(,)(( 1211
s
i
ss xfxfxfuu −+=
−+ + ))(),...,(,)( 1
s
m
s
ii
s
i xfxfxf
( ) +=− 111 ))(),...,(( ss
m
s fuxfxfu
( ) ( ).)()( 22
1 ii
s
i ofu +++
Нехай ОПР вибирає величини i ,1 так,
щоб виконувалась рівність .0=u В та-
236
Агентно-орієнтовані інформаційні системи
кому разі приблизно виконується рівність
( ) ( ) ,011 =+ i
s
i
s fufu тобто
.1
i
s
iw
−= (16)
На кроці (9) методу умовного граді-
єнта розв’язується задача
)),...,((( 1
sss xxtxfu −+
.max)))((
10
→−+
t
sss
m xxtxf (17)
Тут цільова функція є функцією однієї
змінної t . На одному графіку зображують-
ся криві )),(( sss
j xxtxf −+ ,,...,2,1 mj = на
проміжку .10 t Аналізуючи побудовані
графіки, ОПР вибирає найкраще значення
t з проміжку ].1,0[
Отже, в процесі застосування мето-
ду умовного градієнта за допомогою ОПР
розраховуються величини s
iw за форму-
лою (16), оптимальне значення t в задачі
(17) і, можливо, здійснюється вибір почат-
кової точки .0x Всі інші розрахунки вико-
нує комп’ютерна програма.
Очевидно, ОПР не завжди може
якісно виконати покладені на нього за-
вдання в процесі багатокритеріальної оп-
тимізації. Крім того, метод нелінійного
програмування може виконувати велику
кількість ітерацій, що неприйнятно для
ОПР. Тому замість ОПР доцільно викорис-
тати систему штучного інтелекту. Зокрема,
можна використати штучну нейронну ме-
режу, що розраховує величини ,s
iw вико-
ристовуючи формулу (16), та оптимальне
значення t в задачі (17). Такі мережі розг-
лядаються в наступному розділі.
4. Використання штучних
нейронних мереж в методах
оптимізації
Штучні нейронні мережі (далі –
нейронні мережі) набули широкого розпо-
всюдження у складі систем штучного інте-
лекту. Математичною моделлю штучного
нейрона вважаємо функцію
,
1
=
=
r
j
jj xwfy де дійсні числа −rxx ,...,1
входи нейрона, дійсне число −y вихід,
дійсні числа −rww ,...,1 вагові коефіцієнти.
Нейронна мережа, що об’єднує ве-
лику кількість штучних нейронів, здатна
розв’язувати складні задачі. Вважаємо, що
мережа має n входів та один вихід і обчи-
слює деяку функцію ).,...,( 1 nxxf Нехай
−= nnI ]1;0[ n -вимірний одиничний куб.
Важливе значення має наступна теорема
[19].
Теорема 1. Для будь-якого цілого
2n існують такі визначені на одинично-
му відрізку ]1;0[1 =I неперервні дійсні фу-
нкції ),(tij що кожна визначена на n -
вимірному одиничному кубі nI непере-
рвна дійсна функція ),...,( 1 nxxf представ-
на у вигляді
,)(),...,(
12
1 1
1
+
= =
=
n
i
n
j
jijin xxxf (18)
де функції )(yi дійсні та неперервні.
Зауважимо, що функції )( jij x не
залежать від функції .f Формулу (18) мо-
жна представити у вигляді нейронної ме-
режі, що об’єднує 232 2 ++ nn штучних
нейрони. Отже, будь-яку визначену на n -
вимірному одиничному кубі nI неперерв-
ну дійсну функцію ),...,( 1 nxxf можна об-
числити за допомогою нейронної мережі.
Сигмоїдною називається така фун-
кція ),(t що
−→
+→
→
.,0
,,1
)(
t
t
t
Наприклад, −+= − )1/(1)( tet сигмоїдна
функція. Позначимо )( nIС простір непе-
рервних функцій на .nI В роботі [20] дове-
дено таку теорему.
Теорема 2. Нехай − будь-яка не-
перервна сигмоїдна функція. Скінчені су-
ми виду
( )
=
+=
N
j
jjj xyxG
1
,)( (19)
( де −jj , дійсні числа, −jy вектори з
дійсними компонентами, )),...,( 1 jnjj yyy =
утворюють щільну множину в ).( nIС Ін-
шими словами, для кожних )( nIСf та
0 існує сума )(xG виду (19) така, що
237
Агентно-орієнтовані інформаційні системи
,)()( − xfxG .nIx
Формулу (21) можна представити у
вигляді нейронної мережі, що об’єднує
1+N штучний нейрон, за допомогою яких
обчислюються значення функції .G Тео-
реми 1, 2 обгрунтовують придатність ней-
ронних мереж для обчислення будь-яких
неперервних функцій. Нейронна мережа,
яка побудована на основі теореми 1 і точно
обчислює значення функції ,f містить об-
межену кількість нейронів. Функції ,, iji
значення яких обчислюються в нейронах,
можуть бути різними і не мати неперерв-
них похідних. Нейронна мережа, яка побу-
дована на основі теореми 2 і приблизно
обчислює значення функції ,f містить
штучні нейрони, які використовують одну
сигмоїдну функцію . Кількість штучних
нейронів у такій нейронній мережі не об-
межується. Якщо вибрати сигмоїдну фун-
кцію ),(t що має неперервну похідну, то
величина G буде мати неперервні частинні
похідні за всіма величинами jj , та за
всіма компонентами векторів ,jy що може
відігравати важливу роль у процесі пошу-
ку оптимальних значень цих параметрів.
Припустимо, на множині X задано
розподіл імовірностей, та −x випадковий
елемент [21]; тут ,Xx −X замкнута
обмежена множина n -вимірного евклідо-
вого простору. Позначимо ),,...,( 1 N =
),,...,( 11 Nnyyy = ),,...,( 1 N =
( ) ).(,),,,(
1
xfxyxyq
N
j
jjj −+=
=
Виберемо параметри ,, y як оптималь-
ний розв’язок задачі
.min),,,(),,(
,,
2
y
xyEqyF →= (20)
Тут −E знак математичного сподівання.
Припустимо, сигмоїдна функція
)(t має неперервну похідну та виконані
умови, достатні для диференціювання під
знаком математичного сподівання. Маємо
( ) ,,2),,( jj
j
xyqEyF
+=
( ) ,,2),,( jjkj
jk
xyxqEyF
y
+=
( ) ,,2),,( jjj
j
xyqEyF
+=
.,...,1,,...,1 nkNj ==
Тут ( )− t похідна від функції ( ).t
Отже, легко обчислюється вектор
),,,,( xyg математичне сподівання якого
дорівнює градієнту ),,( yF функції
),,,( yF тому для розв’язування задачі
(20) можна застосувати методи стохастич-
ного програмування [9 – 11]. У випадку,
коли цільова функція задачі (20) не опукла,
за допомогою цих методів отримаємо лока-
льний мінімум. У такому разі слід скорис-
татися методом випадкового пошуку з ло-
кальною оптимізацією [12], у якому лока-
льні оптимуми обчислюються за допомо-
гою методу стохастичного програмування.
Виберемо )),(),...,(()( 1 xfxfuxf m=
де −u цільова функція задачі (14), та роз-
рахуємо одним із описаних способів пара-
метри ,, y функції (19). Відповідну ней-
ронну мережу використаємо замість ОПР
для розв’язання задачі багатокритеріальної
оптимізації (14).
Висновки
В роботі розглянуто проблему оп-
тимального планування дій в багатоагент-
них системах, що складаються з раціона-
льних агентів. Наведено визначення по-
нять агента, раціонального агента, систе-
ми, що складається з раціональних агентів.
Основна увага приділяється централізова-
ному плануванню. Описано екстремальні
задачі планування та метод умовного гра-
дієнта. Розглянуто людино-машинну про-
цедуру розв’язування задач багатокритері-
альної оптимізації. Запропоновано вико-
ристати штучну нейронну мережу замість
ОПР. Запропоновано методи визначення
оптимальних значень параметрів такої ме-
режі.
Література
1. Pashko S.V., Sinitsyn I.P. Optimal solutions
in systems consisted of rational agents.
Artificial Intelligence. 2023. № 2. P. 16–26.
(In Ukrainian).
2. Wooldridge M. An introduction to multiagent
systems. John Wiley & Sons, 2009. 348 p.
238
Агентно-орієнтовані інформаційні системи
3. Shlesinger M.I., Glavach V.A. Ten lectures on
statistical and structural recognition. K.:
Nauk. Dumka, 2004. 546 p. (In Russian).
4. Gupal A.M., Sergienko I.V. Optimal
recognition procedures. K.: Nauk. Dumka,
2008. 232 p. (In Russian).
5. Pashko S.V. Optimal placement of multy-
sensor system for threat detection.
Cybernetics and Systems Analysis. 2018. V.
54, N 2. P. 249–257.
6. Pashko S., Molyboha A., Zabarankin M.,
Gorovyy S. Optimal sensor placement for
underwater threat detection. Naval Research
Logistics. 2008. Vol. 55, N 7. P. 684–699.
7. Russell S., Norvig, P. Artificial intelligence: a
modern approach, 4th Edn. Hoboken, NJ:
Pearson, 2021. 1115 p.
8. Polyak B.T. Introduction to optimization.
Moscow: Nauka, 1979. 384 p. (In Russian).
9. Mikhalevich V.S., Gupal A.M., Norkin V.I.
Methods of non-convex optimization.
Moscow: Nauka, 1987. 280 p. (In Russian).
10. Nemirovskii A.S., Yudin D.B. Complexity of
problems and effectiveness of optimization
methods. Moscow: Nauka, 1979. 383 p. (In
Russian).
11. Ermoliev Yu.M. Methods of stochastic
programming. Moscow: Nauka, 1976. 240 p.
(In Russian).
12. Papadimitriou C., Steiglitz K. Combinatorial
optimization: Algorithms and Complexity.
New Jersey: Prentice-Hall, Inc. Englewood
Cliffs, 1982.
13. Kondruk M.E., Malyar M.M. Multi-criteria
optimization of linear systems. Uzhhorod:
DVNZ «Uzhgorod National University»,
2019. 76 p. (In Ukrainian).
14. Geoffrion A.M., Dyer J.S., Fienberg A. An
Interactive Approach for Multi-Criterion
Optimization, with an Application to the
Operation of an Academic Department.
Management Science. 1972. Vol. 19, N 4,
Part I. P. 357–368.
15. Gorodetsky V.I., Grushinsky M.S., Khabalov
A.V. Multiagent systems: review of the
current state of theory and practice. URL:
https://www.slideshare.net/rudnichenko/mas-
10320580. 2015. (In Russian).
16. Durfee E.H. Distributed problem solving and
planning. ECCAI Advanced Course on
Artificial Intelligence. Berlin, Heidelberg:
Springer Berlin Heidelberg. 2001. P. 118–
149.
17. Shamma J. Cooperative control of distributed
multi-agent systems. John Wiley & Sons.
2008. 435 p.
18. Fikhtengolts G.M. Course of Differential and
Integral Calculus. Volume 1. Moscow:
Nauka, 1969. 607 p. (In Russian).
19. Kolmogorov A.N. On the representation of
continuous functions of several variables in
the form of superpositions of continuous
functions of one variable and addition. DAN
USSR. 1957. Vol. 114, № 5. P. 953–956. (In
Russian).
20. Cybenko G. Approximation by Superpositions
of a Sigmoidal function. Mathematics of
Control, Signals and Systems. 1989. Vol. 2, N
4. P. 303–314.
21. Shiryaev A.N. Probability. Moscow: Nauka,
1980. 574 p. (In Russian).
22. Demyanov V.F., Malozemov V.N.
Introduction to minimax. Moscow: Nauka,
1972. 368 p. (In Russian).
Одержано: 14.04.2024
Внутрішня рецензія отримана: 21.04.2024
Зовнішня рецензія отримана: 26.04.2024
Про авторів:
Сініцин Ігорь Петрович,
доктор технічних наук,
старший науковий співробітник,
директор Інституту програмних систем
НАН України.
http://orcid.org/0000-0002-4120-0784
Дорошенко Анатолій Юхимович,
доктор фізико-математичних наук,
професор, завідувач відділу
http://orcid.org/0000-0002-8435-1451
Пашко Сергій Володимирович,
доктор фізико-математичних наук,
провідний науковий співробітник.
http://orcid.org/0000-0002-0453-4128
Місце роботи авторів:
Інститут програмних систем НАН
України,
03187, м. Київ, проспект Академіка
Глушкова, 40.
E-mail: pashko1955@gmail.com
|