Глава 11. Задачи многокритериальной оптимизации и методы их решения

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

В задачах САПР часто возникает задача обеспечить оптимальность объекта проектирования одновременно по нескольким критериям оптимальности . Обычно эти критерии противоречивы и оптимизация по каждому из них приводит к различным значениямвектора варьируемых параметров . Поэтому выделяется отдельный классзадач многокритериальной оптимизации.

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

Будем называть каждый из скалярных критериев оптимальности частным критерием оптимальности. Совокупность частных критериев оптимальности будем называтьвекторным критерием оптимальности. Положим, что ставится задача минимизации каждого из частных критериев оптимальности ф₁(), ф₂(), ... , ф_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) нужна дополнительная информация.

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

Используя покрытие множества допустимых значений вектора варьируемых параметров , постройте приближенномножество Парето для следующей задачи двухкритериальной оптимизации :

.

Изобразите на рисунках множества ,,,.

 Ответ 

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

Рис. 1.  

2. Вычисляем значения частных критериев оптимальности ,в узлах построенной сетки и заносим их в табл. 1.

Таблица 1    

x	y			Номер узла
0	1	4	41	1
0	2	5	34	2
0	3	8	29	3
0	4	13	26	4
0	5	20	25	5
1	1	1	32	6
1	2	2	25	7
1	3	5	20	8
1	4	10	17	9
1	5	17	16	10
2	1	0	25	11
2	2	1	18	12
2	3	4	13	13
2	4	9	10	14
2	5	16	9	15
3	1	1	20	16
3	2	2	13	17
3	3	5	8	18
3	4	10	5	19
3	5	17	4	20
4	1	4	17	21
4	2	5	10	22
4	3	8	5	23
4	4	13	2	24
4	5	20	1	25
5	1	9	16	26
5	2	10	9	27
5	3	13	4	28
5	4	18	1	29
5	5	25	0	30

3. Отображаем вычисленные значения частных критериев оптимальности ,в системе координат(см.рис. 2).

Рис. 2.  

4. На рис. 2 аппроксимируем границу множество ломаной и выделяем множество.

5. Отмечаем точки, соответствующие множеству , на множествеи аппроксимируем полученные точки отрезком прямой. Этот отрезок прямой и представляет собой приближение к искомомумножеству Парето (см. рис. 1).

Метод весовых множителей решения задачи многокритериальной оптимизации

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

(1)

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

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

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

(2)

Т.е. вместо задачи (1) решается многомерная задача условной оптимизации со скалярным критерием оптимальности (2)

(3)

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

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

Таблица 1    

Относительная важность критерия	Определение относительной важности критериев
1	Равная важность
3	Умеренное (слабое) превосходство
5	Сильное (существенное) превосходство
7	Очевидное превосходство
9	Абсолютное (подавляющее) превосходство
2,4,6,8	Промежуточные решения между двумя соседними оценками

Шкала относительной важности частных критериев.

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

Дадим геометрическую интерпретацию метода. Введем в рассмотрение вектор. Тогдакритерий оптимальности (2) можно записать в виде скалярного произведения

(4)

а задачу (3) в виде

(5)

Уравнение , где— некоторая константа, определяет впространстве критериев гиперплоскость. При этом решение задачи (5) можно интерпретировать как поиск такого значения, при котором гиперплоскостьбудет касательной к множествузадачи (1). Компоненты вектораопределяют искомую точку касания этой гиперплоскости с множеством(см. рис. 1). На рис. 1 для любой точкимножества(дуга A,B) найдется вектор весовых множителей= (λ₁, λ₂, ... , λ_s), при котором эта точка удовлетворяет условию (5).

Рис. 1.  Геометрическая интерпретация метода весовых множителей: случай двух критериев; множество D_Ф выпукло.

Множество задачи (1) может быть не выпуклым. В этом случае не все точки множествамогут быть достигнуты с помощью изменения весовых множителей(см. рис. 2). На рис. 2 ни для одной точкимножества, принадлежащей дуге A₁B₁, невозможно найти вектор весовых множителей = (λ₁, λ₂, ... , λ_s), при котором эта точка удовлетворяет условию (5).

Рис. 2.  Геометрическая интерпретация метода весовых множителей: случай двух критериев; множество D_Ф не выпукло.

Метод эпсилон-ограничений решения задачи многокритериальной оптимизации

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

(1)

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

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

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

Дополнительной информацией в методе ε-ограничений является информация о номере самого важного из частных критериев , а также информация о максимально допустимых значения частных критериев .

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

(2)

где

(3)

Метод ε-ограничений в значительной мере свободен от указанного выше недостатка метода весовых множителей в случае, когда множество не выпукло (см. рис. 1). На рис. 1 точка A₂ в данном методе является доступной.

Рис. 1.  Геометрическая интерпретация метода ε-ограничений: случай двух критериев; множество D_Ф не выпукло; самым важным является критерий ф₁(X); на критерий ф₂(X) наложено ограничение ф₂(X) ≤ ε₂.

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

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

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

(1)

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

Положим, что все частные критерии имеют одинаковую важность!

Справедливый компромисс.

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

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

Пусть во множестве Парето задачи (1) даны две точки ,и значения всехчастных критериев оптимальности в них . Введем меру относительного изменения (снижения – знак "минус" или повышения – знак "плюс") качества решения по каждому из этих критериев

(2)

где — абсолютные изменения значенийчастных критериев оптимальности при переходе от решенияк решению. Вычислим максимальное снижение качества решения при переходе от решенияк решению

(3)

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

(4)

Будем говорить, что решение превосходит решение, и писать

(5)

С другой стороны, будем говорить, что решение превосходит решение, и писать

(6)

Пример 1

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

Таблица 1    

	1	2	3	5
	3	2	0	4

По формулам (2), (3), (4) последовательно имеем

Поскольку , т.е. максимальное относительное повышение качества решения превышает максимальное относительное снижение качества решения, то решениепревосходит решения:.

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

Упрощенная схема метода справедливого компромисса.

Рассмотрим основные этапы метода справедливого компромисса.

1. Полагаем счетчик числа итераций .

2. Тем или иным способом выбираем из множества Парето задачи решение.

3. Вычисляем значения всех частных критериев оптимальности в точке.

4. Тем или иным способом выбираем из множества Парето задачи (1) решение .

5. Вычисляем значения всех частных критериев оптимальности в точке.

6. По формулам (2), (3), (4), (5), (6) из числа решений ,находим превосходящее решение. Обозначим его.

7. Если условие окончания итераций выполнено (см. ниже), то принимаем точку в качестве приближенного решения задачи (1) и заканчиваем вычисления. Иначе полагаеми переходим к п.3

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

Выбор решений может быть произведен также с помощью полного перебора узлов какой-либо сетки, покрывающей множество.

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

Метод приближения к идеальному решению для решения задач многокритериальной оптимизации

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

(1)

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

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

Идеальным решением задачи многокритериальной оптимизации (1) называется вектор , где

минимальное значение частного критерия оптимальности во множестве.

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

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

(2)

где — некоторая векторная норма, например, евклидова;— нормированныйвекторный критерий оптимальности; — нормированноеидеальное решение (единичный -вектор).

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

(3)

Заметим, что если — евклидова норма, токритерий оптимальности является квадратичной функцией компонент вектора. Поэтому если, дополнительно, множествоявляется выпуклым, то задача (3) представляет собойзадачу квадратичного программирования. Этот факт значительно упрощает решение задачи (3).

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

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

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

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

(1)

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

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

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

Далее решается задача минимизации критерия

(2)

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

(3)

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

(4)

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

(5)

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

И т.д. до предпоследнего по важности критерия . Решается задача минимизации критерия

(6)

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

(7)

Наконец, переходим к последнему по важности критерию . Решается задача минимизации критерия

(8)

В качестве решения задачи (1) принимается решение со значениямичастных критериев .

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

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

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

2. Поскольку взаимосвязь частных критериев обычно неизвестна, заранее назначить величины уступок , как правило, не удается. Поэтому изучение взаимосвязи частных критериев и назначение величин уступки приходится производить в процессе решения задачи. Практически, для этого вначале оценивают взаимосвязь частных критериев,. Для этого задают несколько величин уступоки определяют соответствующие значения второго по важности критерия. На основе анализа этой информации лицо, принимающее решение, принимает решение о величине первой уступки. Затем аналогично оценивают взаимосвязь частных критериев,и назначают величину второй уступки. И так далее до критериев,и уступки. Таким образом, фактически приходится решать каждую из задач (2), (4), (5), (6) не однократно, как в изложенной схеме, а многократно.

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

4. Сложной самостоятельной проблемой является отыскание в явном виде множеств .

Дополнительной информацией в методе последовательных уступок является информация об относительной важности частных критериев , а также информация обуступках .