Методы замены векторного критерия скалярным

Одним из подходов к поиску компромиссного решения задач векторной оптимизации является сведение её к задаче параметрической оптимизации, т.е. сведение её к однокритериальной (скалярной) оптимизации. Иначе говоря, частные критерии F_i(X), тем или иным способом объединяются в составной (обобщенный, интегральный) критерий f(X)=Ф[F₁(X), F₂(X), . . . , F_m(X)], который затем оптимизируется. Под построением обобщённого критерия в МЗО понимается процедура, которая "синтезирует" набор оценок по заданным частным критериям, в единую численную оценку, выражающую итоговую полезность этого набора оценок для ЛПР. Формально обобщённый критерий для МЗО, представляет собой функцию Ф: , где Yj – множество оценок по j – критерию. Если обобщённый критерий Ф построен, то для каждого допустимого исхода XÎD может быть найдена численная оценка его полезности (ценности, эффективности): f(X)= Ф[F₁(X), F₂(X), . . . , F_m(X)]. Таким образом, задание обобщённого критерия сводит задачу многокритериальной оптимизации к задаче однокритериальной оптимизации с целевой функцией f(X). Наиболее распространённым обобщённым критерием является "взвешенная сумма частных критериев", которая превращает векторную оценку в скалярную оценку.

Метод взвешенных сумм
(Метод линейной свертки)

Идея этого метода заключается в том, что обобщённый критерий записывается в следующем виде:

(1)

который называют аддитивным критерием. Здесь l_i³0 являются весовыми коэффициентами, которые задают предпочтение i - го критерия по сравнению с другими критериями. Величина l_i определяет важность i - го частного критерия. При этом более важному критерию приписывается больший вес, а общая важность всех критериев принимается равной 1, т.е. То, что решение можно получить, используя аддитивность векторного критерия, высказал Парето. Он также ввёл понятие весовых коэффициентов. Таким образом, мы получили однокритериальную задачу математического программирования

.

XÎD XÎD

 

Замечание. Как правило, частные критерии имеют различную размерность. Поэтому при образовании обобщённого критерия нужно работать не с натуральными критериями, а с их нормированными значениями. Нормированный критерий представляет собой отношение “натурального” частного критерия к некоторой нормирующей величине. При этом выбор нормирующего делителя должен быть обоснован. Возможно несколько подходов к выбору нормирующего делителя:

q в качестве нормирующего делителя берут директивные значения параметров, заданные заказчиком, т.е. предполагают, что в ТЗ на проектируемый объект заданы оптимальные значения параметров:

q в качестве нормирующих делителей берут максимальные значения критериев, достигаемых в области существования проектных решений (область D);

q берут лучшие мировые достижения в данной области;

q в качестве нормирующего берут разность между max и min значениями критерия в области D

q или .

Нормированные критерии будем обозначать через f_i(X), т.е. аддитивный критерий примет вид (2)

Какой определён принцип оптимальности?

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

Пусть имеется два решения X₁ и X₂. Тогда в соответствии с изложенным принципом следует вычислить сумму абсолютных изменений всех частных критериев, обусловленных этим переходом (переход от X₁ к X₂)

В случае Lf<0 решение X₂ признаётся лучшим, чем X₁, если Lf>0, то лучше X₁. Тогда оптимальным решением будет такое, для которого Lf³0 при переходе от него к любому другому решению, т.е.

где X_opt – точка min, X любая точка из D.

Таким образом, принцип справедливой абсолютной уступки (компенсации) приводит к утверждению, что оптимальное решение означает минимизацию суммы нормированных частных критериев.

Иногда условия работоспособности позволяют выделить две группы выходных параметров. В первую группу входят выходные параметры, значения которых в процессе оптимизации нужно увеличить (производительность, вероятность безотказной работы), во вторую – выходные параметры, значения которых нужно уменьшить (расход топлива, длительность переходного процесса). Тогда аддитивный критерий (2) примет вид , где m₁+m₂=m. Обобщённый критерий f(X) – максимизируется.

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

Решение, полученное с использованием аддитивного критерия оптимальности — это точка, которая в наибольшей мере удалена от начала координат (при максимизации критериев).

Рассмотрим пример. Пример взят из книги [В.П. Корячко, В.М. Курейчик, И.П. Норенков. Теоретические основы САПР]. Переносной автомат для забивания стальных дюбелей в бетонные стены состоит из корпуса с магазином, содержащим запас дюбелей; подающего-спускового механизма с зарядами и ствола. Требуется определить основные конструктивные параметры автомата – длину ствола L и число дюбелей –N при следующих исходных данных:

число дюбелей , N³12;

масса одного дюбеля с зарядом равна m=50 г;

масса ствола 1.6 кг/м;

масса корпуса 2 кг.

При фиксированной величине заряда и заданной массе дюбеля скорость V выбрасывания связана с длиной ствола L соотношением V=k; где k=. Минимально допустимая скорость V_min=100 м/cек. Масса автомата не должна превышать 6 кг. Частными критериями являются скорость выбрасывания и число дюбелей, помещающихся в магазине. Выбор этих критериев объясняется тем, что чем выше V, тем надёжнее дюбеля проникают в бетонные стены любой марки, а чем больше N, тем удобнее работать. По мнению экспертов оба критерия V и N имеют одинаковую важность.

Введём обозначения: F₁(N,L)= k- первый критерий (скорость);

F₂(N,L)=N – второй критерий (число дюбелей).

Сформулируем задачу многокритериальной оптимизации:

maxF=max(F₁, F₂)

при следующих ограничениях

N³12;

V³100;

1.6L+ 0.05N+2£6.

Построим область D (см. рис.1) и критериальное пространство и определим компромиссную кривую (КК) (см. рис.2).

Рис.1. Область D

 

Для определения оптимальных значений параметров будем использовать аддитивный критерий Так как критерии имеют одинаковую

Рис.2. Критериальное пространство и КК

важность, то весовые коэффициенты можно взять равными единице. В качестве нормирующих делителей возьмём максимальные значения критериев, достигаемых в области существования проектных решений (область D). Для определения нормирующих делителей будем использовать уравнение баланса (массу автомата). Найдем N_max из условия, что V_min=100 м/cек. Определяем длину ствола, соответствующую минимальной скорости L=и подставляем в уравнение баланса. Получим, что N_max=66. Аналогично находим, т.е. берём N=12 и подставляем в уравнение баланса. Получим V_max=219 м/cек.

Таким образом, мы получили следующую задачу оптимизации:

найти максимум функции

при ограничении 1.6L+ 0.05N+2£6.

Так как наша функция f(L,N) монотонно возрастающая, то максимум достигается на границе. Поэтому ограничение неравенство мы можем заменить на ограничение равенство. Окончательно имеем

найти максимум функции

при ограничении 1.6L+0.05N+2=6.

Для определения максимального значения f(L,N) с учётом ограничения равенства мы будем использовать метод неопределённых множителей Лагранжа. Получим следующую задачу безусловной оптимизации:

найти максимум функции

Находим частные производные по L, N, l и приравниваем их к нулю. Получим систему уравнений:

Решая эту систему, получим следующие значения: , , или l=-4/13=0.308, N_opt=64, L_opt=0.499 м, V_opt=106 м/cек.

Аддитивный критерий имеет ряд недостатков:

q Он выступает как формальный математический приём, придающий задаче удобный для решения вид;

q В аддитивном критерии может происходить взаимная компенсация частных критериев. Это значит, что значительное уменьшение одного из них вплоть до нуля может быть покрыто возрастанием другого критерия. Для ослабления этого недостатка следует вводить ограничения на минимальные значения частных критериев и их весовых коэффициентов.

q Более того, оказывается, что сумма оценок основана на следующем неявном постулате: "низкая оценка по одному критерию может быть компенсирована высокой оценкой по другому". Однако, этот постулат верен отнюдь не всегда. Например, пусть качество оператора ввода текстов оценивается двумя критериями: 1) скорость ввода (символов в минуту) и 2) среднее количество ошибок на страницу текста. Очевидно, что ухудшение качества ввода (увеличение количества ошибок) не может быть компенсировано увеличением скорости ввода. Можно даже сказать, что в области оценки персонала такая ситуация типична. Скажем, недостаток компетентности не может быть компенсирован повышенным уровнем активности. Скорее наоборот! Вспомним шутливое изречение: "Кто может быть хуже дурака? Дурак с инициативой!"

Замечание. Хотя аддитивный критерий подвергается сильной критике, но существуют задачи, где критерий качества должен удовлетворять аддитивности. Например, в динамическом программировании эффект от управления процессом F складывается из элементарных эффектов f_k, полученных на отдельных шагах процесса: F=Sf_k.

Мультипликативный критерий преобразуется в аддитивный путём логарифмирования целевой функции, то получим эквивалентный аддитивный критерий, который обращается в максимум одновременно с мультипликативным критерием. Таким образом, несмотря на слабые стороны, обобщённый аддитивный критерий позволят в ряде случаев успешно решать многокритериальные задачи и получать полезные результаты.

Мультипликативный критерий

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

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

В математической формулировке условие оптимальности на основе принципа справедливой относительной компенсации имеет вид

(3)

где ΔF_i(X) – приращение величины i – го критерия, F_i(X) – первоначальная величина i – го критерия.

Полагая , можно представить (3) как дифференциал натурального логарифма

(4)

Из выражения (4) следует, что принцип относительной компенсации приводит к мультипликативному обобщённому критерию оптимальности

(5)

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

(6)

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

m₁+m₂=m; (7)

где в числителе перемножаются все выходные параметры, требующие максимизации и имеющие ограничения а в знаменателе – все выходные параметры, требующие минимизации и имеющие ограничения , где TT_i – значение технического требования, предъявленного к i– му критерию. Целевая функция (7) в дальнейшем подвергается максимизации.

Достоинством мультипликативного критерия является то, что при его использовании не требуется нормирование частных критериев. Недостатки критерия: критерий компенсирует недостаточную величину одного частного критерия избыточной величиной другого и имеет тенденцию сглаживать уровни частных критериев за счёт неравнозначных первоначальных значений частных критериев.

Примеры 1. Производственная функция, отражающая овеществлённый технический прогресс (модель Р. Солоу):

где Y_t – выпуск продукции; L – численность рабочих; K – объём основных производственных фондов. Здесь величины a и 1-a следует рассматривать как весовые коэффициенты.

Пример 2. Обнаружение сигналов в "белом" шуме. На вход RC – фильтра с импульсной характеристикой поступает аддитивная смесь: прямоугольный импульс s(t) плюс "белый" шум n(t). Требуется найти такое значение g, чтобы отношение сигнал/шум было максимальным, т.е. мы желаем, чтобы значение сигнала было максимальным, а уровень шума – минимальным (g – полоса пропускания RC – фильтра).

 

 

Рис.3. Сигнал s(t) Рис 4.Шум n(t)

 

Рис. 5.Сигнал плюс шум Рис.6. Отфильтрованный сигнал

Рис. 7.Система обнаружения сигнала

 

F₁(g)=A(1-e^-gT) ® max (уровень сигнала на выходе фильтра),

F₂(g)=® min (уровень шума на выходе фильтра).

где A,N,T - константы; F₁ и F₂ - имеют одинаковую размерность. Найти оптимальную полосу пропускания g, если справедлив принцип относительной компенсации частных критериев. Согласно формуле (7) мультипликативный критерий будем иметь вид:

Пример. Применим мультипликативный критерий оптимальности для определения оптимальных параметров для автомата. Мы получили следующую задачу оптимизации:

найти максимум функции

при ограничении 1.6L+ 0.05N+2≤6.

Для определения максимального значения f(L,N) с учётом ограничения равенства мы будем использовать метод неопределённых множителей Лагранжа. Получим следующую задачу безусловной оптимизации:

найти максимум функции

Находим частные производные по L, N, l и приравниваем их к нулю. Получим систему уравнений:

Решая эту систему, получим следующие значения: N_opt=53, L_opt=0.83 м, V_opt=137 м/cек.

Использование мультипликативного критерия в задаче оптимизации привело другим значениям параметров автомата по сравнению с решением задачи с аддитивным критерием оптимальности. Это объясняется тем, что диапазоны взаимной компенсации абсолютных и относительных изменений частных критериев неодинаковы. Поэтому в каждом конкретном случае технического проектирования следует тщательно анализировать и обосновывать целесообразность учёта либо абсолютных, либо относительных изменений значений частных критериев и в зависимости от степени важности этих отклонений выбирать либо аддитивный, либо мультипликативный критерий оптимальности.

Заключение. Преимущества и недостатки формальных обобщённых критериев.

Преимущества – возможность учёта в качестве f_i(X) любых выходных параметров системы, а также надёжность и стоимость.

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

Метод "идеальной" точки Метод "идеальной" точки. Рассматривается m-мерное пространство (где m число локальных критериев), в котором априори выбирается вектор, отображающий "идеальное" решение (или, что тоже самое, "идеальная" точка, координатами которой являются "идеальные" значения (например, минимальные или максимальные значения) локальных критериев). В этом пространстве вводится некоторая метрика, с целью вычисления расстояния между вектором, отображающим рассматриваемое решения, и "идеальным". В качестве наилучшего выбирается такое решение, векторная оценка которого наиболее близка к "идеальной" точке. Недостатками метода являются произвол при выборе идеальной точки и введение метрики. Определим обобщенный критерий следующим образом. Положим a_i=maxF_i(X); , т.е. a_i является максимально (минимально) возможным значением по i – му критерию. Положим a=(a₁, a₂, . . ., a_m). Точка a называется идеальной. Смысл названия связан с тем, что такие точки оптимальны сразу по всем критериям – получить большее (меньшее) значение ни по одному критерию невозможно. Как правило, точка aÎY_D. Зададим для всех точек YÎY_D функцию, являющуюся евклидовым расстоянием между точками Y и a . За целевую функцию (обобщённый критерий) берут выражение где li – весовые коэффициенты. Таким образом, задача оптимизации формулируется следующим образом min XÎD С учётом нормировки min (8) XÎD Замечание. Здесь принцип оптимальности выражается функцией выбора определяемой близостью к идеальной точке. Замечание. В качестве идеальной точки берут директивные значения параметров, заданные заказчиком, т.е. в ТЗ (техническом задании). Какие задачи оптимального проектирования приводят к использованию метода идеальной точки? Например, когда все или основные условия работоспособности имеют вид равенств, т.е. F_i(X)=TT_i, где TT_i – значение технического требования, предъявленные к i - критерию. Тогда целевая функция имеет вид:

Пример. Пусть имеются частные критерии F₁(X)=-3x₁+2x₂; F₂(X)=4x₁+3x₂; F₃(X)=2x₁-5x₂, которые требуется максимизировать. Область D задаётся неравенствами –x₁-3x₂+18³0; -2x₁-x₂+10³0; x₁³0; x₂³0. Линейная функция F₁(X) достигает максимального значения a₁=12 в точке X₁=(0, 6); F₂(X) - максимальное значение a₂=24 в точке X₂=(3, 4); F₃(X) - максимальное значение a₃=10 в точке X₃ =(5, 0). По методу идеальной точки составим функцию f(X)=[12-(-3x₁+2x₂)]²+[24-(4x₁+3x₂)]²+[10-(2x₁-5x₂)]². После преобразований получим f(x₁, x₂)=.

Таким образом, задача оптимизации будет такая

min f(x₁, x₂)

g₁(X)= –x₁-3x₂+18³0

g₂(X)= -2x₁-x₂+10³0

g₃(X)=x₁≥0; g₄(X)=x₂≥0

Построим область D.

 

 

Рис. 8. Область D

Найдем максимум функции, не учитывая ограничений. Если полученное значение будет лежать в области D, то оно и будет решением нашей задачи.

Находим частные производные по x₁ и x₂ функции f(x₁, x₂) и приравняем их к нулю. Получим следующую систему линейных уравнений

29x₁-4x₂=80

-4x₁+38x₂=46.

Решение этой системы: x₁=2.97; x₂=1.52. Эта точка находится внутри области D. Следовательно, минимум функции достигается в точке с координатами x_1opt=2.97; x_2opt=1.52.

В найденной точке X_opt, являющейся решением рассматриваемой многокритериальной задачи линейного программирования, F₁(X_opt)=-5.87; F₂(X_opt)=16.44; F₃(X_opt)=-1.66.

Следовательно, x_1opt=2.97; x_2opt=1.52.