HN 日本語サマリー

← 一覧へ戻る
科学・技術

パレートフロント

Pareto Front (en.wikipedia.org)

239 pointsby binyu97 コメント

要約

パレートフロント(またはパレートフロンティア、パレート曲線)は、多目的最適化問題における全てのパレート効率的解の集合を指します。これは、ある解が他の解よりも全ての目的において優れているわけではなく、かつ、セットに含まれない全ての解は、パレートフロント内の少なくとも1つの解によって全ての目的において上回られるような解の集合を表します。工学分野で広く利用され、設計者が全てのパラメータの全範囲を考慮する代わりに、効率的な選択肢の集合に絞り込み、その中でのトレードオフを行うことを可能にします。

全文翻訳

パレートフロンティア

ウィキペディア、フリー百科事典より

(パレートフロントから転送)

多目的最適化において、パレートフロンティア(Pareto frontier、またはパレートフロント、パレート集合、パレート境界、パレート曲線とも呼ばれる)は、すべてのパレート効率的な解の集合です。非公式には、最適化問題に考慮すべき多くの異なる目的がある場合、パレートフロントは、目的間のトレードオフにより、ある解がある他の解をある点で上回ることはないが、他の解に劣ることもない解の集合を表し、残りの劣る解を除外します。つまり、フロンティアは、ある点でより良くすることなしに別の点で悪くすることなしに、より良い選択をすることが不可能な選択の集合です。

上回ることは「パレート優位」と呼ばれます。解Aが解Bを(より良く)上回るとは、Aがすべての目的においてBより悪くなく、かつ少なくとも1つの目的においてBより良い場合です。この概念は工学で広く使用されています。これにより、設計者は効率的な選択肢の集合に注意を限定し、すべてのパラメータの全範囲を考慮するのではなく、この集合内でのトレードオフを行うことができます。

[画像: Front_pareto.svg]

パレートフロンティアの例。箱で囲まれた点は実現可能な選択肢を表し、小さい値が好ましいとします。点Cは、点Aと点Bの両方に劣るため、パレートフロンティア上にありません。点Aと点Bは他の点に厳密には劣らないため、フロンティア上にあります。

[画像: Pareto_Efficient_Frontier_1024x1024.png]

生産可能性フロンティアの例。赤い線はパレート効率的フロンティアの一例であり、フロンティアとその左下領域は連続した選択肢の集合です。フロンティア上の赤い点は、生産のパレート最適選択肢の例です。NやKのようなフロンティアから外れた点はパレート効率的ではありません。なぜなら、それらをパレート優位するフロンティア上の点が存在するからです。

定義

パレートフロンティア、P(Y) は、より形式的に次のように記述できます。関数[画像: {\displaystyle f:X\rightarrow \mathbb {R} ^{m}}]を持つシステムを考えます。ここで、X はコンパクト集合であり、距離空間[画像: {\displaystyle \mathbb {R} ^{n}}]における実現可能な決定の集合です。Y は[画像: {\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 }.}]

代替率

経済学におけるパレートフロンティアの重要な側面は、パレート効率的な配分において、すべての消費者の代替率が同じであることです。m 人の消費者と n 個の商品、および各消費者の効用関数が[画像: {\displaystyle z_{i}=f^{i}(x^{i})}]で表されるシステムを考えることで、形式的な記述を導き出すことができます。ここで、[画像: {\displaystyle x^{i}=(x_{1}^{i},x_{2}^{i},\ldots ,x_{n}^{i})}]は商品のベクトルであり、すべての i について同様です。実現可能性制約は、[画像: {\displaystyle j=1,\ldots ,n}]について[画像: {\displaystyle \sum {i=1}^{m}x{j}^{i}=b_{j}}]です。パレート最適配分を見つけるために、ラグランジュ乗数法を用いて最大化します。

[画像: {\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\quad \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\quad \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}}}.}]

したがって、パレート最適配分では、代替率はすべての消費者で同じでなければなりません。

計算

コンピュータサイエンスおよび電力工学では、有限集合の代替物のパレートフロンティアを計算するためのアルゴリズムが研究されています。これらには以下が含まれます。

  • 「点の集合の最大値」
  • 「最大ベクトル問題」またはスカイラインクエリ
  • 「スカラー化アルゴリズム」または重み付き和法
  • 「[画像: {\displaystyle \epsilon }]-制約法」
  • 多目的進化的アルゴリズム

近似

パレートフロント全体の生成は計算コストが高いことが多いため、パレートフロントの近似を計算するアルゴリズムが存在します。例えば、Legrielらは、集合SがパレートフロントPの「ε-近似」であると呼びます。これは、SとPの間の有向ハウスドルフ距離がε以下である場合です。彼らは、d次元の任意のパレートフロントPのε-近似は(1/ε)d回のクエリで求められることを観察しています。

Zitzler、Knowles、Thieleは、スケーリングへの不変性、単調性、計算複雑性などの様々な基準でパレート集合近似のアルゴリズムを比較しています。

2000年代初頭から、いくつかの進化的アルゴリズムがパレートフロント近似の標準的なツールとなっています。非劣ソート遺伝的アルゴリズムII(NSGA‑II)は、エリート主義とクラウディング距離メカニズムを導入して多様性を維持し、最も広く引用されているMOEAの1つとなりました。その拡張であるNSGA‑IIIは、4つ以上の目的を持つ問題に対処するために、クラウディング距離を基準点ベースの選択に置き換えています。もう1つの影響力のあるアプローチはMOEA/D(分解に基づく多目的進化的アルゴリズム)であり、これは多目的問題を多数のスカラー部分問題に分解し、それらを同時に最適化します。

より最近の開発には、キャリブレーション変数を持つ遺伝的アルゴリズム(GA‑PC)があります。GA‑PCは、目的関数に影響を与えない補助的なキャリブレーション変数を導入することでNSGA‑IIフレームワークを変更しますが、アルゴリズムが局所最適解から脱出し、探索空間の対称性を破るのに役立ちます。これは、競合する基準(例:レイテンシ、エネルギー消費、負荷分散)を持つ制約付きリソース割り当て問題に適用されており、同様の問題インスタンスで標準的なアルゴリズムと比較して、より多くの実現可能なパレート最適解を生成することが示されています。

参考文献

  1. ↑ proximedia. "Pareto Front". www.cenaero.be. Archived from the original on 2020-02-26. Retrieved 2018-10-08.
  2. ↑ Kang, Shida; Li, Kaiwen; Wang, Rui (2025-06-01). "A survey on pareto front learning for multi-objective optimization". Journal of Membrane Computing. 7 (2): 128–134. doi:10.1007/s41965-024-00170-z. ISSN 2523-8914.
  3. ↑ Goodarzi, E., Ziaei, M., & Hosseinipour, E. Z., Introduction to Optimization Analysis in Hydrosystem Engineering (Berlin/Heidelberg: Springer, 2014), pp. 111–148.
  4. ↑ Jahan, A., Edwards, K. L., & Bahraminasab, M., Multi-criteria Decision Analysis, 2nd ed. (Amsterdam: Elsevier, 2013), pp. 63–65.
  5. ↑ Costa, N. R., & Lourenço, J. A., "Exploring Pareto Frontiers in the Response Surface Methodology", in G.-C. Yang, S.-I. Ao, & L. Gelman, eds., Transactions on Engineering Technologies: World Congress on Engineering 2014 (Berlin/Heidelberg: Springer, 2015), pp. 399–412.
  6. ↑ Just, Richard E. (2004). The welfare economics of public policy: a practical approach to project and policy evaluation. Hueth, Darrell L., Schmitz, Andrew. Cheltenham, UK: E. Elgar. pp. 18–21. ISBN 1-84542-157-4. OCLC 58538348.
  7. ↑ Just, Richard E.; Hueth, Darrell L.; Schmitz, Andrew (2005-01-01). The Welfare Economics of Public Policy: A Practical Approach to Project and Policy Evaluation. Edward Elgar Publishing. ISBN 978-1-84542-157-1.
  8. ↑ Tomoiagă, Bogdan; Chindriş, Mircea; Sumper, Andreas; Sudria-Andreu, Antoni; Villafafila-Robles, Roberto (2013). "Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II". Energies. 6 (3): 1439–55. doi:10.3390%2Fen6031439. hdl:2117/18257.
  9. ↑ Nielsen, Frank (1996). "Output-sensitive peeling of convex and maximal layers". Information Processing Letters. 59 (5): 255–9. doi:10.1016/0020-0190(96)00116-0.
  10. ↑ Kung, H. T.; Luccio, F.; Preparata, F.P. (1975). "On finding the maxima of a set of vectors". Journal of the ACM. 22 (4): 469–76. doi:10.1145/321906.321910. S2CID 2698043.
  11. ↑ Godfrey, P.; Shipley, R.; Gryz, J. (2006). "Algorithms and Analyses for Maximal Vector Computation". VLDB Journal. 16: 5–28. doi:10.1007/s00778-006-0029-7. S2CID 7374749.
  12. ↑ Kim, I. Y.; de Weck, O. L. (2005). "Adaptive weighted sum method for multiobjective optimization: a new method for Pareto front generation". Structural and Multidisciplinary Optimization. 31 (2): 105–116. doi:10.1007/s00158-005-0557-6. ISSN 1615-147X. S2CID 18237050.
  13. ↑ Marler, R. Timothy; Arora, Jasbir S. (2009). "The weighted sum method for multi-objective optimization: new insights". Structural and Multidisciplinary Optimization. 41 (6): 853–862. doi:10.1007/s00158-009-0460-7. ISSN 1615-147X. S2CID 122325484.
  14. ↑ "On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization". IEEE Transactions on Systems, Man, and Cybernetics. SMC-1 (3): 296–297. 1971. doi:10.1109/TSMC.1971.4308298. ISSN 0018-9472.
  15. ↑ Mavrotas, George (2009). "Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems". Applied Mathematics and Computation. 213 (2): 455–465. doi:10.1016/j.amc.2009.03.037. ISSN 0096-3003.
  16. ↑ Carvalho, Iago A.; Coco, Amadeu A. (September 2023). "On solving bi-objective constrained minimum spanning tree problems". Journal of Global Optimization. 87 (1): 301–323. doi:10.1007/s10898-023-01295-8.
  17. ↑ Zhang, Qingfu; Hui, Li (December 2007). "MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition". IEEE Transactions on Evolutionary Computation. 11 (6): 712–731. doi:10.1109/TEVC.2007.892759.
  18. ↑ Carvalho, Iago A.; Ribeiro, Marco A. (November 2019). "A node-depth phylogenetic-based artificial immune system for multi-objective Network Design Problems". Swarm and Evolutionary Computation. 50 100491. doi:10.1016/j.swevo.2019.01.007.
  19. ↑ Legriel, Julien; Le Guernic, Colas; Cotton, Scott; Maler, Oded (2010). "Approximating the Pareto Front of Multi-criteria Optimization Problems". In Esparza, Javier; Majumdar, Rupak (eds.). Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science. Vol. 6015. Berlin, Heidelberg: Springer. pp. 69–83. doi:10.1007/978-3-642-12002-2_6. ISBN 978-3-642-12002-2.
  20. ↑ Zitzler, Eckart; Knowles, Joshua; Thiele, Lothar (2008), "Quality Assessment of Pareto Set Approximations", in Branke, Jürgen; Deb, Kalyanmoy; Miettinen, Kaisa; Słowiński, Roman (eds.), Multiobjective Optimization: Interactive and Evolutionary Approaches, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, pp. 373–404, doi:10.1007/978-3-540-88908-3_14, ISBN 978-3-540-88908-3.
  21. ↑ Deb, K.; Agrawal, S.; Pratap, A.; Meyarivan, T. (2002). "A fast and elitist multiobjective genetic algorithm: NSGA‑II". IEEE Transactions on Evolutionary Computation. 6 (2): 182–197. doi:10.1109/4235.996017.
  22. ↑ Deb, K.; Jain, H. (2014). "An Evolutionary Many‑Objective Optimization Algorithm Using Reference‑Point‑Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints". IEEE Transactions on Evolutionary Computation. 18 (4): 577–601. doi:10.1109/TEVC.2013.2281535.
  23. ↑ Zhang, Q.; Li, H. (2007). "MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition". IEEE Transactions on Evolutionary Computation. 11 (6): 712–731. doi:10.1109/TEVC.2007.892759.
  24. ↑ Nikulchev, E. (2026). "Genetic Algorithm with Calibration Variables for Pareto Front Approximation in Prediction Intervals". Mathematics. 14 (15): 2686. doi:10.3390/math14152686.