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