パレートフロント

多目的最適化において、パレートフロント（パレートフロンティアまたはパレート曲線とも呼ばれる）は、すべてのパレート効率的な解の集合である。^{[1]この概念は}工学で広く使用されている。^{[2] : 111–148}これにより、設計者は効率的な選択肢の集合に注意を限定し、すべてのパラメータの全範囲を考慮するのではなく、この集合内でトレードオフを行うことができます。 ^{[3] : 63–65  [4] : 399–412}

パレート境界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^ {\プライム },y^{\プライム }\neq y^{\プライム \プライム }\;\}=\空セット \}.}$

経済学におけるパレート境界の重要な側面は、パレート効率的な配分では、限界代替率がすべての消費者で同じであるということです。^[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] [14]}${\displaystyle \epsilon }$
• 多目的進化アルゴリズム^{[15] [16]}

パレート面全体を生成するのは計算上困難な場合が多いため、近似パレート面を計算するアルゴリズムが存在します。例えば、Legrielら^{[17]は、集合}SとPの間の有向ハウスドルフ距離が最大でもεである場合、集合Sをパレート面Pのε近似と呼びます。彼らは、d次元の任意のパレート面Pのε近似は、(1/ ε ) ^d回のクエリを使用して見つけることができると述べています。

Zitzler、Knowles、Thiele ^[18]は、スケーリング不変性、単調性、計算の複雑さなどのさまざまな基準に基づいて、パレート集合近似のためのいくつかのアルゴリズムを比較しています。