Многокритериальная оптимизация

Для возможности оценки качества найденных решений обычно рассматривают такие точки в области значения целевой функции:

• идеальная точка ${\displaystyle y^{I}}$,
• утопическая точка ${\displaystyle y^{U}}$,
• надир ${\displaystyle y^{N}}$.

В некоторых случаях эти точки могут быть решениями.

Идеальная точка определяется как вектор ${\displaystyle y^{I}=(y_{1}^{I},\dots ,y_{p}^{I})}$, каждая из координат которого имеет оптимальное значение соответствующей составляющей целевой функции:[5]

${\displaystyle y_{k}^{I}=\min _{x\in X}f_{k}(x)=\min _{y\in Y}y_{k}.}$

Точка надир ${\displaystyle y^{N}=(y_{1}^{N},\dots ,y_{p}^{N})}$ определяется как вектор:

${\displaystyle y_{k}^{N}=\max _{x\in X_{E}}y_{k}(x)=\max _{y\in Y_{N}}y_{k},\qquad k=1,\dots ,p.}$

Утопическую точку ${\displaystyle y^{U}}$ вычисляют на основе идеальной:[6]

${\displaystyle y^{U}=y^{I}-\varepsilon U,}$

где ${\displaystyle \varepsilon >0}$, ${\displaystyle U}$ — единичный вектор.

Вектор решения ${\displaystyle {\vec {x}}'\in S}$ называется оптимальным по Парето, если не существует ${\displaystyle {\vec {x}}\in S}$ такого, что ${\displaystyle f_{i}({\vec {x}})\leqslant f_{i}({\vec {x}}')}$ для всех ${\displaystyle i=1,\dots ,k}$ и ${\displaystyle f_{i}({\vec {x}})<f_{i}({\vec {x}}')}$ для хотя бы одного ${\displaystyle i}$. Множество оптимальных по Парето решений можно обозначить как ${\displaystyle P(S)}$. Целевой вектор является оптимальным по Парето, если соответствующий ему вектор из области определения также оптимален по Парето. Множество оптимальных по Парето целевых векторов можно обозначить как ${\displaystyle P(Z)}$.

Множество оптимальных по Парето векторов является подмножеством оптимальных по Парето в слабом смысле векторов. Вектор ${\displaystyle {\vec {x}}'\in S}$ является слабым оптимумом по Парето тогда, когда не существует вектора ${\displaystyle {\vec {x}}\in S}$ такого, что ${\displaystyle f_{i}({\vec {x}})<f_{i}({\vec {x}}')}$ для всех ${\displaystyle i=1,2,\dots ,k}$.

Диапазон значений оптимальных по Парето решений в области допустимых значений дает полезную информацию об исследуемой задаче, если целевые функции ограничены областью определения. Нижние границы оптимального по Парето множества представлены в «идеальном целевом векторе» ${\displaystyle {\vec {z}}\in R^{k}}$. Его компоненты ${\displaystyle z_{i}}$ получены путём минимализации каждой целевой функции в пределах области определения.

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

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

Отношение лексикографического порядка ${\displaystyle <_{\mathrm {lex} }}$ между векторами ${\displaystyle {\vec {a}}}$ и ${\displaystyle {\vec {b}}}$ выполняется, если ${\displaystyle a_{q}<b_{q}}$, где ${\displaystyle q=\min \left\{k:a_{k}\neq b_{k}\right\}}$. То есть первая ${\displaystyle q}$ компонента вектора ${\displaystyle {\vec {a}}}$ меньше компоненты вектора ${\displaystyle {\vec {b}}}$, а компоненты ${\displaystyle q+1}$ — уровни (если есть). Лексикографический порядок для случая действительных чисел является линейным.

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

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

${\displaystyle {\vec {f}}({\vec {x}})<_{\mathrm {lex} }{\vec {f}}({\vec {x}}').}$

Основной особенностью решений по лексикографическому порядку является существование выбора между критериями. Лексикографическая упорядоченность требует ранжирования критериев в том смысле, что оптимизация по критерию ${\displaystyle f_{k}}$ возможна лишь тогда, когда был достигнут оптимум для предыдущих критериев. Это означает, что первый критерий имеет наибольший приоритет, и только в случае существования нескольких решений по этому критерию будет поиск решений по второму и остальным критериям.

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

Для получения оптимальных по Парето решений часто используют методы скаляризации. Поскольку целевая функция задачи многокритериальной оптимизации имеет векторные значения, её превращают в функцию со скалярным значением. Таким образом, задача многокритериальной оптимизации сводится к задаче оптимизации с одной скалярной целевой функцией. Функция скаляризации должна удовлетворять следующим условиям.

Пусть ${\displaystyle F}$ — функция скаляризации, что превращает векторную функцию ${\displaystyle {\vec {y}}={\vec {f}}({\vec {x}})}$ в скалярную. Если ${\displaystyle F}$ сохраняет упорядоченность по Парето ${\displaystyle {\vec {y}}}$, то есть, если для произвольных ${\displaystyle {\vec {y}}^{1},{\vec {y}}^{2}\in {\vec {f}}(X)}$ выполняется:

${\displaystyle {\vec {y}}^{1}\leqslant {\vec {y}}^{2}\implies F({\vec {y}}^{1})<F({\vec {y}}^{2}),}$

тогда решение ${\displaystyle {\vec {x}}^{0}}$, что минимизирует ${\displaystyle F}$ до ${\displaystyle X}$, является решением по Парето.[7] Если ${\displaystyle F}$ сохраняет отношение порядка ${\displaystyle <}$ в ${\displaystyle {\vec {y}}}$, то есть, если для произвольных ${\displaystyle {\vec {y}}^{1},{\vec {y}}^{2}\in {\vec {f}}(X)}$ выполняется:

${\displaystyle {\vec {y}}^{1}<{\vec {y}}^{2}\implies F({\vec {y}}^{1})<F({\vec {y}}^{2}),}$

тогда решение ${\displaystyle {\vec {x}}^{0}}$, что минимизирует ${\displaystyle F}$ до ${\displaystyle X}$, является слабым по Парето. Если ${\displaystyle F}$ непрерывна на ${\displaystyle {\vec {y}}}$ и ${\displaystyle {\vec {x}}^{0}}$ единственная точка минимума ${\displaystyle F}$ на ${\displaystyle X}$, тогда ${\displaystyle {\vec {x}}^{0}}$ является решением по Парето.

${\displaystyle F_{1}({\vec {f}}({\vec {x}}))=w_{1}f_{1}({\vec {x}})+\dots +w_{r}f_{r}({\vec {x}}).}$

Приведенная функция ${\displaystyle F_{1}}$ сохраняет упорядоченность по Парето для ${\displaystyle w>0}$. Поэтому решения, минимизирующие ${\displaystyle F_{1}}$ до ${\displaystyle X}$ для произвольных ${\displaystyle w>0}$, являются оптимальными по Парето. Однако ${\displaystyle F_{1}}$ не сохраняет упорядоченность по Парето для ${\displaystyle w\geqslant 0}$, а сохраняет лишь отношение ${\displaystyle <}$, поэтому решения, минимизирующие ${\displaystyle F_{1}}$ на ${\displaystyle X}$ для ${\displaystyle w\geqslant 0}$, являются слабыми по Парето.[7]

Недостатком метода взвешенных сумм в случае выпуклого множества значений целевых функций является невозможность охватить все оптимальные по Парето точки из множества Парето-фронта. В задачах комбинаторной многокритериальной оптимизации множество целевых значений не является выпуклым, поэтому метод взвешенных сумм не подходит для скаляризации целевых функций для этих задач.

${\displaystyle F_{\infty }({\vec {f}}({\vec {x}}))=\max _{1\leqslant i\leqslant r}w_{i}f_{i}({\vec {x}}).}$

Взвешенная функция скаляризации Чебышёва сохраняет отношения ${\displaystyle <}$ и поэтому минимум ${\displaystyle F_{\infty }}$ является слабым по Парето.[7]

По методу изменения ограничений одну из целевых функций оставляют в качестве целевой, а остальные превращают в ограничения. То есть пусть ${\displaystyle f_{r}}$ будет целевой, а остальные ${\displaystyle f_{1},\dots ,f_{r-1}}$ представим как ограничение неравенства:

${\displaystyle \min _{x}f_{r}({\vec {x}}),}$

при условиях ${\displaystyle f_{i}({\vec {x}})\leqslant \varepsilon _{i},i=1,\dots ,r-1,}$

${\displaystyle {\vec {x}}\in X.}$

Значения ${\displaystyle \varepsilon _{1},\dots ,\varepsilon _{r-1}}$ могут рассматриваться как допустимые уровни для ${\displaystyle f_{1},\dots ,f_{r-1}.}$.

Часто решение задачи многокритериальной оптимизации происходит с участием эксперта — человека, который выбирает и принимает решения на основе информации, представленной системой поддержки принятия решений. Возможно участие группы из нескольких экспертов. В случае участия человека в поиске решения алгоритмы и методы называют интерактивными.[3]

Упоминания о применении генетических алгоритмов для решения задачи многокритериальной оптимизации относятся к концу 1960-х[8].

Метод основан на построении допустимого и Парето-оптимального множеств решений. Позволяет решать задачи проектирования, идентификации[9].

• Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. — М.: Радио и связь, 1981. — 560 с.
• Лотов А. В., Поспелова И. И. Конспект лекций по теории и методам многокритериальной оптимизации. Учеб. пос. М., 2005. 127 с.
• Matthias Ehrgott. Multicriteria Optimization (неопр.). — Springer, 2005. — ISBN 3-540-21398-8.
• M. Ehrgott and X. Gandibleux. Approximative Solution Methods for Multiobjective Combinatorial Optimization (англ.) // TOP : journal. — Sociedad de Estadística e Investigación Operativa, 2004. — Vol. 12, no. 1. Архивировано 23 июля 2007 года.

• Трифонов А. Г. Многокритериальная оптимизация (рус.)