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

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

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

Определение:

Задача многокритериальной оптимизации: [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] - такую пару решений называют недоминируемой

Парето фронт

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

Multi-objectivization

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

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

Источники

• Википедия: Многокритериальная оптимизация
• Knowles J., Watson R., Corne D. Reducing Local Optima in Single-Objective Problems by Multi-objectivization
• Friedrich T., Neumann F. Foundations of Evolutionary Multi-Objective Optimization