Парето-фронт

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

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

Граница производственных возможностей . Красная линия является примером границы, эффективной по Парето, где граница и область слева и под ней представляют собой непрерывный набор вариантов выбора. Красные точки на границе — примеры оптимального по Парето выбора производства. Точки за пределами границы, такие как N и K, не являются эффективными по Парето, поскольку на границе существуют точки, которые над ними доминируют по Парето.

Определение

Граница Парето, P ( Y ), может быть более формально описана следующим образом. Рассмотрим систему с функцией $f:X\rightarrow \mathbb {R} ^{m}$, где X — компактное множество допустимых решений в метрическом пространстве $\mathbb {R} ^{n}$, а Y — допустимый набор критериальных векторов в $\mathbb {R} ^{m}$, такой, что $Y=\{y\in \mathbb {R} ^{m}:\;y=f(x),x\in X\;\}$.

Будем считать, что предпочтительные направления значений критериев известны. точка $y^{\prime \prime }\in \mathbb {R} ^{m}$ предпочтительнее (строго доминирует) другого пункта $y^{\prime }\in \mathbb {R} ^{m}$, записанный как $y^{\prime \prime }\succ y^{\prime }$. Таким образом, граница Парето записывается как:

$P(Y)=\{y^{\prime }\in Y:\;\{y^{\prime \prime }\in Y:\;y^{\prime \prime }\succ y^{\prime },y^{\prime }\neq y^{\prime \prime }\;\}=\emptyset \}.$

Предельная норма замещения

Важным аспектом границы Парето в экономике является то, что при эффективном по Парето распределении предельная норма замещения одинакова для всех потребителей. Формальное утверждение можно получить, рассматривая систему с m потребителями и n товарами и функцию полезности каждого потребителя как $z_{i}=f^{i}(x^{i})$ где $x^{i}=(x_{1}^{i},x_{2}^{i},\ldots ,x_{n}^{i})$ — вектор товаров, как для всех i . Ограничение осуществимости $\sum _{i=1}^{m}x_{j}^{i}=b_{j}$ для $j=1,\ldots ,n$. Чтобы найти оптимальное по Парето распределение, мы максимизируем лагранжиан :

$L_{i}((x_{j}^{k})_{k,j},(\lambda _{k})_{k},(\mu _{j})_{j})=f^{i}(x^{i})+\sum _{k=2}^{m}\lambda _{k}(z_{k}-f^{k}(x^{k}))+\sum _{j=1}^{n}\mu _{j}\left(b_{j}-\sum _{k=1}^{m}x_{j}^{k}\right)$

где $(\lambda _{k})_{k}$ и $(\mu _{j})_{j}$ – векторы множителей. Взяв частную производную лагранжиана по каждому товару $x_{j}^{k}$ для $j=1,\ldots ,n$ и $k=1,\ldots ,m$ дает следующую систему условий первого порядка:

${\frac {\partial L_{i}}{\partial x_{j}^{i}}}=f_{x_{j}^{i}}^{1}-\mu _{j}=0{\text{ for }}j=1,\ldots ,n,$

${\frac {\partial L_{i}}{\partial x_{j}^{k}}}=-\lambda _{k}f_{x_{j}^{k}}^{i}-\mu _{j}=0{\text{ for }}k=2,\ldots ,m{\text{ and }}j=1,\ldots ,n,$

где $f_{x_{j}^{i}}$ обозначает частную производную $f$ относительно $x_{j}^{i}$. Теперь исправьте любую $k\neq i$ и $j,s\in \{1,\ldots ,n\}$. Из приведенного выше условия первого порядка следует, что

${\frac {f_{x_{j}^{i}}^{i}}{f_{x_{s}^{i}}^{i}}}={\frac {\mu _{j}}{\mu _{s}}}={\frac {f_{x_{j}^{k}}^{k}}{f_{x_{s}^{k}}^{k}}}.$

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

Вычисление

Алгоритмы вычисления границы Парето конечного набора альтернатив изучались в информатике и энергетике. Они включают в себя:

• « Максимумы множества точек »
• «Задача о максимальном векторе» или запрос линии горизонта
• «Алгоритм скаляризации» или метод взвешенных сумм
• " $\epsilon$-метод ограничений"
• Многокритериальные эволюционные алгоритмы

Приближения

Поскольку создание всего фронта Парето часто требует вычислительных усилий, существуют алгоритмы для вычисления приблизительного фронта Парето. Например, Легриэль и др. набор S -аппроксимацией назовем ε фронта Парето P , если направленное расстояние Хаусдорфа между S и P не превосходит ε . Они отмечают, что ε -аппроксимация любого фронта Парето P в измерениях d может быть найдена с помощью (1/ ε ) ^д запросы.

Цитцлер, Ноулз и Тиле сравнить несколько алгоритмов аппроксимации множества Парето по различным критериям, таким как инвариантность к масштабированию, монотонность и сложность вычислений.