(57)【要約】  最適化計算における解探索において、探索木中の選択肢となるノードの中からプレイアウトの実行対象となるノードを選択する選択部１０１と、選択されたノードからプレイアウトを実行して解を探索する第一の計算部１０２と、プレイアウト後の解を初期解とし、発見的手法、局所探索法または近傍探索法により解を探索する第二の計算部１０３とを含む。
2014087590.tif 000002
【特許請求の範囲】
【請求項１】
最適化計算における解探索において、探索木中の選択肢となるノードの中からプレイアウトの実行対象となるノードを選択する選択部と、
選択された前記ノードからプレイアウトを実行して解を探索する第一の計算部と、
前記プレイアウト後の解を初期解とし、発見的手法、局所探索法または近傍探索法により解を探索する第二の計算部とを含む
ことを特徴とする最適化装置。
【請求項２】
第二の計算部は、第一の計算部が探索した解と当該第二の計算部が探索した解とをもとに、当該第二の計算部における計算時間の終了条件を算出し、前記終了条件が満たされたときに当該第二の計算部における計算処理を終了する
請求項１に記載の最適化装置。
【請求項３】
第一の計算部が探索した解の評価値と第二の計算部が探索した解の評価値との両方、または、第二の計算部が探索した解の評価値のみをもとに、各ノードの評価値を更新する評価値更新部を含む
請求項１または請求項２に記載の最適化装置。
【請求項４】
第二の計算部は、第一の計算部が実行したプレイアウトにより探索された解のうち予め定められた基準を満たす解に対して、または、第一の計算部が実行した複数回のプレイアウトにより探索された各解のうち当該各解を相対的に比較した結果をもとに選択した解に対して、発見的手法、局所探索法または近傍探索法による解の探索を行う
請求項１から請求項３のうちのいずれか１項に記載の最適化装置。
【請求項５】
最適化計算における解探索において、探索木中の選択肢となるノードの中からプレイアウトの実行対象となるノードを選択し、
選択された前記ノードからプレイアウトを実行して解を探索し、
前記プレイアウト後の解を初期解とし、発見的手法、局所探索法または近傍探索法により第二の解を探索する
ことを特徴とする最適化方法。
【請求項６】
初期解と第二の解とをもとに、第二の解を探索するための計算時間の終了条件を算出し、前記終了条件が満たされたときに第二の解を探索するための計算処理を終了する
請求項５に記載の最適化方法。
【請求項７】
初期解の評価値と第二の解の評価値との両方、または、第二の解の評価値のみをもとに、各ノードの評価値を更新する
請求項５または請求項６に記載の最適化方法。
【請求項８】
コンピュータに、
最適化計算における解探索において、探索木中の選択肢となるノードの中からプレイアウトの実行対象となるノードを選択する処理と、
選択された前記ノードからプレイアウトを実行して解を探索する処理と、
前記プレイアウト後の解を初期解とし、発見的手法、局所探索法または近傍探索法により第二の解を探索する処理とを実行させる
ための最適化プログラム。
【請求項９】
コンピュータに、
初期解と第二の解とをもとに、第二の解を探索するための計算時間の終了条件を算出し、前記終了条件が満たされたときに第二の解を探索するための計算処理を終了する処理を実行させる
請求項８に記載の最適化プログラム。
【請求項１０】
コンピュータに、
初期解の評価値と第二の解の評価値との両方、または、第二の解の評価値のみをもとに、各ノードの評価値を更新する処理を実行させる
請求項８または請求項９に記載の最適化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化計算における解探索に適用される最適化装置、最適化方法および最適化プログラムに関する。
【背景技術】
【０００２】
最適化問題は、設定された目的関数と制約条件とをもとに、当該制約条件の下で当該目的関数が最善となる１つの最適解を導出する問題であることが多い。ＯＲ（Ｏｐｅｒａｔｉｏｎｓ  Ｒｅｓｅａｒｃｈ）などで用いられる最適化はたいてい、１つの目的関数に対して、最も良い１つの解とその解をもたらす要素とを列挙する。しかし、想定されるすべての解を調べて最適な１つの解を求めることは解の組合せが膨大になることから現実的に不可能な場合が多い。従って、最適化計算においては解の探索方法が重要である。解の探索方法には、分枝限定法や発見的手法がある。発見的手法には、シミュレーテッドアニーリング法（以下、ＳＡ（Ｓｉｍｕｌａｔｅｄ  Ａｎｎｅａｌｉｎｇ）という。）、遺伝アルゴリズム（以下、ＧＡ（Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ）という。）などの進化的方法、タブーサーチなどがある。【０００３】
一方で最適化ではないが、複数の選択肢を評価し意思決定をするＭＢＰ（Ｍｕｌｔｉ−Ａｒｍｅｄ  Ｂａｎｄｉｔ  Ｐｒｏｂｌｅｍ）を解く方法として指標ＵＣＢ（Ｕｐｐｅｒ  Ｃｏｎｆｉｄｅｎｃｅ  Ｂｏｕｎｄ）がある（非特許文献１参照。）。ＵＣＢは、選択肢を選択後にランダムシミュレーションのような単純な方法でシミュレーションを加え、その結果を評価して最終的な意思決定に導くためのものである。【０００４】
さらにモンテカルロ木探索（ＭＣＴＳ（Ｍｏｎｔｅ  Ｃａｒｌｏ  Ｔｒｅｅ  Ｓｅａｒｃｈ））は、ＵＣＢを多段に用いることで、１段の選択肢の選択だけではなく、全段を列挙して１つの解を求める最適化に対しても適用可能である。非特許文献２に記載されているように、ＭＣＴＳを用いた解法は、ドメイン知識が必要ないので、様々なドメイン（分野、領域）に適用しやすい。そのため、最適化に対してＭＣＴＳの適用が実現できれば有効性は高い。【０００５】
例えば、最適化では、より良い最適化システムを設計するために、システム設計者が数多くのヒアリングをしてそのドメインの特徴を知る必要がある。そのため、最適化システムの設計では貴重なスキル技術者である最適化システム設計者が膨大な時間を費やす。ドメイン知識を必要としないＭＣＴＳを用いた解法が実現できれば、ヒアリングなどの時間を削減でき最適化システムの設計時間を短縮することができる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｐ．  Ａｕｅｒ，  Ｎ．  Ｃｅｓａ−Ｂｉａｎｃｈｉ，  ａｎｄ  Ｐ．  Ｆｉｓｃｈｅｒ，  Ｆｉｎｉｔｅ−ｔｉｍｅ  Ａｎａｌｙｓｉｓ  ｏｆ  ｔｈｅ  Ｍｕｌｔｉａｒｍｅｄ  Ｂａｎｄｉｔ  Ｐｒｏｂｌｅｍ，  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ，  Ｖｏｌ．４７，  ｐ．２３５−２５６，  ２００２．
【非特許文献２】Ｃ．  Ｂｒｏｗｎｅ，  Ｅ．  Ｐｏｗｌｅｙ，  Ｄ．  Ｗｈｉｔｅｈｏｕｓｅ，  Ｓ．  Ｌｕｃａｓ，  Ｐ．  Ｉ．  Ｃｏｗｌｉｎｇ，  Ｐ．  Ｒｏｈｌｆｓｈａｇｅｎ，  Ｓ．  Ｔａｖｅｎｅｒ，  Ｄ．  Ｐｅｒｅｚ，  Ｓ．  Ｓａｍｏｔｈｒａｋｉｓ  ａｎｄ  Ｓ．  Ｃｏｌｔｏｎ，  Ａ  Ｓｕｒｖｅｙ  ｏｆ  Ｍｏｎｔｅ  Ｃａｒｌｏ  Ｔｒｅｅ  Ｓｅａｒｃｈ  Ｍｅｔｈｏｄｓ，  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ  ａｎｄ  ＡＩ  ｉｎ  Ｇａｍｅｓ，  Ｖｏｌ．  ４，  Ｎｏ．  １，  Ｍａｒｃｈ  ２０１２．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、ＭＣＴＳを用いた解法によって最適化に成功することは難しい。その理由は、ＭＣＴＳで最適化問題を解く場合、問題規模が大きくなった時に解の精度が劣化するためである。【０００８】
図６は、ＭＣＴＳを用いた最適化計算における解探索の様子を示す説明図である。図６に示す探索木では、端点Ａから端点Ｂ、端点Ｃまたは端点Ｄへの選択肢があり、さらに端点Ｂから端点Ｅ、端点Ｆまたは端点Ｇへの選択肢がある。ＭＣＴＳを用いた解法では、各端点において選択肢の選択を行って最終的に最下辺までのパスを１つの解として、最適なパス（解）を求める。その際、途中段階において、展開した各端点Ｅ、端点Ｆ、端点Ｇ、端点Ｃおよび端点Ｄからプレイアウト、すなわち、ランダムシミュレーションのような単純な方法によって、数多くの試行をする。ＵＣＢでは、試行の結果の平均値が各端点の持ち点となり、持ち点の高いノードがさらに下方に展開され、最下辺まで求まった時点で最適化計算が終了となる。図６に示す端点Ｅ、端点Ｆ、端点Ｇ、端点Ｃおよび端点Ｄから伸びる波線はプレイアウトの探索経路を模式化したものである。また、各端点から伸びる波線の数はプレイアウト回数に相当する。なお、プレイアウトは実際には数百万回やそれ以上の単位で実行されることが多い。【０００９】
問題規模が大きくなると、単純な辿り方しかしないプレイアウトの部分が非常に長くなり、各端点Ｅ、端点Ｆ、端点Ｇ、端点Ｃおよび端点Ｄのプレイアウト部分の求解精度が低下する。それにより、各端点Ｅ、端点Ｆ、端点Ｇ、端点Ｃおよび端点Ｄの本来の能力の差を評価することができなくなる。そのため、ＭＣＴＳではプレイアウトを百万回以上の単位で数多くの試行を繰り返す。しかし、プレイアウト部分の木構造の深さがあまりにも深い場合には、プレイアウトを数多く試行したとしても単純な辿り方による精度の悪化により求解精度を向上させることができない。【００１０】
そこで、本発明は、ＭＣＴＳを最適化問題に適用する際に、問題規模が大きい場合であっても、求解精度を向上させることができる最適化装置、最適化方法および最適化プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明による最適化装置は、最適化計算における解探索において、探索木中の選択肢となるノードの中からプレイアウトの実行対象となるノードを選択する選択部と、選択されたノードからプレイアウトを実行して解を探索する第一の計算部と、プレイアウト後の解を初期解とし、発見的手法、局所探索法または近傍探索法により解を探索する第二の計算部とを含むことを特徴とする。【００１２】
本発明による最適化方法は、最適化計算における解探索において、探索木中の選択肢となるノードの中からプレイアウトの実行対象となるノードを選択し、選択されたノードからプレイアウトを実行して解を探索し、プレイアウト後の解を初期解とし、発見的手法、局所探索法または近傍探索法により第二の解を探索することを特徴とする。【００１３】
本発明による最適化プログラムは、コンピュータに、最適化計算における解探索において、探索木中の選択肢となるノードの中からプレイアウトの実行対象となるノードを選択する処理と、選択されたノードからプレイアウトを実行して解を探索する処理と、プレイアウト後の解を初期解とし、発見的手法、局所探索法または近傍探索法により第二の解を探索する処理とを実行させることを特徴とする。
【発明の効果】
【００１４】
本発明によれば、ＭＣＴＳを最適化問題に適用する際に、問題規模が大きい場合であっても、求解精度を向上させることができる。
【図面の簡単な説明】
【００１５】
【図１】最適化システムの第１の実施形態の構成を示すブロック図である。
【図２】第１の実施形態における解探索の様子を示す説明図である。
【図３】計算部の第１の実施形態における動作を示すフローチャートである。
【図４】本発明による最適化装置の最小構成を示すブロック図である。
【図５】本発明による最適化装置の他の最小構成を示すブロック図である。
【図６】ＭＣＴＳを用いた最適化計算における解探索の様子を示す説明図である。
【発明を実施するための形態】
【００１６】
実施形態１．
以下、本発明の第１の実施形態を図面を参照して説明する。
【００１７】
図１は、最適化システムの第１の実施形態の構成を示すブロック図である。
【００１８】
図１に示すように、第１の実施形態における最適化システムは、ユーザ端末１と、最適化装置２とを備える。ユーザ端末１と最適化装置２とは、通信可能に接続される。なお、図１には１つのユーザ端末が例示されているが、ユーザ端末は最適化装置２にいくつ接続されていてもよい。
【００１９】
ユーザ端末１は、例えばパーソナルコンピュータ等の情報処理端末である。ユーザ端末１は、操作部１１と、表示部１２とを含む。
【００２０】
操作部１１は、実行する最適化計算に必要な情報（以下、最適化計算入力情報という。）を入力する。また、操作部１１は、実行指示を入力する。操作部１１は、最適化計算入力情報とともに実行指示を最適化装置２に出力する。
【００２１】
表示部１２は、最適化装置２から最適化計算結果の解を受け取り、表示する。
【００２２】
最適化装置２は、ＧＵＩ（Ｇｒａｐｈｉｃａｌ  Ｕｓｅｒ  Ｉｎｔｅｒｆａｃｅ）部２１と、計算部２２と、記憶部２３とを含む。
【００２３】
ＧＵＩ部２１は、ユーザ端末１の操作部１１から、最適化計算入力情報を受け取る。ＧＵＩ部２１は、最適化計算入力情報を計算部２２に伝達する。ＧＵＩ部２１は、計算部２２から最適化計算結果の解の集合を受け取り、ユーザ端末１の表示部１２へ伝達する。
【００２４】
計算部２２は、選択部２２１と、拡大部２２２と、シミュレーション部２２３と、評価値更新部２２４とを含む。
【００２５】
選択部２２１は、展開されたノードの中からプレイアウトの実行対象となるノードを選択する。以下、プレイアウトの実行対象となるノードを選択ノードという。
【００２６】
拡大部２２２は、探索木（ツリー）を拡大する。具体的には、拡大部２２２は、予め定められた基準に従って、選択部２２１で選ばれたノードを展開する必要があるか否かを判断し、必要となればさらに一段下位にノードを展開する。
【００２７】
シミュレーション部２２３は、シミュレーションを実行する。シミュレーション部２２３は、プレイアウト部２２３１、ヒューリスティクス計算部２２３２、ヒューリスティクス計算結果分析部２２３３を含む。
【００２８】
プレイアウト部２２３１は、プレイアウト、すなわち、ランダムシミュレーションのような単純な方法で１つの解を探索し、解の評価値を算出する。
【００２９】
ヒューリスティクス計算部２２３２は、プレイアウトで得た解を初期解とし、発見的手法で解を探索する。なお、ヒューリスティクス計算部２２３２は、発見的手法の他に、局所探索法や近傍探索法を用いて解を探索するようにしてもよい。
【００３０】
ヒューリスティクス計算結果分析部２２３３は、ヒューリスティクス計算途中の解改善の進捗を把握し、ヒューリスティクス計算の計算時間の上限（タイムリミット）を判断する。また、ヒューリスティクス計算結果分析部２２３３は、評価値更新部２２４における解の評価を更新する指標を計算する。なお、ヒューリスティクス計算結果分析部２２３３は、ヒューリスティクス計算の終了条件として、計算回数の上限など他の終了条件を用いるようにしてもよい。本実施形態では、計算時間の上限を用いる場合を例にする。
【００３１】
評価値更新部２２４は、プレイアウト部２２３１およびヒューリスティクス計算結果分析部２２３３から、解の評価値を得て、各ノードの評価値を計算し更新する。具体的には、評価値更新部２２４は、ノード情報記憶部２３２１が記憶する各ノードの評価値を更新する。各ノードの評価値は、繰り返し実行されるシミュレーションで得られた評価値を集めた統計値を含み、評価値更新部２２４は当該統計値を更新する。
【００３２】
なお、評価値更新部２２４は、ヒューリスティクス計算結果分析部２２３３のみから解の評価値を得るようにしてもよい。つまり、評価値更新部２２４は、プレイアウト部２２３１から得た解の評価値とヒューリスティクス計算結果分析部２２３３から得た解の評価値との両方を用いて各ノードの評価値を計算してもよいし、ヒューリスティクス計算結果分析部２２３３から得た解の評価値のみを用いて各ノードの評価値を計算してもよい。
【００３３】
記憶部２３は、データ記憶部２３１と、計算結果記憶部２３２とを含む。
【００３４】
データ記憶部２３１は、問題データ記憶部２３１１と、環境データ記憶部２３１２とを含む。
【００３５】
問題データ記憶部２３１１は、目的関数や制約条件を記憶する。最適化システムがスケジューリング問題に適用される場合には、問題データ記憶部２３１１は、タスク情報や担当者情報など、問題を解くために必要なデータ（以下、問題データという。）を記憶する。
【００３６】
環境データ記憶部２３１２は、例えばセンサ情報など、刻々と変化し最適化計算に影響がある環境情報を記憶する。
【００３７】
計算結果記憶部２３２は、ノード情報記憶部２３２１と、解情報記憶部２３２２とを含む。
【００３８】
ノード情報記憶部２３２１は、計算部２２での計算処理が進む際に、ノードの評価値など、変化する情報を記憶する。本実施形態では、ノード情報記憶部２３２１は、計算部２２が各計算途中で得たノードの探索回数や評価値を記憶する。
【００３９】
解情報記憶部２３２２は、計算部２２で求められた解の中で保持する必要のある解を記憶する。
【００４０】
なお、ＧＵＩ部２１、計算部２２は、例えば、最適化プログラムに従って動作するコンピュータによって実現される。この場合、最適化装置２が備えるＣＰＵが、最適化プログラムを読み込み、そのプログラムに従って、ＧＵＩ部２１および計算部２２として動作すればよい。また、ＧＵＩ部２１および計算部２２の各部が別々のハードウェアで実現されていてもよい。
【００４１】
また、問題データ記憶部２３１１、環境データ記憶部２３１２、ノード情報記憶部２３２１および解情報記憶部２３２２は、最適化装置２が備えるメモリ等の記憶装置によって実現される。
【００４２】
次に、本実施形態の動作を説明する。
【００４３】
図２は、第１の実施形態における解探索の様子を示す説明図である。図３は、計算部２２の第１の実施形態における動作を示すフローチャートである。
【００４４】
ここでは、図１に示す最適化システムがスケジューリング問題に適用される場合を例にする。
【００４５】
まず、ユーザがユーザ端末１の操作部１１に対して、最適化計算入力情報を入力する。ユーザは、最適化計算をしたいタスク、従事可能な担当者、各担当者がそれぞれのタスクに従事した時のコストや有効性などの問題データを最適化計算入力情報として入力する。このとき、ユーザは、最適化計算入力情報とともに実行指示を操作部１１に入力する。操作部１１は、最適化計算入力情報と実行指示とを最適化装置２に出力する。
【００４６】
最適化装置２のＧＵＩ部２１は、ユーザ端末１から最適化計算入力情報とともに実行指示を受け取ると、最適化計算入力情報を計算部２２へ伝達する。計算部２２は、最適化計算入力情報を入力する（ステップＳ１）。
【００４７】
ステップＳ１の後、計算部２２の選択部２２１は、展開されたノードの中から、シミュレーションすべきノードを選択する（ステップＳ２）。なお、初期状態ではノードは１つのみであるので、そのノードが選択対象となる。ノードの選択方法は、例えば、ＵＣＢなどの指標を基準とする。
【００４８】
拡大部２２２は、選択部２２１で選択されたノードのプレイアウト回数が、事前に定められた条件を満たした時に（ステップＳ３のＹｅｓ）、１段下位のノードまで展開する（ステップＳ４）。本実施形態では、拡大部２２２は、当該プレイアウト回数が予め定められた回数を超えた時にノードを展開する。なお、初期状態でノードが１つのみである時は、拡大部２２２は、この条件に関わらずノードを展開する。展開した場合には、拡大部２２２は、展開したノードのうちの１つを選択ノードとする。
【００４９】
シミュレーション部２２３のプレイアウト部２２３１は、選択ノードからプレイアウト、つまりランダムシミュレーションを実行し解を１つ探索する（ステップＳ５）。なお、１つの選択ノードに対して複数のシミュレーションを実行し複数の解を探索することも可能である。ここでは、もっとも単純な例として１つの選択ノードに対して１つのシミュレーションを実行し１つの解を探索する方法を説明する。本発明の技術的範囲は、１つの選択ノードに対して１つのシミュレーションを実行する形態に限定されない。従って、１つの選択ノードに対して複数のシミュレーションを実行する形態も本発明の技術的範囲に含まれ得る。
【００５０】
ヒューリスティクス計算部２２３２は、プレイアウト後の解、すなわちステップＳ５において探索された１つの解（ノード）を自身で行う計算の初期解として、ＳＡなどの発見的手法や局所探索法で、より良い解を探索し、計算し続ける（ステップＳ６）。なお、本実施形態では、プレイアウト部２２３１がプレイアウトを１回実行する度に、ヒューリスティクス計算部２２３２が、ヒューリスティクス計算を行っている。ただし、ヒューリスティクス計算部２２３２は、プレイアウト部２２３１が複数回プレイアウトを実行した後に、当該複数回のプレイアウトにより探索された解それぞれについてヒューリスティクス計算を行うようにしてもよい。また、ヒューリスティクス計算部２２３２は、当該複数回のプレイアウトにより探索された解のそれぞれを相対的に比較し、比較結果をもとに選択した解についてヒューリスティクス計算を行うようにしてもよい。そのような形態によれば、例えば、他の解よりも相対的に良いと判断した解のみをヒューリスティクス計算の対象とすることができ、計算時間を削減することができる。また、プレイアウト部２２３１がプレイアウトを１回行う度に、ヒューリスティクス計算部２２３２が、予め定められた基準に基づいてヒューリスティクス計算を実行するか否かを判定するようにしてもよい。ヒューリスティクス計算部２２３２は、例えば、プレイアウトにより探索された解の精度が予め定められた閾値より低い場合には、当該解についてのヒューリスティクス計算を実行しないようにしてもよい。
【００５１】
ヒューリスティクス計算結果分析部２２３３は、ヒューリスティクス計算部２２３２が計算し続けている間の計算結果、つまりヒューリスティクス計算の途中結果を取得する。ヒューリスティクス計算結果分析部２２３３は、ヒューリスティクス計算の途中結果と、過去のヒューリスティクス計算の結果とを比較して、ヒューリスティクス計算の計算時間の上限を終了条件として算出し、当該上限に達したか否かを判定する（ステップＳ７）。本実施形態では、ヒューリスティクス計算結果分析部２２３３は、ヒューリスティクス計算の途中結果と過去のヒューリスティクス計算の結果との差が予め定められた閾値以下の場合は、ヒューリスティクス計算の計算時間の上限を低くする。また、当該差が予め定められた閾値より大きい場合は、ヒューリスティクス計算結果分析部２２３３は、ヒューリスティクス計算の計算時間の上限を高くする。なお、計算時間の上限を低くするか高くするかを判定するための閾値は同じ値であってもよいし別々の値であってもよい。また、ヒューリスティクス計算結果分析部２２３３が、ヒューリスティクス計算の経過時間やヒューリスティクス計算途中の解改善の進捗などに応じて、当該閾値を変更するようにしてもよい。ヒューリスティクス計算結果分析部２２３３は、ヒューリスティクス計算の計算時間が上限に達した時には、ヒューリスティクス計算部２２３２に対して、計算の終了を指示する。
【００５２】
なお、ステップＳ７において、ヒューリスティクス計算結果分析部２２３３は、ヒューリスティクス計算の計算結果とともにプレイアウト部２２３１における計算結果を用いて、ヒューリスティクス計算の計算時間の上限を算出するようにしてもよい。
【００５３】
ヒューリスティクス計算部２２３２は、計算終了の指示が入力されたか否か、つまりヒューリスティクス計算を続けるか否かを判定する（ステップＳ８）。ヒューリスティクス計算部２２３２は、計算終了の指示が入力されていない場合、つまり、ヒューリスティクス計算を続ける場合は（ステップＳ８のＹｅｓ）、ステップＳ６の処理に戻る。計算終了の指示が入力された場合は（ステップＳ８のＮｏ）、ヒューリスティクス計算部２２３２はヒューリスティクス計算を終了する。
【００５４】
ヒューリスティクス計算結果分析部２２３３は、計算終了時の解の値を取得し、当該解の値とプレイアウト部２２３１における計算結果とを用いて、今回の選択ノードとその上位のノードに渡す評価値を計算する。なお、算出された評価値は、評価値更新部２２４における解の評価を更新する指標となる。
【００５５】
評価値更新部２２４は、ヒューリスティクス計算結果分析部２２３３からノードに渡す評価値を得て、選択ノードとその上位のノードの評価値を更新する（ステップＳ９）。
【００５６】
計算部２２は、計算部２２における計算時間が事前に定められた上限に達するまで、ステップＳ２〜Ｓ９の処理（選択処理、ツリー拡大処理、シミュレーション計算処理および評価値更新処理）を繰り返し実行する（ステップＳ１０）。つまり、当該計算時間が上限に達していない場合は（ステップＳ１０のＹｅｓ）、計算部２２はステップＳ２の処理に戻る。当該計算時間が上限に達した場合は（ステップＳ１０のＮｏ）、計算部２２は処理を終了する。なお、計算部２２は、計算時間ではなく、要件として与えられた解の値が算出されるまでステップＳ２〜Ｓ９の処理を繰り返し実行するようにしてもよい。
【００５７】
ステップＳ２〜Ｓ９の計算処理において、計算部２２は、環境データ記憶部２３１２から担当者の出社状況や、タスク処理に必要な機械の故障情報などを取得する。
【００５８】
また、ステップＳ２〜Ｓ９の計算処理において、計算部２２は、計算結果記憶部２３２のノード情報記憶部２３２１に、各計算途中で得たノードの探索回数や評価値を含む情報を格納する。また、計算部２２は解情報記憶部２３２２に、探索して得た解を含む情報を格納する。計算部２２は、ノード情報記憶部２３２１および解情報記憶部２３２２に格納された情報を取得することにより、計算途中における各ノードの探索回数や評価値を認識することができる。
【００５９】
計算部２２は計算を終了すると、最適化計算結果、つまり探索して得た解を示す解情報をＧＵＩ部２１に渡す。
【００６０】
ＧＵＩ部２１は、受け取った解情報をユーザ端末１の表示部１２に伝達する。
【００６１】
なお、本実施形態では、問題データがユーザ端末１から最適化計算入力情報として計算部２２に入力される場合を例にしたが、計算部２２は問題データ記憶部２３１１に格納された問題データを取得するようにしてもよい。そのような形態を実現するには、ユーザ等が予め問題データを問題データ記憶部２３１１に格納すればよい。
【００６２】
以上に説明したように、本実施形態では、プレイアウト後にヒューリスティクス計算部２２３２が発見的手法や局所探索でより良い解を計算する。従って、ヒューリスティクス計算を用いてより正確な比較でノードの優劣を判定することができる。それにより、最適化計算全体の解の精度を向上することができる。
【００６３】
また、本実施形態では、ヒューリスティクス計算結果分析部２２３３が、ヒューリスティクス計算の途中結果と、過去のヒューリスティクス計算の結果を比較することで、ヒューリスティクス計算のタイムリミットを調整する。従って、無駄な計算時間を削減し、計算時間の増大を防ぐことができる。それにより、シミュレーション回数の減少を抑えることができ、より良い解を得る可能性を増やすことができる。
【００６４】
また、本実施形態では、プレイアウト部２２３１と、ヒューリスティクス計算結果分析部２２３３の両方の結果を用いて評価値更新部２２４が各ノードの評価値を更新する。それにより、各ノードでの公平な評価（プレイアウト結果の評価）と、より高い精度の解を得るための評価（ヒューリスティクス計算結果の評価）とを同時に実行することができる。
【００６５】
このように、本実施形態によれば、ＭＣＴＳを最適化問題に適用する際に、俯瞰的なＭＣＴＳと、問題規模が大きい場合に特に有効となる局所的な発見的手法（ヒューリスティクス）とを組み合わせることにより、問題規模が大きい場合であっても求解精度を向上させることができる。
【００６６】
なお、本実施形態では、最適化装置２がスケジューリング問題に適用される場合を例にしたが、本発明の適用範囲はその限りではない。本発明は、タスクを担当者に割り当てるスケジューリング問題などの組合せ最適化問題を中心に、最適化問題全般に適用することが可能である。
【００６７】
図４は、本発明による最適化装置の最小構成を示すブロック図である。図５は、本発明による最適化装置の他の最小構成を示すブロック図である。
【００６８】
図４に示すように、本発明による最適化装置は、最適化計算における解探索において、探索木中の選択肢となるノードの中からプレイアウトの実行対象となるノードを選択する選択部１０１（図１に示す最適化装置２における計算部２２の選択部２２１および拡大部２２２に相当。）と、選択されたノードからプレイアウトを実行して解を探索する第一の計算部１０２（図１に示す最適化装置２における計算部２２のシミュレーション部２２３のプレイアウト部２２３１に相当。）と、プレイアウト後の解を初期解とし、発見的手法、局所探索法または近傍探索法により解を探索する第二の計算部１０３（図１に示す最適化装置２における計算部２２のシミュレーション部２２３のヒューリスティクス計算部２２３２およびヒューリスティクス計算結果分析部２２３３に相当。）とを含む。
【００６９】
そのような構成によれば、ＭＣＴＳを最適化問題に適用する際に、俯瞰的なＭＣＴＳと、問題規模が大きい場合に特に有効となる局所的な発見的手法（ヒューリスティクス）、局所探索法または近傍探索法とを組み合わせることにより、問題規模が大きい場合であっても求解精度を向上させることができる。発見的手法等により正確な比較でノードの優劣を判定することができるからである。
【００７０】
上記の実施形態には、図５に示すように、以下のような最適化装置も開示されている。
【００７１】
（１）第二の計算部１０３が、第一の計算部１０２が探索した解と当該第二の計算部１０３が探索した解とをもとに、当該第二の計算部１０３における計算時間の終了条件を算出し、終了条件が満たされたときに当該第二の計算部１０３における計算処理を終了する最適化装置。
【００７２】
そのような構成によれば、無駄な計算時間を削減し、計算時間の増大を防ぐことができる。それにより、シミュレーション回数の減少を抑えることができ、より良い解を得る可能性を増やすことができる。
【００７３】
（２）第一の計算部１０２が探索した解の評価値と第二の計算部１０３が探索した解の評価値との両方、または、第二の計算部１０３が探索した解の評価値のみをもとに、各ノードの評価値を更新する評価値更新部１０４（図１に示す最適化装置２における計算部２２の評価値更新部２２４に相当。）を含む最適化装置。
【００７４】
そのような構成によれば、各ノードでの公平な評価（プレイアウト結果の評価）と、より高い精度の解を得るための評価（ヒューリスティクス計算結果の評価）とを同時に実行することができる。
【００７５】
（３）第二の計算部１０３が、第一の計算部１０２が実行したプレイアウトにより探索された解のうち予め定められた基準を満たす解に対して、または、第一の計算部１０２が実行した複数回のプレイアウトにより探索された各解のうち当該各解を相対的に比較した結果をもとに選択した解に対して、発見的手法、局所探索法または近傍探索法による解の探索を行う最適化装置。
【００７６】
そのような構成によれば、各プレイアウトにより探索された解のうち予め定められた基準を満たす解のみをヒューリスティクス計算の対象とすることができる。また、複数回プレイアウトを実行した後に当該複数回のプレイアウトにより探索された解に対してヒューリスティクス計算を行う場合にも、他の解との相対的な比較により選択した解、例えば、他の解よりも相対的に良いと判断した解のみをヒューリスティクス計算の対象とすることができる。それにより、無駄な計算時間をより削減することができる。
【００７７】
以上、実施形態及び実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００７８】
この出願は、２０１２年１２月５日に出願された日本特許出願２０１２−２６６５９７を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【００７９】
１  ユーザ端末
２  最適化装置
１１  操作部
１２  表示部
２１  ＧＵＩ部
２２  計算部
２３  記憶部
１０１、２２１  選択部
１０２  第一の計算部
１０３  第二の計算部
１０４  評価値更新部
２２２  拡大部
２２３  シミュレーション部
２２４  評価値更新部
２３１  データ記憶部
２３２  計算結果記憶部
２２３１  プレイアウト部
２２３２  ヒューリスティクス計算部
２２３３  ヒューリスティクス計算結果分析部
２３１１  問題データ記憶部
２３１２  環境データ記憶部
２３２１  ノード情報記憶部
２３２２  解情報記憶部
【図１】
2014087590.tif 000003
【図２】
2014087590.tif 000004
【図３】
2014087590.tif 000005
【図４】
2014087590.tif 000006
【図５】
2014087590.tif 000007
【図６】
2014087590.tif 000008
【国際調査報告】
2014087590.tif 000009
2014087590.tif 000010
2014087590.tif 000011
2014087590.tif 000012