§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. В-четвёртых, трудности выбора решения могут скрываться и в самой постановке задачи, если требуется достижение нереальных результатов. Например, получение максимальной прибыли при минимальном риске; строительство в минимальные сроки при максимальном качестве; минимальный ущерб противнику в военных действиях при минимальных собственных потерях.

В целом, все принимаемые в ТПР принципы оптимальности прямо или косвенно отражают идеи устойчивости, выгодности и справедливости.

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

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

Замечание. Оценивая в целом все рассмотренные и перечисленные методы векторной оптимизации, можно заметить, что все они, так или иначе, сводят векторный критерий к скалярному (однокритериальному) критерию или к сужению множества D с последующим выбором одного решения лицом, принимающим решение (ЛПР).

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

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

2. Последовательное решение конечного множества однокритериальных задач;

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

Рис. 3. Методы решения задач векторной оптимизации

Подведём итоги. Все задачи проектирования, управления многокритериальны по своему существу.

Построение допустимого множества – основной этап в постановке и решения задач оптимального проектирования и управления. Многокритериальная задача оптимизации вместе с множеством возможных (допустимых) решений D включает набор частных критериев оптимальности F₁(X), F₂(X), . . . , F_m(X). Набор частных критериев оптимальности образует вектор-функцию (векторный критерий), которую будем обозначать через F(X)=(F₁(X), F₂(X), . . . , F_m(X)).

Каждому решению XÎD соответствует векторная оценка F(X)=(F₁(X), F₂(X), . . . , F_m(X)). С другой стороны, каждой оценке F(X)=(F₁(X), F₂(X), . . . , F_m(X)) ÎY_D=F(D) могут соответствовать несколько решений из D. Таким образом, между множествами D и Y_D имеется связь, и поэтому выбор решения из D равносилен выбору соответствующей оценки из Y_D. В дальнейшем наряду с множеством допустимых решений D будем рассматривать множество Y_D – критериальное пространство (область критериев, пространство оценок).

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

Предыдущая Главная Следующая

СледующаяНачало