Главная | Обратная связь

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

Одним из подходов к поиску компромиссного решения задач векторной оптимизации является сведение её к задаче параметрической оптимизации, т.е. сведение её к однокритериальной (скалярной) оптимизации. Иначе говоря, частные критерии 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.

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