Векторная (многокритериальная) оптимизация

Векторная (многокритериальная) оптимизация - направление в теории оптимизации, в котором критерием оптимальности является вектор с несколькими компонентами (критериями).

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

В случае, когда имеется несколько критериев, будем говорить, что задан набор или вектор критериев {f(x)} = {f_i (x), i = 1, h}, где i -номер критерия, a h- число критериев. Поскольку ситуация может описываться не одним, а несколькими критериями, возникла необходимость расширения представления об экстремизационном выборе так, чтобы оно приводило к осмысленному выбору некоторого подмножества вариантов, лучших с точки зрения этого набора критериев. Для этого необходимо, чтобы неравенства в (9) выполнялись как векторные. То есть формулы (9) заменим формулами:

, (3.8)

Иногда знак > заменяется на ≥ при дополнительном предположении, что хотя бы для одного строгое неравенство сохраняется. Такое видоизмененное правило в литературе называют правилом Парето.

Парето, Вильфредо – итальянский инженер, экономист и социолог.

Родился: 15 июня 1848 г., Париж; умер 19 августа 1923 г., Селиньи.

Он разработал теории, названные впоследствии его именем: статистическое Парето-распределение и Парето-оптимум, широко используемые в экономической теории и иных научных дисциплинах.

 

 

Ключевую роль в многокритериальной оптимизации играет понятие парето-оптимального решения. Решение х^* X называют парето-оптимальным (оптимальным по Парето, эффективным или неулучшаемым), если не существует другого возможного решения x X, такого, что f_i (х) f_i(х^*) длявсех номеров i = 1, 2,...,т, причем по крайней мере для одного номера j (1, 2,..., т) имеет место строгое неравенство f_j (х)> f_j(х *). Другими словами, парето-оптимальное решение не может быть улучшено (в данном случае - увеличено) ни по какому критерию (ни по какой группе критериев) при условии сохранения значений по всем остальным критериям. Множество всех парето-оптимальных решений часто обозначают P_f(X) и называют множеством Парето {множеством Эджворта-Парето) или областью компромиссов.

Заметим, что в частном случае, когда критерий всего один, т.е. т = 1, определение парето-оптимального решения превращается в определение точки максимума функции f, на множестве X. Это означает, что парето-оптимальное решение представляет собой обобщение обычной точки максимума числовой функции.

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

При анализе и решении многокритериальных задач обычно считают выполненной так называемую аксиому Парето, согласно которой в случае выполнения неравенств f_i (x’) ≥ f_i (x’’) для всех номеров i = 1, 2,...,т, где по крайней мере для одного номера j (1,2,..., т} имеет место строгое неравенство f_i (x’) > f_i (x’’), ЛПР из двух данных возможных решений х ' и х " всегда отдает предпочтение первому из них.

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

Математическим выражением этого принципа служит включение

Se1 X Р_f(Х), (3.9)

которое имеет место для любого множества выбираемых решений Se1 X.

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

Недавно проведенные исследования показали (см. [3]), что принцип Парето, т.е. указанное выше включение, не является универсальным, пригодным во всех без исключения многокритериальных задачах, и иногда может нарушаться. Принципа Парето следует придерживаться в тех случаях, когда ЛПР в процессе выбора ведет себя достаточно «рационально». Если же ЛПР действует в определенном смысле «нерационально», то для него наилучшим (выбранным) может оказаться и то решение, которое парето-оптимальным не является.

К настоящему времени свойства множества Парето изучены достаточно подробно. В общем случае множество Парето может

• оказаться пустым;

• состоять из одного элемента;

• содержать бесконечное число элементов;

• совпадать с исходным множеством возможных решений.

Легко доказывается, что для конечного множества возможных решений множество Парето всегда не пусто, т.е. имеет место неравенство P_f(X) . Следует также отметить, что в случае непрерывных целевых функций f_1, ,f₂,...,f_m и непустого компактного множества X, X , обязательно существует хотя бы одно парето-оптимальное решение.

Важную роль в многокритериальной оптимизации играют различного рода необходимые и/или достаточные условия парето-оптимальности. Здесь в первую очередь следует отметить следующий легко проверяемый результат.

Если существует такой набор положительных чисел λ₁,λ₂,...,λ_т, для некоторого возможного решения х' X выполняется неравенство

для всех х Х, (3.10)

то х^* - парето-оптимальное решение.

Согласно приведенному достаточному условию парето-оптимальности, максимизация скалярной функции с положительными коэффициентами λ₁,λ₂,...,λ_т на множестве X, которую называют аддитивной сверткой критериев, всегда приводит к парето-оптимальному решению (при условии, что указанная задача максимизации имеет решение).

При определенных дополнительных условиях имеет место и обратный результат, т.е. необходимое условие парето-оптимальности. Сформулируем этот результат.

Пусть множество возможных решений Х, Х Rⁿ, является выпуклым и все целевые функции f,,f₂,...,f_m вогнуты на этом множестве. Для всякого парето-оптимального решения х' существует соответствующий набор неотрицательных чисел λ₁,λ₂,...,λ_т,, при котором имеет место неравенство (3.10).

Нетрудно заметить, что между достаточным (первым) и необходимым (вторым) условием парето-оптимальности имеется определенная «нестыковка». В достаточном условии требуется строгая положительность всех чисел λ₁,λ₂,...,λ_т,,, тогда как в необходимом условии эти числа неотрицательны и в сумме равны единице, а значит, они одновременно в нуль не обращаются, но среди них могут встречаться равные нулю.

Действительно, имеются примеры, когда максимизация аддитивной свертки, среди коэффициентов λ₁,λ₂,...,λ_т, которой могут встречаться нули, на множестве X приводит к решению, лежащему за пределами множества Парето.

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

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

Существуют определенные модификации понятия парето-оптимального решения. Например, возможное решение х' называют оптимальным по Слейтеру (слабо эффективным), если не существует х X, для которого имеют место строгие неравенства f_i (x) > f_i (x^*), для всех i = 1,2,..., т.

Из приведенных определений следует, что всякое парето-оптимальное решение является оптимальным по Слейтеру. Обратное в общем случае места не имеет, так как существуют оптимальные по Слейтеру решения, не являющиеся парето-оптимальными. Таким образом, множество решений, оптимальных по Слейтеру, в общем случае шире множества Парето.