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