Задача многокритериальной оптимизации. Multiobjectivization — различия между версиями
(→Множество Парето оптимальных значений) |
|||
| Строка 16: | Строка 16: | ||
}} | }} | ||
Выражение <math>x \succ x^*</math> означает, что <math>x</math> ''доминирует над'' <math>x^*</math>. | Выражение <math>x \succ x^*</math> означает, что <math>x</math> ''доминирует над'' <math>x^*</math>. | ||
| − | [[Файл:Dogmin points.jpg|мини|200px|Доминируемые решения]] | + | |
| + | Говорят, что <math>x</math> ''доминирует над'' <math>x^*</math>. по | ||
| + | Парето, если <math>x</math> не хуже <math>x^*</math> по всем критериям и хотя бы по одному критерию превосходит <math>x^*</math>. | ||
| + | В таком случае в выборе <math>x^*</math> нет смысла, т.к. <math>x</math> по всем параметрам не уступает, а по каким-то и превосхожит <math>x^*</math>. Если рассматривать всего | ||
| + | два критерия то на рис. 1 показана область | ||
| + | пространства, доминируемая данным решением А. Эта область «замкнута»: | ||
| + | элементы на ее границе также доминируемы А | ||
| + | [[Файл:Dogmin points.jpg|мини|200px|Рис.1 - Доминируемые решения ]] | ||
{{Определение | {{Определение | ||
| Строка 22: | Строка 29: | ||
Для двух решений <math>x</math> и <math>x'</math> говорят <math>x \sim x'</math> тогда и только тогда, когда <math>\exists i \in 1..K \colon f_i(x) > f_i(x') \land \exists j \in 1..K, j \ne i \colon f_j(x') > f_j(x)</math> - такую пару решений называют '''недоминируемой''' | Для двух решений <math>x</math> и <math>x'</math> говорят <math>x \sim x'</math> тогда и только тогда, когда <math>\exists i \in 1..K \colon f_i(x) > f_i(x') \land \exists j \in 1..K, j \ne i \colon f_j(x') > f_j(x)</math> - такую пару решений называют '''недоминируемой''' | ||
}} | }} | ||
| − | [[Файл:Pareto_front.jpg|мини|200px|Парето фронт]] | + | На рис. 2 показана граница Парето для |
| + | возможных решений в двухкритериальном пространстве | ||
| + | [[Файл:Pareto_front.jpg|мини|200px|Рис.2 - Парето фронт]] | ||
Множество Парето оптимальных недоминируемых решений называется '''Парето фронтом.''' | Множество Парето оптимальных недоминируемых решений называется '''Парето фронтом.''' | ||
| − | |||
== Multi-objectivization == | == Multi-objectivization == | ||
Версия 04:31, 19 июня 2012
Содержание
Задача многокритериальной оптимизации
Постановка задачи
| Определение: |
| Задача многокритериальной оптимизации:
|
Так как не существует единого решение, которое было бы максимальным для всех целевых функций, вместо него можно искать множество множество Парето оптимальных значений.
Множество Парето оптимальных значений
| Определение: |
Множество Парето оптимальных значений:
|
Выражение означает, что доминирует над .
Говорят, что доминирует над . по Парето, если не хуже по всем критериям и хотя бы по одному критерию превосходит . В таком случае в выборе нет смысла, т.к. по всем параметрам не уступает, а по каким-то и превосхожит . Если рассматривать всего два критерия то на рис. 1 показана область пространства, доминируемая данным решением А. Эта область «замкнута»: элементы на ее границе также доминируемы А
| Определение: |
| Для двух решений и говорят тогда и только тогда, когда - такую пару решений называют недоминируемой |
На рис. 2 показана граница Парето для возможных решений в двухкритериальном пространстве
Множество Парето оптимальных недоминируемых решений называется Парето фронтом.
Multi-objectivization
Для выполнения оптимизации многокритериальной задачи мы должны добавить в целевую функцию новые параметры, либо должны добавить новые целевые функции.
Сложность этой процедуры заключается в разложении проблемы на ряд мелких независимых между собой под-проблем.
