WikiSort.ru - Не сортированное

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

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

• идеальная точка ${\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 с.
• Matthias Ehrgott. Multicriteria Optimization. — Springer, 2005. — ISBN 3-540-21398-8.
• M. Ehrgott and X. Gandibleux (2004). “Approximative Solution Methods for Multiobjective Combinatorial Optimization”. TOP. Sociedad de Estadística e Investigación Operativa. 12 (1). Проверено 2011-12-01.

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

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