Книги по разным темам Pages:     | 1 |   ...   | 9 | 10 | 11 | 12 | 13 |   ...   | 17 |

+ ca ( ya )}] = Фmax + max[ Y '- min { Y + ca ( ya )}], С технической точки зрения, пересчет оптимальных планов Y ' Y, ya: Y + ya =Y ' при введении нового агента сводится к вычислению новой фунпоэтому условие выгодности добавления нового агента - кции совокупных затрат CN +a (YN +a ) = min [CN (YN ) + ca (ya )] и d YN + ya =YN +a (86) Фmax - Фmax = max[ Y '- min { Y + ca ( ya )}] > 0.

Y ' Y,ya: Y + ya =Y ' последующей оптимизации целевой функции центра ФN+a(.). Эта Можно вычислить внутренний минимум выражения (86).

задача при известных функциях затрат CN (.) и ca (.) является Условие Лагранжа (равновесные значения Y и ya обозначены задачей выпуклого программирования.

знаком **, в отличие от старого равновесия Y*) дает условие на В то же время, для минимизации времени перенастройки * системы при изменении ее состава или изменении функции производную затрат нового агента: = c'a (ya*). Отсюда можно дохода центра полезно для имеющегося состава агентов иметь * выразить оптимальный план нового агента ya* = [c'a ]-1( ). Тогда * рассчитанные оптимальные планы yi (Y ) в некоторой ** * Y = Y '- ya* и условие (86) преобразуется к выражению окрестности оптимального совокупного плана Y*.

* * * * (87) max[ Y '- (Y '- ya*) - ca (ya*)}] = ya* - ca ( ya*) > 0.

Y ' Задача II Сведение к линейному случаю привело к исчезновению Y ' из Прямолинейный подход к задаче первоначального формимаксимизируемого выражения. Значит в линейном случае выбор рования состава N агентов из множества претендентов Nнового плана из малой окрестности точки Y* не влияет на (каждый из претендентов полностью описывается своей функци** * выигрыш центра. Если выбрать Y = Y, то результат решения ей затрат ci(yi)), состоит в рассмотрении 2N0 -1 задач стимулиролинеаризованной задачи I.2 совпадает с решением линеаризованвания для каждого непустого подмножества N0 и последующего ной задачи I.1 (получаемой из условия (83) линеаризацией выбора подмножества, доставляющего максимум целевой функфункций дохода и затрат аналогично (85)).

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

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

* * * для каждого состава N N0 состоит из следующих этапов:

(92) i** = arg max[H (YN ) - YN - ci0], где YN = [H ']-1( ).

i i NN1. Вычисление совокупной функции затрат (задача выпуклой Как видно из этого выражения, даже рассмотрение линейных оптимизации с |N| переменными и одним ограничением):

функций затрат, хоть и упрощает задачу, все же не позволяет (88) CN (Y ) = min (yi ).

c i y: yi =Y ввести априорное ранжирование агентов на основании только iN iN знания функций их затрат, что позволило бы, не решая задачу 2. Решение одномерной задачи выпуклой оптимизации стимулирования, определить оптимальный состав системы.

* (89) ФN max (YN ) = max[H (Y ) - CN (Y )].

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

(90) N* Arg maxФN max.

ci ( yi ), yi > NN~ ci (yi ) = и решим N0-мерную задачу максимизации Один из возможных подходов к упрощению задачи состоит в 0, yi = поиске условий, позволяющих сократить множество рассматри ваемых составов. Примеры таких условий рассматриваются ниже. разрывной функции y* = arg maxH ( yi ) - c ( yi ). Если оп ~i y iN0 iN Мы не будем рассматривать случай, когда ci0 = 0 для всех тимальный план некоторого агента равен нулю, значит, этот агент i N0. В этом случае, очевидно, N* = N0. Однако если условие не входит в оптимальный состав исполнителей. Этот прием ci0 = 0 выполняется только для некоторых агентов (множество позволяет свести 2( 2N0 -1 ) задач оптимизации к двум, но с таких агентов обозначим M), этот факт позволяет сократить разрывными функциями.

количество рассматриваемых составов только составами, в Пример 6. Задача первоначального формирования состава.

которые входят все агенты множества M.

Рассмотрим задачу выбора состава исполнителей из двух Рассмотрим агентов с линейными затратами вида претендентов с функциями затрат 2 ci ( yi ) = ci0 + yi.

i c1( y1) = 2 + y1, c2 (y2 ) = 1+ 2y2.

Выражение (88) для произвольного состава N N0 приниКак следует из вида функций затрат, первый кандидат мает вид отличается относительно большей производительностью (его функция затрат возрастает более полого), но и более высокими (91) CN (Y ) = ci0 + Y min, i iN iN начальными затратами, чем второй.

то есть для любого состава работает только самый дешевый Пусть доход центра возрастает линейно, H (Y ) = Y.

агент, остальные получают нулевой план и минимальную ставку ~ ~ ~ Построим функцию затрат C(Y ) = min (c1(y1) + c2(y2)).

y1+ y2=Y ci0. Поэтому очевидно, что в линейном случае кандидатами на 84 В случае двух претендентов нужно рассмотреть лишь три Если центр по тем или иным причинам не занимается оптивозможных состава - функции затрат для каждого из них можно мизацией состава системы, то сами агенты могут внутренними построить непосредственно: усилиями лоптимизировать состав, незаметно для центра исключив из нее неэффективный агент и распределив его план (а 2 2 C1(Y ) = 2 + Y, C2(Y ) = 1+ 2Y, C12 (Y ) = 3 + Y, также и стимулирование) между собой. При этом все агенты выигрывают, даже исключенный, так как он получает за свой функции затрат системы, состоящей из первого агента, второго уход выплату. Проигрывает только центр, поскольку он агента и обоих агентов соответственно.

~ продолжает платить за уже отсутствующего в системе агента.

Очевидно, что C(Y ) = min[C1(Y ),C2(Y ),C12(Y )], то есть Для описанной лоптимизации состава системы требуются 1+ 2Y 2 при Y < совместные действия всех или части агентов, ведь агент не может ~ сам незаметно устраниться - кто-то должен взять на себя выполC(Y ) = + Y при 1 Y < 1.нение его плана. Поэтому вполне логичным представляется 3 + 5Y / 9 при Y 1.5.

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

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

водных функции дохода центра и функции минимальных затрат ~ ~ Для произвольной коалиции агентов S введем обозначение C(Y ). Это условие имеет вид: H '(Y ) = = C'(Y ). Таким образом, CS (Y ) := min (zi ) для функции наименьших затрат коалиции ci в зависимости от значения доходности, оптимальным соста=Y zi iS iS вом будет:

S по реализации этой коалицией некоторого суммарного действия 1. При 0 < 3 - система из единственного первого агента, * 2. при 3 < 4.25 - система из единственного второго агента, Y. Обозначим YS = yi - план, назначенный центром коалиции iS 3. при > 4.25 - система из обоих агентов (при этом план второго агента в два раза меньше плана первого агента). Х S, = - стимулирование, назначенное центром коалиции S S i iS Коалиционное взаимодействие в задачах формирования за достижение плана YS.

состава Итак, пусть образовалась коалиция S N. Действие коалиции заключается в выборе подмножества своих участников, В существующих работах [9, 26, 59, 60, 62], посвященных позволяющего с минимальными затратами реализовать назначенисследованию задач стимулирования, почти никогда не делалось ный центром план YS (чтобы центр не заметил изменения состава, предположения о том, что центр может изменять состав ОС. Это коалиция должны выполнить план). Тогда суммарный выигрыш значит, что при решении задачи стимулирования центр назначает коалиции (характеристическая функция игры) определяется каждому агенту стимулирование, как минимум, равное постоi выражением янной составляющей ci0 его функции затрат, даже если план для (93) v(S) = - min CK (YS ).

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

C-ядра) кооперативной игры.

86 Необходимое и достаточное условие непустоты C-ядра (11) то верно и неравенство (94). Обозначим xi = ziS, i N \{l}, S S:iS для данной игры можно записать следующим образом: для тогда любого сбалансированного покрытия xi = ziS = yi - yl = ziS = (94) min CK (YS ) min CL (YN ). S S S {l} S KS LN iN \{l} iN \{l} S:iS SN iS\{l} SN iS SN Обозначим = yi - yl = yi - yl = YN - yl.

S {l} {l} {l} iN S:iS iN (95) K(S) = arg min CK (YS ) - лэффективное подмножество KS Уменьшим еще левую часть неравенства (101):

коалиции, ci (xi ) + {l}cl ( yl ) zimin- yl ci (zi ) + {l}cl ( yl ) = =YN {l} iN \{l} iN \{l} (96) (ziS )iK (S ) = arg min (zi ) - лэффективное распредеci iN \{l} zi =YS iK (S ) iK (S ) = CN \{l}(YN - yl ) + cl ( yl ).

{l} {l} ление планов коалицией S между членами ее эффективного Таким образом, необходимо доказать неравенство подмножества K(S).

cl (yl ) CN \{l}(YN ) - CN \{l}(YN - yl ).

{l} {l} Введем также индикатор В силу выпуклости CN \{l}(.) можно увеличить правую часть 1, i K (S) (97) =.

iS неравенства следующим образом:

0, i K(S) CN \{l}(YN ) - CN \{l}(YN - yl ) [CN \{l}(YN ) - CN \{l}(YN - yl )].

{l} {l} Тогда условие сбалансированности (94) можно преобразовать к виду:

Значит, теорема верна, если (98) CK (S ) (YS ) CK ( N )(YN ).

S cl (yl ) + CN \{l}(YN - yl ) = CN (YN ) CN \{l}(YN ) = min CK (YN ), KN SN а это неравенство очевидно. Х Или, изменяя порядок суммирования в левой части, Из доказанной теоремы следует, что если некоторого агента (99) S iSci (ziS ) iNci (ziN ).

iN S:iS iN выгодно исключить из любой коалиции, то такой агент будет Теорема 4. Если есть такой агент (с номером l), что его выгодно исключен, а оставшиеся агенты перераспределят план так, чтобы исключить из любой коалиции, в которую он входит (за минимизировать суммарные затраты всей системы по реализации исключением, естественно, коалиции {l}), то С-ядро кооперативплана Y *.

ной игры (93) не пусто. Иначе говоря, C-ядро игры не пусто если Если бы центр знал о выгодности исключения этого агента из системы, но не имел возможности изменить суммарный план (100) l N : S N, = 0.

lS системы1, он именно таким образом перераспределил бы Доказательство. Если выполнено (100), то индивидуальные планы между остающимися агентами. Таким ci (ziS ) = ci (ziS ) + cl ( yl ).

S iS S {l} образом, максимальная кооперация агентов в данном случае iN S:iS iN \{l} S:iS является, несомненно, положительным явлением с точки зрения Из свойств выпуклых функций [42] ci ( Sci (ziS ) S ziS ).

iN \{l} S:iS iN \{l} S:iS Например, в силу необходимости выполнения центром взятых на себя Значит, если верно неравенство обязательств перед внешним заказчиком. Как показано выше, при большом (101) ci ( ziS ) + cl ( yl ) ci (ziN ), количестве агентов изменение суммарного плана дает лишь прибавку второго S {l} iN \{l} S:iS iN \{l} порядка малости к выигрышу центра, в то время как исключение лишнего агента приводит к существенному уменьшению затрат системы.

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

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

в ОС, могут привлекать других агентов со стороны. Доказательство. Для того, чтобы воспользоваться результатами, Итак, имеется центр с целевой функцией полученными в разделе 2.2, сведем игру агентов к задаче стимулирования с распределенным контролем, в которой агенты мноФ(y) = H ( yi ) - (y), и n агентов с целевыми функциями i iN iN жества N будут выполнять роль центров промежуточного уроfi ( y) = ( y) - ci ( yi ). Центр использует систему стимулирования вня, а дополнительный агент - роль стимулируемого ими агента.

i * (76)-(77). В этих условиях агенты заинтересованы в выполнении Обозначим i ту часть своего плана yi, которую i-й проплана yN. Пусть, однако, имеется дополнительный агент с межуточный центр передает агенту. Тогда действие агента функцией затрат ca ( ya ), о котором центру неизвестно, но представляет из себя вектор = (i )iN. Функции дохода известно агентам. Условия выгодности для коалиции агентов S лцентров имеют вид привлечения его к выполнению плана описываются следующим * * i - ci ( yi - i ), i yi критерием:

Hi (i ) =, * min[CS (YS - ya) + ca (ya )] CS (YS ).

- ci (0), i > yi i ya а затраты агента c() = ca ( i ).

Pages:     | 1 |   ...   | 9 | 10 | 11 | 12 | 13 |   ...   | 17 |    Книги по разным темам