[
新入生募集]
[JAIST]
[研究テーマ]
[研究室の運営方針]
[プロジェクト]
[メンバー]
[社会人学生ゼミ]
[出版リスト]
[最近の活動]
[写真]
[連絡先]
[english]
解説：離散事象シミュレーション(discrete-event simulation)
北陸先端科学技術大学院大学
知識科学研究科
内平直志
はじめに
オートマトン、ペトリネット、待ち行列理論など離散事象システムの数学的モデル化および解析手法は数多く提案されている。
しかし、数学的モデルは適用可能な範囲が限定されており、現実の複雑なシステムには適用できない場合が多い。
シミュレーションは操作的意味論(operational semantics)を持つすべての離散事象システムに適用可能な解析手段である。
ここで、「操作的意味論を持つ」とは、モデルの動的挙動が厳密に定義されていることであり、
通常のプログラミング言語で記述可能なシミュレーションモデルは操作的意味論を持つ。
離散事象シミュレーションは、工場生産シミュレーション、計算機ネットワークシミュレーション、
交通シミュレーションなど様々な分野で幅広く使われている（表１）。シミュレーションの目的は、
現実世界では実現が難しい様々な条件下でのシステムの挙動を計算機上で擬似的に再現し、
その結果を解析することによりシステムの機能及び性能を理解することにある。
純粋に実在するシステムの性質をシミュレーションで把握することが目的の場合もあるが、
多くの場合はシミュレーションの解析結果を新規設計や設計変更にフィードバックすることを目的としている。
表１：離散事象シミュレーション活用事例
| 工場 | 工場生産ライン設計、生産スケジューリング |
| 交通・物流 | 高速道路渋滞予測、道路合流分岐地点行動解析、バス・トラック運行計画作成 |
| 防災 | 避難誘導シミュレーション |
| 制御システム | エレベータの群管理方式設計、プラントシミュレータを用いたシーケンス制御ソフトウェアの試験 |
| 経営・経済 | 新規事業の収益予測、株式市場シミュレーション |
基本的挙動
離散事象システムでは、システムの状態変化を引き起こす事象(event)が時間軸上の不連続で離散的な時点で生起する。
離散時点の取り方には、一定の時間間隔で状態の変化がおきる時間駆動型(time-stepped)と事象の発生を
トリガーとして状態の変化がおきる事象駆動型(event-driven) がある。
いずれの場合も離散事象シミュレーションの実行は下記のステップを繰り返すことで実現される。
(Step1)シミュレーション時刻(simulation clock)を次の離散時点に進める、
(Step2)新しい時刻で生起可能な事象をすべて取り出す、
(Step3)各事象の生起に伴う処理を実行し、システムの状態を変化させる。
ここで、Step2における事象の生起が確率的か否かにより、確率的シミュレーションと
確定的シミュレーションに分類できる。通常、離散事象シミュレーションでシステムの性能解析を行う場合には、
確率的に生起する事象を含む場合が多い。事象の確率的生起の実現には乱数を用いるが、
乱数を用いたシミュレーションをモンテカルロ・シミュレーション(Monte Carlo simulation)と呼ぶこともある。
モデル化手法
離散事象シミュレーションのモデル化手法には、事象指向(event-oriented)とプロセス指向(process-oriented)およびオブジェクト指向(object-oriented)がある。
モデル化手法の選択をワールドビュー(world view)の決定と呼ぶ。
事象指向モデルは、前述の離散事象シミュレーションの基本的挙動を直接表現したもので、
システムの状態変数の集合、事象の集合、事象ハンドラーの集合（事象の生起条件と生起時の状態変化を記述）から構成される。
事象指向モデルの一例としては、事象ハンドラーをＩＦ−ＴＨＥＮルールで表現する
プロダクションシステム(production system)がある。
事象指向モデルは原始的なモデルであり、プロセス指向モデルやオブジェクト指向モデルも内部的には
事象指向モデルに翻訳されて実行される。
プロセス指向モデルでは、システムを構成する要素(entity)の一連の振る舞いをプロセスとして記述する。
プロセス記述の一例としては、要素の個々の振る舞い（生成、消滅、滞留、リソース確保、等）をネットワーク上のノードで表現し、
ネットワーク上を要素が時間の経過ともに移動することで一連の振る舞いを表現するネットワークモデルがある。
オブジェクト指向モデルでは、システムを相互に作用するオブジェクトの集合としてモデル化する。
現実のシステムの行動主体をオブジェクト指向モデルのオブジェクトに自然に対応させることができ、
抽象データ型などの採用により保守性に優れる。なお、近年広く普及しているオブジェクト指向プログラミング言語は、
離散事象シミュレーション言語として紹介されることが多いSIMULAをルーツの１つとしている。
シミュレーション言語およびツール
離散事象シミュレーションの実現方法としては、（１）通常のプログラミング言語、（２）シミュレーション言語、（３）汎用シミュレータ構築ツール、（４）アプリケーション特化シミュレータ構築ツール、がある。通常のプログラミング言語を用いれば、任意の仕様のシミュレータを構築できるが、プログラムの生産性が悪い。そこで、多くのシミュレーション言語が商用化されている。代表的な言語としては、GPSS、SIMSCRIPT、SIMULA、SLAMなどがある。汎用シミュレータ構築ツールは、言語を意識せずにビジュアルかつインタラクティブにシミュレータを構築する環境である。たとえば、SLAMに基づくシミュレーションプログラム開発をビジュアルに支援するVisual SLAM、状態遷移表現に基づくツールStatemate、一般化確率ペトリネットに基づくツールGreatSPNなどがある。また、工場、交通など分野を特化することにより、部品の組み合わせで簡単にシミュレータを構築できるツールも数多く提案されている。
結果の解析
確率的シミュレーションにおいては、シミュレーションの結果が毎回異なる。そこでシミュレーションを十分な回数繰り返し行うことにより、統計的に意味のある結論を得る。特に、有限長のシミュレーション結果に関しては統計的な信頼区間を求めることが可能である。また、確率的要素の分散を意図的に小さくすることで、同じ計算時間内でも精度のよい信頼区間を求める方法がいくつか提案されており、分散減少法(variance reduction methods)と呼ばれている。
最近の話題
並列離散事象シミュレーション (parallel discrete event simulation)
並列計算機環境でシミュレーションを実行することにより、シミュレーションの高速化を達成できる。ここで、異なる計算機で処理される事象間に因果関係がある場合の効率的な同期制御が課題であるが、先行実行と後戻りを組み合わせたタイムワープ(time warp)法などが提案されている。
分散シミュレーション (distributed simulation)
複数の独立したモデルのシミュレータをネットワークで接続し協調動作させることにより、要素が複雑に絡み合った世界のシミュレーションを行うことができる。具体的事例としては、軍事用シミュレータや大規模交通シミュレータがある。HLA (High Level Architecture)は、異機種間のシミュレータを統合するための標準アーキテクチャであり、ルール、インターフェイス、オブジェクトモデルテンプレートの３つの仕様から構成されている。現在、IEEEにおいて標準化が進められている。
マルチエージェントシミュレーション (multi-agent simulation)
個体をエージェントとしてモデル化することにより、多数の個体で形成される全体システムのシミュレーションを行うことができる。特に、全体システムが個体の特性に還元できない集合的な特性（創発的特性）を示す場合に、そのシステムをマルチエージェントシミュレーションとして定式化し、創発的特性(emergent property)を再現し解析する試みが行われている。具体的には、人工生命と呼ばれる生態系のシミュレーションや人工経済や人工市場と呼ばれる社会システムのシミュレーションがある。
網羅的シミュレーション (exhaustive simulation)
確率的シミュレーションでは、すべてのシナリオを網羅的に実行するわけではない。
生起確率が低いシナリオに関しては見落とす可能性が高い。近年、計算機性能の著しい向上により、
有限状態を持つ離散事象システムのすべてのシナリオを網羅的にシミュレーションするアプローチが
注目されている[内平96] 。通常、起こりうるシナリオの数は膨大になるが、シミュレーションモデルの
依存関係を解析することにより、網羅性を保証しつつ冗長なシミュレーションを枝刈りする手法が提案されており、
半順序法(partial order method)と呼ばれている。
[参考文献]
本解説は，筆者が執筆した
「機械工学便覧 デザイン編 β6 制御システム」
の「7・4・5 離散事象シミュレーション」をベースに，適宜内容に関するメンテナンスを行ったものである．