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

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

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

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

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

где - целевая вектор-функция, где

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

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

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

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

:, где

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

Говорят, что [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 показана область пространства, доминируемая данным решением А. Эта область «замкнута»: элементы на ее границе также доминируемы А

Рис.1 - Доминируемые решения

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

Для двух решений и говорят тогда и только тогда, когда - такую пару решений называют недоминируемой

На рис. 2 показана граница Парето для возможных решений в двухкритериальном пространстве

Рис.2 - Парето фронт

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

Multi-objectivization

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

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

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