Постановка задачи многокритериальной оптимизации

Предполагается, что m³2, при m=1 задача оптимизации является однокритериальной (скалярной).

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

Критерии F_i(X), i=1,2, . . . , m, образуют векторный критерий F(X)=(F₁, F₂, . . . , F_m). Поэтому в литературе также используют термин "векторная оптимизация".

Пусть X₁ÎD, тогда

F₁(X₁) – локальная оценка решения X₁ по 1 – му критерию или критерию F₁;

F₂(X₁) – локальная оценка решения X₁ по 2 – му критерию или критерию F₂;

F_m(X₁) – локальная оценка решения X₁ по m – му критерию или критерию F_m;

F(X₁)=(F₁(X₁), F₂(X₁), F_m(X₁)) – векторная оценка для решения X₁.

Для пояснения сущности задач используют геометрическую интерпретацию, связанную с введением n – мерного пространства Eⁿ пространства параметров проектирования (управляемых параметров) и m – мерного пространства E^m выходных параметров. Каждой точке пространства Eⁿ и E^mсоответствуют векторы X и Y значений переменных проектирования и выходных параметров соответствующего проектируемого объекта.

Следовательно, допустимой области D (образ) можно поставить в соответствие некоторое множество оценок. Это множество будем обозначать Y_D и его будем называть критериальным пространством или областью критериев (областью оценок), т.е. Y_D=F(D) – прообраз множества D.

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

min F(X) min F(X)

XÎD или

h_k(X)=0, k=1,2, . . . , K; (5)

g_j(X) ³ 0, j= 1,2, . . . , J.

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

в квадрате D={-1£x₁£1, -1£x₂£1} заданы два критерия
которые желательно минимизировать.

Замечание. Символ minF(X) понимается как набор символов minF_i(X), i=1,2, . . . , m. Будем предполагать, что все критерии нужно минимизировать, т.к. всегда можно перейти от maxF_i(X) к min[-F_i(X)], i=1,2, . . . , m, т.е. сменой знака перед частным критерием.

Спрашивается, можно ли найти решение, одновременно удовлетворяющее всем этим требованиям? Со всей откровенностью ответим: нет. Решение, обращающее в минимум один какой-то показатель, как правило, не обращает ни в минимум, ни в максимум другие. Поэтому часто применяемая формулировка: "достичь максимального эффекта при минимальных затратах" представляет собой не более чем фразу и при научном анализе должна быть отброшена [стр. 44; Е.С. Вентцель. Исследование операций: задачи, принципы, методология. – 2-е изд., стер. – М.: Гл. ред. физ. мат. лит., 1988. – 208 с.].

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

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

maxF₁(X); maxF₂(X); maxF₃(X); minF₄(X); minF₅(X);

XÎD XÎD XÎD XÎD XÎD

где D – область работоспособности; F₁(X) – нагрузочная способность; F₂(X), F₃(X) – помехоустойчивость; F₄(X) – рассеиваемая мощность, F₅(X) – среднее время задержки сигнала.

Замечание. Векторная задача (выражение (4)) представляет собой ММ проектируемого объекта (технической системы), т.е. критерий эффективности, независимые переменные, ограничения образуют ММ рассматриваемой системы (объекта).

Процесс решения задачи (5), как правило, состоит из двух этапов:

1. Находят множество решений оптимальных по Парето PÌD;

2. Из множества P выбирают вектор , являющийся наиболее предпочтительным из всех векторов множества P и которому соответствует набор технических характеристик объекта F_i(X_opt), i=1,2, . . . , m.

Замечание. Дадим другую форму записи постановки задачи векторной оптимизации:

X_opt=arg minF(X)

XÎD

Таким образом, в результате решения задачи (4) мы получим вектор оптимальных параметров объекта и набор технических характеристик объекта F_i(X_opt), i=1,2, . . . , m.

§2. Проблемы решения задач
многокритериальной оптимизации

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

min F(X) или min (F₁(X), F₂(X), . . . , F_m(X))

XÎD XÎD

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

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

Несравнимость решений. Основная сложность логического анализа многокритериальных задач состоит в том, что в них, в отличие от "обычных" (однокритериальных) задач появляется эффект несравнимости вариантов (решений). Рассмотрим пример. Множество D состоит из 4 возможных решений X₁, X₂, X₃, X₄. Каждому решению соответствуют определённые значения показателей (критериев) F₁ и F₂ (критерии минимизируются). Пусть имеются следующие векторные оценки: F(X₁)=(2;4), F(X₂)=(3;5), F(X₃)=(5;2), F(X₄)=(2;1). Вариант X₁ лучше варианта X₂. Вариант X₁ лучше по первому критерию, но хуже по второму (варианты X₁ и X₃ несравнимы между собой). Вариант X₁ хуже варианта X₄. Вариант X₄ лучше по первому критерию вариант X₃, но хуже по второму (варианты X₃ и X₄ несравнимы между собой). В результате решения мы получили два недоминируемых (неулучшаемых) решения X₃ и X₄. Несравнимость решений является формой неопределённости, которая, в отличие от неопределённости, вызванной воздействием среды, связана со стремлением лица принимающего решение "достичь противоречивых целей" и может быть названа ценностной неопределённостью. Выбор между несравнимыми решениями является сложной концептуальной проблемой и составляет основное содержание многокритериальной оптимизации [В.В. Розен. Математические модели принятия решений в экономике].

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

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

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

Выбор принципа оптимальности, т.е. требуется определить правило, которое позволило бы сказать какое решение лучше. Выбор принципа оптимальности – основная проблема векторной оптимизации. Формально описать принцип оптимальности (критерии "правильности решения") – оказывается затруднительным.

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

2. Во-вторых, цели участников процессов принятия решений – различны и часто противоположны.

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

4. В-четвёртых, трудности выбора решения могут скрываться и в самой постановке задачи, если требуется достижение нереальных результатов. Например, получение максимальной прибыли при минимальном риске; строительство в минимальные сроки при максимальном качестве; минимальный ущерб противнику в военных действиях при минимальных собственных потерях.

⇐ Предыдущая 1 234 5 6 7 8 9 10 Следующая ⇒