РАССЛОЕНИЕ КОНЕЧНОГО МНОЖЕСТВА ПАРЕТО Ногин В.Д.

Санкт-Петербургский государственный университет


Номер: 12-1
Год: 2015
Страницы: 28-30
Журнал: Актуальные проблемы гуманитарных и естественных наук

Ключевые слова

множество Парето, линейная свертка критериев, Pareto set, linear scalarization of criteria

Просмотр статьи

⛔️ (обновите страницу, если статья не отобразилась)

Аннотация к статье

В заметке формулируется алгоритм построения разбиения множества Парето на основе линейных сверток критериев. Дается обоснование этого алгоритма.

Текст научной статьи

1. Постановка задачи многокритериальной оптимизации содержит два объекта - множество возможных (допустимых) решений (вариантов) , которое далее считается конечным, и заданные на этом множестве числовые функции , составляющие векторный критерий . Фундаментальными в рамках многокритериальной оптимизации являются множество эффективных (оптимальных по Парето, парето-оптимальных) решений (см. [1]): и множество соответствующих эффективных векторов . Здесь неравенство означает все компоненты вектора не меньше соответствующих компонент вектора , причем . В этом случае говорят, что вектор доминирует вектор по отношению Парето . В начале второго тысячелетия автором было установлено [2], что при выполнении определенных двух аксиом «разумного» выбора всякое решение задачи многокритериального выбора всегда содержится в множестве Парето. Иными словами, наилучшее решение задачи многокритериальной оптимизации следует искать именно в пределах множества Парето. Исследованию различных свойств множества Парето посвящена многочисленная литература (см., например, [1]). Это множество находит широкое применение при решении различного рода прикладных экономических и технических задач, в которых необходимо учитывать не одну, а несколько целевых функций. Наиболее простой способ найти какое-то парето-оптимальное решение - составить так называемую линейную свертку критериев с положительными коэффициентами и максимизировать ее на множестве . Найденное таким образом решение вне зависимости от конкретных значений положительных коэффициентов линейной свертки всегда будет парето-оптимальным (если оно существует). Применение линейной свертки реализует идею максимума средневзвешенных значений критериев и в случае выпуклого множества возможных решений и вогнутых критериев такой способ позволяет получить практически любое парето-оптимальное решение (см. [1]). Однако если множество состоит из конечного числа элементов, то далеко не всякое решение является максимально средневзвешенным. Пример подобного рода дает плоское множество , в котором каждый двумерный вектор является парето-оптимальным, тогда как максимальные средневзвешенные значения имеют только первые две точки. Остальные точки не могут быть получены в результате максимизации линейной свертки критериев, какими бы не выбирались ее положительные коэффициенты. Оказывается, можно расслоить множество Парето на такие подмножества, которые имеют принципиально различные средневзвешенные значения. Этого расслоения автор уже касался в своей работе [3], однако строгие рассуждения там отсутствуют. 2. Сформулируем алгоритм, в результате работы которого осуществляется разбиение множества Парето на классы, каждый из которых отвечает своему типу средневзвешенного значения. Этот алгоритм без обоснования впервые был впервые кратко изложен в работе автора [3]. Обозначим символом множество парето-оптимальных векторов, которые можно получить в результате решения задачи максимизации различных линейных сверток критериев с положительными коэффициентами: , где означает множество векторов с положительными компонентами, в сумме равными единице. Будем именовать его множеством Парето 1-го уровня (1-го слоя). Далее аналогичная задача решается на множестве , т.е. находится множество Из найденного множества следует удалить такие векторы , для которых найдутся такие, что . Оставшееся множество образует множество Парето 2-го уровня (2-го слоя) . Затем следует найти и удалить из него векторы векторы , для которых найдутся такие, что . Оставшееся множество образует множество Парето 3-го уровня (3-го слоя) . И т.д. Поскольку на каждом шаге множество, на котором производится максимизация, будет сокращаться, после некоторого конечного числа k шагов придём к пустому множеству. Таким образом, на предыдущем шаге k - 1 будет построено множество , а значит и . Как показывает нижеследующая теорема, последнее совпадает с множеством Парето и дает его разбиение на конечное число классов (уровней или слоев). 3. Теорема. Множество , построенное с помощью описанного выше алгоритма, представляет собой разбиение множества Парето на классы . Доказательство. Множества попарно не пересекаются, поскольку каждое следующее множество этой цепочки представляет собой результат максимизации линейных сверток на множестве, из которого удалено предыдущее множество данной цепочки. Включение вытекает из того факта, что максимизация линейной свертки критериев с положительными коэффициентами на множестве всегда приводит к парето-оптимальной точке. Проверим включение . В самом деле, если это не так, то найдутся , для которых . Однако по построению с одной стороны , а с другой . Поэтому в действительности указанного вектора не существует. При помощи аналогичных рассуждений можно убедиться, что все последующие множества цепочки также входят в множество Парето, т.е. имеет место включение . Установим обратное включение. Известно, что множество Парето в случае конечного множества возможных векторов является внешне устойчивым (см. [1]), т.е. всякий возможный вектор, не входящий в множество Парето, доминируется каким-то парето-оптимальным вектором по отношению . Тем самым, исходное множество векторов разбивается на две части, одна из которых совпадает с множеством парето-оптимальных векторов, тогда как другую часть образуют доминируемые ими векторы. Сформулированный алгоритм устроен таким образом, что на каждом шаге вместе с найденным новым слоем Парето удаляются векторы, которые доминируются слоем, построенным на предыдущем шаге. Причем на k-ом шаге образуется пустое множество и работа алгоритма заканчивается. Из этого следует, что в построенное множество не входят лишь те векторы, которые были удалены на том или ином предыдущем шаге как доминируемые. Следовательно, множество Парето не может быть шире . Теорема доказана. Множество состоит из парето-оптимальных векторов, компоненты которых в определенном смысле наиболее близки к так называемому надир-вектору [3]. Это обстоятельство можно учитывать при поиске «наилучшего» решения многокритериальной задачи.

Научные конференции

 

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