(57)【要約】【課題】  ネットワークで接続された多数のコンピュータにおいて、効率の良い分散処理やタスク共有を実現する分散処理プログラムを提供する。【解決手段】  時系列で実行される複数の処理を含むタスクを分散処理するために、複数のコンピュータ間をネットワークの通信チャンネルを介して移動可能な複数のエージェントプログラムを用いた分散処理プログラムであって、各エージェントプログラムは、移動テーブルに基づいて、移動後に所属するコンピュータの記憶装置に、タスクを実行するための処理プログラムと、タスクを実行するための処理データと、所属する通信チャンネルを示す通信チャンネル情報と、移動テーブルと、評価値とを関連づけて格納させ（ステップＳ１１０）、評価値の値に応じて、エージェントプログラムの分裂処理を行い（ステップＳ１１２）、同一の通信チャンネルに属するエージェントプログラムの個数が所定数を超えることに応じて、通信チャンネルを離隔する処理を行う（ステップＳ１１６）。【選択図】        図５
2005332082.tif 000002
【特許請求の範囲】
【請求項１】
時系列で実行される複数の処理を含む所定のタスクを分散処理するための分散処理システムであって、
ネットワークを介して相互に通信可能な複数の情報処理機器を備え、
各前記情報処理機器は、
複数のチャンネルのうち選択を指示した通信チャンネルで、前記ネットワークと通信するための通信手段と、
前記複数の処理のうち対応する処理を実行するための情報処理手段と、
前記処理を行うための情報を格納する記憶手段とを含み、
前記情報処理手段は、前記複数の情報処理機器間を前記通信チャンネルを介して移動可能な複数のエージェント演算処理手段を含み、
各前記エージェント演算処理手段は、
前記タスクに対応し現在所属する前記情報処理機器と移動先の前記処理機器とを関連づける移動テーブルに基づいて通信し、移動後に所属する前記情報処理機器の前記記憶手段に、前記タスクを実行するための処理プログラムと、前記タスクを実行するための処理データと、所属する通信チャンネルを示す通信チャンネル情報と、前記移動テーブルと、評価値とを関連づけて格納させる移動手段と、
所属する前記情報処理機器の前記記憶手段に格納される情報に基づいて、前記タスクの前記複数の処理のうち、前記所属する前記情報処理機器に対応する処理を実行するタスク処理手段と、
前記タスクの処理が完了することに応じて、前記評価値を更新する評価値更新手段と、
前記評価値の値に応じて、前記エージェント演算処理手段の分裂処理を行う分裂処理手段と、
同一の前記通信チャンネルに属する複数の前記エージェント演算処理手段の個数が所定数を超えることに応じて、前記同一の前記通信チャンネルに属する複数の前記エージェント演算処理手段に対応する前記通信チャンネルを離隔する処理を行う通信チャンネル離隔手段とを含む、分散処理システム。
【請求項２】
各前記エージェント演算処理手段は、前記通信チャンネルのうち、選択された通信チャンネルに属する前記エージェント演算処理手段に消去処理を指示する消去指示手段をさらに含む、請求項１記載の分散処理システム。
【請求項３】
前記分裂処理手段は、
分裂前の前記エージェント演算処理手段に付随する前記処理プログラムと、前記処理データと、前記通信チャンネル情報と、前記移動テーブルとを引き継いだエージェント演算処理手段を生成する、請求項１記載の分散処理システム。
【請求項４】
前記分裂処理手段は、
所定の突然変異確率で、前記移動テーブルを更新する突然変異処理手段を含む、請求項３記載の分散処理システム。
【請求項５】
前記移動手段は、さらに、複数のタスクのうち対応する前記エージェント演算処理手段の処理するタスクを指定するタスク指定情報と、前記複数のタスクごとに対応する前記複数の処理を関連づけたタスク処理手順テーブルとを前記移動後に所属する前記情報処理機器の前記記憶手段に格納させ、
前記タスク処理手段は、前記タスク指定情報により指定されるタスクの前記所属する前記情報処理機器に対応する処理を実行する、請求項１記載の分散処理システム。
【請求項６】
時系列で実行される複数の処理を含む所定のタスクを分散処理するために、複数の情報処理機器間をネットワークの通信チャンネルを介して移動可能な複数のエージェントプログラムを用いた分散処理プログラムであって、
各前記エージェントプログラムは、
前記タスクに対応し現在所属する前記情報処理機器と移動先の前記処理機器とを関連づける移動テーブルに基づいて、複数のチャンネルのうち選択を指示した通信チャンネルで前記ネットワークと通信し、移動後に所属する前記情報処理機器の記憶手段に、前記タスクを実行するための処理プログラムと、前記タスクを実行するための処理データと、所属する通信チャンネルを示す通信チャンネル情報と、前記移動テーブルと、評価値とを関連づけて格納させる移動ステップと、
所属する前記情報処理機器の前記記憶手段に格納される情報に基づいて、前記タスクの前記複数の処理のうち、前記所属する前記情報処理機器に対応する処理を実行するタスク処理ステップと、
前記タスクの処理が完了することに応じて、前記評価値を更新する評価値更新ステップと、
前記評価値の値に応じて、前記エージェント演算処理手段の分裂処理を行う分裂処理ステップと、
同一の前記通信チャンネルに属する複数の前記エージェント演算処理手段の個数が所定数を超えることに応じて、前記同一の前記通信チャンネルに属する複数の前記エージェント演算処理手段に対応する前記通信チャンネルを離隔する処理を行う通信チャンネルステップとを、前記情報処理機器に実行させる、分散処理プログラム。
【請求項７】
各前記エージェントプログラムは、前記通信チャンネルのうち、選択された通信チャンネルに属する前記エージェントプログラムに消去処理を指示する消去指示ステップをさらに含む、請求項６記載の分散処理プログラム。
【請求項８】
前記分裂処理ステップは、
分裂前の前記エージェント演算処理手段に付随する前記処理プログラムと、前記処理データと、前記通信チャンネル情報と、前記移動テーブルとを引き継いだエージェントプログラムを生成するステップを含む、請求項６記載の分散処理プログラム。
【請求項９】
前記分裂処理ステップは、
所定の突然変異確率で、前記移動テーブルを更新する突然変異処理ステップを含む、請求項８記載の分散処理プログラム。
【請求項１０】
前記移動ステップは、さらに、複数のタスクのうち対応する前記エージェント演算処理手段の処理するタスクを指定するタスク指定情報と、前記複数のタスクごとに対応する前記複数の処理を関連づけたタスク処理手順テーブルとを前記移動後に所属する前記情報処理機器の前記記憶手段に格納させるステップを含み、
前記タスク処理ステップは、前記タスク指定情報により指定されるタスクの前記所属する前記情報処理機器に対応する処理を実行する、請求項６記載の分散処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークで接続された多数のコンピュータからなるシステムにおいて、一つのタスクを異なる多数の計算機資源を用いて分散処理する分散処理システムおよび分散処理プログラムに関する。
【背景技術】
【０００２】
コンピュータやネットワークの普及により、さまざまな種類の多くのコンピュータからなる、さまざまな形態で接続されたネットワークが増加している。
【０００３】
このような状況の下、近年、多数のコンピュータからなるユビキタスコンピューティングが注目されている（たとえば、非特許文献１を参照）。ユビキタスコンピューティングでは、計算機資源の分布などのネットワーク環境が未知な場合や動的に変化する場合が想定される。 
【０００４】
このような環境における分散処理の最適化には、ネットワーク構造や処理手順の適応的な獲得が期待される。
【０００５】
一方で、マルチエージェントシステム（以下、ＭＡＳと記す）の研究として、たとえば、エージェントが知覚できる範囲の情報である利得や報酬、評価などを個体最適性と定義し、システムの大域的目的として、すべてのエージュントがそれぞれの行動から得る利得の総和をシステム最適性とそれぞれ定義したときに、エージェント学習によるシステム最適性の向上をシミュレート可能な「動的離隔型遺伝的アルゴリズム（Dynamically Separating Genetic Algorithms、以下、ＤＳ−ＧＡと記す）」（たとえば、非特許文献２を参照）や「動的離隔型学習アルゴリズム（Dynamically Separating Learning Algorithms、以下、ＤＳ−ＬＡと記す）」（たとえば、非特許文献３を参照）の提案がなされている。
【０００６】
このＤＳ−ＧＡは、個体数に応じて個体を「コロニー」と呼ぶグループに動的に離隔する遺伝的アルゴリズム（以下、ＧＡ）である。個体を離隔する遺伝的アルゴリズムとしては、他に島モデルＧＡなどがあるが、ＤＳ−ＧＡは離隔状態が個体数に応じて動的に変化する点で異なる。
【非特許文献１】Mark Weiser, “The Computer for the 21st Century,” Scientific American, Vol. 265, No. 3, pp. 99-104, 1991.
【非特許文献２】中山  功一、松井博和、野村由司彦著：動的離隔型ＧＡ（ＤＳ−ＧＡ）の提案、情報処理学会論文誌：数理モデル化と応用、Vol.43, No.SIG10(TOM7), pp.95-109, Nov.2002.
【非特許文献３】K. Nakayama, H. Matsui、 K. Shimohara, O. Katai,“Proposal of Dynamically Separating Learning Algorithm for Interactive Computers (DS-LA): Optimization of collective performance in networked computers,” The journal of three dimensional images, Vol. 18, No. 1, pp. 87-94, 2004.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来は、上述したようなコンピュータネットワーク上に多数のコンピュータが存在する場合に、ＭＡＳを用いることで、一つのタスクを異なる多数の計算機資源を用いて効率良く分散処理するための手法が、必ずしも明らかでない、という問題があった。
【０００８】
本発明は、上記のような問題を解決するためになされたものであって、その目的は、ネットワークで接続された多数のコンピュータにおいて、効率の良い分散処理やタスク共有を実現する分散処理システムおよび分散処理プログラムを提供することである。
【課題を解決するための手段】
【０００９】
このような目的を達成するために、本発明の分散処理システムは、時系列で実行される複数の処理を含む所定のタスクを分散処理するための分散処理システムであって、ネットワークを介して相互に通信可能な複数の情報処理機器を備え、各情報処理機器は、複数のチャンネルのうち選択を指示した通信チャンネルで、ネットワークと通信するための通信手段と、複数の処理のうち対応する処理を実行するための情報処理手段と、処理を行うための情報を格納する記憶手段とを含み、情報処理手段は、複数の情報処理機器間を通信チャンネルを介して移動可能な複数のエージェント演算処理手段を含み、各エージェント演算処理手段は、タスクに対応し現在所属する情報処理機器と移動先の処理機器とを関連づける移動テーブルに基づいて通信し、移動後に所属する情報処理機器の記憶手段に、タスクを実行するための処理プログラムと、タスクを実行するための処理データと、所属する通信チャンネルを示す通信チャンネル情報と、移動テーブルと、評価値とを関連づけて格納させる移動手段と、所属する情報処理機器の記憶手段に格納される情報に基づいて、タスクの複数の処理のうち、所属する情報処理機器に対応する処理を実行するタスク処理手段と、タスクの処理が完了することに応じて、評価値を更新する評価値更新手段と、評価値の値に応じて、エージェント演算処理手段の分裂処理を行う分裂処理手段と、同一の通信チャンネルに属する複数のエージェント演算処理手段の個数が所定数を超えることに応じて、同一の通信チャンネルに属する複数のエージェント演算処理手段に対応する通信チャンネルを離隔する処理を行う通信チャンネル離隔手段とを含む。
【００１０】
好ましくは、各エージェント演算処理手段は、通信チャンネルのうち、選択された通信チャンネルに属するエージェント演算処理手段に消去処理を指示する消去指示手段をさらに含む。
【００１１】
好ましくは、分裂処理手段は、分裂前のエージェント演算処理手段に付随する処理プログラムと、処理データと、通信チャンネル情報と、移動テーブルとを引き継いだエージェント演算処理手段を生成する。
【００１２】
好ましくは、分裂処理手段は、所定の突然変異確率で、移動テーブルを更新する突然変異処理手段を含む。
【００１３】
好ましくは、移動手段は、さらに、複数のタスクのうち対応するエージェント演算処理手段の処理するタスクを指定するタスク指定情報と、複数のタスクごとに対応する複数の処理を関連づけたタスク処理手順テーブルとを移動後に所属する情報処理機器の記憶手段に格納させ、タスク処理手段は、タスク指定情報により指定されるタスクの所属する情報処理機器に対応する処理を実行する。
【００１４】
この発明の他の局面に従うと、時系列で実行される複数の処理を含む所定のタスクを分散処理するために、複数の情報処理機器間をネットワークの通信チャンネルを介して移動可能な複数のエージェントプログラムを用いた分散処理プログラムであって、各エージェントプログラムは、タスクに対応し現在所属する情報処理機器と移動先の処理機器とを関連づける移動テーブルに基づいて、複数のチャンネルのうち選択を指示した通信チャンネルでネットワークと通信し、移動後に所属する情報処理機器の記憶手段に、タスクを実行するための処理プログラムと、タスクを実行するための処理データと、所属する通信チャンネルを示す通信チャンネル情報と、移動テーブルと、評価値とを関連づけて格納させる移動ステップと、所属する情報処理機器の記憶手段に格納される情報に基づいて、タスクの複数の処理のうち、所属する情報処理機器に対応する処理を実行するタスク処理ステップと、タスクの処理が完了することに応じて、評価値を更新する評価値更新ステップと、評価値の値に応じて、エージェント演算処理手段の分裂処理を行う分裂処理ステップと、同一の通信チャンネルに属する複数のエージェント演算処理手段の個数が所定数を超えることに応じて、同一の通信チャンネルに属する複数のエージェント演算処理手段に対応する通信チャンネルを離隔する処理を行う通信チャンネルステップとを、情報処理機器に実行させる。
【００１５】
好ましくは、各エージェントプログラムは、通信チャンネルのうち、選択された通信チャンネルに属するエージェントプログラムに消去処理を指示する消去指示ステップをさらに含む。
【００１６】
好ましくは、分裂処理ステップは、分裂前のエージェント演算処理手段に付随する処理プログラムと、処理データと、通信チャンネル情報と、移動テーブルとを引き継いだエージェントプログラムを生成するステップを含む。
【００１７】
好ましくは、分裂処理ステップは、所定の突然変異確率で、移動テーブルを更新する突然変異処理ステップを含む。
【００１８】
好ましくは、移動ステップは、さらに、複数のタスクのうち対応するエージェント演算処理手段の処理するタスクを指定するタスク指定情報と、複数のタスクごとに対応する複数の処理を関連づけたタスク処理手順テーブルとを移動後に所属する情報処理機器の記憶手段に格納させるステップを含み、タスク処理ステップは、タスク指定情報により指定されるタスクの所属する情報処理機器に対応する処理を実行する。
【発明を実施するための最良の形態】
【００１９】
以下、図面を参照して本発明の実施の形態について説明する。
【００２０】
（本発明の概要）
本発明においては、ネットワークなどで接続された多数のコンピュータが、それぞれエージェントと呼ぶ自律的に処理を実行するプログラムを多数用いて、一つのタスクを異なる多数の計算機資源を用いて効率良く分散処理する。
【００２１】
以下にも説明するとおり、本発明では、コンピュータネットワーク全体での分散処理を最適化する手法として、マルチエージェントシステム（ＭＡＳ）の学習手法、特に、上述したＭＡＳの学習手法の一つであるＤＳ−ＬＡを用いる。
【００２２】
ＤＳ−ＬＡでは、エージェントをコロニーと呼ぶ集団に動的に離隔している。エージェントは、それぞれ特定の集団に所属する。そして、ＤＳ−ＬＡでは、エージェントの相互作用を、原則として、その集団内に制限する。また、高いパフォーマンスを得る他のエージェントの所属集団を真似する。その結果、集団の構成は動的に変化する。
【００２３】
より特定的には、本発明においては、この「集団」の一例として、ネットワーク全体をチャンネルと呼ぶ相互干渉のないいくつかのネットワークに仮想的に分割する。各チャンネルに所属するエージェント数が増加した場合、そのチャンネルに所属するエージェントは動的に離隔される。
【００２４】
本発明においては、一つのタスクを異なる多数の計算機資源を用いて分散処理するという目的を達成するために、コンピュータに所属する多数のエージェントが、コンピュータ間を移動しながら移動先の計算機資源を用いてタスクを処理する。各エージェントは、処理データとその処理プログラム（処理プログラムコード）、条件ごとの移動先、移動に用いる通信チャンネル、及び自己評価値などの情報をもつ。コンピュータは、計算機資源の一部を所属するエージェントに提供する。エージェントは、コンピュータウイルスとは異なり、提供された計算機資源でのみタスクを処理する。エージェントの移動は、各エージェントの属する通信チャンネルを介して行われる。
【００２５】
ＤＳ−ＬＡによる学習において、エージェントはチャンネルごとに離隔され、ネットワーク上で自らが知覚できる情報のみに基づいて更新される自己評価値が規定値を超えたものは分裂する。エージェント数が規定値を超えたチャンネルは、さらに動的に離隔される。
【００２６】
このエージェントの学習により分散処理の効率化が図られることになるが、効率化の際に、処理順序(直列分散)もエージェント学習により最適化される。これに伴い、ネットワークの構造自体、言い換えると、上述したようなコンピュータの集団の構造もエージェント学習により最適化を行うことができる。
【００２７】
［発明の実施の形態］
図１は、本発明の分散処理システム１０００の一例を示す概念図である。
【００２８】
図１を参照して、システム１０００は、無線ネットワークにより相互に通信が可能なコンピュータ１０．１〜１０．Ｎと、コンピュータ１０．１〜１０．Ｎを相互に無線ネットワークにより、いわゆる「インフラストラクチャモード」により接続することが可能な無線アクセスポイント２０とを備える。
【００２９】
ここで、無線アクセスポイント２０と各コンピュータ１０．１〜１０．Ｎとは、所定の通信周波数帯を複数の周波数帯にさらに分割したチャンネルのいずれかにより通信を行うものとする。そして、あるチャンネルで通信するコンピュータと、他のチャンネルで通信するコンピュータとは、ネットワークとしては分離されているものとする。さらに、後に説明するように、各コンピュータ１０．１〜１０．Ｎは、自己に所属するエージェントプログラムに応じて、通信するチャンネルを学習経過に基づいて変更することが可能であるものとする。したがって、無線アクセスポイント２０は、一台で複数のチャンネルでの通信を同時に行うことが可能な構成を有するものとする。また、後に説明するように、通常は、異なるチャンネル間の通信を許可しないものの、所定のブロードキャスト通信では、異なるチャンネル間での通信も許されるものとする。
【００３０】
また、このようなネットワークの例を考える場合、ネットワークの構成は、図１のような無線ネットワークに限られず、各コンピュータが、自己の通信するチャンネルを選択できる構成であれば、有線ネットワークでもかまわない。
【００３１】
なお、図１は、あくまでも本発明を説明するための具体例の１つであり、より一般的には、本発明は、以下のような条件をみたすコンピュータネットワークシステムに適用可能なものである。
【００３２】
（本発明を適用するシステムの条件）
ｉ）ネットワークで接続されている多数のコンピュータが存在する。
【００３３】
ｉｉ）上記コンピュータのハードウェア構成や処理能力は不均質でもかまわない。
【００３４】
ｉｉｉ）「処理すべきデータ」や「処理系(プログラムなど)」を持つ自律的で移動可能なエージェントと呼ぶプログラムが多数存在する、このエージェントに割り当てられるタスクも不均質でかまわない。
【００３５】
ｉｖ）コンピュータは、エージェントに計算機資源を提供する。エージェントは、自らのタスク処理系により、コンピュータ内で自律的に処理する
［ハードウェア構成］
図２に、図１に示したコンピュータ１０．１の外観を例として示す図である。
【００３６】
図２を参照してこのコンピュータ１０．１は、ＣＤ−ＲＯＭ（Compact Disc Read-Only Memory ）等のディスク１１８上の情報を読込むためのディスクドライブ１０８およびフレキシブルディスク（Flexible Disk、以下ＦＤ）１１６に情報を読み書きするためのＦＤドライブ１０６を備えたコンピュータ本体１０２と、コンピュータ本体１０２に接続された表示装置としてのディスプレイ１０４と、同じくコンピュータ本体１０２に接続された入力装置としてのキーボード１１０およびマウス１１２と、コンピュータ本体１０２に接続された無線通信装置１１４とを含む。
【００３７】
図３は、このコンピュータ１０．１の構成をブロック図形式で示す図である。
【００３８】
図３に示されるように、このコンピュータ１０．１を構成するコンピュータ本体１０２は、ディスクドライブ１０８およびＦＤドライブ１０６に加えて、それぞれバスＢＳに接続されたＣＰＵ（Central Processing Unit ）１２０と、ＲＯＭ（Read Only Memory) およびＲＡＭ （Random Access Memory）を含むメモリ１２２と、直接アクセスメモリ装置、たとえば、ハードディスク１２４と、無線通信装置１１４とデータの授受を行うための通信インタフェース１２８とを含んでいる。ディスクドライブ１０８にはディスク１１８が装着される。ＦＤドライブ１０６にはＦＤ１１６が装着される。
【００３９】
なお、ディスク１１８は、コンピュータ本体に対してインストールされるプログラム等の情報を記録可能な媒体であれば、ＣＤ−ＲＯＭ以外の他の媒体、たとえば、ＤＶＤ−ＲＯＭ（Digital Versatile Disc）やメモリカードなどでもよく、その場合は、コンピュータ本体１０２には、これらの媒体を読取ることが可能なドライブ装置が設けられる。
【００４０】
本発明の分散処理システムの主要部は、コンピュータハードウェアと、ＣＰＵ１２０により実行されるソフトウェアとにより構成される。一般的にこうしたソフトウェアはディスク１１８、ＦＤ１１６等の記憶媒体に格納されて流通し、ディスクドライブ１０８またはＦＤドライブ１０６等により記憶媒体から読取られてハードディスク１２４に一旦格納される。または、当該装置がネットワークに接続されている場合には、ネットワーク上のサーバから一旦ハードディスク１２４にコピーされる。そうしてさらにハードディスク１２４からメモリ１２２中のＲＡＭに読出されてＣＰＵ１２０により実行される。なお、ネットワーク接続されている場合には、ハードディスク１２４に格納することなくＲＡＭに直接ロードして実行するようにしてもよい。
【００４１】
図２および図３に示したコンピュータのハードウェア自体およびその動作原理は一般的なものである。したがって、本発明の最も本質的な部分は、ＦＤ１１６、ディスク１１８、ハードディスク１２４等の記憶媒体に記憶されたソフトウェアである。
【００４２】
なお、一般的傾向として、コンピュータのオペレーティングシステムの一部として様々なプログラムモジュールを用意しておき、アプリケーションプログラムはこれらモジュールを所定の配列で必要な時に呼び出して処理を進める方式が一般的である。そうした場合、当該分散処理システムを実現するためのソフトウェア自体にはそうしたモジュールは含まれず、当該コンピュータでオペレーティングシステムと協働してはじめて分散処理システムが実現することになる。しかし、一般的なプラットフォームを使用する限り、そうしたモジュールを含ませたソフトウェアを流通させる必要はなく、それらモジュールを含まないソフトウェア自体およびそれらソフトウェアを記録した記録媒体（およびそれらソフトウェアがネットワーク上を流通する場合のデータ信号）が実施の形態を構成すると考えることができる。
【００４３】
なお、他のコンピュータ１０．２〜１０．Ｎも、コンピュータ１０．１と基本的には、同様な構成を有する。
【００４４】
［本発明による分散処理システムの基本的原理］
［ＤＳ−ＬＡの概要］
図４は、ＤＳ−ＬＡの概念を示す図である。
【００４５】
ＤＳ−ＬＡは、更新された行動戦略による行動戦略の上書きと、所属変更による動的離隔をもつアルゴリズムである。以下に説明する行動戦略の上書きとして、エージェントの移動先を示すテーブルの更新が行なわれ、自身に付随する評価値が所定値を超えたエージェントは分裂し、分裂する際には、この移動先を示すテーブル（行動戦略）は引き継ぐ。さらに、所属するチャンネルのエージェント数が、所定数を越えたチャネルに属するエージェントは、図４に示すとおり２つのチャンネルに離隔される。このような動的離隔では、個々のエージェントは、複数のチャンネルと呼ぶ仮想集団のいずれかに所属し、他のチャンネルに属するエージェントとは、原則的に相互作用しない。あるチャンネルに所属するコンピュータ数がある限度以上増加する場合、たとえば、そのチャンネルに所属するエージェントの半数は新しいチャンネルに所属を変更する。
【００４６】
［シミュレーション実験に用いるＤＳ−ＬＡのアルゴリズム］
図５は、ＤＳ−ＬＡのアルゴリズムを説明するためのフローチャートである。
【００４７】
以下、図５を参照して、ＤＳ−ＬＡのアルゴリズムについて、さらに詳しく説明する。
【００４８】
なお、以下で各エージェントが行う処理は、エージェントに付随して移動する対応するタスクの処理プログラムに基づいて、その時点で当該エージェントが所属するコンピュータのＣＰＵ１２０が実行するものである。
【００４９】
（１）初期化
まず、システム１０００には、ＤＳ−ＬＡを適用するＮ台（Ｎ：２以上の自然数）のコンピュータ、たとえば、５つのコンピュータ｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝、所定数、たとえば１００００の通信チャンネル、および所定数、たとえば１０００００のエージェントが存在するものとする。すなわち、以下の説明では、コンピュータ１０．１〜１０．Ｎとして、コンピュータＡ〜Ｅがシステム１０００に存在するものとする。
【００５０】
各コンピュータＡ〜Ｅにおいて、まず、以下の初期設定の処理が行われる（ステップ１００）。
【００５１】
各エージェントは、ランダムに選択したコンピュータ、およびチャンネルに所属し、自らの評価値、処理すべきタスクの種類、処理すべきタスクのデータ、および移動するコンピュータを示すテーブルをもつ。 
【００５２】
ここで、図６は、あるエージェントが、コンピュータＡに所属する際に、コンピュータＡのハードディスク１２４内に格納するデータテーブルの例を示す図である。
【００５３】
すなわち、このエージェントは、たとえば、ハードディスク１２４の所定の記憶領域に、自分の所属するコンピュータを示す変数ＢＬｐｃ、処理するタスクの種類Ｔｋ、処理すべきタスクのデータＤ、所属チャンネル番号Ｎchan(ｉ)、評価値Ｕ(ｉ、t)および後に説明するようにして獲得した自身と同一チャネルに属するエージェントの個数Ｎａｇを格納している。また、処理の単位時間の経過を示す変数ｔを１とする。
【００５４】
「変数ＢＬｐｃ」は、この例では、コンピュータ｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝のうちの何れかの値をとる。
【００５５】
「所属チャンネル番号Ｎchan(ｉ)」は、ｉ番目のエージェントが所属するチャンネルを示す番号であり、ここでは、Ｎchan(ｉ) ∈｛１，２，…，Ｎchansum（＝１００００）｝であるものとする。
【００５６】
「評価値Ｕ(ｉ、t)」は、自らの累積評価に基づく各コンピュータの学習指標であり、初期値Ｕ(ｉ、０)は、たとえば「１０」である。
【００５７】
さらに、図７は、あるエージェントが、コンピュータＡに所属する際に、コンピュータＡのハードディスク１２４内に格納する、タスクの処理手順テーブルおよび移動先のコンピュータを示す移動テーブルの例を示す図である。
【００５８】
図７（Ａ）に示すとおり、タスクの種類として、たとえば２つのタスクＸおよびタスクＹがあるとき、「タスクの処理手順テーブル」には、タスクＸでは、第１〜第５の処理として、処理ａ、処理ｂ、処理ｃ、処理ｄ、処理ｅがこの順序で行なわれ、タスクＹでは、第１〜第５の処理として、処理ａ、処理ｃ、処理ｅ、処理ｂ、処理ｄがこの順序で行なわれるとの情報が格納される。
【００５９】
一方、図７（Ｂ）に示すとおり、「移動テーブル」には、タスクＩ（Ｉ＝Ｘ，Ｙ）を行なっているエージェントが、あるタイムステップにおいてコンピュータＪ（Ｊ＝Ａ，Ｂ，Ｃ，Ｄ，Ｅ）に所属する場合に、次のタイムステップでどのコンピュータに移動するかを示す情報Ｔ（Ｊ，Ｉ）（ここで、Ｔ（Ｊ，Ｉ）∈｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝）が格納されている。
【００６０】
以上の「移動テーブル」、所属チャンネル番号Ｎchan(ｉ)および評価値Ｕ(ｉ、t)は、学習によりその値が変化する。
【００６１】
初期の「移動テーブル」としては、Ｔ（Ｊ，Ｘ）およびＴ（Ｊ，Ｙ）とも、｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝から無作為に選択された値を有するものとし、初期チャンネル番号としても無作為に選択されたチャンネル番号を持つものとする。また、各エージェントは、自身と同一チャンネル内に存在する他のエージェントを照会し、照会の結果得られる個数Ｎａｇをハードディスク１２４中に記録しておくものとする。
【００６２】
再び、図５を参照して、初期設定に続いて以下の処理が行われる。
【００６３】
（２）タスク獲得：タスクを保持していない、またはタスクを完了したエージェントは、無作為に選択されたタスクＸまたはＹを得る（ステップＳ１０２）。言い換えると、エージェントが発生する乱数にしたがって、いずれかのタスクを自己の処理する対象とするかを選択する。
【００６４】
（３）タスク処理：各エージェントは、ステップＳ１０２において選択されたタスクに応じて、図７（Ａ）に従う処理手順を行う（ステップＳ１０４）。ここで、コンピュータＡ、Ｂ、Ｃ、Ｄ、Ｅに所属するエージェントは、それぞれ、処理ａ、処理ｂ、処理ｃ、処理ｄ、処理ｅを行うことができる。このとき、エージェントは、自己の所属するコンピュータが、その時点で行うべき処理に対応していないときには、この単位時間の処理においては、タスク処理についての処理を行わず、次のステップへ処理を進める。
【００６５】
なお、各コンピュータで、いずれの処理が可能かは、各コンピュータが情報として格納しておき、エージェントがコンピュータに問い合わせることにより判断できる。または、各エージェントが、各コンピュータでいずれの処理が可能かのテーブルを保持しつつ移動することとしてもよいし、あるいは、各エージェントが、現在所属するコンピュータのハードウェアの情報を診断して、現時点で行うべき処理が、現在所属するコンピュータで実行可能かをその都度判断することとしてもよい。
【００６６】
（４）タスク完了判定：各エージェントはタスクを完了したかを判定し（ステップＳ１０６）、タスクの処理を完了したエージェントは、評価値を、たとえば、以下の式にしたがって更新する（ステップＳ１０８）。
【００６７】
Ｕ(ｉ、t)＝Ｕ(ｉ、t−１)＋（５０−ｔ×２）
すなわち、より短い時間でタスクを完了したエージェントほど評価値が増加し、所定の時間以上をタスク完了に要したエージェントの評価値は、初期値を下回ることになる。
【００６８】
なお、タスクが終了したエージェントは、たとえば、処理の結果を所定のコンピュータに通知するものとしておけば、ユーザは、タスクの処理結果を閲覧することができる。
【００６９】
一方、タスクが完了していない場合は、処理はステップＳ１１０に移行する。
【００７０】
（５）移動：各エージェントは、１０の状態空間（タスクの種類×所属するコンピュータの種類）ごとに移動テーブルの値（Ｔ（Ｊ，Ｉ）∈｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝）に従い、自らの保持するタスクと共に移動する（ステップＳ１１０）。
【００７１】
すなわち、各エージェントは、図６に示したデータテーブルの情報ならびに図７に示した「タスクの処理手順テーブル」および「移動テーブル」の情報を伴って移動する。言い換えると、移動元のＣＰＵ１２０は、エージェントの処理プログラム自身と、図６に示したデータテーブルの情報ならびに図７に示した「タスクの処理手順テーブル」および「移動テーブル」の情報とを、エージェントに対応する通信チャネルを介して送信し、移動先のコンピュータのハードディスク１２４に格納させる。移動先のＣＰＵ１２０は、これら移動してきたエージェントの処理プログラムと付随する情報とに基づいて、処理を実行する。
【００７２】
（６）エージェントの分裂：続いて、各エージェントは分裂処理を実行する（ステップＳ１１２）。
【００７３】
図８は、このような分裂処理の手順を示すフローチャートである。図８を参照して、エージェントの評価値が、所定の値、たとえば、初期評価値の２倍を越えた場合（ステップＳ２００）、そのエージェントは分裂する（ステップＳ２０２）。このとき、評価値の分配も行われる（ステップＳ２０２）。たとえば、分裂後の各エージェントの評価値は、分裂前の評価値の半分ずつになり、移動テーブルは引き継ぐ。
【００７４】
つまり、エージェントの分裂では、エージェントは、自身に付随する、処理プログラムと、処理データと、通信チャンネル情報と、移動テーブルとを引き継いだエージェントを、所属するコンピュータのハードディスク１２４上に生成する。
【００７５】
続いて、突然変異確率Ｐｍｕｔ(たとえば、Ｐｍｕｔ＝０．０５)に従いテーブルの値が変異する。このとき、突然変異確率に従い、突然変異を行うこととなったときには、たとえば、Ｔ（Ｊ，Ｘ）およびＴ（Ｊ，Ｙ）とも、｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝から無作為に値を選択するものとする。
【００７６】
（７）チャンネルの動的離隔：再び、図５を参照して、続いて、各エージェントは、所属するエージェント数が限界個体数（たとえば、１０）を超えたか否かを判断し（ステップＳ１１４）、限界数を超えている場合は、当該チャンネルに所属するエージェントは、２つのチャンネルに離隔される（ステップＳ１１６）。このときは、同一のチャンネルに属するエージェントは相互に通信可能であるので、たとえば、無線アクセスポイント２０に現在空き状態であるチャネルを照会した上で、相互に情報を交換して、従前のチャンネルに残るエージェントと、新しいチャンネル（空チャンネル）に移るエージェントを決定する。なお、このとき、２つのグループは、ほぼ同数となるようにするとの条件を付加してもよい。
【００７７】
さらに、たとえば、チャンネル離隔を行ったエージェントのうち、元のチャンネルに残存したエージェントは、相互通信によりランダムに他のチャンネルを選択し、ブロードキャスト通信により、その選択されたチャンネルに所属する全てのエージェントに対して消去を指示する。消去が指示されたチャンネルに属するエージェントは自身を消去する（ステップＳ１１８）。
【００７８】
続いて、変数ｔをインクリメントして、処理は、ステップＳ１０２に復帰する。
【００７９】
このようなステップＳ１０２からステップＳ１１８までの処理を行う期間を「単位時間」と呼ぶ。
【００８０】
以上説明したようなエージェントの動作により、各エージェントは、この場合５10通りの移動テーブルから最適なものを学習する。
【００８１】
（シミュレーション実験の結果）
図９は、実験結果の一つとして、移動テーブルにおける状態空間ごとの個体数比率の時間変化を示す図である。
【００８２】
たとえば、タスクＸをコンピュータＡで実行するエージェントについて、次の移動先Ｔ（Ａ，Ｘ）は、時間の経過とともに、コンピュータＢに収束していく。他のコンピュータＢ〜Ｅについても、特定の移動先に収束する。
【００８３】
同様に、タスクＹをコンピュータＡで実行するエージェントについて、次の移動先Ｔ（Ａ，Ｙ）は、時間の経過とともに、コンピュータＣに収束していく。タスクＹにおいても、他のコンピュータＢ〜Ｅおける移動先は、特定のコンピュータに収束する。
【００８４】
図１０は、このようにして移動先が収束した際に生成されるタスク処理のネットワークを示す図である。
【００８５】
図１０に示すとおり、タスクＸについては、コンピュータＡ→コンピュータＢ→コンピュータＣ→コンピュータＤ→コンピュータＥ→コンピュータＡというネットワークができる。これは、タスクＸの処理の順序に対応したネットワークである。
【００８６】
同様に、タスクＹについては、コンピュータＡ→コンピュータＣ→コンピュータＥ→コンピュータＢ→コンピュータＤ→コンピュータＡというネットワークができる。これも、タスクＹの処理の順序に対応したネットワークである。
【００８７】
図１１は、エージェントの平均評価値の時間変化示す図である。時間の経過とともに、各エージェントの評価値の平均値も時間の経過とともに一定値に収束する。
【００８８】
図９〜図１１に示したこれらの結果から、各エージェントがタスクの種類と自らの所属するコンピュータに応じて最適な移動先を自律的に選択し、高い評価値を獲得していることがわかる。
【００８９】
タスク処理の手順やネットワーク状況が未知である多数のエージェントが、ＤＳ−ＬＡにより学習することで、コンピュータ間を最適な手順で移動しタスクを処理した実験結果から、創発的なネットワーク生成が可能であることがわかる。
【００９０】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【００９１】
【図１】本発明の分散処理システム１０００の一例を示す概念図である。
【図２】図１に示したコンピュータ１０．１の外観を例として示す図である。
【図３】コンピュータ１０．１の構成をブロック図形式で示す図である。
【図４】ＤＳ−ＬＡの概念を示す図である。
【図５】ＤＳ−ＬＡのアルゴリズムを説明するためのフローチャートである。
【図６】あるエージェントが、コンピュータＡに所属する際に、コンピュータＡのハードディスク１２４内に格納するデータテーブルの例を示す図である。
【図７】タスクの処理手順テーブルおよび移動先のコンピュータを示す移動テーブルの例を示す図である。
【図８】分裂処理の手順を示すフローチャートである。
【図９】移動テーブルにおける状態空間ごとの個体数比率の時間変化を示す図である。
【図１０】移動先が収束した際に生成されるタスク処理のネットワークを示す図である。
【図１１】エージェントの平均評価値の時間変化示す図である。
【符号の説明】
【００９２】
１０．１〜１０．Ｎ  コンピュータ、２０  無線アクセスポイント、１０２  コンピュータ本体、１０４  ディスプレイ、１０６  ＦＤドライブ、１０８  ディスクドライブ、１１０  キーボード１１０、１１２  マウス、１１４  無線通信装置、１１８  ＣＤ−ＲＯＭ、  １２０  ＣＰＵ、  １２２  メモリ、１２４  ハードディスク、１２８  通信インタフェース、１０００  システム。
【図１】
2005332082.tif 000003
【図２】
2005332082.tif 000004
【図３】
2005332082.tif 000005
【図４】
2005332082.tif 000006
【図５】
2005332082.tif 000007
【図６】
2005332082.tif 000008
【図７】
2005332082.tif 000009
【図８】
2005332082.tif 000010
【図９】
2005332082.tif 000011
【図１０】
2005332082.tif 000012
【図１１】
2005332082.tif 000013