(57)【要約】【課題】ニーポイントを適切に検出すること。【解決手段】検出装置１００は、Ｎ個（Ｎは自然数）の目的関数を用いた最適化問題についての複数の非劣解の入力を受け付ける。検出装置１００は、複数の非劣解それぞれについて、Ｎ個の目的関数を座標軸とするＮ次元空間上に設定される特定の方向に基づき高さ情報を付与する。検出装置１００は、複数の非劣解から、高さ情報の極小点に対応した第１の非劣解群を特定する。ここで、特定の方向は、Ｎ次元空間上において、Ｎ個の目的関数の値がいずれも大きくなる方向である。【選択図】図１
2018037032.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
Ｎ個（Ｎは自然数）の目的関数を用いた最適化問題についての複数の非劣解の入力を受け付け、
前記複数の非劣解それぞれについて、前記Ｎ個の目的関数を座標軸とするＮ次元空間上に設定される特定の方向に基づき高さ情報を付与し、
前記複数の非劣解から、前記高さ情報の極小点に対応した第１の非劣解群を特定する
処理を実行させることを特徴とする特定プログラムであって、
前記特定の方向は、前記Ｎ次元空間上において、前記Ｎ個の目的関数の値がいずれも大きくなる方向である、
ことを特徴とする特定プログラム。
【請求項２】
前記Ｎ個の非劣解を前記Ｎ次元空間上の位置に応じて複数のクラスタに分類する処理を更に実行し、前記特定する処理は、前記第１の非劣解群を含むクラスタを特定することを特徴とする請求項１に記載の特定プログラム。
【請求項３】
前記複数のクラスタの高さ情報を基にして、異なる高さに位置し、隣接するクラスタを辺で接続した無向グラフを生成し、クラスタに属する非劣解の高さ情報を基にして、高さの低い側から高い側へ辺に向きを持たせることで、前記無向グラフを有向グラフに変換する処理を更に実行し、前記特定する処理は、前記有向グラフを基にして、前記第１の非劣解群を含むクラスタを特定することを特徴とする請求項２に記載の特定プログラム。
【請求項４】
前記特定する処理は、着目するクラスタに向かう辺がなく、着目するクラスタから他のクラスタに向かう辺が存在する場合に、前記着目するクラスタを特定することを特徴とする請求項３に記載の特定プログラム。
【請求項５】
前記特定する処理は、他の着目するクラスタに向かう辺が１つであり、前記他の着目するクラスタから他のクラスタに向かう辺がなく、前記他の着目するクラスタと前記着目するクラスタの両方に属する非劣解が存在する場合に、前記両方のクラスタに属する非劣解を特定することを抑止することを特徴とする請求項４に記載の特定プログラム。
【請求項６】
コンピュータが実行する特定方法であって、
Ｎ個（Ｎは自然数）の目的関数を用いた最適化問題についての複数の非劣解の入力を受け付け、
前記複数の非劣解それぞれについて、前記Ｎ個の目的関数を座標軸とするＮ次元空間上に設定される特定の方向に基づき高さ情報を付与し、
前記複数の非劣解から、前記高さ情報の極小点に対応した第１の非劣解群を特定する
処理を実行、
前記特定の方向は、前記Ｎ次元空間上において、前記Ｎ個の目的関数の値がいずれも大きくなる方向である、
ことを特徴とする特定方法。
【請求項７】
Ｎ個（Ｎは自然数）の目的関数を用いた最適化問題についての複数の非劣解の入力を受け付け、前記複数の非劣解それぞれについて、前記Ｎ個の目的関数を座標軸とするＮ次元空間上に設定される特定の方向に基づき高さ情報を付与し、前記複数の非劣解から、前記高さ情報の極小点に対応した第１の非劣解群を特定する検出部を有する特定装置であって、
前記特定の方向は、前記Ｎ次元空間上において、前記Ｎ個の目的関数の値がいずれも大きくなる方向である、
ことを特徴とする特定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特定プログラム等に関する。
【背景技術】
【０００２】
多目的最適化問題では、各目的関数がトレードオフの関係にあり、最適解は一つに決まらないため、各目的関数の非劣解集合を求める。非劣解集合は、優劣のつけられない非劣解の集合のことで、目的関数値のいずれかを改善しようとした場合に、他の目的関数値が改悪されるような状態と言える。非劣解集合が形成する面は、パレートフロントと呼ばれる。
【０００３】
図１２は、パレートフロントの一例を示す図である。図１２において、横軸は目的関数ｆ１の目的関数値に対応する軸であり、左側に向かうほど、目的関数ｆ１に関する目的関数値がより良いものとなる。縦軸は目的関数ｆ２の目的関数値に対応する軸であり、下側に向かうほど、目的関数ｆ２に関する目的関数値がより良いものとなる。
【０００４】
意志決定者は、パレートフロントに含まれる非劣集合の中から最終的な非劣解を一つ選ぶこととなる。好ましい非劣解は、トレードオフ比のバランスがよいニーポイントＰとなる。なお、ニーポイントＰの周辺では、目的関数ｆ１を少し改善すると目的関数ｆ２が大きく改悪され、目的関数ｆ２を改善すると目的関数ｆ１が大きく改悪されるという特徴がある。
【０００５】
例えば、パレートフロントのニーポイントを検出する従来技術として、法線境界交差法を用いるものがある。この従来技術では、パレートフロントの端点Ａ，Ｂを結んだ境界線Ｃから優越法線方向に最も遠い点をニーポイントとして検出する。図１２に示す例では、Ｐがニーポイントとして検出される。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】I.  Das.  On  characterizing  the  “knee”  of  the  Pareto  curve  based  on  normal-boundary  intersection.  Structural  Optimization,  18(2):107-115,  1999.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した従来技術では、ニーポイントを適切に検出できないという問題がある。
【０００８】
図１３および図１４は、従来技術の問題を説明するための図である。図１３に示すように、パレートフロントに複数の凹凸があり、パレートフロントが境界線Ｃから優越法線方向に存在していない場合には、ニーポイントとして非劣解Ｐ１，Ｐ２が検出され、一部のニーポイントＰ３，Ｐ４が検出されない。
【０００９】
図１４に示すように、非劣解の近似精度にばらつきがあると、ニーポイントの位置を誤る場合がある。図１４に示す例では、非劣解１ａ〜１ｉが存在し、実際のニーポイントの位置をＰとする。この場合には、ニーポイントＰに最も近い非劣解１ｅをニーポイントとして検出することが望ましいが、従来技術では、境界線Ｃから優越法線方向に最も遠い点１ｆをニーポイントとして検出してしまう。
【００１０】
１つの側面では、本発明は、ニーポイントを適切に検出することができる特定プログラム、特定方法および特定装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
第１の案では、コンピュータに下記の処理を実行させる。コンピュータは、Ｎ個（Ｎは自然数）の目的関数を用いた最適化問題についての複数の非劣解を入力する。コンピュータは、複数の非劣解それぞれについて、Ｎ個の目的関数を座標軸とするＮ次元空間上に設定される特定の方向に基づき高さ情報を付与する。コンピュータは、複数の非劣解から、高さ情報の極小点に対応した第１の非劣解群を特定する。ここで、特定の方向は、Ｎ次元空間上において、Ｎ個の目的関数の値がいずれも大きくなる方向である。
【発明の効果】
【００１２】
ニーポイントを適切に検出することができる。
【図面の簡単な説明】
【００１３】
【図１】図１は、本実施例に係る検出装置の構成を示す機能ブロック図である。
【図２】図２は、非劣解集合情報のデータ構造の一例を示す図である。
【図３】図３は、重み情報のデータ構造の一例を示す図である。
【図４】図４は、無向グラフ情報のデータ構造の一例を示す図である。
【図５】図５は、有向グラフ情報のデータ構造の一例を示す図である。
【図６】図６は、正規化部の処理を説明するための図である。
【図７】図７は、距離行列のデータ構造の一例を示す図である。
【図８】図８は、検出部がニーポイントを検出する処理を説明するための図（１）である。
【図９】図９は、検出部がニーポイントを検出する処理を説明するための図（２）である。
【図１０】図１０は、本実施例に係る検出装置の処理手順を示すフローチャートである。
【図１１】図１１は、検出装置と同様の機能を実現するコンピュータのハードウェア構成の一例を示す図である。
【図１２】図１２は、パレートフロントの一例を示す図である。
【図１３】図１３は、従来技術の問題を説明するための図（１）である。
【図１４】図１４は、従来技術の問題を説明するための図（２）である。
【発明を実施するための形態】
【００１４】
以下に、本願の開示する特定プログラム、特定方法および特定装置の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００１５】
図１は、本実施例に係る検出装置の構成を示す機能ブロック図である。図１に示すように、この検出装置１００は、通信部１１０と、入力部１２０と、表示部１３０と、記憶部１４０と、制御部１５０とを有する。検出装置１００は、特定装置の一例である。
【００１６】
通信部１１０は、ネットワークを介して図示しない外部装置に接続し、外部装置とデータ通信を実行する処理部である。通信部１１０は、ＮＩＣ（Network  Interface  Card）等の通信装置に対応する。
【００１７】
入力部１２０は、各種の情報を検出装置１００に入力するための入力装置である。入力部１２０は、キーボードやマウス、タッチパネル等に対応する。例えば、利用者は、入力部１２０を操作して、後述する非劣解集合情報１４１、重み情報１４２、Mapperパラメータ１４３等を入力する。
【００１８】
表示部１３０は、制御部１５０から出力される情報を表示する表示装置である。表示部１３０は、液晶ディスプレイやタッチパネル等に対応する。
【００１９】
記憶部１４０は、非劣解集合情報１４１、重み情報１４２、Mapperパラメータ１４３、無向グラフ情報１４４、有向グラフ情報１４５を有する。記憶部１４０は、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）、フラッシュメモリ（Flash  Memory）などの半導体メモリ素子や、ＨＤＤ（Hard  Disk  Drive）などの記憶装置に対応する。
【００２０】
非劣解集合情報１４１は、多目的最適化問題における、複数の目的関数に対する非劣解の情報である。
【００２１】
図２は、非劣解集合情報のデータ構造の一例を示す図である。たとえば、Ｎ個の目的関数に対する非劣解は、図２に示すように、Ｎ次元空間上の解として示され、非劣解集合情報１４１は、非劣解ＩＤと、ｆ１、ｆ２、ｆ３とを対応付ける。非劣解ＩＤは、非劣解を一意に識別する情報である。ｆ１、ｆ２、ｆ３は、各目的関数ｆ１、ｆ２、ｆ３に対応する目的関数値である。例えば、非劣解ＩＤ「１」に対応する非劣解は、「ｆ１＝１．４、ｆ２＝−２．４、ｆ３＝７．７」となる。図２に示す例では、ｆ１〜ｆ３を示すが、非劣解集合情報１４１は、他の目的関数値を含んでいても良い。
【００２２】
重み情報１４２は、各目的関数値に与える重みの情報である。利用者が重要だと考える目的関数値ほど、大きな重みが与えられる。
【００２３】
図３は、重み情報のデータ構造の一例を示す図である。図３に示すように、重み情報１４２は、重み種別と、重みとを対応付ける。重み種別は、重みを識別する情報である。重みは、目的関数値に与える重みである。例えば、ｗ１は、目的関数ｆ１の目的関数値に与える重みであり、値は「１」となる。ｗ２は、目的関数ｆ２の目的関数値に与える重みであり、値は「２」となる。ｗ３は、目的関数ｆ３の目的関数値に与える重みであり、値は「−１」となる。
【００２４】
Mapperパラメータ１４３は、Mapperに基づいて非劣解をクラスタリングする場合に利用するパラメータの情報を含む。例えば、Mapperパラメータ１４３には、Mapperの区間数、Mapperの区間のオーバーラップ率、Mapperのクラスタリングにおけるビン数を含む。
【００２５】
無向グラフ情報１４４は、Mapperに基づいてクラスタリングされたクラスタを、オーバーラップするクラスタ同士、辺で接続した情報である。ここで、２つのクラスタがオーバーラップするとは、非劣解集合の中に、２つのクラスタの両方に属する非劣解があることをいう。
【００２６】
図４は、無向グラフ情報のデータ構造の一例を示す図である。図４に示す例では、無向グラフ情報１４４は、各クラスタに高さ情報が付与され、オーバーラップするクラスタ同士が、辺で接続されている。各クラスタの高さ情報は、Mapperに基づいてクラスタリングされる非劣解それぞれの高さ情報に基づき付与される。
【００２７】
すなわち、多次元空間上に配置された非劣解に対しては、多次元空間上の被優越方向に位置する非劣解ほど値の大きくなる高さ情報が付与され、各クラスタｃ１〜ｃ７には、クラスタを構成する非劣解の高さ情報に基づき、高さ情報が付与される。例えば、多次元空間上に存在するクラスタについて、被優越方向に位置するクラスタほど、高さ情報の値が大きくなる。図４に示す例では、クラスタｃ１，ｃ２，ｃ３，ｃ４，ｃ５，ｃ６，ｃ７には、高さ情報１，３，２，１，２，３，２が付与されている。
【００２８】
また、クラスタｃ２とクラスタｃ３とが辺ｈ１で接続される。クラスタｃ３とクラスタｃ４とが辺ｈ２で接続される。クラスタｃ４とクラスタｃ５とが辺ｈ３で接続される。クラスタｃ５とクラスタｃ６とが辺ｈ４で接続される。クラスタｃ６とクラスタｃ７とが辺ｈ５で接続される。
【００２９】
有向グラフ情報１４５は、図４で説明した無向グラフ情報１４４に示した各辺に向きの情報を持たせた情報である。例えば、第１のクラスタと第２のクラスタとを接続する辺の向きは、第１のクラスタの高さ情報が、第２のクラスタの高さ情報よりも大きい場合に、第２のクラスタから第１のクラスタに向かう方向となる。第１のクラスタと第２のクラスタとを接続する辺の向きは、第２のクラスタの高さ情報が、第１のクラスタの高さ情報よりも大きい場合に、第１のクラスタから第２のクラスタに向かう方向となる。
【００３０】
図５は、有向グラフ情報のデータ構造の一例を示す図である。図５に示すように、図４で説明した情報に加えて、各辺ｈ１〜ｈ５に向きの情報が付与されている。辺ｈ２は、クラスタｃ４からクラスタｃ３に向かう有向辺である。辺ｈ１は、クラスタｃ３からクラスタｃ２に向かう有向辺である。辺ｈ３は、クラスタｃ４からクラスタｃ５に向かう有向辺である。辺ｈ４は、クラスタｃ５からクラスタｃ６に向かう有向辺である。辺ｈ５は、クラスタｃ７からクラスタｃ６に向かう有向辺である。
【００３１】
図１の説明に戻る。制御部１５０は、受付部１５１と、正規化部１５２と、検出部１５３と、出力部１５４とを有する。制御部１５０は、ＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などによって実現できる。また、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などのハードワイヤードロジックによっても実現できる。
【００３２】
受付部１５１は、通信部１１０または入力部１２０から、各種の情報を受け付け、受け付けた情報を、記憶部１４０に格納する処理部である。例えば、受付部１５１は、非劣解集合情報１４１、重み情報１４２、Mapperパラメータ１４３を受け付け、記憶部１４０に格納する。
【００３３】
正規化部１５２は、非劣解集合情報１４１を正規化する処理部である。以下の説明では、正規化された非劣解集合情報１４１を、正規化情報と適宜表記する。図６は、正規化部の処理を説明するための図である。
【００３４】
正規化部１５２は、非劣解集合情報１４１を読み出し、各列の値から、最大値と最小値を検索する。例えば、ｆ１の列において、最大値は「４．４」、最小値は「１．４」となる。ｆ２の列において、最大値は「２．６」、最小値は「−２．４」となる。ｆ３の列において、最大値は「１２．６」、最小値は「５．６」となる。
【００３５】
正規化部１５２は、非劣解集合情報１４１の各列の値から最小値を引き、（最大値−最小値）で割る処理をそれぞれ実行することで、各目的関数値を更新し、中間データ１４１ａを生成する。
【００３６】
例えば、非劣解集合情報１４１の非劣解ＩＤ「１」の目的関数値ｆ１「１．４」を更新する場合について説明すると、（１．４−１．４）／（４．４−１．４）＝０となる。このため、中間データ１４１ａの非劣解ＩＤ「１」の目的関数ｆ１は「０」となる。非劣解集合情報１４１の非劣解ＩＤ「２」の目的関数ｆ１「２．６」を更新する場合について説明すると、（２．６−１．４）／（４．４−１．４）＝０．４となる。このため、中間データ１４１ａの非劣解ＩＤ「２」の目的関数ｆ１は「０．４」となる。正規化部１５２は、他の目的関数値も同様にして更新する。
【００３７】
正規化部１５２は、中間データ１４１ａの値に、目的関数の種別に応じた値を乗算することで、各値を更新し、正規化情報１４１ｂを生成する。例えば、正規化部１５２は、図３に示した重み情報１４２を用いて、目的関数ｆ１の目的関数値にｗ１を乗算し、目的関数ｆ２の目的関数値にｗ２を乗算し、目的関数ｆ３の目的関数値にｗ３を乗算する。
【００３８】
このため、正規化部１５２は、中間データ１４１ａのｆ１の値にｗ１「１」をそれぞれ乗算し、ｆ２の値にｗ２「２」をそれぞれ乗算し、ｆ３の値にｗ３「−１」をそれぞれ乗算する。正規化部１５２が係る処理を実行することで、中間データ１４１ａから正規化情報１４１ｂが生成される。正規化部１５２は、正規化情報１４１ｂを検出部１５３に出力する。
【００３９】
検出部１５３は、前述したように、多次元空間上に配置された非劣解に対して、多次元空間上の被優越方向に位置する非劣解ほど値の大きくなる高さ情報を付与し、高さ情報を付与した各非劣解から、極小点となる非劣解をニーポイントとして検出する処理部である。以下において、検出部１５３の処理の一例について説明する。
【００４０】
検出部１５３は、正規化情報１４１ｂを基にして、距離行列を計算する。図７は、距離行列のデータ構造の一例を示す図である。例えば、検出部１５３は、第１の非劣解（ｐ１，ｐ２，ｐ３）と、第２の非劣解（ｑ１，ｑ２，ｑ３）との距離ｄ（ユークリッド距離）を、式（１）に基づいて算出する。式（１）のｎは、目的関数値の次元に対応する。
【００４１】
【数１】
2018037032.tif 000003
【００４２】
検出部１５３は、正規化情報１４１ｂを基にして、各非劣解ＩＤの行方向の和を算出する。この行方向の和は、該当する非劣解の高さに対応する情報となる。また、検出部１５３は、非劣解集合を高さに沿って複数の区間に分割する。
【００４３】
検出部１５３は、距離行列を基にして、距離の近い非劣解を同一のクラスタに分類するクラスタリングを、同一の高さに属する非劣解毎に実行する。例えば、検出部１５３は、Mapperパラメータ１４３を基にして、Mapperによるクラスタリングを実行することで、各非劣解をクラスタに分類する。例えば、検出部１５３は、Mapperによるクラスタリングとして「G.Singh,  F.Memoli,  and  G.Carlsson.  Topological  Methods  for  the  Analysis  of  High  Dimensional  Data  Sets  and  3D  Object  Recognition.  In  Proceedings  of  the  Symposium  on  Point  Based  Graphics,Prague,Czech  Republic,2007.」に記載された技術を用いる。
【００４４】
検出部１５３は、Mapperによるクラスタリングの結果となる無向グラフ情報１４４を記憶部１４０に格納する。また、検出部１５３は、各クラスタに高さの情報を付与する。例えば、検出部１５３は、クラスタに付与する高さ情報を、同一のクラスタに属する非劣解の高さの平均値または中央値等に設定する。
【００４５】
検出部１５３は、各クラスタの高さの情報を基にして、無向グラフ情報１４４を有向グラフ情報１４５に変換する。例えば、検出部１５３は、第１のクラスタの高さ情報が、第２のクラスタの高さ情報よりも大きい場合に、第１のクラスタと第２のクラスタとを接続する辺の向きを、第２のクラスタから第１のクラスタに向かう方向に設定する。検出部１５３は、第２のクラスタの高さ情報が、第１のクラスタの高さ情報よりも大きい場合に、第１のクラスタと第２のクラスタとを接続する辺の向きを、第１のクラスタから第２のクラスタに向かう方向に設定する。
【００４６】
検出部１５３は、有向グラフ情報１４５を基にして、ニーポイントに対応する非劣解を含むクラスタを検出する。図８は、検出部がニーポイントを検出する処理を説明するための図（１）である。検出部１５３は、入力次数＝０となり、かつ、出力次数≧１となる極小クラスタを検出する。図８に示す例では、クラスタｃ４，ｃ７が、入力次数＝０となり、かつ、出力次数≧１となる極小クラスタとなる。極小クラスタとは、極小クラスタの周囲に、極小クラスタよりも低い他のクラスタが存在しないものとなる。検出部１５３は、極小クラスタｃ４に含まれる非劣解の非劣解ＩＤおよび極小クラスタｃ７に含まれる非劣解の非劣解ＩＤを、ニーポイントとして検出する。
【００４７】
例えば、極小クラスタｃ４に含まれる非劣解の非劣解ＩＤを「１，３」とし、極小クラスタｃ７に含まれる非劣解の非劣解ＩＤを「２，５」とする。この場合には、検出部１５３は、非劣解ＩＤ「１，２，３，５」を、ニーポイントとして検出する。検出部１５３は、ニーポイントとして検出した非劣解ＩＤを、出力部１５４に出力する。
【００４８】
ところで、検出部１５３は、入力次数＝０となり、かつ、出力次数≧１となる極小クラスタに属する非劣解であっても、下記の条件を更に満たす場合には、該当する非劣解を、ニーポイントとして検出することを抑止する。具体的には、検出部１５３は、極小クラスタに属する非劣解が、他の極大クラスタにも含まれる場合には、該当する非劣解を、ニーポイントとして検出することを抑止する。極大クラスタとなるクラスタの条件は、入力次数＝１となり、かつ、出力次数＝０となるクラスタである。
【００４９】
図９は、検出部がニーポイントを検出する処理を説明するための図（２）である。図９において、グラフ２０は、各非劣解を２次元上にプロットしたグラフである。例えば、横軸は、目的関数ｆ１の目的関数値に対応する軸であり、左側に向かうほど、目的関数ｆ１に関する目的関数値がより良いものとなる。縦軸は目的関数ｆ２の目的関数値に対応する軸であり、下側に向かうほど、目的関数ｆ２に関する目的関数値がより良いものとなる。グラフ２０は、右上から左下に向かう方向が、優越方向である。このため、グラフ２０の各非劣解は、グラフ２０の右上に位置するものほど、高さが大きくなる。
【００５０】
検出部１５３は、図９のグラフ２０に示した各非劣解に対してMapperによるクラスタリングを実行することで、有向グラフ情報１４５ａが生成される。例えば、グラフ２０において、領域２０ａ〜２０ｈに含まれる各非劣解が、極小クラスタ３０ａ〜３０ｈにそれぞれ分類される。
【００５１】
なお、Mapperによる非劣解集合の高さに基づく区間分割では、隣接する区間をオーバーラップさせて分割し、各区間に属する非劣解に対してクラスタリングを行うことで無向グラフ情報１４４を生成する。このため、区間がオーバーラップした領域に位置する非劣解は、それぞれの区間において１つずつのクラスタに属するため、全区間を通して２つ以上のクラスタに属することになる。そのため、領域２０ｅのように単一の非劣解しか存在しない場合でも、非劣解が区間のオーバーラップする位置にあれば、該当する非劣解は、生成される無向グラフ１４４において、極小クラスタ３０ｅに属するだけでなく、その次に大きい高さのクラスタ４１ａにも属し，さらには極大クラスタ４２ａにも属する。領域２０ｆの非劣解についても同様にして、極小クラスタ３０ｆだけでなく、クラスタ４１ｂや，極大クラスタ４２ｂにも属する。
【００５２】
図９において、極小クラスタ３０ａ〜３０ｄ，３０ｇ，３０ｈは、検出対象となる極小クラスタである。しかし、極小クラスタ３０ｅ，３０ｆに属する非劣解は、領域２０ｅ，２０ｆに含まれる孤立点であり、ニーポイントとして相応しくない。このため、検出部１５３は、極小クラスタに属する非劣解が、他の極大クラスタにも属するかを判定する。検出部１５３は、係る条件を満たす非劣解を、ニーポイントとして検出することを抑止することで、領域２０ｅ，２０ｆに含まれる非劣解を検出しないようにする。
【００５３】
出力部１５４は、検出部１５３の検出結果を表示部１３０に表示させる処理部である。また、出力部１５４は、ネットワークを介して、外部装置に検出結果を通知しても良い。出力部１５４は、検出結果として、ニーポイントとして検出された非劣解ＩＤのレコードを、非劣解集合情報１４１から取得し、取得したレコードを出力する。
【００５４】
次に、本実施例に係る検出装置１００の処理手順の一例について説明する。図１０は、本実施例に係る検出装置の処理手順を示すフローチャートである。図１０に示すように、検出装置１００の受付部１５１は、各種データ、たとえば、外部のプログラム等で生成された複数の非劣解や、Mapperのパラメータ等の入力を受け付ける（ステップＳ１０１）。検出装置１００の正規化部１５２は、非劣解集合情報１４１に対する正規化を実行する（ステップＳ１０２）。
【００５５】
検出装置１００の検出部１５３は、Mapperによるクラスタリングを実行することで、無向グラフ情報１４４を生成する（ステップＳ１０３）。検出部１５３は、クラスタの高さ情報を基にして、無向グラフ情報１４４を有向グラフ情報１４５に変換する（ステップＳ１０４）。検出部１５３は、極小クラスタを検出する（ステップＳ１０５）。検出装置１００の出力部１５４は、検出結果を出力する（ステップＳ１０６）。      
【００５６】
次に、本実施例に係る検出装置１００の効果について説明する。検出装置１００は、多次元空間上に配置された複数の非劣解に対して、多次元空間上の被優越方向に位置する非劣解ほど値の大きくなる高さ情報を付与し、高さ情報を付与した各非劣解から、極小点となる非劣解を検出する。このため、ニーポイントを適切に検出することができる。例えば、図１３で説明したように、パレートフロントに複数の凹凸がある場合でも、ニーポイントに相当するＰ３、Ｐ４を検出することができる。
【００５７】
検出装置１００は、複数の非劣解を多次元空間上の位置に応じて複数のクラスタに分類し、極小点となる非劣解を含むクラスタを検出する。このため、少なくとも適切な非劣解を含んだ複数の非劣解を利用者に通知することができる。例えば、図１４で説明したものでは、極小クラスタとして、非劣解１ｄ，１ｅ，１ｆが検出されることになり、適切な非劣解１ｅを含んだ検出結果を通知できる。従来は、専門家の試行錯誤で絞り込まれていた非劣解を、自動で高速に絞り込むことが可能となる。
【００５８】
検出装置１００は、Mapperを用いて、無向グラフ情報１４４を生成し、無向グラフ情報１４４を、クラスタの高さ情報を基にして、有向グラフ情報１４５に変換する。そして、検出部１００は、有向グラフ情報１４５を基にして、非劣解を含む極小クラスタを検出する。このため、Mapperを利用して、簡易的に、ニーポイントを適切に検出することができる。
【００５９】
次に、上記実施例に示した検出装置１００と同様の機能を実現するコンピュータのハードウェア構成の一例について説明する。図１１は、検出装置と同様の機能を実現するコンピュータのハードウェア構成の一例を示す図である。
【００６０】
図９に示すように、コンピュータ２００は、各種演算処理を実行するＣＰＵ２０１と、ユーザからのデータの入力を受け付ける入力装置２０２と、ディスプレイ２０３とを有する。入力装置２０２が受け付けるデータとしては、たとえば、外部のプログラム等で生成された複数の非劣解や、Mapperのパラメータ等である。また、コンピュータ２００は、記憶媒体からプログラム等を読み取る読み取り装置２０４と、ネットワークを介して他のコンピュータとの間でデータの授受を行うインタフェース装置２０５とを有する。また、コンピュータ２００は、各種情報を一時記憶するＲＡＭ２０６と、ハードディスク装置２０７とを有する。そして、各装置２０１〜２０７は、バス２０８に接続される。
【００６１】
ハードディスク装置２０７は、受付プログラム２０７ａ、正規化プログラム２０７ｂ、検出プログラム２０７ｃ、出力プログラム２０７ｄを有する。ＣＰＵ２０１は、受付プログラム２０７ａ、正規化プログラム２０７ｂ、検出プログラム２０７ｃ、出力プログラム２０７ｄを読み出してＲＡＭ２０６に展開する。
【００６２】
受付プログラム２０７ａは、受付プロセス２０６ａとして機能する。正規化プログラム２０７ｂは、正規化プロセス２０６ｂとして機能する。検出プログラム２０７ｃは、検出プロセス２０６ｃとして機能する。出力プログラム２０７ｄは、出力プロセス２０６ｄとして機能する。
【００６３】
受付プロセス２０６ａの処理は、受付部１５１の処理に対応する。正規化プロセス２０６ｂの処理は、正規化部１５２の処理に対応する。検出プロセス２０６ｃの処理は、検出部１５３の処理に対応する。出力プロセス２０６ｄの処理は、出力部１５４の処理に対応する。
【００６４】
なお、各プログラム２０７ａ〜２０７ｄについては、必ずしも最初からハードディスク装置２０７に記憶させておかなくても良い。例えば、コンピュータ２００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ２００が各プログラム２０７ａ〜２０７ｄを読み出して実行するようにしても良い。
【００６５】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００６６】
（付記１）コンピュータに、
Ｎ個（Ｎは自然数）の目的関数を用いた最適化問題についての複数の非劣解の入力を受け付け、
前記複数の非劣解それぞれについて、前記Ｎ個の目的関数を座標軸とするＮ次元空間上に設定される特定の方向に基づき高さ情報を付与し、
前記複数の非劣解から、前記高さ情報の極小点に対応した第１の非劣解群を特定する
処理を実行させることを特徴とする特定プログラムであって、
前記特定の方向は、前記Ｎ次元空間上において、前記Ｎ個の目的関数の値がいずれも大きくなる方向である、
ことを特徴とする特定プログラム。
【００６７】
（付記２）前記Ｎ個の非劣解を前記Ｎ次元空間上の位置に応じて複数のクラスタに分類する処理を更に実行し、前記特定する処理は、前記第１の非劣解群を含むクラスタを特定することを特徴とする付記１に記載の特定プログラム。
【００６８】
（付記３）前記複数のクラスタの高さ情報を基にして、異なる高さに位置し、隣接するクラスタを辺で接続した無向グラフを生成し、クラスタに属する非劣解の高さ情報を基にして、高さの低い側から高い側へ辺に向きを持たせることで、前記無向グラフを有向グラフに変換する処理を更に実行し、前記特定する処理は、前記有向グラフを基にして、前記第１の非劣解群を含むクラスタを特定することを特徴とする付記２に記載の特定プログラム。
【００６９】
（付記４）前記特定する処理は、着目するクラスタに向かう辺がなく、着目するクラスタから他のクラスタに向かう辺が存在する場合に、前記着目するクラスタを特定することを特徴とする付記３に記載の特定プログラム。
【００７０】
（付記５）前記特定する処理は、他の着目するクラスタに向かう辺が１つであり、前記他の着目するクラスタから他のクラスタに向かう辺がなく、前記他の着目するクラスタと前記着目するクラスタの両方に属する非劣解が存在する場合に、前記両方のクラスタに属する非劣解を特定することを抑止することを特徴とする付記４に記載の特定プログラム。
【００７１】
（付記６）コンピュータが実行する特定方法であって、
Ｎ個（Ｎは自然数）の目的関数を用いた最適化問題についての複数の非劣解の入力を受け付け、
前記複数の非劣解それぞれについて、前記Ｎ個の目的関数を座標軸とするＮ次元空間上に設定される特定の方向に基づき高さ情報を付与し、
前記複数の非劣解から、前記高さ情報の極小点に対応した第１の非劣解群を特定する
処理を実行、
前記特定の方向は、前記Ｎ次元空間上において、前記Ｎ個の目的関数の値がいずれも大きくなる方向である、
ことを特徴とする特定方法。
【００７２】
（付記７）前記Ｎ個の非劣解を前記Ｎ次元空間上の位置に応じて複数のクラスタに分類する処理を更に実行し、前記特定する処理は、前記第１の非劣解群を含むクラスタを特定することを特徴とする付記６に記載の特定方法。
【００７３】
（付記８）前記複数のクラスタの高さ情報を基にして、異なる高さに位置し、隣接するクラスタを辺で接続した無向グラフを生成し、クラスタに属する非劣解の高さ情報を基にして、高さの低い側から高い側へ辺に向きを持たせることで、前記無向グラフを有向グラフに変換する処理を更に実行し、前記特定する処理は、前記有向グラフを基にして、前記第１の非劣解群を含むクラスタを特定することを特徴とする付記７に記載の特定方法。
【００７４】
（付記９）前記特定する処理は、着目するクラスタに向かう辺がなく、着目するクラスタから他のクラスタに向かう辺が存在する場合に、前記着目するクラスタを特定することを特徴とする付記８に記載の特定方法。
【００７５】
（付記１０）前記特定する処理は、他の着目するクラスタに向かう辺が１つであり、前記他の着目するクラスタから他のクラスタに向かう辺がなく、前記他の着目するクラスタと前記着目するクラスタの両方に属する非劣解が存在する場合に、前記両方のクラスタに属する非劣解を特定することを抑止することを特徴とする付記９に記載の特定方法。
【００７６】
（付記１１）Ｎ個（Ｎは自然数）の目的関数を用いた最適化問題についての複数の非劣解の入力を受け付け、前記複数の非劣解それぞれについて、前記Ｎ個の目的関数を座標軸とするＮ次元空間上に設定される特定の方向に基づき高さ情報を付与し、前記複数の非劣解から、前記高さ情報の極小点に対応した第１の非劣解群を特定する検出部を有する特定装置であって、
前記特定の方向は、前記Ｎ次元空間上において、前記Ｎ個の目的関数の値がいずれも大きくなる方向である、
ことを特徴とする特定装置。
【００７７】
（付記１２）前記検出部は、前記Ｎ個の非劣解を前記Ｎ次元空間上の位置に応じて複数のクラスタに分類する処理を更に実行し、前記特定する処理は、前記第１の非劣解群を含むクラスタを特定することを特徴とする付記１１に記載の特定装置。
【００７８】
（付記１３）前記検出部は、前記複数のクラスタの高さ情報を基にして、異なる高さに位置し、隣接するクラスタを辺で接続した無向グラフを生成し、クラスタに属する非劣解の高さ情報を基にして、高さの低い側から高い側へ辺に向きを持たせることで、前記無向グラフを有向グラフに変換する処理を更に実行し、前記特定する処理は、前記有向グラフを基にして、前記第１の非劣解群を含むクラスタを特定することを特徴とする付記１２に記載の特定装置。
【００７９】
（付記１４）前記検出部は、着目するクラスタに向かう辺がなく、着目するクラスタから他のクラスタに向かう辺が存在する場合に、前記着目するクラスタを特定することを特徴とする付記１３に記載の特定装置。
【００８０】
（付記１５）前記検出部は、他の着目するクラスタに向かう辺が１つであり、前記他の着目するクラスタから他のクラスタに向かう辺がなく、前記他の着目するクラスタと前記着目するクラスタの両方に属する非劣解が存在する場合に、前記両方のクラスタに属する非劣解を特定することを抑止することを特徴とする付記１４に記載の特定装置。
【符号の説明】
【００８１】
１００  検出装置
１１０  通信部
１２０  入力部
１３０  表示部
１４０  記憶部
１５０  制御部
【図１】
2018037032.tif 000004
【図２】
2018037032.tif 000005
【図３】
2018037032.tif 000006
【図４】
2018037032.tif 000007
【図５】
2018037032.tif 000008
【図６】
2018037032.tif 000009
【図７】
2018037032.tif 000010
【図８】
2018037032.tif 000011
【図９】
2018037032.tif 000012
【図１０】
2018037032.tif 000013
【図１１】
2018037032.tif 000014
【図１２】
2018037032.tif 000015
【図１３】
2018037032.tif 000016
【図１４】
2018037032.tif 000017