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

В задачах САПР часто возникает задача обеспечить оптимальность объекта проектирования одновременно по нескольким критериям оптимальности

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

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

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

Будем называть каждый из скалярных критериев оптимальности

частным критерием оптимальности. Совокупность частных критериев оптимальности

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

), ф₂(

), ... , ф_s(

) в одной и той же области допустимых значений

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

в целом.

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

(1)

где

— множество допустимых значений вектора варьируемых параметров

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

к одному масштабу. Чаще всего при этом используют относительные отклонения частных критериев от их минимальных значений:

где

Метод относится к классу стохастических методов оптимизации

Сохраним за нормализованными частными критериями оптимальности обозначения

Множество Парето.

Введем понятие пространства критериев

. Пространство критериев имеет размерность

(по числу частных критериев) и образуется

ортогональными осями координат, вдоль которых откладываются значения частных критериев оптимальности

Векторный критерий оптимальности

выполняет отображение множества допустимых значений

в некоторую область

, где

— пространство варьируемых параметров (см. рис. 1).

Рис. 1. К отображению векторным критерием оптимальности Φ(X) множества допустимых значений D_X пространства варьируемых параметров {X} в область D_Φ пространства критериев {Φ}. Случай n=2, s=2.

Введем на множестве

отношение предпочтения.

Отношение предпочтения

. Будем говорить, что вектор

предпочтительнее вектора

, и писать

, если среди равенств и неравенств

имеется хотя бы одно строгое неравенство (см. рис. 2).

Аналогично на множестве

введем отношение доминирования: будем говорить, что векторный критерий оптимальности

доминирует векторный критерий оптимальности

, и писать

, если

(см. рис. 2).

Примечание 1

Введенные отношение предпочтения и отношение доминирования являются транзитивными, т.е.

если

, то

;

если

) и

(

, то

(

Рис. 2. К понятию отношения предпочтения и отношения доминирования (s = 2). Для всех точек заштрихованной области Ф(X¹) ⊳ Ф(X²), т.е. заштрихованной области пространства критериев соответствуют векторы варьируемых параметров X ∈ D_Ф, для которых X¹ ⊱ X².

Выделим из множества

подмножество

точек, для которых нет точек, их доминирующих. Множество

, соответствующее

, называется множеством Парето (переговорным множеством, областью компромисса) — см. рис. 3. Поскольку множество D_Ф на рисунке является выпуклым, то множество D

- есть часть границы множества D_Ф — дуга AB, в которой точка A соответствует (ф₂)_min, а точка B — (ф₁)_min. Среди точек

(X¹)

D^*_Ф,

(X²)

D^*_Ф нет более предпочтительных, поскольку ф₁(X¹) > ф₁(X²), но ф₂(X¹) > ф₂(X²).

Таким образом, если

, то

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

Рис. 3. К определению множества Парето (s = 2).

Пример 1

Пусть множество допустимых значений

(см. рис. 4) и заданы два частных критерия оптимальности

. Можно показать, что множество

при этом имеет вид, представлены на рис. 5, а множество Парето

представляет собой отрезок прямой, соединяющий точки

— см. рис. 4.

Рис. 4. К прим. 1.

Рис. 5. К прим. 1.

Заметим, что точки

являются точками минимума частных критериев оптимальности

, соответственно.

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

Теорема 1. Если для некоторых весовых множителей

и вектора

имеет место равенство

(2)

то вектор

оптимален по Парето, т.е.

Доказательство. Пусть вектор

не оптимален по Парето. Тогда существует такой вектор

, что

(3)

причем хотя бы одно из неравенств строгое. Умножая каждое из неравенств (3) на

и складывая, получим

что противоречит условию теоремы

Теорема 1 доказана для случая неотрицательных весовых коэффициентов

, хотя не содержит этого условия. Однако доказательство возможно и для произвольных весовых коэффициентов.

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

Заметим, что теорема 1 задает лишь необходимое условие оптимальности по Парето вектора

. Т.е. из того факта, что точка

принадлежит множеству Парето, не следует, что эта точка обязательно удовлетворяет условию (2).

В постановке задачи многокритериальной оптимизации (1) фиксируется лишь множество допустимых значений

и вектор частных критериев

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