ОПТИМАЛЬНЫЙ МЕТОД ВЫДЕЛЕНИЯ МНОЖЕСТВА ПАРЕТО ИЗ МНОЖЕСТВА АЛЬТЕРНАТИВ

Манжула В.Г.

Кандидат технических наук, доцент, Институт коммуникативных технологий

ОПТИМАЛЬНЫЙ МЕТОД ВЫДЕЛЕНИЯ МНОЖЕСТВА ПАРЕТО ИЗ МНОЖЕСТВА АЛЬТЕРНАТИВ

Аннотация

В статье приведен проблемно-ориентированный метод выделения множества Парето из множества альтернатив. Метод позволяет строить компактное множество Парето в соответствии с предпочтениями ЛПР.

Ключевые слова: многокритериальный отбор, множество Парето, оптимизация по Парето, многокритериальная оптимизация.

Manzhula V.G.

Candidate of technical science, associate professor, Institute of communicative technologies

OPTIMAL METHODS FOR DETERMINING THE PARETO SET OF VARIETY OF ALTERNATIVES

Abstract

The paper presents a problem-oriented method for the determination of the Pareto set of alternatives. The method allows to build compact Pareto set in accordance with the preferences of decision-makers.

Keywords: multi-criteria selection, Pareto optimization, Pareto set, multi-objective optimization.

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

Каждая альтернатива имеет определенный набор параметров. Выделение множества Парето в общем случае предполагает, что имеется некоторый набор параметров, характерный для любой альтернативы из исходного множества альтернатив. Из общего набора параметров формируется общий набор критериев отбора в задаче поиска. На основе этого общего набора критериев и строится множество Парето или альтернатив, среди которых нет доминируемых.

Данный принцип построения множества Парето является оптимальным с математической точки зрения, но в определенных случаях, когда количество альтернативных решений и критериев отбора велико, может привести к необходимости сужения или свертки множества Парето из-за большого количества элементов, вошедших в него[3].

При решении задачи отбора зачастую ЛПР заранее знает, какие из критериев отбора его интересуют больше, а какие меньше. То есть имеется возможность выбора наиболее значимых критериев из всех критериев отбора [4,5]. На основании этой дополнительной информации, полученной от ЛПР, можно строить компактное множество Парето, куда войдут решения, оптимальные не по всем имеющимся критериям, а по критериям, наиболее значимым для ЛПР.

Для реализации этого метода необходимо представить множество критериев отбора в виде множества булевых функций, где значения элементов соответствуют  полученной от ЛПР информации. Если данный критерий имеет значимость для ЛПР, то его значение «истина», в противном случае – «ложь». Далее по критериям со значением «истина» производится выделение множества Парето из множества заданных альтернатив. Полученное таким образом множество Парето будет полностью соответствовать предпочтениям ЛПР, а количество элементов в нем будем меньше или равно количеству элементов множества Парето, построенного обычным способом.

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

Таким образом, использование дополнительной информации, полученной от ЛПР еще до построения множества Парето, позволяет значительно сократить и упростить автоматизированное решение задачи многокритериального отбора.