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

Сентябрь 2, 2022

Главная
Алгебра
Многокритериальная оптимизация

Содержание

2. Оптимальность по Парето Большинство реально возникающих задач оптимизации являются многокритериальными. То есть, нужно оптимизировать одновременно не
3. Оптимальность по Парето Функции (критерии) могут быть согласованными, нейтральными, конфликтующими. Критерии являются согласованными, если улучшение одного
4. Оптимальность по Парето Определение 1. Решение называется оптимальным по Парето, если во множестве допустимых решений не
5. Оптимальность по Парето Из определения следует, что решение многокритериальной задачи оптимизации целесообразно выбирать из множества Парето,
6. Оптимальность по Парето Рассмотрим простейшую ситуацию. Заштрихованная область изображает значения двух критериев оптимизации f1 и f2,
7. Оптимальность по Парето Точек оптимальных по Парето, даже в простейших задачах может быть много. Чем больше
8. Оптимальность по Парето Для построения множества Парето могут быть использованы следующие методы: 1) методы свертки критериев,
9. Методы сверток критериев Задача многокритериальной оптимизации сводится к задаче однокритериальной оптимизации введением одного обобщенного критерия где
10. Методы сверток критериев Функция называется аддитивной сверткой. В результате оптимизации аддитивной свертки может быть получена точка,
11. Методы сверток критериев Аддитивная свертка критериев имеет ряд недостатков: • не всегда потеря качества по одному
12. Методы сверток критериев Другие свертки критериев мультипликативного вида: с теми же самыми ограничениями, как в аддитивной
13. Методы, использующие ограничения на критерии Это направление различает два подхода: Дискриминационный метод. Метод последовательных уступок.
14. Дискриминационный метод На все или на часть критериев накладывается определенный уровень ограничений. Затем ищется оптимум по
15. Метод последовательных уступок Все критерии располагаются в порядке уменьшения их приоритета (важности). Затем решается последовательность однокритериальных
16. Метод последовательных уступок 1 этап. Решается задача при Определяется и назначается уступка 2 этап. Решается задача
17. Метод последовательных уступок Точка, полученная после последнего этапа, является оптимальной по Парето. Чтобы получить несколько точек,
18. Метод последовательных уступок Однако этот метод также имеет недостатки: • величины уступок не соизмеримы друг с
20. Скачать презентацию

Слайд 2

Оптимальность по Парето
Большинство реально возникающих задач оптимизации являются многокритериальными. То есть,

нужно оптимизировать одновременно не одну, а целое множество функций (критериев оптимальности).
Пусть имеются критерии оптимальности (эффективности): ,
где
удовлетворяют ограничениям
Тогда задача оптимизации примет вид:

Слайд 3

Оптимальность по Парето
Функции (критерии) могут быть согласованными, нейтральными, конфликтующими.
Критерии являются

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

Слайд 4

Оптимальность по Парето
Определение 1. Решение называется оптимальным по Парето, если во

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

Слайд 5

Оптимальность по Парето
Из определения следует, что решение многокритериальной задачи оптимизации целесообразно

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

Слайд 6

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

оптимизации f1 и f2, которые соответствуют переменным X в допустимой области.

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

Слайд 7

Оптимальность по Парето
Точек оптимальных по Парето, даже в простейших задачах может

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

Слайд 8

Оптимальность по Парето
Для построения множества Парето могут быть использованы следующие методы:
1) методы

свертки критериев,
2) методы, основанные на наложении ограничений на критерии,
3) методы, основанные на отыскании компромиссного решения,
4) методы целевого программирования и др.

Слайд 9

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

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

Слайд 10

Методы сверток критериев
Функция называется аддитивной сверткой.
В результате оптимизации аддитивной свертки

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

Слайд 11

Методы сверток критериев
Аддитивная свертка критериев имеет ряд недостатков:
• не всегда потеря качества

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

Слайд 12

Методы сверток критериев
Другие свертки критериев мультипликативного вида:
с теми же самыми ограничениями,

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

Слайд 13

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

Метод последовательных уступок.

Слайд 14

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

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

Слайд 15

Метод последовательных уступок
Все критерии располагаются в порядке уменьшения их приоритета (важности).

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

Слайд 16

Метод последовательных уступок
1 этап. Решается задача при Определяется и назначается уступка

2 этап. Решается задача при при наличии ограничения
Определяется и назначается уступка .
k-ый этап. Решается задача при при наличии ограничений

Слайд 17

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

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

Слайд 18

Метод последовательных уступок
Однако этот метод также имеет недостатки:
• величины уступок не соизмеримы

друг с другом, сложно их выбирать;
• в общем случае полученное решение не оптимально по Парето.

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

Содержание

Оптимальность по ПаретоБольшинство реально возникающих задач оптимизации являются многокритериальными. То есть,

Оптимальность по ПаретоФункции (критерии) могут быть согласованными, нейтральными, конфликтующими. Критерии являются

Оптимальность по ПаретоОпределение 1. Решение называется оптимальным по Парето, если во

Оптимальность по ПаретоИз определения следует, что решение многокритериальной задачи оптимизации целесообразно

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

Оптимальность по ПаретоТочек оптимальных по Парето, даже в простейших задачах может

Оптимальность по ПаретоДля построения множества Парето могут быть использованы следующие методы:1) методы

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

Методы сверток критериевФункция называется аддитивной сверткой. В результате оптимизации аддитивной свертки

Методы сверток критериевАддитивная свертка критериев имеет ряд недостатков:• не всегда потеря качества

Методы сверток критериевДругие свертки критериев мультипликативного вида:с теми же самыми ограничениями,

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

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

Метод последовательных уступокВсе критерии располагаются в порядке уменьшения их приоритета (важности).

Метод последовательных уступок1 этап. Решается задача при Определяется и назначается уступка

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

Метод последовательных уступокОднако этот метод также имеет недостатки:• величины уступок не соизмеримы

Похожие презентации