(57)【要約】【課題】複数の評価関数を組み合わせて最適化問題などを解く際に、求解精度をより向上させることができる解探索装置、解探索方法および解探索プログラムを提供する。【解決手段】シミュレーションを用いた解探索において、探索木中の選択肢となるノードの中からシミュレーションの実行対象となるノードを選択し、選択されたノードからシミュレーションを実行する実行部１０１と、シミュレーション結果をもとに、複数の評価関数を用いて、複数の評価関数ごとに評価値を算出する指標算出部１０２と、指標算出部１０２が算出した各評価値の調和平均を総合評価値として算出する調和平均算出部１０３と、総合評価値をもとに、選択されたノードおよびその上位ノードの評価値を更新する更新部１０４とを含む。【選択図】図６
2014142848.tif 000002
【特許請求の範囲】
【請求項１】
シミュレーションを用いた解探索において、探索木中の選択肢となるノードの中からシミュレーションの実行対象となるノードを選択し、選択された前記ノードからシミュレーションを実行する実行部と、
シミュレーション結果をもとに、複数の評価関数を用いて、前記複数の評価関数ごとに評価値を算出する指標算出部と、
前記指標算出部が算出した各評価値の調和平均を総合評価値として算出する調和平均算出部と、
前記総合評価値をもとに、選択された前記ノードおよびその上位ノードの評価値を更新する更新部とを含む
ことを特徴とする解探索装置。
【請求項２】
指標算出部は、評価値を算出する際に、各ノードにおける評価値のうち、予め定められた基準により最も良いと判断される値がどの評価関数においても同じ値になるように、評価値を正規化する
請求項１に記載の解探索装置。
【請求項３】
指標算出部は、評価値を算出する際に、各ノードにおける評価値が一定の分散に収まるように、評価値を正規化する
請求項１に記載の解探索装置。
【請求項４】
調和平均算出部は、探索木の深さに応じて、調和平均を算出する際の各評価値に対する重み係数を変更する
請求項１から請求項３のうちのいずれか１項に記載の解探索装置。
【請求項５】
シミュレーションを用いた解探索において、探索木中の選択肢となるノードの中からシミュレーションの実行対象となるノードを選択し、選択された前記ノードからシミュレーションを実行し、
シミュレーション結果をもとに、複数の評価関数を用いて、前記複数の評価関数ごとに評価値を算出し、
各評価値の調和平均を総合評価値として算出し、
前記総合評価値をもとに、選択された前記ノードおよびその上位ノードの評価値を更新する
ことを特徴とする解探索方法。
【請求項６】
評価値を算出する際に、各ノードにおける評価値のうち、予め定められた基準により最も良いと判断される値がどの評価関数においても同じ値になるように、評価値を正規化する
請求項５に記載の解探索方法。
【請求項７】
評価値を算出する際に、各ノードにおける評価値が一定の分散に収まるように、評価値を正規化する
請求項５に記載の解探索方法。
【請求項８】
コンピュータに、
シミュレーションを用いた解探索において、探索木中の選択肢となるノードの中からシミュレーションの実行対象となるノードを選択し、選択された前記ノードからシミュレーションを実行する処理と、
シミュレーション結果をもとに、複数の評価関数を用いて、前記複数の評価関数ごとに評価値を算出する処理と、
各評価値の調和平均を総合評価値として算出する処理と、
前記総合評価値をもとに、選択された前記ノードおよびその上位ノードの評価値を更新する処理とを実行させる
ための解探索プログラム。
【請求項９】
コンピュータに、
評価値を算出する際に、各ノードにおける評価値のうち、予め定められた基準により最も良いと判断される値がどの評価関数においても同じ値になるように、評価値を正規化する処理を実行させる
請求項８に記載の解探索プログラム。
【請求項１０】
コンピュータに、
評価値を算出する際に、各ノードにおける評価値が一定の分散に収まるように、評価値を正規化する処理を実行させる
請求項８に記載の解探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化計算などにおける解探索に適用される解探索装置、解探索方法および解探索プログラムに関する。
【背景技術】
【０００２】
最適化問題は、目的関数と制約条件が設定され、目的関数が最善となる最適解一つを導出する問題であることが多い。人工知能の分野では、非特許文献１に記載されたＭＣＴＳ（モンテカルロ木探索（Ｍｏｎｔｅ−Ｃａｒｌｏ  Ｔｒｅｅ  Ｓｅａｒｃｈ））など、シミュレーションを用いた探索方法が注目されている。それらの探索方法は、データマイニングや機械学習の分野で注目されているＭＢＰ（Ｍｕｌｔｉ−ａｒｍｅｄ  Ｂａｎｄｉｔ  Ｐｒｏｂｌｅｍ）を解く方法の発展形として位置付けられる。また、それらの探索方法は、実用化されつつあり、既に実用化に成功した例として、コンピュータ囲碁がある。ＯＲ（Ｏｐｅｒａｔｉｏｎｓ  Ｒｅｓｅａｒｃｈ）などで用いられる最適化においては、それらの探索方法の実用化が期待されているが、実用化が難しい。
【０００３】
ＭＣＴＳで重要となる技術は、シミュレーション結果を用いた各ノードの評価関数の設定方法と、プレイアウト（Ｐｌａｙｏｕｔ）と呼ばれる１回のシミュレーションをする方法である。コンピュータ囲碁で用いられる評価関数は、非特許文献２に記載されたＵＣＢ（Ｕｐｐｅｒ  Ｃｏｎｆｉｄｅｎｃｅ  Ｂｏｕｎｄ）を元にしたものである。コンピュータ囲碁で用いられる評価関数では、期待値が用いられる。期待値は、囲碁における勝率などである。しかし、期待値よりも、最適な解や、上位ｋ個の解、つまりｋ番目までに良い解の平均を評価関数に用いる方が良いとされている（非特許文献３参照。）。以下、期待値にもとづく評価関数をｍｅａｎ、最適な解にもとづく評価関数をｂｅｓｔ、上位ｋ個の解の平均にもとづく評価関数をｋｂｅｓｔと表現する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｃ．  Ｂｒｏｗｎｅ，  Ｅ．  Ｐｏｗｌｅｙ，  Ｄ．  Ｗｈｉｔｅｈｏｕｓｅ，  Ｓ．  Ｌｕｃａｓ，  Ｐ．  Ｉ．  Ｃｏｗｌｉｎｇ，  Ｐ．  Ｒｏｈｌｆｓｈａｇｅｎ，  Ｓ．  Ｔｒａｖｅｎｅｒ，  Ｄ．  Ｐｅｒｅｚ，  Ｓ．  Ｓａｍｏｔｈｒａｋｉｓ  ａｎｄ  Ｓ．  Ｃｏｌｔｏｎ，  Ａ  Ｓｕｒｖｅｙ  ｏｆ  Ｍｏｎｔｅ  Ｃａｒｌｏ  Ｔｒｅｅ  Ｓｅａｒｃｈ  Ｍｅｔｈｏｄｓ，  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ  ａｎｄ  ＡＩ  ｉｎ  Ｇａｍｅｓ，  Ｖｏｌ．  ４，  Ｎｏ．  １，  Ｍａｒｃｈ  ２０１２.
【非特許文献２】Ｐ．  Ａｕｅｒ，  Ｎ．  Ｃｅｓａ−Ｂｉａｎｃｈｉ，  ａｎｄ  Ｐ．  Ｆｉｓｃｈｅｒ，  Ｆｉｎｉｔｅ−ｔｉｍｅ  Ａｎａｌｙｓｉｓ  ｏｆ  ｔｈｅ  Ｍｕｌｔｉａｒｍｅｄ  Ｂａｎｄｉｔ  Ｐｒｏｂｌｅｍ，  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ，  Ｖｏｌ．４７，  ｐ．２３５−２５６，  ２００２
【非特許文献３】Ａ．  Ｒｉｍｍｅｌ，  Ｆ．  Ｔｅｙｔａｕｄ，  ａｎｄ  Ｔ．  Ｃａｚｅｎａｖｅ，  ”Ｏｐｔｉｍｉｚａｔｉｏｎ  ｏｆ  ｔｈｅ  ｎｅｓｔｅｄ  Ｍｏｎｔｅ−Ｃａｒｌｏ  ａｌｇｏｒｉｔｈｍ  ｏｎ  ｔｈｅ  ｔｒａｖｅｌｉｎｇ  ｓａｌｅｓｍａｎ  ｐｒｏｂｌｅｍ  ｗｉｔｈ  ｔｉｍｅ  ｗｉｎｄｏｗｓ，”  ｉｎ  Ｐｒｏｃ．  Ａｐｐｌ．  Ｅｖｏｌ．  Ｃｏｍｐｕｔ．  ２，  Ｔｏｒｉｎｏ，  Ｉｔａｌｙ，  ２０１１，  ｐｐ．  ５０１-５１０
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、ｂｅｓｔやｋｂｅｓｔのどちらを用いる方が良いかは最適化を行う対象によって異なるため、一意には定めることができない。また、ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔのどれを採用したとしても、ＭＣＴＳの計算を通じてすべて一定の評価関数を使用し続けるため、求解精度を向上できない場合がある。
【０００６】
上記の複数の指標（ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔ）を組み合わせて、求解精度を向上させる方法がある。複数の指標を組み合わせる方法には、大きく分けて２つの方法がある。一つは、並列計算である。並列計算は、例えば、ｂｅｓｔを評価関数とするＭＣＴＳ、ｍｅａｎを評価関数とするＭＣＴＳ、ｋｂｅｓｔを評価関数とするＭＣＴＳの３つを同時に計算し、最終的に３つの探索方法で得られた解の中で最も良い解を選択する方法である。並列計算では、例えば、３つの探索方法で得られた解それぞれを少しずつ選択した方がより良い解が得られる場合であっても、いずれか１つの探索方法で得られた解のみが選択される。従って、並列計算では、各指標のトレードオフを考慮した解の抽出をすることができない。
【０００７】
もう一つは、ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔそれぞれの評価関数値（以下、解の評価値と表現する。）を重み付け加算等した総合評価値を用いる方法である。ＭＣＴＳを最適化に適用する際には、最終的に良い解を１つだけ得ることを目標とするため、ｂｅｓｔの値が良いノードを軽んじることはできない。また、ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔのいずれかの値が特に良いノードを高く評価することが求められる。しかし、単に重み付け加算する方法では、例えばｂｅｓｔの値だけが極端に良く、ｍｅａｎ，ｋｂｅｓｔの値があまり良くないノードは高く評価されない可能性がある。
【０００８】
また、ＭＣＴＳを最適化に適用する際には、最終的に探索木を深く展開しなければならない。そのため、終盤になるほど最終的な評価値に近いｂｅｓｔの値がより高く評価されるべきである。しかし、上述した２つの方法など既存の方法では、木の深さに関わらず、ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔが一定に用いられる。つまり、木の深さに応じて評価関数が用いられていない。従って、求解精度を向上できない場合がある。
【０００９】
そこで、本発明は、複数の評価関数を組み合わせて最適化問題などを解く際に、求解精度をより向上させることができる解探索装置、解探索方法および解探索プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明による解探索装置は、シミュレーションを用いた解探索において、探索木中の選択肢となるノードの中からシミュレーションの実行対象となるノードを選択し、選択されたノードからシミュレーションを実行する実行部と、シミュレーション結果をもとに、複数の評価関数を用いて、複数の評価関数ごとに評価値を算出する指標算出部と、指標算出部が算出した各評価値の調和平均を総合評価値として算出する調和平均算出部と、総合評価値をもとに、選択されたノードおよびその上位ノードの評価値を更新する更新部とを含むことを特徴とする。
【００１１】
本発明による解探索方法は、シミュレーションを用いた解探索において、探索木中の選択肢となるノードの中からシミュレーションの実行対象となるノードを選択し、選択されたノードからシミュレーションを実行し、シミュレーション結果をもとに、複数の評価関数を用いて、複数の評価関数ごとに評価値を算出し、各評価値の調和平均を総合評価値として算出し、総合評価値をもとに、選択されたノードおよびその上位ノードの評価値を更新することを特徴とする。
【００１２】
本発明による解探索プログラムは、コンピュータに、シミュレーションを用いた解探索において、探索木中の選択肢となるノードの中からシミュレーションの実行対象となるノードを選択し、選択されたノードからシミュレーションを実行する処理と、シミュレーション結果をもとに、複数の評価関数を用いて、複数の評価関数ごとに評価値を算出する処理と、各評価値の調和平均を総合評価値として算出する処理と、総合評価値をもとに、選択されたノードおよびその上位ノードの評価値を更新する処理とを実行させることを特徴とする。
【発明の効果】
【００１３】
本発明によれば、複数の評価関数を組み合わせて最適化問題を解く際に、求解精度をより向上させることができる。
【図面の簡単な説明】
【００１４】
【図１】最適化システムの第１の実施形態の構成を示すブロック図である。
【図２】第１の実施形態における計算部の動作を示すフローチャートである。
【図３】ＭＣＴＳを用いた最適化計算における解探索の様子を示す説明図である。
【図４】最適化システムの第３の実施形態の構成を示すブロック図である。
【図５】第３の実施形態における計算部の動作を示すフローチャートである。
【図６】本発明による解探索装置の最小構成を示すブロック図である。
【発明を実施するための形態】
【００１５】
実施形態１．
以下、本発明の第１の実施形態を図面を参照して説明する。
【００１６】
図１は、最適化システムの第１の実施形態の構成を示すブロック図である。
【００１７】
図１に示すように、第１の実施形態における最適化システムは、ユーザ端末１と、最適化装置２とを備える。ユーザ端末１と最適化装置２とは、通信可能に接続される。なお、図１には１つのユーザ端末が例示されているが、ユーザ端末は最適化装置２にいくつ接続されていてもよい。
【００１８】
ユーザ端末１は、例えばパーソナルコンピュータ等の情報処理端末である。ユーザ端末１は、操作部１１と、表示部１２とを含む。
【００１９】
操作部１１は、実行する最適化計算に必要な情報（以下、最適化計算入力情報という。）を入力する。また、操作部１１は、実行指示を入力する。操作部１１は、最適化計算入力情報とともに実行指示を最適化装置２に出力する。
【００２０】
表示部１２は、最適化装置２から最適化計算結果の解を受け取り、表示する。
【００２１】
最適化装置２は、ＧＵＩ（Ｇｒａｐｈｉｃａｌ  Ｕｓｅｒ  Ｉｎｔｅｒｆａｃｅ）部２１と、計算部２２と、記憶部２３とを含む。
【００２２】
ＧＵＩ部２１は、ユーザ端末１の操作部１１から、最適化計算入力情報を受け取る。ＧＵＩ部２１は、最適化計算入力情報を計算部２２に伝達する。ＧＵＩ部２１は、計算部２２から最適化計算結果の解を受け取り、ユーザ端末１の表示部１２へ伝達する。
【００２３】
計算部２２は、選択部２２１と、拡大部２２２と、シミュレーション部２２３と、評価値更新部２２４とを含む。
【００２４】
選択部２２１は、展開されたノードの中からプレイアウトの実行対象となるノードを選択する。以下、プレイアウトの実行対象となるノードを選択ノードという。
【００２５】
拡大部２２２は、探索木（ツリー）を拡大する。具体的には、拡大部２２２は、予め定められた基準に従って、選択部２２１で選ばれたノードを展開する必要があるか否かを判断し、必要となればさらに一段下位にノードを展開して、探索木を拡大する。拡大部２２２は、ノードを展開した場合には、選択ノードを当該一段下位のノードに選択し直す。
【００２６】
シミュレーション部２２３は、シミュレーションを実行する。具体的には、シミュレーション部２２３は、プレイアウト、すなわち、ランダムシミュレーションのような単純な方法で１つの解を探索し、解の評価値を取得する。
【００２７】
評価値更新部２２４は、シミュレーション部２２３が行ったプレイアウトの結果により、各ノードの解の評価値を更新する。
【００２８】
評価値更新部２２４は、指標算出部２２４１と、調和平均算出部２２４２と、評価フィードバック部２２４３とを含む。
【００２９】
指標算出部２２４１は、指標値を算出する。本実施形態では、ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔの解の評価値を指標値として、それぞれ算出する。
【００３０】
調和平均算出部２２４２は、指標算出部２２４１で算出された評価値を組み合わせて総合評価値を算出する。その際、調和平均算出部２２４２は、各指標のトレードオフを考慮し、また各指標で特長を持つ値が強調されるように、総合評価値の算出を行う。
【００３１】
評価フィードバック部２２４３は、調和平均算出部２２４２が算出した結果をもとに、各ノードの評価値を更新する。
【００３２】
記憶部２３は、問題データ記憶部２３１と、ノード情報記憶部２３２と、解情報記憶部２３３とを含む。
【００３３】
問題データ記憶部２３１は、目的関数や制約条件を記憶する。最適化システムがスケジューリング問題に適用される場合には、問題データ記憶部２３１は、タスク情報や担当者情報など、問題を解くために必要なデータ（以下、問題データという。）を記憶する。
【００３４】
ノード情報記憶部２３２は、計算部２２での計算処理が進む際に、ノードの評価値など、変化する情報を記憶する。本実施形態では、ノード情報記憶部２３２は、計算部２２が各計算途中で得たノードの探索回数や評価値を記憶する。
【００３５】
解情報記憶部２３３は、計算部２２で求められた解の中で保持する必要のある解を記憶する。
【００３６】
なお、ＧＵＩ部２１、計算部２２は、例えば、解探索プログラムに従って動作するコンピュータによって実現される。この場合、最適化装置２が備えるＣＰＵが解探索プログラムを読み込み、そのプログラムに従って、ＧＵＩ部２１および計算部２２として動作する。また、ＧＵＩ部２１および計算部２２の各部は別々のハードウェアで実現されていてもよい。
【００３７】
また、問題データ記憶部２３１、ノード情報記憶部２３２および解情報記憶部２３３は、最適化装置２が備えるＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等の記憶装置によって実現される。
【００３８】
次に、本実施形態の動作を説明する。
【００３９】
図２は、第１の実施形態における計算部２２の動作を示すフローチャートである。
【００４０】
ここでは、図１に示す最適化システムがスケジューリング問題に適用される場合を例にする。
【００４１】
まず、ユーザがユーザ端末１の操作部１１に対して、最適化計算入力情報を入力する。ユーザは、最適化計算をしたいタスク、従事可能な担当者、各担当者がそれぞれのタスクに従事した時のコストや有効性などの問題データを最適化計算入力情報として入力する。このとき、ユーザは、最適化計算入力情報とともに実行指示を操作部１１に入力する。操作部１１は、最適化計算入力情報と実行指示とを最適化装置２に出力する。
【００４２】
最適化装置２のＧＵＩ部２１は、ユーザ端末１から最適化計算入力情報とともに実行指示を受け取ると、最適化計算入力情報を計算部２２へ伝達する。計算部２２は、最適化計算入力情報を入力する（ステップＳ２０１）。
【００４３】
ステップＳ２０１の後、計算部２２の選択部２２１は、展開されたノードの中から、シミュレーションすべきノードを選択する（ステップＳ２０２）。なお、初期状態ではノードは１つのみであるので、そのノードが選択対象となる。ノードの選択は、本実施形態では、評価値更新部２２４によって算出された指標値（総合評価値）を用いて行う。
【００４４】
拡大部２２２は、選択部２２１で選択されたノードのプレイアウト回数が、事前に定められた条件を満たした時に（ステップＳ２０３のＹｅｓ）、探索木を１段下位のノードまで展開する（ステップＳ２０４）。本実施形態では、拡大部２２２は、当該プレイアウト回数が予め定められた回数を越えた時に展開する。なお、初期状態でノードが１つのみである時は、この条件に関わらず展開する。展開した場合には、拡大部２２２は、展開したノードのうちの１つを選択ノードとする。
【００４５】
シミュレーション部２２３は、選択ノードからプレイアウト、つまりランダムシミュレーションを実行し解を１つ探索する（ステップＳ２０５）。なお、１つの選択ノードに対して複数のシミュレーションを実行し複数の解を探索することも可能であるが、ここでは、もっともシンプルな例として１つの選択ノードに対して１つのシミュレーションを実行し１つの解を探索する方法について説明する。本発明の技術的範囲は、１つの選択ノードに対して１つのシミュレーションを実行する形態に限定されない。従って、１つの選択ノードに対して複数のシミュレーションを実行する形態も本発明の技術的範囲に含まれ得る。
【００４６】
指標算出部２２４１は、シミュレーション部２２３によって得られた解を用いて、ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔの解の評価値を更新する。ｂｅｓｔの解の評価値は、現在までにその選択ノードから実行されたシミュレーションの結果の中で最適なものである。ｍｅａｎの解の評価値は、現在までにその選択ノードから実行されたシミュレーションの結果を平均したものである。ｋｂｅｓｔの解の評価値は、現在までにその選択ノードから実行されたシミュレーションの結果の中でｋ番目までに良い解を平均したものである。指標算出部２２４１は、以下に示す正規化の処理を、ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔの解の評価値それぞれについて行う。なお、ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔの解の評価値に対する処理は並行して行われる。
【００４７】
選択ノードとその兄弟ノード（選択ノードと共通の親ノードをもつノード）における指標値をそれぞれｖ１，ｖ２，ｖ３，…ｖＬとした時、最大値Ｍ、最小値ｍは以下のように表すことが可能である。なお、Ｌは、共通の親ノードをもつ子ノードの総数である。
【００４８】
【数１】
2014142848.tif 000003
【００４９】
【数２】
2014142848.tif 000004
【００５０】
ここで、ｖｉは、予め定められた基準により、最小値ｍに近い場合に良い値であると判断されるとする。また、最大値Ｍに近い場合に悪い値であると判断されるとする。指標算出部２２４１は、良い値である最小値ｍを０、悪い値である最大値Ｍを１とするために、ｖｉを正規化する。具体的には、指標算出部２２４１は、ｖｉを次のように変換する。Ｖａｌｕｅｉは、ｖｉの正規化後の値である。
【００５１】
【数３】
2014142848.tif 000005
【００５２】
また、Ｖａｌｕｅｉの値が一定の分散におさまるように、ｖｉをさらに正規化してもよい。
【００５３】
指標算出部２２４１が、ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔそれぞれについて上記の処理を実行することにより、ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔのそれぞれに対応するＶａｌｕｅｉが算出される（ステップＳ２０６）。以下、ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔに対応するＶａｌｕｅｉを、それぞれｂｅｓｔＶａｌｕｅ，ｍｅａｎＶａｌｕｅ，ｋｂｅｓｔＶａｌｕｅ（ｋ）と表現する。“（ｋ）”は、上位ｋ個の解を平均算出の対象とすることを表す。
【００５４】
調和平均算出部２２４２は、ノードごとに次の計算式を用いてノードの総合評価値を算出する（ステップＳ２０７）。ｈＶａｌｕｅは、ノードの総合評価値である。ｗ、εは、各指標ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔの重みを表す係数である。
【００５５】
【数４】
2014142848.tif 000006
【００５６】
例えば、ｗｂｅｓｔ，ｗｍｅａｎ，ｗｋｂｅｓｔ（ｋ）を大きくすると、式全体に対する各指標の影響度、つまりｈＶａｌｕｅに対する各指標の影響度を強くすることができる。
【００５７】
εｂｅｓｔ，εｍｅａｎ，εｋｂｅｓｔ（ｋ）は、ｂｅｓｔＶａｌｕｅ，ｍｅａｎＶａｌｕｅ，ｋｂｅｓｔＶａｌｕｅ（ｋ）がそれぞれ最も良い時、つまりゼロ付近にある時の各指標の影響度を調整する係数である。各指標の影響度を強くしたい場合には、εｂｅｓｔ，εｍｅａｎ，εｋｂｅｓｔ（ｋ）の値を小さくする、つまりゼロに近づける。例えば、ｂｅｓｔＶａｌｕｅがゼロ付近にある場合、εｂｅｓｔ＝０．０１であれば、分母のｂｅｓｔの項は「ｗｂｅｓｔ×１００」になる。εｂｅｓｔ=０．１であれば、分母のｂｅｓｔの項は「ｗｂｅｓｔ×１０」になる。このように、ｂｅｓｔＶａｌｕｅがゼロ付近にある時に、εｂｅｓｔを小さくすればするほど、指標ｂｅｓｔの影響度が強くなる。εを調整することにより、ｂｅｓｔＶａｌｕｅ，ｍｅａｎＶａｌｕｅ，ｋｂｅｓｔＶａｌｕｅ（ｋ）が良い値であるときに、総合評価値ｈＶａｌｕｅを、最も良い値であるゼロに到達させる速さを調節することが可能となる。
【００５８】
このように、ｗ、εの値を用いることにより、各指標のトレードオフを考慮できる。また、特定の指標に強みを持つノードの評価値をより良くすることができる。なお、ｗ、εは、予め最適化装置２の記憶部２３に格納される。
【００５９】
評価フィードバック部２２４３は、調和平均算出部２２４２から総合評価値を、ノードに渡す評価値として取得する。評価フィードバック部２２４３は、取得した総合評価値で、選択ノードとその上位のノードの評価値を更新する（ステップＳ２０８）。
【００６０】
計算部２２は、計算部２２における計算時間が事前に定められた上限に達するまで、ステップＳ２０２〜Ｓ２０８の処理（選択処理、ノード展開処理、シミュレーション計算処理および評価値更新処理）を繰り返し実行する（ステップＳ２０９）。つまり、当該計算時間が上限に達していない場合は（ステップＳ２０９のＹｅｓ）、計算部２２はステップＳ２０２の処理に戻る。当該計算時間が上限に達した場合は（ステップＳ２０９のＮｏ）、計算部２２は処理を終了する。なお、計算部２２は、計算時間ではなく、要件として与えられた解の値が算出されるまでステップＳ２０２〜Ｓ２０８の処理を繰り返し実行するようにしてもよい。
【００６１】
また、ステップＳ２０２〜Ｓ２０９の計算処理において、計算部２２は、各計算途中で得たノードの探索回数や評価値を含む情報をノード情報記憶部２３２に格納する。また、計算部２２は、探索して得た解を含む情報を解情報記憶部２３３に格納する。計算部２２は、ノード情報記憶部２３２および解情報記憶部２３３に格納された情報を取得することにより、計算途中における各ノードの探索回数や評価値を認識することができる。
【００６２】
計算部２２は計算を終了すると、最適化計算結果、つまり探索して得た解を示す解情報をＧＵＩ部２１に渡す。
【００６３】
ＧＵＩ部２１は、受け取った解情報をユーザ端末１の表示部１２に伝達する。
【００６４】
なお、本実施形態では、問題データがユーザ端末１から最適化計算入力情報として計算部２２に入力される場合を例にしたが、計算部２２は問題データ記憶部２３１に格納された問題データを取得するようにしてもよい。そのような形態を実現するには、ユーザ等が予め問題データを問題データ記憶部２３１に格納すればよい。
【００６５】
以上に説明したように、本実施形態では、調和平均により算出したノードの総合評価値で、選択ノードとその上位のノードの評価値を更新する。それにより、複数の評価関数（指標）を組み合わせて最適化問題を解く際に、各指標のトレードオフを考慮でき、かつ特定の指標に強みを持つノードの評価値をより良くすることができる。従って、そのノードのシミュレーション回数を増やすことができる。
【００６６】
つまり、本実施形態によれば、最適化などに適した評価値を提供することができるとともに、より重要なノードのシミュレーション回数を適切に増やすことができる。よって、ＭＣＴＳなどのシミュレーションによって評価値を算出する探索方法の解の精度を改善する可能性を高めることができる。また、解の精度を改善することで、実用化が難しいＯＲなどについて、実用化の可能性を高めることができる。
【００６７】
なお、ステップＳ２０６〜Ｓ２０７において、３つの指標ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔをもとに、総合評価値を算出する場合を例にしたが、指標は３つに限定されない。例えば、３つ以上の指標をもとに総合評価値を算出してもよい。
【００６８】
実施形態２．
以下、本発明の第２の実施形態を図面を参照して説明する。
【００６９】
第２の実施形態における最適化システムの構成は、第１の実施形態の構成と同様である。
【００７０】
しかし、最適化装置２の調和平均算出部２２４２は、探索木の深さのレベルごとに、ノードの総合評価値を算出する。
【００７１】
ここでは、第１の実施形態と同様に、最適化システムがスケジューリング問題に適用される場合を例にする。
【００７２】
第２の実施形態における計算部２２の動作は、図２に示す第１の実施形態の動作と同様である。
【００７３】
しかし、ステップＳ２０７における調和平均算出部２２４２の動作が異なる。ここで、ステップＳ２０７における調和平均算出部２２４２の動作を説明する。
【００７４】
図３は、ＭＣＴＳを用いた最適化計算における解探索の様子を示す説明図である。図３に示す探索木では、端点Ａから端点Ｂ，Ｃ，Ｄへの選択肢があり、さらに端点Ｂから端点Ｅ，Ｆ，Ｇへの選択肢がある。ＭＣＴＳを用いた解法では、各端点において選択肢の選択を行って最終的に最下辺までのパスを１つの解として、最適なパス（解）を求める。その際、途中段階において、展開した各端点Ｅ，Ｆ，Ｇ，Ｃ，Ｄからプレイアウト、すなわち、ランダムシミュレーションのような単純な方法によって、数多くの試行をする。図３に示す端点Ｅ，Ｆ，Ｇ，Ｃ，Ｄから伸びる波線はプレイアウトの探索経路を模式化したものである。
【００７５】
ＭＣＴＳでＮ個のタスクのそれぞれを誰に割り当てるかを決める場合、解空間の木はＮ段のレベルを有する。つまり、探索木は最終的にＮ段の深さを有する木となる。図３では、探索木の１段目がタスク１に、２段目がタスク２に、Ｎ段目がタスクＮに相当する。つまり、端点Ｂ、Ｃ、Ｄは、タスク１を割り当てる人物を表し、端点Ｅ、Ｆ、Ｇは、タスク２を割り当てる人物を表す。
【００７６】
このような場合、調和平均算出部２２４２は、深さのレベルごとにノードの総合評価値を算出する。具体的には、調和平均算出部２２４２は、ｎ段目のノードについて次の計算式を用いて、ノードの総合評価値を算出する（ステップＳ２０７）。ｗｂｅｓｔ（ｎ），ｗｍｅａｎ（ｎ），ｗｋｂｅｓｔ（ｋ）（ｎ）、εｂｅｓｔ（ｎ），εｍｅａｎ（ｎ），εｋｂｅｓｔ（ｋ）（ｎ）は、ｎ段目におけるｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔに対する重みを表す。
【００７７】
【数５】
2014142848.tif 000007
【００７８】
ただし、
【００７９】
【数６】
2014142848.tif 000008
【００８０】
とする。なお、ｍｉｎ（ａ、ｂ）は、ａ、ｂのいずれか小さい方を出力する。ｍａｘ（ａ、ｂ）は、ａ、ｂのいずれか大きい方を出力する。また、ｗｂｅｓｔ（ｎ），ｗｍｅａｎ（ｎ），ｗｋｂｅｓｔ（ｋ）（ｎ）は、上記以外の方法で決定してもよい。
【００８１】
以上に説明したように、本実施形態では、第１の実施形態と同様の効果が得られるとともに、探索木の深さのレベルに応じて、各ノードに適切な評価関数を設定することができる。そのため、各ノードのシミュレーション回数をより増やすことができる。より重要なノードのシミュレーション回数を適切に増やすことができるので、ＭＣＴＳなど、シミュレーションによって評価値を算出する探索方法の解の精度をさらに改善する可能性を高めることができる。
【００８２】
実施形態３．
以下、本発明の第３の実施形態を図面を参照して説明する。
【００８３】
図４は、最適化システムの第３の実施形態の構成を示すブロック図である。
【００８４】
図４に示すように、本実施形態における最適化システムは、ユーザ端末１と、最適化装置３とを備える。ユーザ端末１と最適化装置３とは、通信可能に接続される。なお、図４には１つのユーザ端末が例示されているが、ユーザ端末は最適化装置３にいくつ接続されていてもよい。
【００８５】
図４に示すように、最適化装置３は、ＧＵＩ部２１と、計算部３２と、記憶部２３とを含む。
【００８６】
計算部３２は、選択部２２１と、拡大部２２２と、シミュレーション部２２３と、評価値更新部３２４とを含む。
【００８７】
評価値更新部３２４は、シミュレーション部２２３が行ったプレイアウトの結果により、各ノードの解の評価値を更新する。
【００８８】
評価値更新部３２４は、ｋｂｅｓｔ算出部３２４１と、評価フィードバック部２２４３とを含む。
【００８９】
ｋｂｅｓｔ算出部３２４１は、探索木の深さを考慮したｋｂｅｓｔを算出する。以下、ｎ段目の深さを深さｎと表現する。ｋｂｅｓｔ算出部３２４１は、解の平均を算出する際の解の個数ｋを、深さｎに応じて変更する。なお、ｋには、予め初期値Ｋが設定される。なお、初期値Ｋは、予め最適化装置３の記憶部２３に格納される。ｋｂｅｓｔ算出部３２４１は、算出したｋｂｅｓｔの値を評価フィードバック部２２４３に伝達する。
【００９０】
なお、本実施形態におけるその他の構成は、第１の実施形態と同様であるため説明を省略する。
【００９１】
なお、計算部３２は、例えば、解探索プログラムに従って動作するコンピュータによって実現される。この場合、最適化装置３が備えるＣＰＵが解探索プログラムを読み込み、そのプログラムに従って、計算部３２として動作する。また、ＧＵＩ部２１および計算部３２の各部は別々のハードウェアで実現されていてもよい。
【００９２】
次に、本実施形態の動作を説明する。
【００９３】
図５は、第３の実施形態における計算部３２の動作を示すフローチャートである。
【００９４】
ここでは、図４に示す最適化システムがスケジューリング問題に適用される場合を例にする。
【００９５】
ステップＳ５０１〜Ｓ５０５、Ｓ５０８の処理は、それぞれ、第１の実施形態におけるステップＳ２０１〜Ｓ２０５、Ｓ２０９の処理と同様であるため説明を省略する。
【００９６】
ステップＳ５０５の後、ｋｂｅｓｔ算出部３２４１は、シミュレーション部２２３によって得られた解を用いて、ｋｂｅｓｔの解の評価値を更新する。
【００９７】
ここで、ｋｂｅｓｔ算出部３２４１は、第１の実施形態における指標算出部２２４１と同様に、式１〜式３を用いてｋｂｅｓｔＶａｌｕｅ（ｋ（ｎ））を算出する（ステップＳ５０６）。ｋ（ｎ）は、深さｎにおけるｋを表す。
【００９８】
ｋｂｅｓｔ算出部３２４１は、以下の式を用いて、ｋ（ｎ）を決定する。
【００９９】
【数７】
2014142848.tif 000009
【０１００】
その結果、深さｎが小さい場合、つまりノードが探索木の浅い位置に存在する場合には、ｋｂｅｓｔに対応するＶａｌｕｅｉは、ｋｂｅｓｔＶａｌｕｅ（Ｋ）として算出される。深さｎが大きい場合、つまりノードが探索木において深い位置に存在する場合には、ｋｂｅｓｔに対応するＶａｌｕｅｉは、最終的には第１の実施形態におけるｂｅｓｔＶａｌｕｅ（＝ｋｂｅｓｔＶａｌｕｅ（１））として算出される。従って、深さｎに応じた評価関数を各ノードに設定することができる。なお、ｋ（ｎ）は、上記以外の方法で決定してもよい。
【０１０１】
評価フィードバック部２２４３は、ｋｂｅｓｔ算出部３２４１の算出結果をノードに渡す評価値として取得する。評価フィードバック部２２４３は、取得した算出結果で、選択ノードとその上位のノードの評価値を更新する（ステップＳ５０７）。
【０１０２】
以上に説明したように、本実施形態では、第２の実施形態と同様に、探索木の深さのレベルに応じて、各ノードに適切な評価関数を設定することができる。
【０１０３】
なお、各実施形態において、最適化装置がスケジューリング問題に適用される場合を例にしたが、本発明の適用範囲はその限りではない。本発明は、タスクを担当者に割り当てるスケジューリング問題などの組合せ最適化問題を中心に、最適化問題全般に適用することが可能である。また、最適化問題以外の解探索にも適用することが可能である。
【０１０４】
図６は、本発明による解探索装置の最小構成を示すブロック図である。図６に示すように、解探索装置（図１に示す最適化装置２に相当。）は、シミュレーションを用いた解探索において、探索木中の選択肢となるノードの中からシミュレーションの実行対象となるノードを選択し、選択されたノードからシミュレーションを実行する実行部１０１（図１に示す最適化装置２における選択部２２１、拡大部２２２およびシミュレーション部２２３に相当。）と、シミュレーション結果をもとに、複数の評価関数を用いて、複数の評価関数ごとに評価値を算出する指標算出部１０２（図１に示す最適化装置２における指標算出部２２４１に相当。）と、指標算出部１０２が算出した各評価値の調和平均を総合評価値として算出する調和平均算出部１０３（図１に示す最適化装置２における調和平均算出部２２４２に相当。）と、総合評価値をもとに、選択されたノードおよびその上位ノードの評価値を更新する更新部１０４（図１に示す最適化装置２における評価フィードバック部２２４３に相当。）とを含む。
【０１０５】
そのような構成によれば、各指標のトレードオフを考慮でき、かつ特定の指標に強みを持つノードの評価値をより良くすることができ、そのノードのシミュレーション回数を増やすことができる。つまり、最適化などに適した評価値を提供することができる。それにより、より重要なノードのシミュレーション回数を適切に増やすことが可能となり、ＭＣＴＳなどのシミュレーションによって評価値を算出する探索方法の解の精度を改善する可能性を高めることができる。
【０１０６】
上記の実施形態には、以下のような解探索装置も開示されている。
【０１０７】
（１）指標算出部１０２は、評価値を算出する際に、各ノードにおける評価値のうち、予め定められた基準により最も良いと判断される値がどの評価関数においても同じ値になるように、評価値を正規化する解探索装置。
【０１０８】
そのような構成によれば、指標値、例えば、ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔなどの解の評価値を、各ノードについて公平に用いることができる。
【０１０９】
（２）指標算出部１０２は、評価値を算出する際に、各ノードにおける評価値が一定の分散に収まるように、評価値を正規化する解探索装置。
【０１１０】
そのような構成によれば、指標値、例えば、ｂｅｓｔ，ｍｅａｎ，ｋｂｅｓｔなどの解の評価値を、各ノードについて公平に用いることができるとともに、指標値を一定の分散に抑えることができる。
【０１１１】
（３）調和平均算出部１０３は、探索木の深さに応じて、調和平均を算出する際の各評価値に対する重み係数を変更する解探索装置。
【０１１２】
そのような構成によれば、本実施形態によれば、探索木の深さに応じて、各ノードの評価値を柔軟に変更することができるので、最適化のように解空間の底まで辿らなければいけないＭＣＴＳにおいて、より精度の高い評価値を提供することができる。それにより、ＭＣＴＳなど、シミュレーションによって評価値を算出する探索方法の解の精度をさらに改善する可能性を高めることができる。
【０１１３】
また、上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下に限られない。
【０１１４】
（付記１）シミュレーションを用いた解探索において、探索木中の選択肢となるノードの中からシミュレーションの実行対象となるノードを選択し、選択されたノードからシミュレーションを実行する実行部（図４に示す最適化装置３における選択部２２１、拡大部２２２およびシミュレーション部２２３に相当。）と、選択されたノードから実行されたシミュレーション結果のうち、予め定められた基準により良いと判断された上位複数個を平均して評価値を算出する指標算出部（図４に示す最適化装置３におけるｋｂｅｓｔ算出部３２４１に相当。）と、指標算出部が算出した評価値をもとに、選択されたノードおよびその上位ノードの評価値を更新する更新部（図４に示す最適化装置３における評価フィードバック部２２４３に相当。）とを含み、指標算出部は、平均算出の対象とするシミュレーション結果の個数を探索木の深さに応じて変更することを特徴とする解探索装置。
【０１１５】
そのような構成によれば、ｋｂｅｓｔを評価関数とする解探索において、探索木の深さのレベルに応じて、各ノードに適切な評価関数を設定することができる。
【０１１６】
（付記２）指標算出部は、評価値を算出する際に、各ノードにおける評価値のうち、予め定められた基準により最も良いと判断される値がゼロになるように、評価値を正規化する付記１に記載の解探索装置。
【０１１７】
そのような構成によれば、ｋｂｅｓｔを評価関数とする解探索において、指標値を各ノードについて公平に用いることができる。
【０１１８】
（付記３）指標算出部は、評価値を算出する際に、各ノードにおける評価値が一定の分散に収まるように、評価値を正規化する付記１に記載の解探索装置。
【０１１９】
そのような構成によれば、ｋｂｅｓｔを評価関数とする解探索において、指標値を各ノードについて公平に用いることができるとともに、指標値を一定の分散に抑えることができる。
【符号の説明】
【０１２０】
１  ユーザ端末
２、３  最適化装置
１１  操作部
１２  表示部
２１  ＧＵＩ部
２２、３２  計算部
２３  記憶部
１０１  実行部
１０２、２２４１  指標算出部
１０３、２２４２  調和平均算出部
１０４  更新部
２２１  選択部
２２２  拡大部
２２３  シミュレーション部
２２４、３２４  評価値更新部
２３１  問題データ記憶部
２３２  ノード情報記憶部
２３３  解情報記憶部
３２４１  ｋｂｅｓｔ算出部
２２４３  評価フィードバック部
【図１】
2014142848.tif 000010
【図２】
2014142848.tif 000011
【図３】
2014142848.tif 000012
【図４】
2014142848.tif 000013
【図５】
2014142848.tif 000014
【図６】
2014142848.tif 000015