仮想取引市場における自動取引ロボット実行のスケジューリング手法

(1)

2004 年度卒業論文

仮想取引市場における自動取引ロボット実行のスケジューリング手法

提出日： 2005 年 2 月 2 日指導：山名早人助教授

早稲田大学理工学部情報学科学籍番号：1G01P088-2

深山辰徳

(2)

概要

本稿では、カブロボ上でロボットを公平に実行するためのスケジューリング手法を提案する。本稿で言う公平さとは、次の三つの条件を満たすものである。第一にすべてのロボットは少なくとも一度は実行される。第二に処理を完了することが出来ないロボットの実行時間はすべて同じになる。第三に第一の条件と第二の条件を損なわない範囲で、時間は余らないようにする。カブロボとは仮想証券取引市場の上でロボットが株式の取引を自動で行うシステムがある。制限された時間の中で多数の様々なアルゴリズムを実装したロボットを限られた計算資源の中で実行しなければならない。従来のジョブスケジューリング手法として地球シミュレータ用ジョブスケジューリングアルゴリズムの評価、時分割空間分割スケジューリング、Grid 計算環境における予定ガント図を用いたジョブスケジューリングといったものがある。しかし、これらの研究には制限された時間内にジョブを公平に実行するという概念が無いため、従来の手法を適用することができない。既存のカブロボで実装されているロボット実行スケジューリングは単純にタイムアウトをある値で固定し、

制限時間内に処理が終わらなければ処理を打ち切るというものである。既存の手法では、

まったく実行されないロボットが出てくる可能性があるという問題がある。従って本稿では、この問題に対してタイムアウトを動的に変更することで、出来る限りすべてのロボットに均等に処理の機会が与えられる手法を提案する。本手法では、各処理の完了後残りの処理時間からタイムアウトを再設定し、残された時間を残りのロボットの処理に有効に活用するものである。ただしタイムアウトを再設定するのみでは、ロボットを実行する順序によってすべてのロボットの処理を完了することが出来ないという問題が残ってしまう。

そこで、後者の問題に対してタスクの実行順序を制御するための手法も提案する。

(3)

第１章はじめに

本稿では、カブロボ上でロボットを公平に実行するためのスケジューリング手法を提案する。本稿で言う公平とは、次の三つの条件を満たすものとして定義する。第一にすべてのロボットは少なくとも一度は実行される。第二に処理を完了することが出来ないロボットの実行時間はすべて同じになる。第三に第一の条件と第二の条件を損なわない範囲で、時間は余らないようにする。

カブロボとは仮想証券取引市場の上でロボットが株式の取引を自動で行うシステムである。カブロボのシステムがロボットをタスクキューに登録してから実行するまでの一連の流れは次の通りである。システムは毎日この一連の流れを相場の終了後に実行している。

1. 相場が終わり、終値が確定する。

2. タスクキューにすべてのロボットを登録する。

3. タスクキューに登録されているロボットを実行していく。

カブロボのシステムは有限な時間の中で多数の様々なアルゴリズムを実装したロボットを限られた計算資源の中で実行しなければならない。ロボットの処理が完了するまでにかかる時間は様々であり、予測は困難である。制限された時間の中で出来る限り多数のロボットの処理を完了したい。また、制限時間内にすべてのロボットの処理を完了することが出来ない場合、出来る限りすべてのロボットに均等に処理する時間を割り振りたい。

従来、こうしたジョブスケジューリングに関連した研究に地球シミュレータ用ジョブスケジューリングアルゴリズムの評価[2]、時分割空間分割スケジューリング[3]、Grid計算環境における予定ガント図を用いたジョブスケジューリング[4]といったものがある。地球シミュレータのジョブスケジューリングアルゴリズムでは、ユーザが予めジョブの計算に必要な時間とノード数を宣言する。ジョブの計算に必要な時間（宣言経過時間）とノード数の少ないジョブほど優先度が高くなるというものである。しかし、今回の場合二つの理由から、ロボットのアルゴリズムの処理に必要な時間をユーザが事前に計算し宣言すること

(5)

は困難である。第一に、すべてのユーザが情報科学の専門家ではなく、むしろ大多数のユーザは計算時間の見積もりができない素人である。第二に、ロボットのアルゴリズムによっては、市場の局面によって実行時間がまちまちで、実行時間の予測が困難であることである。仮にすべてのユーザが実行時間を予測することが出来たとする。この場合優先度の高いものから逐次実行されていくことになる。全ロボットの実行時間の総計が制限時間内であれば問題はないが、制限時間を超えると処理が途中で打ち切られてしまう。するとまったく実行されることのないロボットも出てきてしまう。これらの研究には、制限された時間内にジョブを公平に実行するという概念が無いため、従来の手法を適用することができない。

カブロボにおいて公平ではない状況として３つのケースに分類することができる。以下にその３つのケースと具体的な例を示す。３つのケースに共通した条件として、ロボットを処理するコンピュータは２台であり、18時間（2160分）以内に１日の処理を終わらせなければならないというものがある。

ケース１：

タイムアウト時間内に処理を完了することが出来ないロボットがタスクキューの優先順位の高いところに多数分布している場合。この場合途中で制限時間に達してしまい、以後ロボットの処理をまったく実行することが出来なくなってしまう。

このケースでは、公平の第一の条件であるすべてのロボットは少なくとも一度は実行されると第二の条件である処理を完了することが出来ないロボットの実行時間はすべて同じになるを満たしていない。

具体的な例を挙げると次のようになる。登録されたロボット数は3000台とし、そのうち

の約30％のロボットが処理を完了する為に３分以上の時間を要し、それらのロボットが偶

然優先度の高い状態でスケジューリングされてしまった場合。

ケース２：

短時間で処理の終了してしまうロボットが多数存在し、最終的に時間が余ってしまう場

(6)

合。且つ、タイムアウトで処理が打ち切られてしまっているロボットが在る場合。この場合、余った時間を処理が終わらなかったロボットに対して均等に分配したい。

このケースでは、公平の第三の条件である処理の終わっていないロボットがある限り、

時間は余らないようにするを満たしていない。

具体的な例を挙げると次のようになる。登録されたロボット数は3000台とし、そのうち

の約90％のロボットが10秒程度で処理を完了することが出来る。残りの10％のロボット

の処理はいつ完了するかは分からないが、最低でも３分以上はかかる場合。

ケース３：

すべてのロボットがタイムアウト時間内に処理を終了することが出来ない場合。この場合、どのような順序で実行したとしても必ず一度も実行されないロボットが出てきてしまう。

このケースでは、公平の第一の条件であるすべてのロボットは少なくとも一度は実行されると第二の条件である処理を完了することが出来ないロボットの実行時間はすべて同じになるを満たしていない。

具体的な例を挙げると次のようになる。登録されたロボット数は3000台とし、すべてのロボットの処理に３分以上の時間がかかってしまう場合。

既存のカブロボのシステムでは、ロボットのタイムアウトは静的に３分で固定されている。ケース１の場合、30％のロボットというと900台に相当する。900台のロボットが３分間処理を実行してしまうと2700分が経過してしまう。2160分を超えた時点ですべての処理は打ち切られてしまうので、結果的にロボット全体の 70%がまったく実行されない可能性がある。ケース２の場合どのような順序でロボットを実行したとしても、18 時間以内に処理を終えることは出来るが、時間が余ってしまう。余った時間は処理を完了することが出来なかったロボットに均等に割り振りたい。ケース３の場合、何をどうやってもケース１と同様にまったく実行されないロボットが出てきてしまう。

(7)

そこでこの３つのケースの問題に対して、タイムアウトを動的に変更することで、出来る限りすべてのロボットに公平に処理の機会を与えられる手法を提案する。本手法では、

各ロボットの処理完了後、残りの処理可能時間と残りのロボットからタイムアウトを動的に再設定することで、すべてのロボットに公平に処理の機会を与えることを実現するものである。

ただしケース１に関しては、タイムアウトを再設定するのみではケース２のように時間が余る問題が発生してしまう。これは公平の第三の条件である処理の終わっていないロボットがある限り、時間は余らないようにするを満たさない。そこで日々の処理にかかるロボットそれぞれの実行時間の履歴を取り、過去の実行時間の履歴を元にタスクキュー内で事前に優先順位をつけることによって、この不公平さを解消する手法を提案する。

本稿ではこれより、第２章ではカブロボというシステムについて説明する。第３章では関連する研究について紹介する。第４章では提案する手法を紹介する。第５章で提案する手法の評価を行う。第６章でまとめを述べる。

(8)

第２章カブロボにおけるスケジューリング

本章では、カブロボというシステムとそのスケジューリング手法について説明する。

2.1 カブロボとは

カブロボ[1]とは、正式にはカブロボ・コンテストという。PC上で動作するソフトウェアのロボット（ソフトウェア・エージェント）を作成し、株の売買を仮想証券会社に対して自動で行い、その運用成績を競うものである。コンテスト期間中は、そのロボットに対して参加者が指示を出すことはできない。参加者があらかじめ設定したプログラムに従ってソフトウェアのロボットが売買を行う。（株の銘柄と株価などは実際のものを用いる。）

カブロボ・コンテストは、プログラミングの未経験者から上級者まで、それぞれに楽しめる工夫がされている。未経験者には、Web ブラウザを使ってコンピュータと対話しながらアルゴリズムを設定できる「簡易ロボット」を提供する。またプログラム初心者でも大会が提供する「サンプルロボット」（プログラム・コード）を改造することで、ゲーム感覚で楽しみながら最先端のプログラミング技術を身に付けていくことができる。

カブロボ・コンテストへの参加は無料で、必要な開発環境もインターネットから無料でダウンロードできる。最大3名が1チームとなって参加する。

このコンテストでは、先進ソフトウェア技術であるLinux、Struts、Eclipseなどのオープンソース・ソフトウェアや、プログラム言語「Java」を用いる。コンテストを通じ、オープンソース・ソフトウェアの普及に貢献することを目指している。

ロボットの処理は一日に一回、その日の終値が発表されてから、次の日の市場が開くまでの間に行われる。この間に出来る限り多くのロボットの処理を完了し、処理が終わらないものに関しては均等に処理の機会を割り当てる必要がある。

(9)

2.2 システム概要

カブロボのシステムには大きく分けて３つの機能を持ったコンピュータが存在する。

１．大会運営サーバー

大会運営サーバーは、カブロボのコンテストを開催するにあたって必要な情報を管理する。大会運営中はロボットの資産の状況などを参照することが可能である。

２．証券会社サーバー

証券会社サーバーは、仮想の証券会社として働く。ロボットの口座の管理や売買の処理などはこのサーバーで行われる。ロボットが株式の売買を行うには、このサーバーに対して売買の注文を発行する。証券会社サーバーは、発行された注文が成立しうるかどうかを判断し、成立した場合にはロボットの口座情報を適宜変更する。

３．ロボット稼動サーバー

ロボット稼動サーバー上でロボットは稼動することになる。図１では、ロボット稼動サーバーは１台のように見えるが、正確には複数台用意されている。ロボットを稼動させるためのプログラムをインストールし、ネットワークに接続することでサーバーの数を増やすことが出来る。

この３つのサーバーが図１のようにそれぞれネットワークで接続されている。

(10)

図１：カブロボにおけるサーバーの関係

2.3 カブロボにおけるスケジューリング

ロボット稼動サーバーは毎日3000台ものロボットを処理しなければならない。多数のロボットを公平に処理するためには適切なスケジューリングが必要不可欠である。

本稿で言う公平とは、次の三つの条件を満たすものとして定義する。第一にすべてのロボットは少なくとも一度は実行される。第二に処理を完了することが出来ないロボットの実行時間はすべて同じになる。第三に第一の条件と第二の条件を損なわない範囲で、

時間は余らないようにする。

(11)

現在のカブロボのシステムにおけるスケジューリングの概要を図２に示す。大会に登録されたロボットをすべてタスクキューに入れるという作業は大会運営サーバーによって行われる。この作業は、単純に大会に登録されたロボットの一覧をそのままタスクキューに登録するだけである。

図２：カブロボにおけるスケジューリング

ロボット実行の流れには二つのパターンがある。

・タイムアウト時間内に処理が完了する

・タイムアウト時間内に処理が完了しない

それぞれどのように違うのか図３と図４に示した。図３はタイムアウト時間内に処理が完了する場合の流れになっている。図４はタイムアウト時間内に処理が完了しない場合の流れになっている。

どちらの場合も共通しているのは次の２点である。

１.KabuRoboDaemon が RobotMonitorThread を生成し、RobotMonitorThread が

Robotを別プロセスとして起動する。

(12)

２.Robot はタイムアウト時間内に繰り返し証券会社サーバーに対して株式売買の注文を発行することができる。

タイムアウト時間内に処理を完了することができるかどうかで違ってくるのはロボットの終わり方である。以下時間内に完了する場合としない場合についてロボットの終わり方の詳細を示す。

図３：ロボットの処理がタイムアウト時間内に終わる場合の流れ

タイムアウト時間内に処理が完了する場合

１．KabuRoboDaemonがロボット稼動サーバー上で起動される。

２．KabuRoboDaemon はタスクキューが空でなければタスクキューからロボットを一つ取り出す。

３．KaburoboDaemonはRobotMonitorThreadを生成し、タスクキューから取り出し

(13)

てきたロボットの情報をRobotMonitorThreadにセットする。

４．正しく情報をセットすることが出来たら KabuRoboDaemon は

RobotMonitorThreadを開始させる。

５．開始した RobotMonitorThread は KabuRoboDaemon に設定された情報を元に

Robotのプロセスを起動する。

６．Robotのプロセスは起動している間にどの銘柄の売買を行うかを判断し、証券会社サーバーに対して売買の注文を発行する。

７．Robot のプロセスの処理が終わると、KabuRoboDaemon は新たな

RobotMonitorThreadを生成する。

図４：ロボットの処理がタイムアウト時間内に終わらない場合の流れ

タイムアウト時間内に処理が完了しない場合

１．KabuRoboDaemonがロボット稼動サーバー上で起動される。

２．KabuRoboDaemon はタスクキューが空でなければタスクキューからロボットを一つ取り出す。

３．KaburoboDaemonはRobotMonitorThreadを生成し、タスクキューから取り出し

(14)

てきたロボットの情報をRobotMonitorThreadにセットする。

４．正しく情報をセットすることが出来たら KabuRoboDaemon は

RobotMonitorThreadを開始させる。

５．開始した RobotMonitorThread は KabuRoboDaemon に設定された情報を元に

Robotのプロセスを起動する。

６．Robotのプロセスは起動している間にどの銘柄の売買を行うかを判断し、証券会社サーバーに対して売買の注文を発行する。

７．タイムアウトの時間を過ぎてもRobotが処理を終了しないと、KabuRoboDaemon

がRobotMonitorThreadに対してinterrupt命令を発行します。

８．InterruptされたRobotMonitorThreadは待機状態から復帰し、Robotプロセスを強制的に終了させる。

統計を取ると、初心者用の簡易ロボットは１つのロボットの処理に10秒程度しか必要とせず、短い時間で処理が完了することが分かっている。しかし、上級者の作るロボットはどのようなアルゴリズムを採用しているか分からないので、実行時間の予測が困難である。

コンテストでは便宜上３分という制限を設けているが、すべてのロボットの処理が３分以内に終わる保証はない。

ロボットは与えられた時間内に自由に株式売買の注文を出すことが出来る。仮に３分以内にロボットの実行が終了しなかったとしても、その間にロボットが発行した注文は有効である。よって、ロボットの処理が完了しなかったとしてもそのロボットが優秀な成績を残す可能性はある。

(15)

第３章関連研究

本章では、ジョブスケジューリング手法を紹介する。

3.1 地球シミュレータ用ジョブスケジューリングアルゴリズム[2]

地球シミュレータのジョブスケジューリングアルゴリズムでは、ユーザが予めジョブの計算に必要な時間とノード数の宣言をする。ジョブの計算に必要な時間（宣言経過時間）

とノード数の少ないジョブほど優先度が高くなるというものである。要するに、ジョブの計算をするにあたって、資源を占有する割合の少ないものを優先的にスケジューリングしていくということである。この点に関しては、本手法も同じ考え方を採用している。一度すべてのロボットを実行し、その処理にかかった時間を履歴として保存しておく。次回実行時には、前回実行時に処理の早く終わったロボットから順次処理するようになっている。

しかし、地球シミュレータ用ジョブスケジューリングでは制限された時間の中でスケジューリングを行うことが考慮されていない。また、本手法を適用するカブロボのシステムでは、ロボットは事前に実行時間を宣言するという制約が無い。

(16)

第４章提案手法

本章では、本稿が提案する手法について説明をする。

4.1 従来手法の問題点

カブロボシステムの従来の手法では、ロボットを実行する際にある一定のタイムアウトを設定している。タイムアウト内に処理を完了することの出来ないロボットは、タイムアウトした時点で処理を打ち切ってしまう。従来の手法では、タイムアウトは３分に設定されている。

現在ロボットの登録総数は3000を超えている。それに対してロボットを処理するコンピュータは２台である。また、１度の処理に使える時間は18時間である。

カブロボにおいて公平ではない状況として３つのケースに分類することができる。以下にその３つの具体的な例を示す。３つのケースに共通した条件として、ロボットを処理するコンピュータは２台であり、18時間（2160分）以内に１日の処理を終わらせなければならないというものがある。

ケース１：

登録されたロボット数は 3000 台とし、そのうちの約30％のロボットが処理を完了する為に３分以上の時間を要し、それらのロボットが偶然優先度の高い状態でスケジューリングされてしまった場合。30％のロボットというと 900台に相当する。900台のロボットが３分間処理を実行してしまうと 2700分が経過してしまう。2160分を超えた時点ですべての処理は打ち切られてしまうので、結果的にロボット全体の 70%がまったく実行されない可能性がある。

問題点：

まったく実行されないロボットが出てきてしまう。

(17)

処理を完了していないロボット（実行されていないものも含む）の実行時間が同じではない。

ケース２：

仮に登録ロボット数が3000台だったとする。その内９割のロボットの処理時間の平均が 10 秒程度だとし、残りの１割の処理時間が３分以上とする。この場合９割のロボットの処理にかかる時間は450分である。残り１割のロボットの処理に使える時間は1710分である。

この時従来の手法では、残りの１割のロボットはすべて３分で処理を打ち切られてしまい、

900 分で処理を完了することになる。そして 810 分時間があまることになる。この余った 810分を処理の終了しなかったロボットに対して均等に割り振りたい。

問題点：

処理を完了していないロボットがあるにもかかわらず、時間が余ってしまう。

ケース３：

仮に登録ロボット数が3000台だったとして、すべてのロボットが制限時間いっぱいまで使うアルゴリズムを採用した場合、すべての処理を終えるためには理論上9000分が必要になる。一方２台のコンピュータを18時間フルに稼動させた場合、ロボットの処理に使える時間は合計で2160分である。これは、理論的にすべてのロボットの処理を終了させるのは不可能である。問題はこのような状況になった場合に従来手法では、720台のロボットは処理を完了し、残りの2280台はまったく処理が開始されないまま終わってしまうことだ。コンテストの性質上この様な場合、すべてのロボットに対して43.2秒の時間を割り当てたい。

問題点：

まったく実行されないロボットが出てきてしまう。

処理を完了していないロボット（実行されていないものも含む）の実行時間が同じではない。

4.2 提案手法の概要

(18)

本稿では、すべてのロボットを公平に実行するために以下の３つのケースについて考える。はじめにでも述べている通り、本稿で言うところの公平とは、次の三つの条件を満たすものと定義する。第一にすべてのロボットは少なくとも一度は実行される。第二に処理を完了することが出来ないロボットの実行時間はすべて同じになる。第三に第一の条件と第二の条件を損なわない範囲で、時間は余らないようにする。

本稿で提案する手法は主に以下の２点から成る 1. 動的にタイムアウトを設定する

2. ロボットの過去の実行履歴に応じて優先度を決定する

動的にタイムアウトを設定

本稿ではコンピュータの数と残り時間の積を残計算可能時間と定義する。残計算可能時間は以下のように定義される。ここで、終了時刻とはシステムが最終的に処理を終了させるべき時刻であり、現在時刻はタイムアウトを計算しようとしている時点での時刻である。

( ^終了時刻 ^現在時刻 ) ^{コンピュータの台数}

残計算可能時間 [s ] = − ×

残計算可能時間を用いてタイムアウトTは次の式によって算出される。

残ロボット数残計算可能時間 [s ] T =

式 1：タイムアウトTの算出方法

登録されているロボットの数を3000台として、上の式に当てはめて考えると初期のTの値は、

) ( 2 . 3000 43

2 60 60

18 s

T = × × × =

となる。

(19)

ロボットの過去の実行履歴に応じた優先度の決定

本稿で提案する手法では、ロボットの実行履歴に応じてロボットを実行する優先度を切り替える。その際に参照する過去の実行履歴は平均実行時間と最長実行時間である。最長実行時間の履歴は10秒単位で切り上げをして履歴に保存されている。最長実行時間の短いロボットほど優先度が高くなる。最長実行時間の同じもの同士では、平均実行時間の短いロボットほど優先度が高くなる。参考になる過去の実行履歴がない場合には、今までの経験から簡易ロボットの実行が10〜30秒程度で終わることが分かっているので、それらの優先度を高くする。

提案手法を適用した後のカブロボシステムの処理の流れを以下に示す。

１．タスクキューを過去の実行履歴を元に上記の規則で設定された優先度順にソートする。

２．タスクキューからロボットを取り出す。

３．式１を用いてタイムアウトを算出する。

４．３で算出されたタイムアウトを設定しロボットを起動する。

５．ロボットが正常終了するか、タイムアウトで強制終了される。

６．タスクキューが空でなければ、２に戻る。

4.3 実行例

以下に本手法を適用した場合と適用しなかった場合の実行例を示す。ここでは、登録されたロボットの数を10台とし、ケース１の状態に似せたモデルを用いて説明をする。登録されたロボットの数が4.1で共通した条件の300分の１なので、18時間の制限は216秒となる。

表１にケース１の状態を想定したロボットとその実行に必要な時間を示す。表１の必要時間はロボットが処理を完了するまでに必要な時間である。タイプは、ロボットがカブロボのシステム側で用意された簡易タイプのものを使っているのか、ユーザが作ったオリジナルのものなのかを示している。

(20)

ロボット名必要時間タイプ robot1 550 自作 robot2 480 自作 robot3 180 自作 robot4 110 自作 robot5 10 簡易 robot6 30 簡易 robot7 25 簡易 robot8 20 簡易 robot9 15 簡易 robot10 25 簡易表１：ケース１の登録ロボット例

(21)

第５章評価

0 100000 200000 300000 400000 500000 600000 700000 800000

1 19 37 55 73 91 109 127 145 163 181 199

elapsed timeout

0 20000 40000 60000 80000 100000 120000 140000 160000 180000 200000

1 16 31 46 61 76 91 106 121 136 151 166 181 196

elapsed timeout

(22)

第６章おわりに

(23)

参考文献

[1] カブロボ・コンテスト URL http://kaburobo.jp/

[2] 宇野篤也，板倉憲一，地球シミュレータ用ジョブスケジューリングアルゴリズムの評価，情報処理学会研究報，2003-HPC-95，pp83-88

[3] 堀敦史，石川裕，小中裕喜，前田宗則，友清孝志，時分割空間分割スケジューリング，情報処理学会論文誌，Vol. 37， No.7，pp1320-1331(1996)

[4] 上田清詩，本多弘樹，弓場敏嗣， Grid 計算環境における予定ガント図を用いたジョブスケジューリング，情報処理学会論文誌，Vol.44，No.SIG1(HOS 6)，pp93-102(2003)

仮想取引市場における自動取引ロボット実行の スケジューリング手法

2004 年度卒業論文