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

Эта статья находится в разработке!

Определение

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

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

Задача многокритериальной оптимизации формулируется следующим образом:

[math]\min\limits_{\vec{x}}\{f_1(\vec{x}), f_2(\vec x), \dots, f_k(\vec x)\},[/math]

[math]\vec x \in S[/math]

где [math]f_i: R^n \to R[/math] это [math]k[/math] ([math]k\ge 2[/math]) целевых функций. Векторы решений [math]\vec x = (x_1, x_2, \dots, x_n)^T[/math] Относятся к области определения [math]S[/math].

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

Критерий оптимальности

Перечислим основные критерии оптимальности

Критерий Парето

Вектор решения [math]\vec x\in S[/math] - оптимальный по Парето, если [math]\not\exists\vec x'\in S[/math]:[math]f_i(\vec x) \le f_i(\vec x')[/math] для всех [math]i=1, \dots, k[/math] и [math]f_i(\vec x) \lt f_i(\vec x')[/math] для хотя бы одного [math]i[/math].

[math]P(S)[/math] - множество оптимальных по Парето решений.

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

[math]P(Z)[/math] - множество оптимальных по Парето целевых векторов.

Множество оптимальных по Парето векторов является подмножеством оптимальных по Парето в слабом смысле векторов. Вектор [math]\vec x'\in S[/math] является слабым оптимумом по Парето тогда, когда не существует вектора [math]\vec x\in S[/math] такого, что [math]f_i(\vec x) \lt f_i(\vec x')[/math] для всех [math]i=1, 2, \dots, k[/math].

Множество оптимальных по Парето решений также называют Парето-фронтом.

Парето-фронт не может быть вычислен за полиномиальное время

Лексикографический порядок

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

Отношение лексикографического порядка [math]\lt _{\mathrm{lex}}[/math] между векторами [math]\vec a[/math] и [math]\vec b[/math] выполняется, если [math]a_q \lt b_q[/math], где [math]q = min \left\{k : a_k \neq b_k\right\}[/math]. То есть, первая [math]q[/math] компонента вектора [math]\vec a[/math] меньше компоненты вектора [math]\vec b[/math], а компоненты [math]q+1[/math] — уровни (если есть). Лексикографический порядок для случая действительных чисел является линейным.

Вектор [math]\vec x \in X[/math] является лексикографическим решением, если не существует вектора [math]\vec x' \in X[/math], такого, что [math]f(\vec x') \lt _{\mathrm{lex}} f(\vec x)[/math].

Поскольку отношение лексикографического порядка является линейным, можно доказать, что вектор [math]\vec x[/math] является лексикографическим решением, если для всех [math]\vec x' \in X[/math] выполняется:

[math]\vec f(\vec x) \lt _{\mathrm{lex}} \vec f(\vec x').[/math]