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

Множество всех ситуаций, эффективных по Парето

В многокритериальной оптимизации фронт Парето (также называемый границей Парето или кривой Парето ) представляет собой набор всех эффективных по Парето решений. ^[1] Эта концепция широко используется в технике . ^{[2] : 111–148} Это позволяет разработчику ограничить внимание набором эффективных вариантов и делать компромиссы в рамках этого набора, вместо того, чтобы рассматривать полный диапазон каждого параметра. ^{[3] : 63–65  [4] : ​​399–412}

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

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

Определение

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

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

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

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

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

${\displaystyle 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)}$

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

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

${\displaystyle {\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,}$

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

${\displaystyle {\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}}}.}$

Таким образом, при оптимальном по Парето распределении предельная норма замещения должна быть одинаковой для всех потребителей. ^{[ нужна цитата ]}

Вычисление

Алгоритмы вычисления границы Парето конечного набора альтернатив изучались в информатике и энергетике. ^[6] К ним относятся:

• « Максимумы множества точек »
• «Задача о максимальном векторе» или запрос линии горизонта ^{[7] [8] [9]}
• «Алгоритм скаляризации» или метод взвешенных сумм ^{[10] [11]}
• « Метод -ограничений» ^{[12] [13]} ${\displaystyle \epsilon }$
• Многокритериальные эволюционные алгоритмы

Приближения

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

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

Рекомендации

1. Проксимедиа. «Фронт Парето». www.cenaero.be . Проверено 8 октября 2018 г.
2. Гударзи, Э., Зиаи, М., и Хоссейнипур, Э.З., Введение в оптимизационный анализ в гидросистемотехнике ( Берлин / Гейдельберг : Springer , 2014), стр. 111–148.
3. Джахан А., Эдвардс К.Л. и Бахраминасаб М., Многокритериальный анализ решений , 2-е изд. ( Амстердам : Elsevier , 2013), стр. 63–65.
4. Коста, Н.Р., и Лоренсо, Ж.А., «Исследование границ Парето в методологии поверхности отклика», в G.-C. Ян, С.-И. Ао и Л. Гельман, ред., «Транзакции по инженерным технологиям: Всемирный инженерный конгресс, 2014 г.» (Берлин/Гейдельберг: Springer, 2015), стр. 399–412.
5. Просто, Ричард Э. (2004). Экономика благосостояния государственной политики: практический подход к оценке проектов и политики. Хют, Даррелл Л., Шмитц, Эндрю. Челтнем, Великобритания: Э. Элгар. стр. 18–21. ISBN 1-84542-157-4. OCLC  58538348.
6. Томойага, Богдан; Чиндрис, Мирча; Сампер, Андреас; Судрия-Андреу, Антони; Виллафафила-Роблес, Роберто (2013). «Оптимальная по Парето реконфигурация систем распределения электроэнергии с использованием генетического алгоритма на основе NSGA-II». Энергии . 6 (3): 1439–55. дои : 10.3390/en6031439 . hdl : 2117/18257 .
7. Нильсен, Франк (1996). «Выходно-чувствительный пилинг выпуклых и максимальных слоев». Письма об обработке информации . 59 (5): 255–9. CiteSeerX 10.1.1.259.1042 . дои : 10.1016/0020-0190(96)00116-0. 
8. Кунг, HT; Люччио, Ф.; Препарата, Ф.П. (1975). «О нахождении максимумов множества векторов». Журнал АКМ . 22 (4): 469–76. дои : 10.1145/321906.321910 . S2CID  2698043.
9. Годфри, П.; Шипли, Р.; Грыз, Дж. (2006). «Алгоритмы и анализ для максимальных векторных вычислений». Журнал ВЛДБ . 16 :5–28. CiteSeerX 10.1.1.73.6344 . дои : 10.1007/s00778-006-0029-7. S2CID  7374749. 
10. Ким, И.Ю.; де Век, OL (2005). «Адаптивный метод взвешенной суммы для многокритериальной оптимизации: новый метод генерации фронта Парето». Структурная и междисциплинарная оптимизация . 31 (2): 105–116. дои : 10.1007/s00158-005-0557-6. ISSN  1615-147X. S2CID  18237050.
11. Марлер, Р. Тимоти; Арора, Джасбир С. (2009). «Метод взвешенной суммы для многокритериальной оптимизации: новые идеи». Структурная и междисциплинарная оптимизация . 41 (6): 853–862. дои : 10.1007/s00158-009-0460-7. ISSN  1615-147X. S2CID  122325484.
12. «О бикритериальной формулировке задач комплексной идентификации систем и оптимизации систем». Транзакции IEEE по системам, человеку и кибернетике . СМК-1 (3): 296–297. 1971. дои : 10.1109/TSMC.1971.4308298. ISSN  0018-9472.
13. Мавротас, Джордж (2009). «Эффективная реализация метода ε-ограничений в задачах многокритериального математического программирования». Прикладная математика и вычислительная техника . 213 (2): 455–465. дои : 10.1016/j.amc.2009.03.037. ISSN  0096-3003.
14. Легриэль, Жюльен; Ле Герник, Колас; Коттон, Скотт; Малер, Одед (2010). Эспарса, Хавьер; Маджумдар, Рупак (ред.). «Аппроксимация фронта Парето задач многокритериальной оптимизации». Инструменты и алгоритмы построения и анализа систем . Конспекты лекций по информатике. Берлин, Гейдельберг: Springer. 6015 : 69–83. дои : 10.1007/978-3-642-12002-2_6 . ISBN 978-3-642-12002-2.
15. Зицлер, Эккарт; Ноулз, Джошуа; Тиле, Лотар (2008), Бранке, Юрген; Деб, Калянмой; Миеттинен, Кайса; Словинский, Роман (ред.), «Оценка качества аппроксимаций множества Парето», Многокритериальная оптимизация: интерактивные и эволюционные подходы , конспекты лекций по информатике, Берлин, Гейдельберг: Springer, стр. 373–404, doi : 10.1007/978-3 -540-88908-3_14, ISBN 978-3-540-88908-3, получено 8 октября 2021 г.