(57)【要約】【課題】本開示は、得られるサンプルの統計的正しさを犠牲にすることなく、シミュレーション時間を短縮することを目的とする。【解決手段】本開示は、ある状態に対する遷移先の状態（Ｓ０，Ｓ１，Ｓ３）を取得すると、乱数値が位置に対応付けられた乱数領域の行（Ｒ１）を生成し、各状態の範囲が各状態の遷移確率と一致するように、取得した各状態を行（Ｒ１）の乱数領域上に割り当てる遷移先状態追加ステップと、生成された乱数領域が異なりかつ状態が共通する状態ペア（Ｓ１）について、乱数領域における重複位置が広がるように、遷移先状態追加ステップで生成された乱数領域に含まれる状態Ｓ０及び状態Ｓ１同士の位置を入れ替える乱数位置変更ステップと、乱数位置変更ステップで位置を入れ替えた各状態に割り当てられている乱数値を用いて状態遷移を行うシミュレーション方法である。【選択図】図５
2018036829.tif 000002
【特許請求の範囲】
【請求項１】
遷移先の状態を取得すると、乱数値が位置に対応付けられた乱数領域を生成し、各状態の範囲が各状態の遷移確率と一致するように、取得した各状態を乱数領域上に割り当てる遷移先状態追加部と、
前記遷移先状態追加部で生成された乱数領域が異なりかつ状態が共通する状態ペアについて、乱数領域における重複位置が広がるように、前記遷移先状態追加部で生成された乱数領域に含まれる状態同士の位置を入れ替える乱数位置変更部と、を備え、
前記乱数位置変更部が位置を入れ替えた各状態に割り当てられている乱数値を用いて状態遷移を行う、
シミュレーション装置。
【請求項２】
前記状態ペアが複数存在する場合、前記乱数位置変更部は、状態ペアごとに重複領域を計算し、全ての状態ペアに対する和が最大になるように、前記遷移先状態追加部で生成された乱数領域に含まれる状態同士の位置を入れ替える、
請求項１に記載のシミュレーション装置。
【請求項３】
遷移先の状態を取得すると、乱数値が位置に対応付けられた乱数領域を生成し、各状態の範囲が各状態の遷移確率と一致するように、取得した各状態を乱数領域上に割り当てる遷移先状態追加ステップと、
前記遷移先状態追加ステップで生成された乱数領域が異なりかつ状態が共通する状態ペアについて、乱数領域における重複位置が広がるように、前記遷移先状態追加ステップで生成された乱数領域に含まれる状態同士の位置を入れ替える乱数位置変更ステップと、を備え、
前記乱数位置変更ステップで位置を入れ替えた各状態に割り当てられている乱数値を用いて状態遷移を行う、
シミュレーション方法。
【請求項４】
コンピュータを、請求項１又は２に記載の各機能部として機能させるためのシミュレーションプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、シミュレーション装置、シミュレーション方法及びシミュレーションプログラムに関する。
【背景技術】
【０００２】
パーフェクトシミュレーション（例えば、非特許文献１参照。）は、同じ乱数列に従ういくつかの状態遷移過程が「合体（合流）」するまでシミュレーションを進めることで、初期状態から独立した「統計的に正しいサンプル」を得る技法である。図１に、状態遷移過程の一例を示す。０からｎまでの状態番号を有する全状態Ｓが、乱数により遷移させることで徐々に一致していき、Ｍステップの状態遷移を繰り返した後に、１つの状態に合体（合流）する。典型的には、図１に示すように、最大の状態Ｓｎと最小の状態Ｓ０の２状態から遷移を開始する（ここでは状態の大小関係を所与とする）。
【０００３】
パーフェクトシミュレーションは「正しいサンプル」を得られる点で優れたシミュレーション技法である。しかし、状態遷移過程が「合体（合流）」するまでシミュレーションを進めるため、計算時間を要する問題がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｊ．  Ｍ．  Ｖｉｎｃｅｎｔ  ａｎｄ  Ｃ．  Ｍａｒｃｈａｎｄ，  “Ｏｎ  ｔｈｅ  ｅｘａｃｔ  ｓｉｍｕｌａｔｉｏｎ  ｏｆ  ｆｕｎｃｔｉｏｎａｌｓ  ｏｆ  ｓｔａｔｉｏｎａｒｙ  Ｍａｒｋｏｖ  ｃｈａｉｎｓ，”  Ｌｉｎｅａｒ  Ａｌｇｅｂｒａ  ａｎｄ  ｉｔｓ  Ａｐｐｌｉｃａｔｉｏｎｓ，  ｖｏｌ．  ３８６，  ｐｐ．  ２８５−３１０，  ２００４．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本開示は、得られるサンプルの統計的正しさを犠牲にすることなく、シミュレーション時間を短縮することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、本開示は、パーフェクトシミュレーションにおいて、任意性のある乱数の値と遷移先との対応関係を決定する際に、乱数の値に対して隣り合う状態ペアを交換すると遷移先の状態が一致する（重複する）領域が大きくなる場合に当該状態ペアを交換する処理を各状態ごとにすべての隣接状態ペアについて繰り返し実行する。
【０００７】
具体的には、本開示に係るシミュレーション装置は、
遷移先の状態を取得すると、乱数値が位置に対応付けられた乱数領域を生成し、各状態の範囲が各状態の遷移確率と一致するように、取得した各状態を乱数領域上に割り当てる遷移先状態追加部と、
前記遷移先状態追加部で生成された乱数領域が異なりかつ状態が共通する状態ペアについて、乱数領域における重複位置が広がるように、前記遷移先状態追加部で生成された乱数領域に含まれる状態同士の位置を入れ替える乱数位置変更部と、を備え、
前記乱数位置変更部が位置を入れ替えた各状態に割り当てられている乱数値を用いて状態遷移を行う。
【０００８】
具体的には、本開示に係るシミュレーション方法は、
遷移先の状態を取得すると、乱数値が位置に対応付けられた乱数領域を生成し、各状態の範囲が各状態の遷移確率と一致するように、取得した各状態を乱数領域上に割り当てる遷移先状態追加ステップと、
前記遷移先状態追加ステップで生成された乱数領域が異なりかつ状態が共通する状態ペアについて、乱数領域における重複位置が広がるように、前記遷移先状態追加ステップで生成された乱数領域に含まれる状態同士の位置を入れ替える乱数位置変更ステップと、を備え、
前記乱数位置変更ステップで位置を入れ替えた各状態に割り当てられている乱数値を用いて状態遷移を行う。
【０００９】
具体的には、本開示に係るシミュレーションプログラムは、本開示に係るシミュレーション装置に備わる各機能部としてコンピュータを機能させるためのプログラムであり、本開示に係るシミュレーション方法に備わる各ステップをコンピュータに実行させるためのプログラムである。
【発明の効果】
【００１０】
本開示によれば、得られるサンプルの統計的正しさを犠牲にすることなく、遷移過程が「合体」するまでの期待ステップ数を削減することができ、シミュレーション時間を短縮することができる。
【図面の簡単な説明】
【００１１】
【図１】パーフェクトシミュレーションによるサンプルの一例を示す。
【図２】２状態システムの一例を示す。
【図３】乱数と遷移先の対応関係の一例を示す。
【図４】装置構成図の一例を示す。
【図５】フローチャートの一例を示す。
【図６】乱数と遷移先の最適化の一例を示す。
【発明を実施するための形態】
【００１２】
以下、本開示の実施形態について、図面を参照しながら詳細に説明する。なお、本開示は、以下に示す実施形態に限定されるものではない。これらの実施の例は例示に過ぎず、本開示は当業者の知識に基づいて種々の変更、改良を施した形態で実施することができる。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００１３】
まず、図２に示す２状態のシステムを考える。パーフェクトシミュレーションを行うために、状態Ｓ０と状態Ｓ１それぞれから遷移を開始する。本実施形態では、図３に示すように、乱数値が位置に対応付けられた乱数領域を１次元の「行」で表記する。行の長さは乱数値の幅を示す。例えば０〜１の乱数値を用いる場合、図３に示すように、行の左端が乱数値「０」を示し、行の右端が乱数値「１」を示し、左から右に順に乱数値が高くなる。
【００１４】
この「０」と「１」の乱数値の間に、各遷移先状態Ｓ０及びＳ１を、各状態の遷移確率に応じた幅で配置する。例えば、図２に示すように、状態Ｓ０から状態Ｓ０への遷移確率は０．４であり、状態Ｓ０から状態Ｓ１への遷移確率は０．６である場合、遷移先状態Ｓ０の幅Ｗ００と遷移先状態Ｓ１の幅Ｗ０１の比率は２対３になる。状態Ｓ１から状態Ｓ１への遷移確率は０．７であり、状態Ｓ１から状態Ｓ０への遷移確率は０．３である場合、遷移先状態Ｓ１の幅Ｗ１１と遷移先状態Ｓ０の幅Ｗ１０の比率は７対３になる。
【００１５】
乱数値が０．１であれば、状態Ｓ０、Ｓ１とも現在の状態に留まり、遷移過程は合体しない。乱数値が０．９であれば、状態Ｓ０はＳ１に遷移し、状態Ｓ１はＳ０に遷移する。つまり、状態が入れ替わり、やはり合体しない。乱数値が０．５であれば、状態Ｓ０はＳ１に遷移し、状態Ｓ１はそのまま留まるため、２つの遷移過程は合体してシミュレーションは終わる。このように、図３の例では、２つの遷移過程が合体する乱数値の範囲αは０．３である。ただし、図３の例では状態Ｓ１でしか合体しないが、非特許文献１に開示されている技術を用いることで、このような偏りを解消することは可能である。
【００１６】
ここで、乱数の値と遷移先状態の対応関係には任意性があることに注目する。つまり、図２の遷移確率を満たしていれば、図３以外にも無数の対応関係を利用できる。直観的には、なるべく同じ状態に遷移するように乱数を割り当てればよいと予想される。つまり、図３に示したαが大きくなるようにすればよい。なお、乱数の範囲を［０，１］とするときは、αは同じ状態に遷移する「確率」となる。
【００１７】
２状態の場合、この直感を解析的に証明できる。遷移先が一致する確率をαとする。遷移先の状態は、状態Ｓ０でもＳ１でもよい。いずれの状態でも合体しうるときは、それぞれの重複領域の和をαとする。ｉステップで合体する確率Ｐ（ｉ）は、
（数１）
Ｐ（ｉ）＝（１−α）ｉ−１α    （１）
なので、合体までのステップ数の期待値Ｅは、
【数２】
2018036829.tif 000003
となる。つまり、αが大きいほど期待ステップ数が小さく、早く合体できる。
【００１８】
状態数が２より大きい場合、状態ペアごとに重複領域を計算し、全ペアに対する和をαとすればよい。状態数が２より大きくても、なるべく同じ状態に遷移するように乱数を割り当てることで、合体までの期待ステップ数を削減できると予想される。
【００１９】
また、乱数割り当てを「オンデマンド」に決められることが望ましい。というのは、システムが取り得る状態のうち、シミュレーションで訪問するのは一部だけであるため、事前に全状態について乱数を割り当てるのは無駄だからである。新しい状態を訪問するたびに、オンデマンドで乱数を割り当てていくようにする。
【００２０】
以下、αの最大化とオンデマンドの動作を実現する乱数割り当て方法を述べる。なお、同じ状態に遷移するような乱数の割り当て方は、他にもいろいろ考えられる。
【００２１】
図４に、実施形態に係るシミュレーション装置の構成例を示す。実施形態に係るシミュレーション装置は、遷移先状態追加部として機能する行追加部１１、乱数位置変更部として機能する隣接状態交換部１２、α計算部１３、遷移確率格納部１４、乱数割り当て表１５を備える。
【００２２】
図５は、実施形態に係るシミュレーション方法の一例を示すフローチャートである。実施形態に係るシミュレーション方法は、遷移先状態追加ステップ（Ｓ１０１）及び乱数位置変更ステップ（Ｓ１０２〜Ｓ１０４）を順に実行する。
【００２３】
以下、図６の例を用いて具体的に説明する。このシステムは、状態Ｓ０から状態Ｓ３までの４状態を持つ。遷移後の状態を示す行Ｒ０の後に新たな状態を訪問した場合、行追加部１１が遷移先状態追加ステップ（Ｓ１０１）を実行して行Ｒ１を追加する。例えば、新たな状態が状態Ｓ０、Ｓ１、Ｓ３を有する場合、行Ｒ１は、各状態Ｓ０、Ｓ１、Ｓ３を含む。
【００２４】
行追加部１１は、遷移確率格納部１４から状態Ｓ０、Ｓ１、Ｓ３の各遷移確率を取得し、取得した状態遷移確率に従うように、行Ｒ１における状態Ｓ０、Ｓ１、Ｓ３の幅を割り当てる。また、乱数割り当て表１５に従うように、行Ｒ１における状態Ｓ０、Ｓ１、Ｓ３の位置を割り当てる。
【００２５】
ここで、行Ｒ１における位置は、図３において説明したように、乱数の値に対応している。乱数割り当て表１５に従う乱数の割り当て方法は任意であるが、例えば、状態番号の小さい順に、又は、遷移確率の小さい順に、小さな乱数の値を割り当てる。
【００２６】
次に、乱数位置変更ステップでは、隣接状態交換部１２が、交換していない状態のペアが残っているか否かを判定し（Ｓ１０２）、残っている場合に、追加した行Ｒ１に含まれる隣り合う状態を交換する。α計算部１３は、交換後のαの値を計算する。隣接状態交換部１２は、交換前後のαを比較し（Ｓ１０３）、交換後のαが交換前よりも大きくなるようなら、交換を採用する（Ｓ１０４）。
【００２７】
例えば、図６（ａ）に示す行Ｒ１における状態Ｓ０と状態Ｓ１を交換すると、図６（ｂ）に示すようにαが大きくなるため、交換を実施する。この後、追加した行Ｒ１に含まれる状態Ｓ０と状態Ｓ３を交換した場合のαを判定する（Ｓ１０２、Ｓ１０３）。状態Ｓ０と状態Ｓ３を交換してもαは大きくならないため、これらは交換せず、交換前に戻す。このように、新たな状態の行を追加したら、すべての隣り合う状態間でこのような交換を試してみる。
【００２８】
（本開示によって生じる効果）
本開示は、乱数領域における位置が重なるように、乱数領域に割り当てられている状態同士の位置を入れ替えるため、遷移先が一致する確率αを高めることができる。このため、本開示は、パーフェクトシミュレーションで遷移過程が「合体」するまでの期待ステップ数を削減し、シミュレーション時間を短縮することができる。なお、このとき、得られるサンプルの統計的正しさはまったく犠牲にしていない。
【００２９】
本実施形態の装置はコンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【産業上の利用可能性】
【００３０】
本開示は情報通信産業に適用することができる。
【符号の説明】
【００３１】
１１：行追加部
１２：隣接状態交換部
１３：α計算部
１４：遷移確率格納部
１５：乱数割り当て表
【図１】
2018036829.tif 000004
【図２】
2018036829.tif 000005
【図３】
2018036829.tif 000006
【図４】
2018036829.tif 000007
【図５】
2018036829.tif 000008
【図６】
2018036829.tif 000009