Воронов Е. М. Методы оптимизации управления ММС на основе стабильно-эффективных игровых решений (2001) (1264203), страница 24
Текст из файла (страница 24)
Однако это условие превращает задачу (3.27) в нелинейную и требует иных подходов к ее решению. В работе [47] задача Ωоптимизации в нелинейном варианте решается на основе объединения иобобщения результатов [8, 110, 363]. В итоге от задачи (3.27) переходим клинейной задаче дополнительности относительно переменных u, v:−Hu + v =h; (3.31)T=u v 0; u, v ≥ 0, где T;H = CCопределитьmax z;[ d T , z ]∈DhT = [ −1TP , OTSa ] ; ∂J ( q)B∂qC = A a1P .O Sa Решение задачи (3.31) осуществляется с помощью алгоритма дополнительного ведущего преобразования Лемке [8], после чего легко вычисляется вектор d. Как доказывается в [8], алгоритм Лемке сходится к решениюзадачи (3.31) за конечное число шагов, если матрица H является сильнокоположительной. Матрица H в (31) является сильно коположительной.Действительно, во-первых, H – симметричная матрица и, следовательно, T .
Поэтому из равенствакоположительная. Во-вторых, H + HT =2CCzTHz = 0 следует, что (H + HT)z = 0.Таким образом, построены эффективные вычислительные процедурывыбора направления спуска внутри конуса доминирования, решающие по-114Стабильные эффективные решения и компромиссы. Часть Iставленную задачу за конечное число шагов, и дающие возможность формализовать информацию о предпочтениях проектировщика в виде матрицмногогранных конусов доминирования.Вычисление шаговой длины в выбранном направлении.
Вычисление шаговой длины (k ) в выбранном направлении d (k ) на k-й итерациипринципиально может производиться с помощью алгоритмов, аналогичных алгоритмам одномерной минимизации, используемым в задачахусловной оптимизации скалярных целых функций. Анализ алгоритмов одномерной оптимизации можно найти в [186]. Учет свойства многокритериальности и использование понятие Ω-оптимальности требуют модификации существующих алгоритмов, так как при этом изменяется вид условия спуска [312, 428]. Рассмотрим алгоритмы вычисления шаговой длиныследующих двух типов.1. Выбор (k ) , явно обеспечивающего условие спуска. В задачеΩ-оптимизации условие спуска формируется в виде(3.32)∆J(k)∈Ω,(k)(k +1)(k)(k +1)–J ;J= J(q(k)+ (k)d(k)); J(k) = J(q(k)).где ∆J = JВ том случае, когда Ω – многогранный конус вида (3.19), условие (3.32)представляет собой систему неравенств вида (3.26).2.
Вычисление (k ) по конечным формулам, использующим значениявекторного показателя J(q(k)), а также его производной∂J (q ( k ) ), вычисля∂qемых на предыдущих итерациях для целевого выбора направления d ( k ) взадаче (3.27) (так как специально для выбора ( k ) это делать нерационально). В соответствии с [312, 428] условие спуска (3.26) означает одновременное уменьшение всех компонент векторного показателя H = BJ. Тогдаспуск вдоль выбранного направления d(k) целесообразно проводить доближайшего минимума одной из компонент векторного показателя H илидо выхода на границу области допустимых значений параметров Q.
Прирешении этой задачи могут быть использованы обычные методы одномерной минимизации (метод Фибоначчи, золотого сечения, параболическойинтерполяции и др.) [8, 186]. Метод параболической интерполяции обобщается на случай задачи Ω-оптимизации следующим образом. Легко покаk)экстремумов интерполирующих парабол вычисляетзать, что вектор h(minся по формулеГлава 3.
Стабильные и эффективные оптимальные решения(k )hmini ∂J ( k ) ( k ) ( k ) 2 − 1 Bd h 2 ∂qi,=k() ( k )(k )( k ) ∂J(k ) B J − J − hd ∂qi115(3.33)(k )где J ( k ) = J (q ( k ) ) ; J ( k ) = J (q ( k ) ) ; q=q ( k ) + h( k ) d ( k ) ; q ( k ) – вспомогательная точка, необходимая для построения интерполирующей параболы;h( k ) задается отдельно.Шаговая длина (k ) вычисляется в виде{}(k )( k ) =min λ (dk ) , hmin, i=1, p ,i(3.34))(k )до границы допустимой области Q вгде λ(kd – расстояние от точки λнаправлении d ( k ) . Необходимо отметить, что другие методы одномернойоптимизации обобщаются на задачу Ω-оптимизации аналогично.Таким образом, процедуру поиска оптимального решения в [213] предлагается рассматривать в виде последовательности следующих основныхэтапов, составляющих в совокупности одну диалоговую итерацию:• формирование конуса доминирования;• выбор направления спуска внутри конуса доминирования;• вычисление шаговой длины в выбранном направлении.Некоторые виды комплексирования систем управления при решениитехнических задач приводят к появлению разрывности компонент векторного показателя исследуемой системы.
Это обстоятельство требует модификации построенной выше процедуры Ω-оптимизации с учетом указанного свойства. При этом используется подход к решению задач оптимизации разрывных показателей, изложенный в [16].В [16] формируются численные методы поиска экстремума разрывныхпоказателей, по своему содержанию аналогичные известным градиентнымметодам для непрерывно дифференцируемых показателей. Показано, чтодля этого необходимо в соответствующих методах для непрерывно дифференцируемых функций использовать вместо градиента понятие аппроксимационного градиента.3.2.5.Выбор начального приближения в задачемногокритериальной оптимизации (постановка (3.8))Как известно, для векторного показателя J(q) общего вида, когда некоторые его компоненты, вообще говоря, являются невыпуклыми на Qфункциями, на множество достижимых векторных оценок J(Q) могут существовать локально эффективные точки, не принадлежащие глобальномумножеству Парето J П (Q).
В этих точках также выполняются необходимые116Стабильные эффективные решения и компромиссы. Часть Iусловия Ω-оптимальности (17). Поэтому неудачное расположение начального приближения в задаче (7) может привести к неправильному результату вследствие преждевременного останова алгоритма Ω-оптимизации влокально эффективной внутренней точке множества J(Q).С другой стороны, при решении задачи Нэш-оптимизации (глава 2) вслучае неединственности равновесия по Нэшу необходимо на множестверавновесных решений определить недоминируемые точки, т.е. ближайшиек множеству Парето [32]. В этом случае начальное приближение целесообразно назначать в окрестности множеств Парето, что повышает возможность определения недоминируемого равновесного решения.Таким образом, выбор начального приближения является важным фактором, влияющим на эффективность вычислительных процедур и правильность получаемых результатов.Постановку задачи выбора начального приближения на основе (3.8)предлагается формализовать в виде [48, 213]:(3.35)определить { J iΩi (Q (i )) Ki∂ , Ωi } ,q∈Q ( i )где Q(i) = {q∈E | q ∈Q i ; qri( M K \i )= const}.То есть необходимо определить множество J iΩi значений показателяJ i ( q) , являющееся дискретной аппроксимацией множества Ω i -оптимальных решений (в частном случае – множества Парето).
При этом аналогич~ iное множество определяется в пространстве параметров: QΩI i . Если поло-жить Ki ≡ M K , то получим J i = J , Q(i) = Q. Для конуса доминированияпри этом полагаем Ωi = Ω = E≤m . Тогда задача (3.35) будет интерпретироваться, как построение дискретной аппроксимации множества Парето относительно векторного показателя J∈Em и вектора параметров q∈Q⊂Er.Если положить i = M K \j, то можно оценивать конфликтное взаимодействие коалиции K j и контркоалиции K i .В данном разделе для решения задачи (3.35) предлагается использоватьизвестный метод зондирования пространства параметров, основанный наметодике ЛП-поиска [238]. В этом методе условно можно выделить дваосновных этапа:1) составления таблицы испытаний;2) оптимизация таблицы испытаний.Для определенности полагаем, что Ki составляет все множество M K .Эт а п 1.
Генерируется последовательность точек {p(i)}, равномернораспределенная в r-мерном единичном кубе. Как обосновывается в [238],наилучшими характеристиками равномерности обладают так называемыеЛП τ -последовательности. Для генерации ЛП τ -последовательности в [238]Глава 3. Стабильные и эффективные оптимальные решения117предлагается арифметический алгоритм, использующий специальную таблицу направляющих чисел.
После этого с помощью линейного преобразования L, сохраняющего равномерность распределения, преобразуем множество сгенерированных точек {p(i), i = 1, N }∈П p в множество точек {q(i),i = 1, N }, равномерно заполняющих r-мерный параллелепипед П q , определяемый верхними и нижними ограничениями на параметры задачи q L и q H :(3.36)П q = L(П p ).Преобразование L задается [238] в видеq (ji ) = qLj + Pj(i ) ( qHj − qLj ) .(3.37)Так как в описании области Q используются линейные ограниченияобщего вида, то в каждой точке q(i) необходимо проверять выполнение системы неравенств Cq(i) ≤ b. Если q(i) является допустимой, то в ней вычисляется значение векторного показателя J(q(i)) и заносится в таблицу испытаний.Эт а п 2.
Предлагается алгоритм оптимизации таблицы испытаний поконусу доминирования Ω, заданному в виде (19). Для этого из таблицы испытаний выбирается какая-либо точка q(i) и помечается. Просматривая всеточки q(j) таблицы испытаний, отличные от q(i), исключим те из них, длякоторыхB(J(q(j)) – J(q(i))) ≥ Ο,(3.38)причем хотя бы одно из неравенств строгое. То есть проверяется принадлежность точек ∆ ij конусу (– Ω); ∆ ij = J(q(j)) – J(q(i)).Затем среди оставшихся точек выбирается непомеченная, и вновь повторяется процесс исключения по правилу (3.38). После конечного числашагов останутся только такие помеченные точки, которые являются дискретной аппроксимацией множества Ω-оптимальных решений.Второй этап данного алгоритма [213] отличается от [238] более общейпостановкой, основанной на использовании понятия конуса доминирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
