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

Многокритериальная оптимизация, или программирование (англ. Multi-objective optimization) — это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения.

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

Определение

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

${\displaystyle \min _{\vec {x}}\{f_{1}({\vec {x}}),f_{2}({\vec {x}}),\dots ,f_{k}({\vec {x}})\},}$

${\displaystyle {\vec {x}}\in S}$

где ${\displaystyle f_{i}:R^{n}\to R}$ это ${\displaystyle k}$ (${\displaystyle k\geqslant 2}$) целевых функций. Векторы решений ${\displaystyle {\vec {x}}=(x_{1},x_{2},\dots ,x_{n})^{T}}$ относятся к непустой области определения ${\displaystyle S}$.

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

Эталонные точки

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

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

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

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

${\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}}$ вычисляют на основе идеальной:

${\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}$, является решением по Парето. Если ${\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}$, являются слабыми по Парето.

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

Функция скаляризации Чебышёва

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

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

Метод изменения ограничений (ε-ограничения)

По методу изменения ограничений одну из целевых функций оставляют в качестве целевой, а остальные превращают в ограничения. То есть пусть ${\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}.}$.

Методы решения

Интерактивность

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

Эволюционные методы

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

Метод исследования пространства параметров

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

См. также

• Эффективность по Парето
• Задача оптимизации
• Скалярное ранжирование

Примечания

1. Steuer, R.E. Multiple Criteria Optimization: Theory, Computations, and Application (англ.). — New York: John Wiley & Sons, Inc, 1986. — ISBN 047188846X.
2. Sawaragi, Y.; Nakayama, H. and Tanino, T. Theory of Multiobjective Optimization (vol. 176 of Mathematics in Science and Engineering) (англ.). — Orlando, FL: Academic Press Inc, 1985. — ISBN 0126203709.
3. Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen та Roman Slowinski. Multiobjective Optimization: Interactive and Evolutionary Approaches (Lecture Notes in Computer Science) (англ.). — Springer. — ISBN 3-540-88907-8.
4. A. Osyzka. Multicriteria optimization for engineering design (неопр.) // Design Optimization. — Academic Press. — С. 193—227.
5. (Ehrgott, c. 34)
6. (Jürgen et al, с. XI)
7. Nakayama, Hirotaka; Yun, Yeboon; Yoon, Min. Sequential Approximate Multiobjective Optimization Using Computational Intelligence (Vector Optimization) (англ.). — Springer. — ISBN 978-3-540-88909-0.
8. R. S. Rosenberg. Simulation of genetic populations with biochemical properties (англ.). — Ann Harbor: University of Michigan, 1967.
9. Соболь И.М. Выбор оптимальных параметров в задачах со многими критериями. — М.: Дрофа, 2006. — 175 с. — ISBN 5-7107-7989-X.

Литература

• Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. — М.: Радио и связь, 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 года.

Ресурсы интернета

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