Tunny Icon
TunnyDocs

The next-gen Grasshopper optimization tool.

PROMETHEE

概要

PROMETHEE（Preference Ranking Organisation METHod for Enrichment Evaluations）は、1982 年に J.-P. Brans が提案し、Brans & Vincke (1985) らにより発展した多基準意思決定（MCDM）手法です。 トライアル間のペアワイズ比較に基づいて選好度を計算し、正のフロー（Φ+）と負のフロー（Φ-）からランキングを導出します。

PROMETHEE I は理論上は部分ランキング（Partial Ranking、比較不能なペアを許容）です。 Tunny Dashboard では Φ+ 降順、Φ- 昇順のタイブレークによる全順序で表示しつつ、トライアルごとの比較不能件数（チャートでは ⇹N 表示）もあわせて示します。 PROMETHEE II は完全ランキング（Complete Ranking）を提供します。

Tunny Dashboard では、各トライアルについて次の情報が得られます:

出力 説明
正のフロー Φ+ そのトライアルが他をどれだけ上回るか
負のフロー Φ- そのトライアルが他にどれだけ下回るか
ネットフロー Φnet Φ+ − Φ-（正なら概ね優位、負なら概ね劣位）
PROMETHEE I 順位 Φ+ 降順（同値は Φ- 昇順）に並べたトライアルの順位
PROMETHEE II 順位 Φnet 降順に並べたトライアルの順位

理論背景

基本思想

PROMETHEE はすべてのトライアルペア (a, b) について「a は b よりどの程度好ましいか」を数量化し、それを集約してランキングを作ります。 距離測度（TOPSIS）や妥協指標（VIKOR）ではなく、選好関数を用いたペアワイズ比較が特徴です。

アルゴリズムの概要

m 個のトライアル × n 個の目的関数からなる決定行列を入力とし、以下のステップで計算します:

Step 1: 各目的関数の閾値（p）を自動算出
Step 2: 選好関数 P(d) の計算（Linear 型）
Step 3: 多指標選好度 π(a, b) の集約
Step 4: 正のフロー Φ+ と負のフロー Φ- の計算
Step 5: PROMETHEE I / II ランキングの生成

Step 1: 閾値の自動算出

各目的関数 j について、有効トライアルの値域から閾値を設定します:

rangej=max⁡ifij−min⁡ifij\text{range}j = \max_i f{ij} - \min_i f_{ij}

pj=0.2×rangejp_j = 0.2 \times \text{range}_j

  • q（無差別閾値）：0（わずかな差でも選好に反映）
  • p（厳格選好閾値）：値域の 20%（これを超える差は完全な選好）

Tunny Dashboard は Linear 型のみ対応です。他の選好関数（Usual, U-shape, Level, Gaussian 等）は将来的な拡張候補です。

Step 2: Linear 選好関数

トライアル a と b の目的 j における差分:

  • 最小化目的: dj=fbj−fajd_j = f_{bj} - f_{aj}（a が小さいほど d が正）
  • 最大化目的: dj=faj−fbjd_j = f_{aj} - f_{bj}（a が大きいほど d が正）

Linear 選好関数:

Pj(d)={0d≤0dpj0<d<pj1d≥pjP_j(d) = \begin{cases} 0 & d \leq 0 \ \frac{d}{p_j} & 0 < d < p_j \ 1 & d \geq p_j \end{cases}

  • d≤0d \leq 0: a は b より劣る（選好なし）
  • 0<d<pj0 < d < p_j: 差が閾値未満（部分選好）
  • d≥pjd \geq p_j: 差が閾値以上（完全選好）

Step 3: 多指標選好度

すべての目的関数について重み付き和をとり、a と b の総合選好度を計算します:

π(a,b)=∑j=1nwj⋅Pj(dj(a,b))\pi(a, b) = \sum_{j=1}^{n} w_j \cdot P_j(d_j(a, b)) π(a,b)∈[0,1]\pi(a, b) \in [0, 1]

Tunny Dashboard は VIKOR / TOPSIS と同様に、渡された重みを内部で合計 1 に正規化してから使用します。 これにより、未正規化の重みを渡しても π∈[0,1]\pi \in [0,1]、 Φnet∈[−1,1]\Phi^{\text{net}} \in [-1,1] が保証されます。

  • π(a,b)=0\pi(a, b) = 0: a は b より全目的で劣るか同等
  • π(a,b)=1\pi(a, b) = 1: a は b より全目的で厳格に優位
  • π(a,b)+π(b,a)\pi(a, b) + \pi(b, a) は必ずしも 1 になりません（非対称）

Step 4: フローの計算

各トライアル i について、正のフローと負のフローを計算します:

Φ+(i)=1m−1∑b≠iπ(i,b)\Phi^+(i) = \frac{1}{m-1} \sum_{b \neq i} \pi(i, b)

Φ−(i)=1m−1∑b≠iπ(b,i)\Phi^-(i) = \frac{1}{m-1} \sum_{b \neq i} \pi(b, i)

Φnet(i)=Φ+(i)−Φ−(i)\Phi^{\text{net}}(i) = \Phi^+(i) - \Phi^-(i)

  • Φ+(i): トライアル i が他をどれだけ上回るか（高いほど優秀）
  • Φ-(i): トライアル i が他にどれだけ下回るか（低いほど優秀）
  • Φnet(i): ネットフロー。正なら概ね優位、負なら概ね劣位
  • Φnet(i)∈[−1,1]\Phi^{\text{net}}(i) \in [-1, 1]（すべてのフロー値は [0, 1] に正規化されるため）

Step 5: ランキング

PROMETHEE I（理論上は部分ランキング）

Φ+ の降順でソートします。Φ+ が同値の場合、Φ- の昇順でタイブレークします。

a≻b  ⟺  Φ+(a)>Φ+(b)  or  (Φ+(a)=Φ+(b)  and  Φ−(a)<Φ−(b))a \succ b \iff \Phi^+(a) > \Phi^+(b) ;\text{or}; \bigl(\Phi^+(a) = \Phi^+(b) ;\text{and}; \Phi^-(a) < \Phi^-(b)\bigr)

理論上は以下のケースで比較不能となります:

  • Φ+(a)>Φ+(b)\Phi^+(a) > \Phi^+(b) かつ Φ−(a)>Φ−(b)\Phi^-(a) > \Phi^-(b) → 比較不能（一方が上回る面と下回る面の両方を持ちます）

Tunny Dashboard での扱い: 表示順は上記のタイブレーク規則（Φ+ 降順、Φ- 昇順）による全順序です。 あわせて、各トライアルが何件の有効トライアルと比較不能か（Φ+ と Φ- の両方で厳密に上回るか下回る相手の数）も示します。 チャートではフロー値の隣に ⇹N として表示され、⇹N が 0 のトライアルは他の全トライアルと優劣が定まっています。

PROMETHEE II（完全ランキング）

Φnet の降順でソートします。すべてのトライアルが順位付けされます。

a≻b  ⟺  Φnet(a)>Φnet(b)a \succ b \iff \Phi^{\text{net}}(a) > \Phi^{\text{net}}(b)

TOPSIS / VIKOR との比較

項目 TOPSIS VIKOR PROMETHEE
アプローチ 理想解との距離 ギャップの線形結合 ペアワイズ選好比較
距離測度 ユークリッド（L2） マンハッタン（L1）+ Chebyshev（L∞） 重み付き選好度
ランキング スコア降順（完全） Q 値昇順（完全） I: 部分 / II: 完全
パラメータ なし v（戦略的重み） 閾値 p（自動算出）
計算量 O(m × n + m log m) O(m × n + m log m) O(m² × n + m log m)
スコア範囲 [0, 1] [0, 1] Φnet ∈ [-1, 1]

数値例

問題設定

3 トライアル × 2 目的、両方最小化、重み w=[0.5,0.5]w = [0.5, 0.5]

トライアル 目的1 目的2
0 1 1
1 3 3
2 5 5

Step 1: 閾値

目的1: range = 5 - 1 = 4, p₁ = 0.8 目的2: range = 5 - 1 = 4, p₂ = 0.8

Step 2-3: 選好度行列 π

π(0,1)\pi(0,1): 目的1 は d=3−1=2≥0.8d = 3 - 1 = 2 \geq 0.8 → P=1.0P = 1.0、目的2 も同様 → π=0.5×1.0+0.5×1.0=1.0\pi = 0.5 \times 1.0 + 0.5 \times 1.0 = 1.0 π(0,2)\pi(0,2): 目的1 は d=5−1=4≥0.8d = 5 - 1 = 4 \geq 0.8 → P=1.0P = 1.0、目的2 も同様 → π=1.0\pi = 1.0 π(1,0)\pi(1,0): 目的1 は d=1−3=−2≤0d = 1 - 3 = -2 \leq 0 → P=0P = 0、目的2 も同様 → π=0\pi = 0 π(1,2)\pi(1,2): 目的1 は d=5−3=2≥0.8d = 5 - 3 = 2 \geq 0.8 → P=1.0P = 1.0、目的2 も同様 → π=1.0\pi = 1.0 π(2,0)=0\pi(2,0) = 0, π(2,1)=0\pi(2,1) = 0

π(a,b) b=0 b=1 b=2
a=0 - 1.0 1.0
a=1 0 - 1.0
a=2 0 0 -

Step 4: フロー

Φ+(0)=(1.0+1.0)/2=1.0,Φ−(0)=(0+0)/2=0\Phi^+(0) = (1.0 + 1.0) / 2 = 1.0, \quad \Phi^-(0) = (0 + 0) / 2 = 0

Φ+(1)=(0+1.0)/2=0.5,Φ−(1)=(1.0+0)/2=0.5\Phi^+(1) = (0 + 1.0) / 2 = 0.5, \quad \Phi^-(1) = (1.0 + 0) / 2 = 0.5

Φ+(2)=(0+0)/2=0,Φ−(2)=(1.0+1.0)/2=1.0\Phi^+(2) = (0 + 0) / 2 = 0, \quad \Phi^-(2) = (1.0 + 1.0) / 2 = 1.0

Φnet=[1.0,0.0,−1.0]\Phi^{\text{net}} = [1.0, 0.0, -1.0]

Step 5: ランキング

ランキング 順位
PROMETHEE I 0 → 1 → 2（Φ+ 降順）
PROMETHEE II 0 → 1 → 2（Φnet 降順）

挙動の詳細

NaN / Inf トライアルの扱い

いずれかの目的関数値が非有限（NaN または ±Inf）のトライアルは、有効トライアルから除外され、フローは 0.0、ランキング末尾に配置されます。 すべてのトライアルが非有限値の場合は、全フロー 0.0、ランキングは元の並び順になります。

単一トライアルの場合

m=1m = 1 のときはペアが存在しないため、分母のゼロ除算を防ぐガードが働き、全フローは 0.0 となります。

値域ゼロ（全トライアル同一値）

pj=0p_j = 0 となり選好関数は d>0d > 0 の場合常に 1.0 を返しますが、すべての差分が 0 なので Pj=0P_j = 0 となり、結果として全フロー 0.0 となります。

計算量

ステップ 計算量
閾値算出 O(m × n)
選好度行列 O(m² × n)
フロー計算 O(m²)
ソート O(m log m)
合計 O(m² × n + m log m)

選好度行列の O(m²) がボトルネックです。 1 万トライアル × 4 目的関数でも数十ミリ秒程度ですが、トライアル数が増えると急激に遅くなります。

UI での表示

PROMETHEE I

トライアルごとに 2 本のバーを表示します:

  • Φ+ バー（青系）: 他をどれだけ上回るか
  • Φ- バー（赤系）: 他にどれだけ下回るか

PROMETHEE I のランキング順に並びます。 比較不能な相手がいるトライアルには、フロー値の隣に ⇹N（比較不能件数）が表示されます。

PROMETHEE II

トライアルごとに 1 本の Φnet バーを表示します:

  • 正値（青系）: 概ね優位
  • 負値（アクセント色）: 概ね劣位
  • バーの幅は |Φnet| に比例

PROMETHEE I ↔ II の切替は即座に行われます。 Φ+/Φ-/Φnet は常に同時に計算されるため、切替時の再計算は不要です。

特性・限界

強み:

  • ペアワイズ比較に基づく直感的な解釈ができます（a は b よりどれだけ好ましいか）
  • PROMETHEE I は比較不能なペアを許容する部分ランキングです。Tunny Dashboard は Φ+ 降順、Φ- 昇順のタイブレークによる全順序で表示しつつ、トライアルごとの比較不能件数（⇹N）を明示します
  • PROMETHEE II で完全な順序付けができます
  • 選好関数の種類と閾値で、目的関数ごとの選好の度合いを調整できます

弱み:

  • O(m²) の計算量です。トライアル数が増えると急激に遅くなります（10 万件で数秒）
  • 閾値 p の設定が結果に影響します（Tunny Dashboard では固定で range×0.2）
  • Linear 型のみ対応しています（他の選好関数は将来拡張）
  • Φnet が負値をとり得るため、TOPSIS/VIKOR のような [0, 1] スケールと直接比較できません

使用場面の目安

多目的最適化結果からペアワイズの優劣関係を可視化したい
  ↓
トライアル間の「どちらがどの程度好ましいか」を定量化したい
  ↓
PROMETHEE I / II ランキング

トライアル数が多い（>1万）場合は計算時間に注意。
Entropy 重みと組み合わせることで客観的な重み設定が可能。

参考文献

  • Brans, J.-P. (1982). L'ingénierie de la décision: élaboration d'instruments d'aide à la décision. La méthode PROMETHEE. In R. Nadeau & M. Landry (Eds.), L'aide à la décision: Nature, Instruments et Perspectives d'Avenir (pp. 183–214). Presses de l'Université Laval.
  • Brans, J.-P., & Vincke, P. (1985). A Preference Ranking Organisation Method: The PROMETHEE Method for MCDM. Management Science, 31(6), 647–656. https://doi.org/10.1287/mnsc.31.6.647
  • Brans, J.-P., Vincke, P., & Mareschal, B. (1986). How to select and how to rank projects: The PROMETHEE method. European Journal of Operational Research, 24(2), 228–238. https://doi.org/10.1016/0377-2217(86)90044-5
  • Brans, J.-P., & Mareschal, B. (2005). PROMETHEE methods. In Multiple Criteria Decision Analysis: State of the Art Surveys (pp. 163–186). Springer. https://doi.org/10.1007/0-387-23081-5_5
← 前へ多基準意思決定(MCDM): VIKOR次へ →多基準意思決定(MCDM): エントロピー重み法