Задача векторной оптимизации

В классических задачах оптимизации необходимо найти минимум или максимум скалярной функции - функции цели или критерия эффективности. Но в практических задачах редко удается свести эффективность к одному показателю.

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

В том случае, когда имеется несколько конфликтующих критериев, говорят, что имеет место задача векторной оптимизации F(x) = { f ₁(x), f ₂(x),..., f _n(x) } ® орt,

где f _I – частные критерии эффективности.

Как правило, не существует такой точки, в которой все f _i оптимальны. Поэтому в задаче векторной оптимизации ищут компромиссное решение. Для эффективного поиска такого решения необходимо, чтобы число возможных допустимых вариантов было как можно меньше.

Для достижения такой цели задачу разбивают на 2 этапа.

1) Поиск нехудших (недоминируемых) решений в смысле безусловного критерия предпочтения (БКП). Множество таких точек называется множеством Парето.

2) Выбор компромиссного решения на множестве Парето.

Рассмотрим пример [4]. Пусть имеем два критерия эффективности q₁(x) и q₂(x), зависящих от одного аргумента х, каждый из которых необходимо минимизировать (Рис.3).

Обозначим Х₁ и Х₂ – точки минимума критериев q₁(x) и q₂(x), соответственно. Разобьем область определения аргумента х на три участка: I, II, III. Осуществим на каждом участке выбор точек, лучших по Парето, т.е. по обоим критериям одновременно:

а) C_par(I) = Х₁ – выбор на I участке есть точка X₁;

б) C_par(III) = X₂ – выбор на III участке есть точка X₂;

в) на участке II нет точки, которая была бы лучше остальных сразу по обоим критериям, т.е. он весь состоит из конфликтующих точек, следовательно, C_par(II)=[X₁, X₂].

 

 

Рис. 3

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

Для задачи второго этапа необходимо применять неформальные методы выбора, основанные на интуитивных предпочтениях эксперта или лица принимающего решения (ЛПР).

Для организации паретовского механизма выбора необходимо произвести парные сравнения исходных вариантов и отбросить те, для которых найдется доминирующий элемент. Если исходное множество велико, то метод попарного сравнения трудоемок, т.к в общем случае необходимо произвести m(m-1)/2 сравнений, где m – число сравниваемых вариантов.

Более эффективен следующий алгоритм, который производит последовательное накопление элементов искомого множества.

Обозначим X = {x_i} – исходное множество сравниваемых вариантов. Для него будем производить отсев плохих точек и получение множества П(Х), содержащее точки Парето.

begin П(Х):= {х₁};

for i:= 2 to m do

П(Х):= C ^par ({x_i} È П(Х));

end.

При реализации этого алгоритма возможны три случая:

1) Для х_i существует такой у Î П(Х), что у Par x_i. В этом слу-чае необходимо прекратить сравнение х_i с паретовскими точками и перейти к х_i+1.

2) Для х_i существует такой у Î П(Х), что x_i Par у. В этом слу-чае необходимо исключить y из П(Х) и продолжить сравнение х_i с оставшимися точками пока не будет просмотрено все текущее множество П(Х). Если процесс сравнения не прекратился раньше, чем было просмотрено все П(X), то х_i необходимо включить в П(Х).

3) Для х_i не существует такого у Î П(Х), чтобы у Par x_i или x_i Par у. В этом случае y не исключают и продолжают сравнение х_i с оставшимися точками также, как и в случае 2).

Обычно множество недоминируемых точек содержит значительно меньше элементов, чем исходное т.е k = |П(Х)|<<|Х| = m. В этом случае нужно провести O(m×k) сравнений, т.е. значительно меньше, чем при всевозможных парных сравнениях.

Данный алгоритм даст верное решение, если для любых множеств X и Y выполняется условие:

C^R(X È Y) = C^R(X È C^R(Y)) (1)

ТЕОРЕМА 7 [1]. Соотношение (1) выполняется, если функция выбора обладает свойствами Н и О.

ДОКАЗАТЕЛЬСТВО. Вспомним свойства

- наследования (B Í A) Þ C(A) Ç B Í C(B);

- отбрасывания: (C(A) Í B Í A) Þ (C(B) = C(A)).

Покажем, что при их выполнении для любых множеств Z, YÍ X выполняется соотношение:

C^R(Z È Y) Í Z È C^R(Y). (2)

Пусть х ÎC^R(ZÈY). Предположим, что при этом х Î Y, тогда х Î C^R(Z È Y)ÇY. Так как Y Í Z ÈY, то, в силу свойства наследования (положив B = Y, A = Z ÈY) получим, что C^R(ZÈY)ÇYÍ C^R(Y). Значит, если х Î Y, то x Î C^R(Y), а, следовательно, x Î Z È C^R(Y).

Если же х Î Z то последнее включение также верно. Таким образом, из х ÎC^R(ZÈY) следует x Î Z È C^R(Y), что доказывает утверждение (2.2).

Обозначим теперь A = ZÈY; B = ZÈC^R(Y). По соотношению (2) C^R(Z ÈY) Í ZÈC^R(Y) Í ZÈY, т.е. C(A) Í B Í A. Тогда по свойству отбрасывания C^R(A) = C^R(B) или С^R(Z ÈY) = С^R(Z ÈС^R(Y)), что совпадает с (1).

Условие (1) в частности выполняется, если R – качественный порядок (см. п. 11, ТЕОРЕМА 5). T.к. отношение Парето таковым является, то алгоритм позволяет построить искомое конфликтное множество.

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Построить множество Парето задачи векторной оптимизации q₁ = x₁² + x₂² ® min,

q₂ = (x₁ – 2)² + (x₂ – 4)² ® min,

где x₁, x₂Î N и –1 £ x₁, x₂ £ 5.

2. Изобразить графически множество Парето задачи векторной оптимизации q₁(x) = x² ® min,

q₂(x) = 2(x – 4)² ® min

в системе координат q₁Oq₂.

3. Изобразить графически множество Парето-оптимальных точек множества Q = { (q₁, q₂) | q₁² + q₂² £ 4 }, если оба критерия q₁ и q₂ необходимо максимизировать.

4. Пусть линия, задаваемая уравнением q₁ + 2q₂ = 4, является множеством Парето в пространстве критериев. Критерий q₁ необходимо максимизировать. Каким должен быть критериий q₂ (максимизируемым или минимизируемым)?

5. Доказать, что условия теоремы 7 являются не только достаточными, но и необходимыми.

ПРИЛОЖЕНИЕ