Воронов Е. М. Методы оптимизации управления ММС на основе стабильно-эффективных игровых решений (2001) (1264203), страница 28
Текст из файла (страница 28)
3.5, получена с учетомоценки времени выполнения процедур на языках низкого уровня, которые,как правило, применяются в бортовых вычислительных комплексах.Для оценки такта выдачи команд управления при распараллеливаниипрограммы на несколько транспьютеров целесообразно декомпозироватьвторой блок. Время вычисления процедур данного блока при небольшомчисле транспьютеров будет обратно пропорционально их количеству.Глава 3. Стабильные и эффективные оптимальные решения139Структура вычислений в других блоках алгоритма не позволяет эффективно распараллелить их.Та блица 3 .5Вре ме нные о це нк и э тапов а л гор ит маВремявыполненияпроцедурблока (tics)Время выполненияпроцедурблока (с)116,0890,052,6112597,2621,996,92932,7680,0090,458Итого:616,1791,959100Номер блока(этапа)(см.
рис. 3.4)В процентах к общемувремени (%)В следующей таблице дана приближенная оценка эффективности параллельной реализации процедур второго блока.Та блица 3 .6О ценк а пара л л е ль но й р еа л из а ц и иКоличество транспьютеровв сетиВремя выполненияв секундах123451,95910,70,550,45Таким образом, рассмотренный в пунктах 3.4 и 3.5 пример примененияалгоритма векторного равновесия в составе СТЭК-3 показывает его работоспособность для нелинейных систем высокого порядка.Данный пример имеет практическую ценность, так как позволяет получить ПКЗУ управления коалиции ЛА в режиме ближнего наведения инамечает пути повышения быстродействия алгоритма для его реализации вБЦВМ.Глава 4.
Стабильные коалиционные решения в ММС на основе УКУ139ГЛАВА 4СТАБИЛЬНЫЕ КОАЛИЦИОННЫЕ РЕШЕНИЯ В ММСУПРАВЛЕНИЯ НА ОСНОВЕ МЕТОДА «УГРОЗ И КОНТРУГРОЗ»4.1. КОАЛИЦИОННАЯ СТРУКТУРА. ПОДХОДЫ В КОАЛИЦИОННЫХ ИГРАХЕстественное расширение потребностей практики в технических, экономических, биотехнических, социальных и других предметных областяхтребует развития методов исследования взаимодействия в многообъектных многокритериальных системах (ММС) на основе коалиционных подходов.В настоящее время сформированы лишь общие подходы к анализу коалиционных взаимодействий [32, 39, 42, 50, 54] на основе теоретикоигровых моделей в рамках векторных равновесий, которые являются частными случаями коалиционного равновесия (см.
определения 3.6 – 3.13 иматериал главы 3).В работе [39] обсуждается понятие общей динамической игры. Реализация такой игры состоит из последовательных состояний игры,набора возможных коалиционных структур в данных состояниях и выбранных ситуациях, каждая из которых определяется текущим состоянием и текущей коалиционной структурой. В традиционных динамических играх, по мнению Э.Й. Вилкаса [39], основная проблема заключается в недостаточном обмене информацией между участниками игры инедостаточно гибких приемах формирования коалиций: либо по заранеепредписанным правилам, либо в начальный момент коалиционнаяструктура задается на весь период игры.Поэтому типичный существующий вариант коалиционной модели[32, 39] связан с коалиционным разбиением=P{K1,..., Kl ,..., Km } ⊂ P.k(4.1)140Стабильные эффективные решения и компромиссы.
Часть IПоказатель потерь (эффективности) коалиции Kl :TJ Kl ( u) =F Kl (T , x(T )) + ∫ FKl (t , x, u K1 ,..., u Km ) ⋅ dt , l =1,..., mk ,k(4.2)t0гдеF=Kl{ui , i ∈ Kl },∑ αK i ⋅ Fi ; F=∑ αi ⋅ Fi ; u =KKi∈K r0 ≤ α Kl i ≤ 1 ,ll∑ αK=i1, i ∈ K l ,li∈Kll(4.3)iα Kl i — определяют приоритетность участника коалиции.Общее динамическое описание системы (см. гл.
1):=x f ( x, u K1 ,..., u Km ), x(t=0 ) x 0 , u Kl ∈ U =Klk∏ Ui .i∈KlУправляющие вектор-функции ui ∈ U i(4.4)ui = ui (t , x ) или ui = ui (t )имеют свойства, сформированные, например, в [32, стр. 59 – 60], и допускают параметризацию ПКЗУ или оптимального управления:(4.5)ui = ui (t , x, q ) или ui = ui (t , q ) .Если ограничиться случаем, когда коалиционное разбиение формируется до начала игры, то коалиционные подходы можно сгруппировать подвум направлениям: взаимной информированности коалиций о количествеP коалиционных разбиений P и их структуре; взаимной информированности о внутренних свойствах коалиций-партнеров, например, о целях иприоритетности объектов-участников коалиций и условиях вступления вкоалицию.В частном случае, когда у коалиции K l отсутствует информация о коалиционной структуре и внутренних свойствах коалиций, то естественнымявляется принцип гарантированных решений (см.
главу 7)(4.6)min max J K ( u).uKuN/KЕсли коалиционное разбиение Р единственное и известно до внутренних свойств каждой коалиции, то имеем бескоалиционную игрумежду коалициями с определением Нэш-равновесия коалиций (ur)(см. главу 2)(4.7)J Kl ( u r ) ≤ J Kl ( u rK1 ,..., u rKl −1 , u Kl , u rKl +1 ,..., u rKm ), l =(1,..., mk ).kЕсли коалиционное разбиение единственное, его структура известна,взаимная информация о целевой приоритетности участников коалиций отсутствует, то коалиционный подход основывается на векторном равновесии(глава 3).Глава 4. Стабильные коалиционные решения в ММС на основе УКУ141Если имеется несколько коалиционных разбиений P ⊂ P и структуракаждого известна, а взаимная информация коалиций-партнеров о внутренних свойствах полная, то применяется метод доминирования риска Харшаньи [32] со сведением данной коалиционной игры к кооперативной (таккак предполагаются переговоры о совместном выборе управлений и структуры игры) в форме характеристической функцииν( K ) =maxK∈P∑ J i (ur )для всех K ⊂ P ⊂ P ,(4.8)i∈Kпричем n(0) = 0, n(1,..., N ) = minu∈UN∑ J i ( u) .i=1В равенстве (4.8) максимум берется по всем разбиениям P ⊂ P, содержащим коалицию К, а u r – набор недоминируемых равновесных решенийпри фиксированном Р, который изменяется при переходе от структуры кструктуре.Если коалиционное разбиение P может быть не единственным и перестраиваемым, взаимная информация о внутренних свойствах коалиций неполная (известны лишь цели участников), то понятие коалиционной оптимальности базируется на наиболее общем принципе «стабильности» – коалиционном равновесии в ММС [39, стр.
61, определение 3.6главы 3].То есть, во-первых, решение игры должно принадлежать к V-решениям [см. гл. 3, опр. 3.4], когда любая допустимая коалиционная группировка из N, с целью собственной выгоды отклоняясь от V-решения (реализуя «угрозу»), может быть «демпфирована» остальными игроками изN, реализующими «контругрозу» (т.е. V-решение игры не имеет эффективных «угроз» – угроз без контругроз), во-вторых, для любой коалицииKl ∈ P решение должно обеспечивать векторную эффективность показателей коалиции.Вариант V-решения на основе метода «угроз и контругроз» (УКУ) рассмотрен в работу [50]. Исследованию предостережений-контругроз посвящен ряд работ в кооперативных играх, например [380, 381, 405].
Так, вработе [381] рассматриваются предостережения в арбитражных схемах.В работе [405] формируется устойчивый кооперативный компромисс спредостережением к действиям тех, кто отклоняется от согласованного кооперативного решения (см. главу 6).Далее рассматривается решение коалиционной дифференциальной игрына основе «угроз и контругроз», двухэтапный метод оптимизации и вариантпрактически полезной технической задачи управления ресурсами ММС вусловиях конфликта, полное исследование которой дано в главе 10.142Стабильные эффективные решения и компромиссы. Часть I4.2.
ПОНЯТИЕ РАВНОВЕСИЯ НА ОСНОВЕ «УГРОЗ И КОНТРУГРОЗ» (УКУ).СТРАТЕГИЧЕСКАЯ ЗНАЧИМОСТЬ УКУ. СУЩЕСТВОВАНИЕ УКУ.ДВУХЭТАПНАЯ ПРОЦЕДУРА ОПТИМИЗАЦИИ НА ОСНОВЕ ПРИНЦИПА УКУ«Угрозой» коалиции K , где K= Kl ∈ P или K – объединение несколькихкоалицийизоднойилинесколькихструктур(=K Kl , K ∈ P, K ∈ P ), называется [32] возможность такого измененияуправления uK на v K ∈ U K , чтобы(4.9)J K ( v K , u N / K ) < J K (u K , u N / K ) ,где N/K – контркоалиция, составленная из всех, кроме состава K, игроковмножества K ( N K ∈ P) .Из неравенства (4.9) следует, что хотя потери какого-либо из игроковиз K могут и увеличиться, но игроки коалиции K в свою очередь могут договориться, чтобы суммарное снижение потерьJ K (u K , u N / K ) − J ( v K , u N / K ) = ∆ > 0разделить между собой поровну, уменьшив потери каждого участника коалиции K на величину ∆ / K .Чтобы у игроков коалиции K при выполнении условия (4.9) не былостремления к изменению ситуации ( u K , u N / K ) , у контркоалиции N/Kдолжна быть возможность заменить свои управления u N / K на управленияv N / K ∈ U N / K так, что для набора v = ( v K , v N / K ) выполняются условияконтругрозы контркоалиции N/KJ K ( v K , v N / K ) ≥ J K ( u K , u N / K );(4.10)J N / K ( v K , v N / K ) < J N / K ( v K , u N / K ).Условия (4.10) показывают, что если коалиция K заменила набор( u K , u N / K ) набором ( v K , u N / K ) , то у контркоалиции N/K есть возможность заменить набор ( v K , u N / K ) набором ( v K , v N / K ) , для которого еесуммарные потери меньше, чем при наборе ( v K , v N / K ) , а суммарные потери K выше, чем при начальном наборе ( u K , u N / K ) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
