Задача многокритериальной оптимизации. 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|Доминируемые решения]]
−
 
 
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
−
Для двух решений <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|Парето фронт]]
 +
== Получение оптимальных по Парето решений ==
 +
Для выполнения оптимизации по нескольким критериям мы должны либо заменить единственную целевую
  
 
== Источники ==
 
== Источники ==

Версия 03:57, 19 июня 2012

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

Постановка задачи

Определение:
Задача многокритериальной оптимизации:
[math]maximize \{f(x) = (f_1(x),\dots,f_K(x))\}[/math]
[math] x \in X[/math]
где [math] f(x) : X \rightarrow R^K[/math] - целевая вектор-функция, где [math]K \ge 2[/math]

Так как не существует единого решение, которое было бы максимальным для всех целевых функций, вместо него можно искать множество [math]X^* \subseteq X [/math] множество Парето оптимальных значений.

Множество Парето оптимальных значений

Определение:
Множество Парето оптимальных значений:
[math]\forall x^* \in X^* \not\exists x \in X [/math]:[math]x \succ x^*[/math], где [math]x \succ x^* \Leftrightarrow (\forall i \in 1..K, (f_i(x) \ge f_i(x^*))\land (\exists i \in 1..K, f_i(x) \gt f_i(x^*)))[/math]

Выражение [math]x \succ x^*[/math] означает, что [math]x[/math] доминирует над [math]x^*[/math].

Доминируемые решения
Определение:
Для двух решений [math]x[/math] и [math]x'[/math] говорят [math]x \sim x'[/math] тогда и только тогда, когда [math]\exists i \in 1..K \colon f_i(x) \gt f_i(x') \land \exists j \in 1..K, j \ne i \colon f_j(x') \gt f_j(x)[/math] - такую пару решений называют недоминируемой


Множество Парето оптимальных недоминируемых решений называется Парето фронтом.

Парето фронт

Получение оптимальных по Парето решений

Для выполнения оптимизации по нескольким критериям мы должны либо заменить единственную целевую

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Задача_многокритериальной_оптимизации._Multiobjectivization&oldid=25723»