魅力的なPython: 複雑なモデルをシンプルにするSimPy
離散的、同時発生事象のシミュレーションは、面白くもあり、役にも立つ
私がSimPyというパッケージを知ったのは、その製作者の一人であるKlaus Müller氏が私に連絡してきたときでした。Müller博士は、Python 2.2+ のジェネレーターを使って半コルーチンや「無重量」スレッドを実装する手法を紹介した魅力的なPython の記事を読んで連絡してきたのでした。とりわけ、私を喜ばせたのは、「これらの手法がSimula-67スタイルのシミュレーションをPythonで実装するのに役に立つ」と彼が話してくれたことでした。
それ以前にTony VignauxとChang Chuiが別のPythonライブラリーを作成していることも分かりました。それは、考え方としてはSimscriptに近く、私の半コルーチンの手法ではなく、標準的なスレッド処理を利用するものでした。このグループは、共同で開発を進め、ジェネレーターを利用するスタイルのほうが、ずっと効率的であると考え、最近、SourceForgeで、SimPyと呼ばれるGPLプロジェクトを立ち上げ (SimPyのホームページへのリンクは、参考文献を参照)、それが現在ではベータ段階になっています。Vignaux教授は、将来、ウェリントンにあるビクトリア大学での教育に、この統合化されたSimPyパッケージを使用したいと考えています。私は、このライブラリーが、さまざまな応用問題にも充分利用できるのではないかと思います。
最近の意見交換や研究について紹介する前に、私にはプログラミングの1分野であるシミュレーションについての予備知識がないことをお断りしておきたいと思います。本稿の読者も、ほとんどは、そのような予備知識がないのではないでしょうか。このようなスタイルのプログラミングの考え方には目新しい面があるかもしれませんが、資源の制約される現実のシステムの動作を理解するときに、シミュレーションは有効です。バンド幅の制約されたネットワーク、自動車の交通現象、マーケットや商業の最適化、生物学的 / 進化論的相互作用、あるいはその他の「確率論的」システムのいずれに関心があるにしろ、SimPyは、そうしたモデリング用の簡単なPythonツールとして利用することができます。
本稿では、食料雑貨店にレジの通路が何本かあるという非常に単純な状況を例にとることにします。今回紹介するシミュレーションを使うことで、スキャナーの技術や買物客の傾向、必要な人員配置などをいろいろと変化させてみたときに、経済的意味付けや待ち時間に関してどんなことが起こるのかという疑問に答えることができます。こうしたモデリングを行うことの良い点は、いろいろと変化させてみたときにどんなことが起こるのかを明確に把握することができ、前もって方針決定を行うことができるということです。もちろん、ほとんどの読者は、食料雑貨店を経営するわけではありませんが、この手法は、さまざまな種類のシステムに広く応用できます。
シミュレーションの考え方
SimPyライブラリーには、3つの抽象 / 親クラスが用意されていますが、これらは、シミュレーションの基本的な3つの考え方に対応しています。その他の数多くの関数や定数は、シミュレーションの実行を制御するために使われるもので、重要な概念は、これら3つのクラスで表現されています。
シミュレーションで中心となる考え方は、プロセス です。プロセスとは、何かを行い、ときには、次に何かを行う準備ができるまでの間待機するオブジェクトのことです。SimPyでは、プロセスを「非活性化する (passivate)」こともできます。つまり、そのプロセスは、別のプロセスから何か行うように呼び出されるまでは、何も行わないようになります。プロセスは、目的を達成しようとしているものとして捉えると、理解し易くなる場合がよくあります。多くの場合、プロセスは、ループとしてプログラムされ、ループの中で、いろいろなアクションが実行されます。個々のアクションの間には、Pythonのyield文が挿入されますが、これは、制御を戻すまでの間、待機中の各プロセスのアクションをシミュレーション・スケジューラーに実行させるためのものです。
プロセスが実行するアクションの多くは、資源 の使用状況に依存します。資源とは、簡単に説明するならば、使用可能かどうかが制限されているもののことです。生物学的モデルの場合、たとえば、食料供給が資源となるでしょうし、ネットワーク・モデルの場合、ルーターや有限なバンド幅のチャネルを資源として考えることができるでしょう。われわれのマーケットのシミュレーションの場合、レジの通路が資源となります。資源が行う唯一のことは、それを同時に1個のプロセスにしか使わせないということです。SimPyのプログラミング・モデルでは、ある資源をどれだけの期間保持したいかは、プロセスだけが決定でき、資源自体は、まったく受動的な存在です。現実のシステムでは、SimPyのモデルが、概念的な仕組みに合う場合もあれば、合わない場合もあるでしょうが、資源が本来その利用を制限するものであることは、容易に想像できます (たとえば、要求された時間内に満足できる反応が得られない場合には、接続を切断するサーバー・コンピューターなど)。しかし、プログラミングの観点からすれば、プロセスと資源のどちらが「能動的な」分子 ("active" party) なのかということは大して重要な問題ではありません (ただ、どのようにしたいのかをはっきりさせておけばよいだけのことです)。
SimPyの最後のクラスは、モニター です。モニターは、さして重要なものではなく、単に便宜的なものです。モニターが行うことは、報告されてくるイベントを記録し、それらのイベントについての統計 (平均、回数、分散など) を保存することだけです。SimPyに用意されているMonitor クラスは、シミュレーションの測定値を記録するのに都合のよいツールですが、必要なら、別の方法でイベントを記録することもできます。実際、私の例では、Monitor のサブクラスを作成し、いくつかの機能を (少し) 拡張しています。
店の設定: シミュレーションのプログラミング
私の記事では、たいてい、サンプル・アプリケーションを一挙に紹介するのが常ですが、今回は、食料雑貨店アプリケーションを順を追って説明したほうが、有益だと思います。皆さんは、必要なら、各部をつなぎ合わせていけばよいでしょう。SimPyの製作者は、今回の例題を、将来のバージョンに含めることにしています。
SimPyのシミュレーションの第1番目の部分には、一般的なインポート文をいくつか記述します。
リスト1. SimPyライブラリーのインポート
#!/usr/bin/env python from __future__ import generators from SimPy import Simulation from SimPy.Simulation import hold, request, release, now from SimPy.Monitor import Monitor import random from math import sqrt
SimPyに添付されているサンプルには、import * というスタイルを使用しているものもありますが、ここでは、私が占めている名前空間をより明示的に記述する方法のほうを採用しています。Python 2.2 (SimPyが必要とする最低限のバージョン) では、リストにあるように、ジェネレーターの機能をインポートする必要があります。Python 2.3以降では、これは不要になります。
今回のアプリケーションでは、あるシミュレーションを実行する際に試してみたいと思ういろいろなシナリオを表現するためのランタイム定数をいくつか定義しています。シナリオを変更するときには、メイン・スクリプト中にあるこれらの定数を書き換える必要があります。これが、もっと具体的なところまで完成したアプリケーションであれば、これらのパラメーターは、コマンド・ライン・オプションとか、環境変数とか、構成ファイルを使って設定できるようにしてもよいところでしょうが、とりあえずは、このやり方で十分です。
リスト2. シミュレーション・パラメーターの設定
AISLES = 5 # Number of open aisles ITEMTIME = 0.1 # Time to ring up one item AVGITEMS = 20 # Average number of items purchased CLOSING = 60*12 # Minutes from store open to store close AVGCUST = 1500 # Average number of daily customers RUNS = 10 # Number of times to run the simulation
今回のシミュレーションで第一に行うべきことは、プロセスを何個か定義することです。食料雑貨店のシミュレーションでわれわれが興味をもっているプロセスは、レジで支払いを行う客です。
リスト3. 客が何を行うかの定義
class Customer(Simulation.Process):
def __init__(self):
Simulation.Process.__init__(self)
# Randomly pick how many items this customer is buying
self.items = 1 + int(random.expovariate(1.0/AVGITEMS))
def checkout(self):
start = now() # Customer decides to check out
yield request, self, checkout_aisle
at_checkout = now() # Customer gets to front of line
waittime.tally(at_checkout-start)
yield hold, self, self.items*ITEMTIME
leaving = now() # Customer completes purchase
checkouttime.tally(leaving-at_checkout)
yield release, self, checkout_aisle客は、それぞれ、一定の個数の品物を購入することを決めています (今回のシミュレーションでは、食料雑貨店の商品棚から品物を選択する部分は扱っていません。客は、買物カゴを携えてレジのところにやってくるだけです)。この場合、指数確率変数分布が、完全に正確なモデルであるかどうかは、私にはわかりません。現実の買物客がいったい何個の品物を購入するのかについて、下限は問題なさそうですが、上限には曖昧なところがあるような気がします。いずれにせよ、より良いモデル情報が利用できるとすれば、シミュレーションを調整するのも簡単であることがわかります。
ここでは、客のとるアクションに焦点を合わせます。客の「実行メソッド」は、.checkout() です。このプロセス・メソッドには、よく.run() とか.execute() といった名前が付けられますが、今回のサンプルの場合、.checkout() がその働きにぴったりの名前だと思いました。名前は、好きなものにすることができます。Customer オブジェクトが実際に行うアクション は、シミュレートされた時間を何ヶ所かで確認し、いくつかの所要時間をwaittime モニターおよびcheckouttime モニターに記録することだけです。しかし、アクションとアクションの間には、重要なyield 文が存在します。最初のyieldでは、客は資源 (レジの通路) を要求します。客は、必要な資源が得られるまでは、他のことを何も行うことはできません。レジの通路に着くと、客は実際に支払いを行います。これには、購入した品物の数に比例した時間がかかります。最後に、レジの通路を通り抜けると、客は、資源を解放し、他の客がその通路を利用できるようにします。
上のコードは、Customer クラスが行うことを定義するものですが、シミュレーションを実行するには、客の実際のオブジェクトをいくつか生成する必要があります。1日の間に買物にくる客一人ひとりについて客オブジェクトを生成し、それぞれに適当な支払い所要時間を割り当てるというやり方もできるでしょう が、「個々の客が店に入ってくるつど」必要な客オブジェクトを、ファクトリー・オブジェクトに生成させるというやり方のほうがムダがありません。今回のシミュレーションは、1日の間に買物にくるすべての客に同時に関心があるわけではなく、レジの通路を同時に競って求める客に関心があるだけです。Customer_Factory クラスは、それ自身がシミュレーションの一部となっていること、すなわち1個のプロセスであることに注意してください。ひょっとすると、フリッツ・ラング (Fritz Lang) のメトロポリス (Metropolis) 流の製造されたロボット労働者を連想させるかもしれませんが、客ファクトリーは、プログラミングの便宜上のものです。モデル化された状況の何かに直接対応しているわけではありません。
リスト4. 客の流れの生成
class Customer_Factory(Simulation.Process):
def run(self):
while 1:
c = Customer()
Simulation.activate(c, c.checkout())
arrival = random.expovariate(float(AVGCUST)/CLOSING)
yield hold, self, arrival先に触れたように、今回のサンプル・プログラムでは、現在のSimPyのMonitor クラスで対応していない、いくつかの統計データを収集したいと考えました。すなわち、ただ単に平均的な支払い所要時間に関心があるのではなく、特定のシナリオでの最悪のケースにも関心があります。そこで、最小値と最大値を収集するように機能拡張したモニターを作成しました。
リスト5. モニターを使ってのシミュレーションの監視
class Monitor2(Monitor):
def __init__(self):
Monitor.__init__(self)
self.min, self.max = (int(2**31-1),0)
def tally(self, x):
Monitor.tally(self, x)
self.min = min(self.min, x)
self.max = max(self.max, x)シミュレーションの最終段階は、当然のことながら、それを実行する ことです。標準的なサンプル・プログラムでは、ほとんどの場合、シミュレーションを1回だけ実行するようになっていますが、この食料雑貨店の場合、シミュレーションを何回かループさせ、1回のシミュレーションを1日の営業に対応させることにしました。統計データの中には、日によって大きく違ってくるものもありますので (来店する客の数と品物の個数に、ランダムな値をいろいろと使用しているため)、このほうが良いことがわかります。
リスト6. 日ごとのシミュレーションの実行
for run in range(RUNS):
waittime = Monitor2()
checkouttime = Monitor2()
checkout_aisle = Simulation.Resource(AISLES)
Simulation.initialize()
cf = Customer_Factory()
Simulation.activate(cf, cf.run(), 0.0)
Simulation.simulate(until=CLOSING)
#print "Customers:", checkouttime.count()
print "Waiting time average: %.1f" % waittime.mean(),\
"(std dev %.1f, maximum %.1f)" % (sqrt(waittime.var()),waittime.max)
#print "Checkout time average: %1f" % checkouttime.mean(),\
# "(standard deviation %.1f)" % sqrt(checkouttime.var())
print 'AISLES:', AISLES, ' ITEM TIME:', ITEMTIME3人いれば客の群れ: なにがしかの結果 (とその意味)
私が食料雑貨店のモデルについて考え出した当初は、シミュレーションを行えば、いくつかの直接的な疑問に答が出るだろうと考えていました。たとえば、店主は、改良型のスキャナーを購入する (ITEMTIME を短縮する) か、店員を増やす (AISLES を増やす) かを選択できるようになるかもしれないと予想していました。それぞれのシナリオで (一定の労働やテクノロジーのコストの下) シミュレーションを実行すれば、どちらのコストが安いのかを決定できるだろうと思っていました。
しかし、シミュレーションを実際に行ってみると、私が予想していたよりも多分もっと面白い結果が得られていることに気付きました。収集したいろいろなデータを眺めていると、私が最適化しようとしているのが何なのか をわかっていないことに気付いたのです。たとえば、平均の 支払い所要時間を減らすのがよいのか、それとも最悪の場合 の時間を減らすのがよいのか。客の総体的な満足度を高めるには、そのどちらが効果的なのか。さらに、客がレジのところに到着するまでに待っている時間と、品物の値段をレジに打ち込むのにかかる時間とは、どうやって比較すればよいのか。私の個人的な経験では、列に並んで待っているのはじれったいのですが、私の買った品物をレジに打ち込む時間は (少し時間がかかったとしても) それほど苦にはなりません。
食料雑貨店を経営しているわけではありませんので、当然ながら、これらの疑問に対する答はわかりません。しかし、シミュレーションによって、どんな二律背反 (tradeoffs) が存在するのかはわかりますし、(たとえば、「客は、実際に 1日中一定の割合で来店するのか」など、まだ明示的にパラメーター化していないものも含め) 行動を変化させるのは非常に簡単なことです。
このモデルの価値を明らかにしてくれる例を最後に1つ紹介しておきたいと思います。先に、複雑なシステムの動作を概念化するのは難しいと述べました。以下のことが、このことを証明しているのではないかと思います。レジの数が6台から5台に減ったときに (他のパラメーターは同じであるとして)、皆さんは、どんなことが起こると思いますか。私は、最初、支払い所要時間の最悪値が少し 悪くなるだろうと思っていました。しかし、実際の結果は違います。
リスト7. レジの数を変えての2回のサンプル実行
% python Market.py Waiting time average: 0.5 (std dev 0.9, maximum 4.5) Waiting time average: 0.3 (std dev 0.6, maximum 3.7) Waiting time average: 0.4 (std dev 0.8, maximum 5.6) Waiting time average: 0.4 (std dev 0.8, maximum 5.2) Waiting time average: 0.4 (std dev 0.8, maximum 5.8) Waiting time average: 0.3 (std dev 0.6, maximum 5.2) Waiting time average: 0.5 (std dev 1.1, maximum 5.2) Waiting time average: 0.5 (std dev 1.0, maximum 5.4) AISLES: 6 ITEM TIME: 0.1 % python Market.py Waiting time average: 2.1 (std dev 2.3, maximum 9.5) Waiting time average: 1.8 (std dev 2.3, maximum 10.9) Waiting time average: 1.3 (std dev 1.7, maximum 7.3) Waiting time average: 1.7 (std dev 2.1, maximum 9.5) Waiting time average: 4.2 (std dev 5.6, maximum 21.3) Waiting time average: 1.6 (std dev 2.6, maximum 12.0) Waiting time average: 1.3 (std dev 1.6, maximum 7.5) Waiting time average: 1.5 (std dev 2.1, maximum 11.2) AISLES: 5 ITEM TIME: 0.1
レジの数を1つ減らした場合、1/5程度悪化するのではなく、平均の待ち時間が約4倍に増えるのです。さらに、(この2回のシミュレーションにおいて) 最も運の悪い客は、待ち時間が6分から21分になっています。私がこの店の経営者なら、このしきい値条件を知ることは、客に満足してもらう上で極めて重要だと考えるでしょう。誰もそんな結果を予想していなかったわけですから。
ダウンロード可能なリソース
関連トピック
- SimPyのホームページには、APIの詳細やSimPyの利用例など、役に立つ文書が多数掲載されています。本稿執筆時点では、ベータ版となっていますが、その後、SimPyの構成要素に変更されているものがあるかもしれません。
- Davidの記事Pythonジェネレーターで「無重量スレッド」を実装するには、本格的なコルーチンをシミュレートする斬新な方法が紹介されています (developerWorks、2002年6月)。
- Davidの記事ジェネレーターによるステート・マシンは、Pythonのジェネレーターを基礎としたステート・マシンとコルーチンを使用することで得られる効率について説明しています (developerWorks、2002年7月)。
- イテレーターとシンプル・ジェネレーターで、Davidは、Python 2.2に新たに導入された構文要素 (constructs) のジェネレーターとイテレーターを紹介しています (developerWorks、2001年9月)。皆さんも理解しておきたいと思われるのではないでしょうか。
- フリッツ・ラングのメトロポリス のことをよく知らない方は、Mark RobinsonのMetropolis論やInternet Movie Databaseファイル を訪れると、この (2026年のことを映画化した) 1926年制作の無声映画について詳しく知ることができます。フリッツ・ラングという制作者については、Jeffrey Scheuerのサイトで詳しく知ることができます。
- developerWorks のLinuxゾーンには、他にもLinux開発者向けの参考文献が多数掲載されています。