Воронов Е. М. Методы оптимизации управления ММС на основе стабильно-эффективных игровых решений (2001) (1264203), страница 29
Текст из файла (страница 29)
Поэтому коалиция Kтеряет стимул для замены ( u K , u N / K ) на ( v K , u N / K ) .Определение 4.1. Набор ( u K , u N / K ) является угрозой и контругрозой(УКУ) для коалиции K, если для любой ее угрозы существует контругрозаконтркоалиции N/K.Определение 4.2. Набор ( u K , u N / K ) является УКУ-оптимальным решением дифференциальной коалиционной игры, если для любой угрозылюбой коалиции K у контркоалиции существует контругроза.Глава 4. Стабильные коалиционные решения в ММС на основе УКУ143Замечание 4.1. Если N = 2, то определения (4.1), (4.2) без измененияпереносятся на бескоалиционную игру двух игроков.Но при N > 2 в бескоалиционной игре не существует контругроз.Замечание 4.2. Равновесие по Нэшу – частный случай УКУ-оптимальности игры (см.
гл. 3).Действительно, в ситуации Нэш-равновесия ( u rK , u rN / K ) замена u K наv K приводит по определению к неравенству (4.9) противоположного знака (угроза не существует) и нет необходимости в контругрозе.В фундаментальной работе [39] на основе принципа УКУ сформировано общее понятие V-оптимальности и коалиционного равновесия.Угроза считается эффективной, если на нее нет контругрозы.Исход игры считается оптимальным, если против него нет эффективных угроз. Множество всех оптимальных исходов есть V-решение игры.Тогда для динамической игры исход называется V-оптимальным, еслина любую угрозу против него существует контругроза.
Определения 3.6,3.7 для коалиционной дифференциальной игры принимают вид:Определение 4.3. Ситуация u будет коалиционным равновесием, еслиu ∈V и для любого K ∈ P ⊂ P и uK ∈ U K ситуация uKp минимизирует(максимизирует) по Парето вектор потерь (выигрышей) J i (u uK )i∈K в U K .Обобщает понятие коалиционного равновесия так называемое сильноеравновесие [26].Определение 4.4. Сильным равновесием называется ситуация u c , еслиона оптимальна по Парето в U K относительно J i ( u c u K )i∈K для всехK⊂N.Против сильного равновесия нет угроз.
Кроме того, оно является равновесием при любом Р.В работе [39] даны общие условия существования коалиционного равновесия.Утверждение 4.1 [39]. Если множества U i компактны, а функции J i непрерывны по u ∈ U N , то коалиционное равновесие u p существует хотя быдля P = {N } .В работе [32] эти условия конкретизируются в рамках варианта УКУоптимальности и формируются необходимые или достаточные условияопределения УКУ-оптимальных решений дифференциальной коалиционной игры.Рассмотренные условия сложны и трудноприменимы для практическихприложений за исключением «линейно-квадратичных» моделей игр [32,стр.
162], поэтому обсудим эти условия с позиции требуемых свойствмножеств и функций для существования решений.144Стабильные эффективные решения и компромиссы. Часть IТак, для определения УКУ-оптимальных решений из необходимых( )условий [32, стр. 144] требуется компактность множеств U i , i = 1, Nинепрерывная дифференцируемость функции J i opt (t , x, u K , u N / K ) по t и x.При поиске оптимальных УКУ-решений игры на Парето-множествепоказателей ( J K , J N / K ) и соответственно на множестве Парето-решений( u пK , u пN / K ) рассмотрены два случая.Введена функцияH K (t , x, v K , u пN / K ) == FK (t , x, v K , u пN / K ) +T∂VK ∂VK n+ ⋅ f (t , x, v K , u N / K );∂t ∂x (4.11)гдеTVK (t=, x)п∫ FK ( t, x, v K , u N / K ) ⋅ d t + ΦK (T , x);tпп=VK (t0 , x 0 ) J=K ( u K , u N / K ); VK (T , x ) Φ K (T , x ); .x f=x(t0 ) x 0 .=(t , x, u пK , u пN K );Случай 1.
Для любых v K ∈ U K выполняется неравенствоH K (t , x, v K , u пN / K ) ≥ 0 .(4.12а)Случай 2. Существуют v K ∈ U K , для которых неравенство (4.12) нарушается.Утверждение 4.2 (случай 1). Для того чтобы ( u пK , u пN / K ) ∈ U являлисьУКУ-решениями для коалиции K, достаточно, чтобы при любых v K ∈ U Kвыполнялось неравенство (4.12а).Также может быть показано [32], что при условии (4.12а) имеет местоотсутствие угроз.
Тогда в соответствии с определением 3.12 при фиксацииP = {K , N / K } имеет место равновесие по Нэшу.То есть выполнения условия (4.12а) достаточно, чтобы решения( u пK , u пN / K ) были равновесными, что имеет место в частном случае УКУ, когда угроза K отсутствует. Поэтому условия (4.12а) – также достаточныеусловия равновесности решений по Парето. Данное свойство справедливо,если (4.12а) выполняется и для любой другой фиксированной структуры(4.1).Утверждение 4.3 (случай 2) [32]. Для того чтобы решения ( u пK , u пN / K )были для коалиции K УКУ-решениями, достаточно, чтобы при(4.12б)H K (t , x, v K , u пN K ) < 0, ( I K ( v K , u пN / K ) < I K ( u пK , u пN / K ))Глава 4. Стабильные коалиционные решения в ММС на основе УКУимело местоH K (t , x, v K , v N / K ) ≥ 0;H N / K (t , x, v K , v N / K ) ≤ 0.Здесь H N/K определено аналогично H K с заменой K на N/K.До к аз ат е льс тво .
Если решение v K реализует угрозу и()(145(4.13))J K v K , u пN / K < J K u пK , u пN / K ,то неравенство (4.12б) выполняется. Так какПарето, то()( u пK , u пN / K )(оптимальны по)J N / K v K , u пN / K > J N / K u пK , u пN / K .Из (4.13) соответственно следует [32]:()J K ( v K , v N / K ) ≥ J K u пK , u пN / K ;()J N / K ( v K , v N / K ) ≤ J N / K u пK , u пN / K .(4.14)(4.15)Объединяя (4.15) с (4.14), получаем (4.10).Таким образом, наличие угрозы K в точке ( u пK , u пN / K ) (4.12б) и условий(4.13) позволяет находить УКУ-решения на Парето–границе.
Наличиесильной выпуклости J K , J N / K по u K и u N/K соответственно тем болееобуславливает выполнение (4.13).При кажущейся конструктивности необходимых и достаточных условий применить их сложно.Поэтому, используя определенным образом условия существованияУКУ-решений, можно предложить следующий двухэтапный подход ихопределения [50]. На первом этапе на основе простейшей параметризацииуправлений и создания ортогональной сети на основе определений УКУформируется сеть приближенных решений.
На втором этапе, используянайденные оценки множества УКУ в качестве начальных приближений всетевой «ячейке», решается задача определения точных УКУ-решений наоснове понятия локальных угроз и контругроз [32, 50].4.3. ЭТАП 1: ВЫБОР НАЧАЛЬНЫХ ПРИБЛИЖЕНИЙ УКУ НА ОСНОВЕПОСТРОЕНИЯ ОРТОГОНАЛЬНОЙ РАВНОМЕРНОЙ СЕТИ4.3.1.Формирование ортогональной равномерной сетиРассмотрим скалярные кусочно-непрерывные управления u j (t ) коалиций видаСтабильные эффективные решения и компромиссы. Часть I146u j (t ) = q1 j ⋅ (1[t − t0 ] − 1[t − t1 ]) + ... + qnj ⋅ (1[t − tn −1 ] − 1[t − tn ]) ,{}1, mk ,j∈MK =(4.16а)где qij min ≤ qij ≤ qijmax , а qijmin и qijmax определяются значениями сети пара-(метров qijmin ≥ qLij ; qijmax ≤ qH ij).Управление (4.16а) является параметризованной программой вида(4.14) на r-м интервале ПКЗУ при r = 1u j=(t )n∑ qij (1[t − ti −1 ] − 1[t − ti ]),i =rtr −1 ≤ t ≤=tn T , =r 1, n .(4.16б)На каждом интервале ПКЗУ формируется (n – r) наборов m K -мернойортогональной сети шагов управлений (или m K наборов (n – r)-мерной ортогональной сети каждого управления).Тогда для выбора начальных приближений УКУ для ПКЗУ вида (4.16а)для каждого i-го шага управления(4.17)uij (t ) = qij ⋅ (1[t − ti −1 ] − 1[t − ti ])формируется m K -мерная совместная ортогональная сеть.На областях параметров qi , i = r, n определяется множество (n – r)равномерных ортогональных сетей точек размерности m K и густоты li , намножестве которых и вычисляются области стабильного по УКУ взаимодействия коалиций [55].Множество точек этой сети размерности (( n − r ) ⋅ mK ) отображаются впространство показателей J, формируя таким образом ее допустимый вид.Если рассматривается двухкоалиционное взаимодействие, то на каждом i-м шаге изменения управления формируется совместная двухмернаяортогональная равномерная сеть, представленная на рис.
4.1.qi2qHi2 = 1…qLi1 = qLi2 = 0lqHi1 = 1 qi1Рис. 4.1. Формирование ортогональной сети на пространстве параметровГлава 4. Стабильные коалиционные решения в ММС на основе УКУ147В том случае, когда имеет место вырожденное управление, постоянноена всем интервале взаимодействия u j (t=) q=const , сеть формируетсяjперед началом игры и остается неизменной при взаимодействии (не зависит от i).Густота сети l i (длина шага сети) неявно характеризует точность определения области показателей J в целом, а также области УКУ-равновесныхточек в частности.
В каждом конкретном случае «густота» достаточная всмысле точности области J определяется свойствами сжатия функционалов J. При этом густота сети и размерность области q непосредственносвязаны с временем оптимизации – уменьшение шага сети ведет к значительному увеличению продолжительности работы алгоритма поиска УКУоптимальных решений, так как количество «ячеек» сети N яi и точек сетиN тi определяется из выраженияmk qqH ij − qLijH − qL=N,∏ l∏ ij l ij + 1 ,тii =j 1 i=i 1 =i 1 =j 1где n – размерность области параметров q; l i – густота сети на i-м шаге; qLij , qH ij – нижняя и верхняя границы i-й компоненты qij вектора па-=Nяn=N яi , N т∏nN тi , N яi∏=mkраметров.Так как УКУ-решения, полученные на первом этапе алгоритма оптимизации методом УКУ, используются только для формирования начальныхприближений для дальнейшей оптимизации, то возможен выбор достаточно большого значения шага (малой густоты) сети l.
При этом имеет местоувеличение быстродействия алгоритма.Например, для ряда приложений имеет местоqH ij − qLij≥ 5 − 10 .liНа втором этапе для рассматриваемых в работе приложений трактовка(4.16) является начальным приближением ПКЗУ многошагового взаимодействия, когда urj = u j (t , x (tr −1 )), где tr −1 ≤ t ≤ t=T, =r 1, n . Очевидноnобобщение сетей для векторных управлений коалиций=uK4.3.2.{uiK }, i ∈ K .Алгоритм получения сетевых УКУ-решенийАлгоритм вычисления сетевых УКУ-решений является итерационными в общем случае имеет следующий вид:Ша г 1 : задается модель конфликта, определяются параметры системы;Стабильные эффективные решения и компромиссы. Часть I148Ша г 2 : для r-го интервала ПКЗУ формируется ортогональная равномерная сеть c N я и N т для t ∈ [tr −1 , tn ] ;Ша г 3 : для точки в сети c координатами ( u K , u N / K ) проверяетсяналичие «угрозы» коалиции K, т.е. точки с координатами ( v K , u N / K ) , длякоторой выполняется условие (4.9);Ша г 4 : а) если «угроза» существует, проверяется наличие «контругрозы» коалиции N/K, т.е.
точки с координатами ( v K , v N / K ) , для которой выполняются условие (4.10); б) если «угрозы» не существует, то переходимна шаг 6б;Ша г 5 : а) если «контругроза» существует, то переходим на шаг 6а;б) если «контругрозы» не существует, то данная точка не является УКУоптимальной и происходит переход на шаг 7;Ша г 6 : а) точка ( u K , u N / K ) является УКУ-решением; б) точка имеетпризнаки равновесия.Ша г 7 : а) переходим к следующей точке сети на шаг 3; б) если перебраны все точки сформированной сети, то переходим к шагу 2 для (r+1)-гоинтервала ПКЗУ.4.4. ЭТАП 2: ОПТИМИЗАЦИЯ УПРАВЛЕНИЯ ММС НА ОСНОВЕМОДИФИЦИРОВАННЫХ ДОСТАТОЧНЫХ УСЛОВИЙ ЛОКАЛЬНЫХ УКУ(ЛУКУ) [50] И МЕТОДА МОМЕНТОВ Н.Н. КРАСОВСКОГО [129]4.4.1.Общий вид достаточных условий ЛУКУ Э.
Вайсбордаи В. Жуковского [32]В соответствии с общими принципами формирования коалиционнойструктуры [32] вводится коалиционное разбиение{}P = K1 ,..., Kl ,..., K mk , P ⊂ P,где P – множество коалиционных структур при частичном объединении K lиз P. Показатель потерь коалиции K l :TJ Kl ( u) =F Kl (T , x(T )) + ∫ FKl (t , x, u K1 ,..., u Km )dt , l =1,..., mk , (4.18)kt0гдеF Kl =∑ Fi ;i∈KlFKl =∑ Fi ;i∈KluKl = {uiK }, i ∈ Kl .lКоалиционное динамическое описание системы:(4.19)Глава 4. Стабильные коалиционные решения в ММС на основе УКУ∏ Ui .x f ( x, u K1 ,..., u Km ); x(==t0 ) x 0 ; u Kl ∈ U=Klk149(4.20)i = KlЗдесь, как и ранее, множество U i обладает свойствами [32]:1) для любого набора уравнений u(t ) = {u1 ,..., u N } существует единственное решение x(t ) системы (4.20);2) компоненты n i -мерных вектор-функций ui ( t )являются кусочно-непрерывными функциями, имеющими конечное число точек разрыва(свойства 1, 2 определяют множество U i )ui ∈ U i ⊂ Ln2i (t0 , T ) ;3) управление ui ( t ) называется допустимым, если ui ( t ) ∈ U i ⊂ U i ;4) множество U i является открытым в смысле: для любого подмножестваU i ⊂ U i при uin ∈ U i управление ui ∈ U i также принадлежит U i , еслиT∫2uin (t ) − ui (t ) dt < ε ,t0где ε > 0 – малая положительная константа.Локальной угрозой коалиции K = Kl (или K = Klпо некоторымlKl из P или из P ) является возможность замены коалицией K управлеTния u K (t) на v K (t ) ∈ U K ,∫2u K (t ) − v K (t ) dt < ε так, чтобыt0(4.21)J K (u K , u N / K ) > J K ( v K , u N / K ) .Локальной контругрозой контркоалиции N/K является возможность замены контркоалицией N/K управления u N / K (t ) на v N / K (t ) ∈ U N / K ,T∫2u N / K (t ) − v N / K (t ) dt < ε так, чтобыt0J K ( v K , v N / K ) > J K (u K , u N / K ) ,J N / K (vK , v N / K ) < J N / K (vK , uN / K ) .(4.22)Локальный характер угроз и контругроз принят к рассмотрению дляуточнения сетевых УКУ в промежутках между узлами сети.Определение 4.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
