Сформулировать задачу многокритериальной (векторной) оптимизации (стр. 8 )

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

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

m1+m2=m;

Метод "идеальной" точки

Рассматривается m-мерное пр-во (где m число локальных критериев), в к-ом априори выбирается вектор, отображающий "идеальное" решение (или, что тоже самое, "идеальная" точка, корд-ми которой являются "идеальные" значения (например, мин или макс значения) локальных критериев). В этом пространстве вводится некоторая метрика, с целью вычисления расстояния между вектором, отображающим рассматриваемое решения, и "идеальным". В кач. Наилуч. выбирается такое решение, векторная оценка к-го наиболее близка к "идеальной" точке. Недостатками метода являются произвол при выборе идеальной точки и введение метрики.

Численные методы определения множества Парето

Часто используют следующий подход. Во множестве D выбирается некоторая сетка, например, координаты которой определяются с помощью датчика случайных чисел, распределённых по равномерному закону. Потом вычисляют значения векторного критерия F в точках этой сетки, после чего за конечное число сравнений, используя функцию выбора по Парето, строится множество Парето на указанной сетке, являющееся при большом N приближением множества Парето относительно D (N – число точек сетки).

Рис. 11. Левый рисунок – область D и P (красная линия), правый рисунок – область векторных оценок YD и КК (красная линия)

Комбинация ожидаемого среднего значения и дисперсии как задача двухкритериальной оптимизации.

В теории вероятностей в качестве меры отклонения случайной величины от её среднего значения обычно используют дисперсию Dξ или среднеквадратичное отклонение σ=. В задачах принятия решений в условиях риска будем рассматривать в качестве показателя риска среднеквадратичное отклонение σ, т. к. σ.имеет такую же размерность, что и случайная величина ξ, математическое ожидание Mξ.

Таким образом, для принятия решения в условиях риска выбор альтернативы Xi приводит к случайной величине ξi, которая может быть охарактеризована парой показателей (Mξ, σi). Теперь приступим к построению адекватного критерия сравнения альтернатив. Фактически здесь получается задача двухкритериальной оптимизации, где в качестве частных критериев выступают математическое ожидание Mξ (значение данного критерия нужно максимизировать) и среднеквадратичное отклонение σ (значение данного критерия нужно минимизировать).

Рассмотрим нахождение Парето-оптимальных решений для данной многокритериальной задачи. Предположим, что требуется выбрать одну оптимальное решение из множества допустимых решений, каждое из которых определяется парой показателей (Mξi, σi). Изобразив на координатной плоскости точки с координатами (Mξi, σi), получим картинку типа изображённой на рис. 1, т. е. мы получили пространство оценок. Левая часть рисунка (красные точки) значения математического ожидания мы взяли положительными, а σ отрицательные значения, т. к. этот критерий (σ) мы должны минимизировать. Парето-оптимальными оценками является правая верхняя граница и соответственно Парето оптимальными решениями X1, X2, X9 и X7.

В данном примере множество Парето-оптимальных решений есть X1, X2, X9, X7 и окончательный выбор оптимального решения проводится из этого множества.

Рис. 1. Пространство оценок

Классификация методов решения задач векторной оптимизации

задачу многокритериальной оптимизации (ЗМО):

min F(X) или min (F1(X), F2(X), . . . , Fm(X))

XÎD XÎD

где Fi(X), i=1,2, . . . , m, частные критерии, D - область работоспособности. Заметим, что к выходным параметрам относят не только физические параметры (масса, скорость, задержка сигнала), но и стоимость, надёжность. Говорят, что мы построили ММ МЗО. Но эту задачу нужно ещё и решить, т. е. найти оптимальное решение. Главная особенность МЗО заключается в том, что частные критерии противоречивы, т. е. улучшение одного приводит к ухудшению другого (других) критериев. Такие критерии (выходные параметры) ещё называют конфликтными.

При разработке методов решения МЗО приходится решать специфические проблемы. Рассмотрим эти проблемы подробнее.

Нормализация критериев. Так как частные критерии имеют различный физический смысл, т. е. измеряются в различных единицах; масштабы их не соизмеримы, поэтому невозможно сравнение качества полученных результатов по каждому критерию. Операция приведения масштабов локальных критериев к единому, обычно безразмерному, носит название нормализации критериев.

Выбор принципа оптимальности, т. е. требуется определить правило, которое позволило бы сказать какое решение лучше. Принцип оптимальности - основная проблема векторной оптимизации.

Учёт приоритета критериев. Обычно из физического смысла задачи следует, что локальные критерии имеют различную важность при решении задачи, т. е. один локальный критерий имеет какой-то приоритет над другим локальным критерием. Это следует учитывать при выборе принципа оптимальности и определении области возможных решений, отдавая предпочтение более важным критериям.

Вычисление оптимума ЗВО. Сейчас достигнуты определённые успехи в области решения задач математического программирования (МП). Так по одним данным, методов однокритериальной оптимизации и их модификаций более 500 (пятисот), по другим - их количество перевалило за несколько тысяч! Но их, как правило, нельзя один к одному применять к решению. ЗМО, т. к. известны примеры, когда вычислительные алгоритмы становятся непригодными для решения задач МП в результате небольших изменений и добавлений к первоначальной задаче, поэтому встаёт проблема - вычисление оптимума построенной задачи векторной оптимизации. Однако отметим, что перечисленные проблемы так или иначе сводят многокритериальную задачу к однокритериальной, т. е. сводят к проблеме вычисления оптимума.

Замечание. Оценивая в целом все рассмотренные и перечисленные методы векторной оптимизации, можно заметить, что все они, так или иначе, сводят векторный критерий к скалярному (однокритериальному) критерию.

Развитие методов решения ЗВО идёт по трём направлениям (хотя некоторые авторы называют больше):

4.  Замена векторного критерия скалярным критерием, т. е. переход к однокритериальной задаче оптимизации;(обобщенные критерии)

5.  Последовательное решение конечного множества однокритериальных задач; (последовательная оптимизация)

6.  Сужение множества D с последующим непосредственным выбором оптимального решения. Далее рисунок-схема.(сужение области D)

Формальные методы определения весовых коэффициентов

Рассмотрим некоторые способы и числовые приемы, позволяющие по информации о качестве значений частных критериев оптимальности определять значения весовых коэффициентов λi.

Способ 1. Для каждого частного критерия оптимальности Fi(X)>0, вычисляется коэффициент относительного разброса по формуле:

,

где , который определяет максимально возможное отклонение по -му частному критерию. Весовые коэффициенты λi получают наибольшее значение для тех критериев, относительный разброс которых в области оценок наиболее значителен

.

Пример 1. В качестве примера рассмотрим конкретную числовую задачу в следующей постановке:

При этом имеем следующие значения промежуточных вычислений:

Тогда весовые коэффициенты будут иметь следующие значения:

,

,

т. к. λ2>λ1, то локальный критерий F2 важнее локального критерия F1.

Способ 2. Пусть все , тогда рассматриваются коэффициенты

,

которые характеризуют отклонение частного критерия оптимальности от его наименьшего значения.

Предположим, что важность -го критерия оптимальности зависит от выполнения неравенства

. (1)