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