インタラクティブな意思決定マップ

多目的最適化のインタラクティブ決定マップ（IDM）手法は、実行可能目的集合のエッジワース・パレートハル（EPH）を近似することに基づいています。EPHとは、実行可能目的集合を、それが支配する目的点によって拡張したものです。あるいは、この集合は自由処分ハルとも呼ばれます。EPHは実行可能目的集合と同じパレートフロンティアを持つことが重要ですが、EPHの2目的スライスははるかに単純です。EPHの2目的スライスの境界には、パレートフロンティアのスライスが含まれます。パレートフロンティア自体とは対照的に、EPHは通常、データの変動に対して安定していることが重要です。IDM手法は、事前に近似されたEPHの2目的スライスを高速にオンラインで表示します。

選択された 2 つの目的に対する EPH の二目的スライスは単調に拡大 (または縮小) し、他の目的 (「3 番目の」目的) の値は単調に変化するため、「3 番目の」目的の値のみが変化する EPH スライスの境界は交差しません。そのため、EPH の二目的スライスを重ね合わせた図は、通常の地形図のように見え、決定マップとも呼ばれます。他の (4 番目の、5 番目のなど) 目的の影響を調べるには、決定マップのアニメーションを使用できます。このようなアニメーションは、EPH を事前に近似することで可能になります。あるいは、アニメーションのさまざまなスナップショットのコレクションを調べることもできます。コンピュータは、3 つから約 8 つの目的に対する線形および非線形決定問題の決定マップの形でパレートフロンティアを視覚化できます。コンピュータネットワークは、たとえば、要求に応じてパレートフロンティアのグラフを表示する Java アプレットを提供できます。 IDM技術の実際の応用例については、^{[ 1 ]に記載されています。}

IDM技術の図解

上の図は、5つの目的を含む実際の水質問題^{[ 1 ]}に関するカラーコンピュータディスプレイのグレースケールコピーを表しています。決定マップは、異なる色で重ね合わされた4つの2目的スライスで構成されています。パレットは、「3番目の」目的の値と色との関係を示しています。2つのスクロールバーは、4番目と5番目の目的の値に関連しています。

スクロールバーを動かすと、意思決定マップが変更されます。スライダーは手動で動かすこともできますが、意思決定者（DM）に情報を表示する最も効果的な方法は、スライダーを自動的に動かすこと、つまり、目標値に課される制約を徐々に増減させることです。意思決定マップを素早く切り替えることで、アニメーションのような効果が得られます。画面上には任意の数のスクロールバーを配置できるため、4番目、5番目（場合によっては6番目、7番目など）の目標が意思決定マップに与える影響を調べることができます。

EPHを近似する

IDM手法では、決定マップを表示する前にEPHを近似する必要があります。EPHを近似する方法は、EPHの凸性特性に依存します。近似方法は通常、凸多面体集合によるEPHの近似、またはパレートフロンティアに近い頂点を持つ目的空間内の多数だが有限個の支配錐によるEPHの近似に基づいています。最初の形式は凸問題にのみ適用できますが、2番目の形式は普遍的であり、一般的な非線形問題に使用できます。^{[ 1 ]}

凸型EPHの場合の近似と可視化

多面体集合によって近似される EPH は、近似手法によって構築されなければならない有限個の線形不等式のシステムによって記述されます。凸体の最適な多面体近似の数学理論は最近開発され、その結果は EPH を近似するための効果的な方法の開発に適用できます。 ^{[ 1 ]}このような近似の多数の二目的スライスは、数秒で計算され、決定マップの形式で表示されます。

パレートフロンティアの点ごとの近似とその可視化

多数だが有限個の支配錐による EPH 近似は、パレートフロンティアの任意の点ごとの近似に基づいて構築できます。これは、古典的な単目的最適化手法^{[ 2 ]}^{[ 3 ]から最新の進化的手法}^{[ 4 ]}まで幅広い手法を使用して見つけることができます。古典的な手法と進化的手法の組み合わせに基づく EPH 近似のためのハイブリッド手法も使用できます。^{[ 5 ]}このような近似の二目的スライスも非常に高速に計算できます。これらの手法を適用すると、近似点の数が十分に大きい場合、かなり理解しやすい決定マップが得られます。

希望する決定を検索する

IDM手法では、最適な意思決定の探索は、パレート最適解（実現可能な目標）となる目標点を特定することに基づいています。意思決定マップは、ユーザーがコンピュータ画面に描画されたトレードオフ曲線上で目標を直接特定するのに役立ちます。その後、目標に関連付けられたパレート最適解が自動的に見つかります。パレートフロンティアの可視化問題に関する詳細な議論は、論文「Visualizing the Pareto Frontier」（Lotov and Miettinen、2008）に記載されています。

参考文献

1 2 3 4 A. V. Lotov; VA Bushenkov; GK Kamenev (2004年2月29日). Interactive Decision Maps: Approximation and Visualization of Pareto Frontier . Springer. ISBN 978-1-4020-7631-22012年5月29日取得。
↑カイサ・ミエッティネン (1999)。非線形多目的最適化。スプリンガー。ISBN 978-0-7923-8278-22012年5月29日取得。
↑ Jürgen Branke; Kalyanmoy Deb; Kaisa Miettinen; Roman Slowinski (2008年11月21日).多目的最適化：対話型および進化型アプローチ. Springer. ISBN 978-3-540-88907-62012年11月1日に取得。
↑ Kalyanmoy Deb (2009年3月23日).進化アルゴリズムを用いた多目的最適化. John Wiley & Sons. ISBN 978-0-470-74361-42012年11月1日に取得。
↑ Berezkin, VE; Kamenev, GK; Lotov, AV (2006). "非凸多次元パレートフロンティアを近似するためのハイブリッド適応法". Computational Mathematics and Mathematical Physics . 46 (11): 1918. Bibcode : 2006CMMPh..46.1918B . doi : 10.1134/S096554250611008X . S2CID 121051510 .

[LotovBushenkov2004-1] 1 2 3 4 A. V. Lotov; VA Bushenkov; GK Kamenev (2004年2月29日). Interactive Decision Maps: Approximation and Visualization of Pareto Frontier . Springer. ISBN 978-1-4020-7631-22012年5月29日取得。

[Miettinen1999-2] カイサ・ミエッティネン (1999)。非線形多目的最適化。スプリンガー。ISBN 978-0-7923-8278-22012年5月29日取得。

[BrankeDeb2008-3] Jürgen Branke; Kalyanmoy Deb; Kaisa Miettinen; Roman Slowinski (2008年11月21日).多目的最適化：対話型および進化型アプローチ. Springer. ISBN 978-3-540-88907-62012年11月1日に取得。

[Deb2009-4] Kalyanmoy Deb (2009年3月23日).進化アルゴリズムを用いた多目的最適化. John Wiley & Sons. ISBN 978-0-470-74361-42012年11月1日に取得。

[BerezkinKamenev2006-5] Berezkin, VE; Kamenev, GK; Lotov, AV (2006). "非凸多次元パレートフロンティアを近似するためのハイブリッド適応法". Computational Mathematics and Mathematical Physics . 46 (11): 1918. Bibcode : 2006CMMPh..46.1918B . doi : 10.1134/S096554250611008X . S2CID 121051510 .

[ 1 ]に記載されています。

[ 2 ]

[ 3 ]から最新の進化的手法

[ 4 ]

[ 5 ]