Материал: ОиММПР. Лекция 10
Методы ЭЛЕКТРА, предложенные профессором Б. Руа (Франция). В этих методах отношения предпочтения полученных на множестве Парето альтернатив строятся следующим образом.
Для каждого из m критериев (предполагается, что все критерии числовые) определяется вес – положительное число, характеризующее его важность. Например, при назначении весов критериям выбора автомобиля: цена (критерий 1), важнее комфортности (критерий 2), а та, в свою очередь, важнее, чем скоростные качества (критерий 3) и внешний вид автомобиля (критерий 4). Кроме того, критерии 3 и 4 имеют одинаковую важность, а, рассматриваемые совместно, имеют большую важность, чем критерий 1, т.е.:
w1 > w2 > w3 = w4 , w3 + w4 > w1.
Назначим весовые коэффициенты: w1 = 5; w2 = 4; w3 = w4 = 3. Выполним нормирование весовых коэффициентов:
w m
λi= m i , i=1, ... ,m; ∑ λi=1 .
∑ wi i=1 i=1
Для определения, превосходит ли альтернатива Ak альтернативу Al, необходимо:
1)Разбить множество критериев на три подмножества:
•критерии, по которым Ak превосходит Al ;
•критерии, по которым Ak и Al имеют одинаковые оценки;
•критерии, по которым Al превосходит Ak .
2)Определить относительную важность каждого из этих подмножеств
Wkl+ , Wkl= , Wkl- как сумму весов входящих в них критериев и считать, что вариант
Ak превосходит Al если, выполняется условие: |
Wkl+ |
> |
W−kl |
m |
m |
||
|
∑ wi |
|
∑wi |
|
i =1 |
|
i=1 |
Это условие является необходимым, но не достаточным условием превосходства Ak над Al. Некоторые методы ЭЛЕКТРА формулируют и дополнительные условия оптимизации, которые учитывают не только оценки Ak и Al по критериям, но и значения разностей этих оценок.
11 из 20
Отыскание парето-оптимальных решений.
Определение. Множество безусловно несравнимых альтернатив, оставшихся после отбрасывания всех безусловно худших альтернатив, называется множеством Парето. Парето оптимальное множество еще называют областью компромиссов. Ясно, что множество Парето можно получить в результате анализа критериального пространства.
Таким образом, векторная оптимизация включает два этапа:
1.Безусловная оптимизация. Здесь анализируется критериальное пространство, отсеиваются безусловно худшие варианты и получают множество Парето.
2.Условная оптимизация. Так как множество Парето, как правило, состоит из более чем одной точки, то для получения единственного решения необходимо применить дополнительные принципы оптимальности (условия согласования критериев).
Этап безусловной оптимизации.
Определение множества Парето
Непрерывный случай. |
|
|
|
Если |
целевая |
функция |
векторная |
X R K¯ =f ( X1 , X2 , …, Xn )− множество |
точек, в |
||
котором небольшое улучшение X влечёт за собой
небольшое изменение K . И критериальное пространство — это область с внутренними точками и границей (не обязательно замкнутая). Пусть есть два показателя ( K1 , K2) . При этом по
условию оптимальности K1 и K2 максимизируются
каждый по своему критерию.
Рассмотрим область возможных значений критериев см.рисунок. Точки, лежащие на одной вертикали или на одной горизонтали, всегда, безусловно,
12 из 20
сравнимы (точки 1, 2, 3). Получается, что все внутренние точки можно отсеять. Дуга АВ состоит из лучших точек по критерию K2 при постоянном K1. Но часть точек дуги АВ, а именно точки дуги AС можно отбросить, так как они хуже точек на дуге СB. Поэтому точками множества Парето будут точки, находящиеся на дуге CB. При анализе характерными являются точки касания вертикалей и горизонталей к области критериев (точки А, В, С, D).
Существует несколько алгоритмов нахождения множества Парето. Они зависят от того, в каком виде задано множество вариантов критериев. В практических задачах сначала приходится получать само множество критериев, затем множество Парето в критериальном пространстве и только затем можно определить Парето-оптимальное множество в области допустимых решений X.
Существуют два основных метода нахождения множества Парето:
1)Метод обхода конусом применяется для непрерывной области критериев.
Назовем конусом пространственный угол, образуемый лучами, идущими из общей вершины и ограниченными в каждой плоскости углом 90°. Направление ограничивающих лучей соответствует направлению оптимизации критериев.
Для получения множества Парето достаточно установить вершину конуса на все точки границы области критериев, если при этом ни один луч не пересекает область, то вершина лежит в точке Парето, а если пересекает, то нет.
Пример: K1 => min, K2 => min см. рисунок. Множество Парето: [AB] U [CD].
13 из 20
Дискретный случай.
2)Метод прямоугольников применяют, когда критериальное пространство представляет собой отдельные точки или табличные
значения. Сформулируем алгоритм для случая двух критериев, когда K1 => min, K2 => min, а критериальное пространство — точки на плоскости.
1.Фиксируем самые левые точки. Если их несколько, выбираем среди них самую нижнюю. Эта точка является точкой Парето, фиксируем ее.
2.Выберем самую нижнюю точку. Если их несколько, то выбираем самую левую. Это точка Парето, фиксируем ее.
3.Через полученные точки проводим вертикаль и горизонталь. Отбрасываем сами точки Парето, точки, лежащие на границе полученного прямоугольника, и точки вне прямоугольника.
4.К внутренним точкам полученного прямоугольника применяем
алгоритм из пункта 1.
Алгоритм заканчивается тогда, когда внутри прямоугольника не останется ни одной точки.
Решение: множество Парето: 1, 2, 3, 4, 5, 6.
Изложенный алгоритм легко обобщается на случай большего числа критериев, при других направлениях оптимизации, а также на случай табличного задания критериев.
14 из 20
Этап условной оптимизации.
После нахождения множества Парето, если количество точек в нём 2 , встаёт вопрос о выборе единственной точки, которую необходимо выбрать в качестве оптимальной. Так как точки на множестве Парето отбираются так, что каждая из них лучше по одному критерию, но хуже по другому, то совместное улучшение по двум критериям невозможно. Условная оптимизация предполагает введение условия согласованности в компонентах критерия.
Все это подробно рассмотрено выше в проблемах и задачах векторного многокритериального отбора.
Принцип разделения в задаче стохастического оптимального управления.
Сведение векторной задачи оптимизации к скалярной, выполняемой по обобщенному критерию (4), делает целесообразным рассмотрение общего подхода к решению задач скалярной динамической оптимизации [1,2,3](лекция 7). Для линейных стохастических процессов, описываемых уравнениями состояния и наблюдения вида:
x (k )=A (k )x ( k−1)+B(k )u( k )+v (k ),
z (k )=H (k )x (k )+w (k ), |
(5) |
а также при квадратичном критерии оптимальности типа:
Iобобщ=min M |
|
K−1 |
K=1 |
|
} |
|
|
[ xT ( K )ρ x ( K )+ ∑ |
xT ( k )Q1 x (k)+ ∑ |
uT ( k ) R−1 |
1 u (k )]/ z( x (k )) |
, (6 ) |
|||
u U |
{ |
k =1 |
k =1 |
|
|
|
|
где ρ и Q1- неотрицательно определенные матрицы;
R1- положительно определенная матрица. Остальные параметры имеют введенный выше смысл.
Как показано в работах [1, 3], для линейной постановки задачи (3, 4.) справедлив принцип разделения, который разбивает решение общей стохастической динамической задачи управления на два раздельно выполняемых, но взаимоувязанных этапа:
15 из 20