ネットワーク資源分配方法
【目的】 効率よく大規模なネットワーク資源を所定のタスクに最適に分配することができるネットワーク資源分配方法を提供する。
【構成】 各タスクを実現する複数の経路候補を生成し、各タスクの経路候補を直列的にコード化した経路候補染色体を所定の集合サイズの個数だけ生成する経路候補染色体生成工程２００と、前記経路候補染色体に対して交叉と選択と評価とからなる操作を繰り返して最適な経路を特定する最適経路特定工程３００とを有し、前記最適経路特定工程３００で特定した経路が所定の適合条件を満足しない時に、前記経路候補染色体生成工程２００と最適経路特定工程３００を繰り返すこととした。
【構成】 各タスクを実現する複数の経路候補を生成し、各タスクの経路候補を直列的にコード化した経路候補染色体を所定の集合サイズの個数だけ生成する経路候補染色体生成工程２００と、前記経路候補染色体に対して交叉と選択と評価とからなる操作を繰り返して最適な経路を特定する最適経路特定工程３００とを有し、前記最適経路特定工程３００で特定した経路が所定の適合条件を満足しない時に、前記経路候補染色体生成工程２００と最適経路特定工程３００を繰り返すこととした。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は複数のノードと容量を有する複数のリンクからなるネットワーク資源を、所定の起点ノードと終点ノードと流量とを有する複数のタスクに最適に分配するネットワーク資源分配方法に係り、特に遺伝的アルゴリズムの手法によって最適解を得るようにしたネットワーク資源分配方法に関する。
【０００２】
【従来の技術】一般に、所定の通信ネットに所定数の通信回線を接続する場合や、所定の交通網に所定数の車両を走らせる場合は、如何に前記通信ネットや交通網を最大限に利用し、かつ、各通信回線あるいは各車両の運行がもっと効率良くなるかが問題となる。
【０００３】上記通信ネットや交通網は、ノードと容量を有するリンクからなるネットワークとして把握でき、また、上記通信回線や運行車両は、起点ノードと終点ノードと流量とを有するタスクとして把握できるので、上記問題は複数のタスクにネットワーク資源（ノードとリンク）を最適に分配する最適化問題となる。
【０００４】従来、このようなネットワーク資源の分配に対しては、一タスクずつ順番に経路を探索していく方法が用いられていた。
【０００５】上記方法は、予め決められた順番に従ってタスクごとに経路探索を行い、ｉ番目に探索する経路は、（ｉ−１）番目までのタスクで使用した経路は使用できないという条件の下で、順次最短経路を探索していく方法であった。
【０００６】上記従来の方法によるネットワーク資源分配方法は、ネットワークの規模やその負荷がある程度限られたものであるときは、比較的速く最適解を求めることができた。
【０００７】
【発明が解決しようとする課題】しかしながら、上記従来の方法によるネットワーク資源分配方法では、ネットワークの規模や負荷が大きくなると、経路の組合せが膨大になり、計算量の増加によって最適解を得ることが困難になる。
【０００８】また、最適解を得られる場合でも、経路探索するタスクの順番が得られる最適解の質に大きく影響するため、客観的に質のよい最適解を得られるネットワーク資源分配方法が求められていた。
【０００９】そこで、本発明の目的は、上記従来技術の問題を解決し、効率よく大規模なネットワーク資源を所定のタスクに最適に分配することができるネットワーク資源分配方法を提供することにある。
【００１０】
【課題を解決するための手段】上記目的を達成するために、本発明によるネットワーク資源分配方法は、複数のノードと容量を有する複数のリンクからなるネットワーク資源を、所定の起点ノードと終点ノードと流量とを有する複数のタスクに最適に分配するネットワーク資源分配方法において、前記各タスクを実現する複数の経路候補を生成し、各タスクの経路候補を直列的にコード化した経路候補染色体を所定の集合サイズの個数だけ生成する経路候補染色体生成工程と、前記経路候補染色体に対して交叉と選択と評価とからなる操作を繰り返して最適な経路を特定する最適経路特定工程とを有し、前記最適経路特定工程で特定した経路が所定の適合条件を満足しない時に、前記経路候補染色体生成工程と最適経路特定工程を繰り返すことを特徴とするものである。
【００１１】
【作用】上記経路候補染色体生成工程は、所定の数（集合サイズ）の経路候補染色体を生成する。この経路候補染色体の生成は、経路の競合が可能な限り少なくなるように経路の選択をするが、原則的には競合が生じても良いので、経路の作成順序に関わらずに経路候補を生成することができる。これにより、大規模のネットワークに対して容易に経路候補を生成することができる。
【００１２】上記経路候補染色体に対して、上記最適経路特定工程は、生物界における遺伝子染色体に類似した評価と選択と交叉という操作を繰り返し、与えられた条件（適合条件）により適合する最適経路を特定する。
【００１３】また、本発明のネットワーク資源分配方法で、最適経路特定工程で交叉と選択と評価を繰り返して求めた最適解が所定の適合条件を満たしていないとき、再度経路候補染色体生成工程に戻って新たな経路候補染色体の集合を生成する。これは、最初の経路候補染色体の集合が違った方向に進化することがあるからである。
【００１４】すなわち、本発明のネットワーク資源分配方法では、最初の経路候補染色体から求めた最適経路が適合条件を満たさない場合は経路候補染色体が違った方向に進化したとみなし、新たに別の経路候補染色体の集合から最適経路を求める。これは、生物界の進化における突然変異と同様にいわゆる個体の多様化と同一の作用を有し、経路候補染色体が違った方向に収束するのを防止することができる。
【００１５】
【実施例】以下、添付の図面を用いて本発明のネットワーク資源分配方法の一実施例について説明する。
【００１６】図１は、本発明によるネットワーク資源分配方法の処理の流れを示している。図１に示すように、本発明のネットワーク資源分配方法では、最初に対象とするネットワークに対してダイクストラ法によるラベル付けを行ってネットワークやタスクのモデル化を行う（ステップ１００）。このラベル付けによって、対象とする事象（ネットワークとタスク）をモデル化でき、計算機で取り扱うことができるようになるとともに、後述する確率的経路探索の方法で方向付けをすることが可能となる。
【００１７】ここで、ダイクストラ法によるラベル付けとは、所定の順番に従って、既にラベル付けをしたノードについてはラベル付けをしないという条件の下で、対象とするネットワークのすべてのノードにラベルを付すことである。このようにしてモデル化されたラベル付きネットワーク１の一例を図２に示す。
【００１８】図２はモデル化されたネットワークの具体例を示しており、全体を符号１で示したこの例のネットワークは、９個のノードＡ，Ｂ，Ｄ，Ｆ，…と、それらのノードを接続するリンクとからなり、各ノード間のリンクの本数はリンクの容量を示している。
【００１９】このネットワークに対して、タスクは下記のようになる。
今、上記タスク番号０のタスク（Ａ→Ｆ）を例にラベル付けについて説明すると、終点ノードＦはノード０となりノード０に隣り合うノード（ノードＤを含む）はラベル１とラベル付けされ、そのさらに隣りのノードはラベル２となり、起点ノードＡはラベル４となる。
【００２０】タスクに対するネットワーク資源の分配は換言すれば、各リンク容量の制約と各タスクの流量の保存という制約条件下で、上記ラベル付けされたネットワークの総ネットワーク資源使用量を最小にする最適化問題ということができる。
【００２１】次に上記最適化問題の解を求める本発明の方法について説明する。本発明による上記最適化問題の解法（ネットワーク資源分配方法）は、図１に示すように、経路候補染色体生成工程２００と最適経路特定工程３００とを有し、この経路候補染色体生成工程２００と最適経路特定工程３００を繰り返し実行することによって、ラベル付きネットワーク（タスクを含む）１を入力とし、最終的に適合解３を出力する。
【００２２】経路候補染色体生成工程２００における経路候補の生成は、経路候補間の競合（同一リンクを重複して使用する等）を考慮せずに経路候補を生成することも可能であるが、無作為に経路を生成すると一般的に計算時間は増加する。そこで、本実施例では、上記経路候補染色体生成工程２００において、確率的経路探索の手法を用いて経路候補を生成する。
【００２３】この確率的経路探索による経路候補生成では、経路を生成する途中で、所定のノードから進むことができる方向が複数存在するときに、終点ノードまでの距離とリンクの空き容量の期待値とによって重み付けをして正規化した確率を各方向に割り当て、その確率に基づいて方向選択をする。
【００２４】終点ノードまでの距離は、前記ダイクストラ法によって付けられたラベルを基に、ラベルの小さくなる方向に大きな値を割り当てる。また、リンクの空き容量の期待値は、まずタスクの要求状況に基づいて各リンクの資源使用量の期待値を算出し、各リンク容量からこれを差し引いたものを空き容量の期待値とする。
【００２５】上記確率的経路探索を用いた本実施例の経路候補染色体生成工程２００では、経路候補を生成する前にリンクの使用状況を計算し（ステップ２０１）、この計算結果を用いて上記方法で方向選択を行いながら、新しい経路候補を生成する（ステップ２０２）。生成された経路候補は、後述する方法でコード化され、経路候補の集合に加えられる（ステップ２０３）。このとき、経路候補の生成で経路間に競合が生じた場合は、必要に応じて経路候補の削除をして新たな経路候補を生成する。この繰り返しの処理を経路生成サイクル（Alternative Paths ）という。
【００２６】次に、生成された経路候補のコード化について説明する。コード化とは、各タスクを実現する一つずつの経路候補を直列的に羅列することであり、コード化によって生成される経路候補の羅列を経路候補染色体という。図３に経路候補染色体を具体的に示した。一つの経路候補染色体は、タスクを実現する経路の組を表している。経路候補染色体生成工程２００では、上記経路候補染色体は所定の集合サイズの個数ずつ生成される。
【００２７】次に、上記経路候補染色体の集合から、遺伝的アルゴリズムの手法によって最適な経路の組合せを有する経路候補染色体（最適解）を生成する最適経路特定工程３００について説明する。
【００２８】最適経路特定工程３００では、最初に各経路候補染色体の評価を行う（ステップ３０１）。この評価は、下記の適応度関数（式(1) ）と各リンクのオーバーフロー度（式(2) ）によって行う。
適応度関数＝１／（リンクの総使用量×リンクの総オーバーフロー度） (1) ただし、 リンクの総オーバーフロー度＝Πリンク各リンクのオーバーフロー度 各リンクのオーバーフロー度 ＝１ （オーバーフローなし） または、 リンク使用量／リンク容量 （オーバーフローあり） (2) 上記適応度関数は、リンクの総使用量が小さいほど経路候補染色体の適応度が大きくなることと、リンクの総オーバーフロー度が小さいほど染色体の適応度が大きくなることとを考慮して作成したものである。
【００２９】各リンクのオーバーフロー度は、最終的な経路候補の適合条件となり、求められた最適な経路の組合せで、オーバーフローするリンクが存在すれば、その経路の組合せは適合性がないということになる。
【００３０】次に、最適経路特定工程３００では、適合解があるか否かを判断し（ステップ３０２）、適合解でない場合は、適応度が高い（適応度関数の値が大きい）経路候補染色体を選択し（ステップ３０３）、選択された経路候補染色体同士を交叉させる（ステップ３０４）。全個体数に対して交叉させる個体の比率が交叉確率である。
【００３１】図３は、経路候補染色体の交叉の様子を示している。図３において、交叉する２つの経路候補染色体を親１および親２とすると、親１の経路候補染色体はＫ1,1-Ｋ2,2-Ｋ3,4-Ｋ4,1 の構成を有し、親２の経路候補染色体はＫ1,4-Ｋ2,1-Ｋ3,1-Ｋ4,3 の構成を有している。これら経路候補染色体を構成する構成部分Ｋn,mは、ｎ番目のタスクのｍ個目の経路候補を示している。
【００３２】交叉という操作では、上記親１と親２の経路候補染色体は、交叉点４で互いに構成部分Ｋ3,4 ，Ｋ4,1 とＫ3,1 ，Ｋ4,3 を入れ換える。この結果生成された子１および子２の経路候補染色体はそれぞれ、Ｋ1,1-Ｋ2,2-Ｋ3,1-Ｋ4,3 とＫ1,4-Ｋ2,1-Ｋ3,4-Ｋ4,1 となる。交叉点４は、意味のない経路の組合せ（致死遺伝子）を生じさせないように、各構成部分Ｋn,m の接続点となるように選択する。
【００３３】上記子１および子２の経路候補染色体は、前記適応度関数と各リンクのオーバーフロー度によって評価され（ステップ３０１，ステップ３０２）、適応度の高い経路候補染色体は選択され、再度交叉される。
【００３４】上記経路候補染色体の選択の代表的な選択方法として、ルーレット法とエリート保存法とがある。ルーレット法は、適応度に比例した確率を各個体に割り当て、これに従って個体のペアが順次生成する方法である。エリート保存法は、適応度が最大の個体を無条件に次の世代に残す方法である。
【００３５】ルーレット法の長所は、適応度の低い個体も選択され、進化の過程で結果的に適応度の高い個体を生成する可能性があることである。その反面、ルーレット法では、適応度の高い個体も淘汰される危険性がある。一方、エリート保存法の長所は、適応度の高い個体が必ず保存されることであるが、その反面、進化の過程で結果的に高い適応度を有することになる個体が進化の途中で淘汰される危険性を有している。
【００３６】本実施例における選択方法は、上記ルーレット法とエリート保存法の長所を組み合わせたものであり、所定数の適応度の高い個体を無条件に選択し、残るものについては、ルーレット法によって選択する。交叉によって制約に違反した経路候補染色体（たとえば、リンクの容量を超えるような場合）が発生しても、これを直ちに切り捨てるのではなく、制約に違反したレベルに応じてペナルティーを付けて保留する。これにより、適応度が高い経路候補染色体は必ず保存され、適応度が低い経路候補染色体も、進化の過程で良い適合解となることがある。
【００３７】上記最適経路特定工程３００における評価、選択、交叉の１サイクルは、進化の１世代という。本実施例のネットワーク資源分配方法では、予め最適経路特定工程３００で進化の世代数を指定しておき、この世代数進化を繰り返した後の解について適合条件（所定値以上の適応度を有し、リンクのオーバーフローがないという条件）を満足するか否か判断する。適合条件を満足すれば、その解を適合解３とし、満足しなければ経路候補染色体生成工程２００に戻って、別の経路候補染色体の集合を生成する。この経路候補染色体生成工程２００と最適経路特定工程３００の間の繰り返しのサイクルは、経路生成−経路特定サイクル（Generate Path - GA Cycles ）という。
【００３８】このように経路生成−経路特定サイクルを有しているのは、生物界の突然変異と同じ作用・効果を取り入れるためである。すなわち、生物界では、進化は必ずしも最適な形態にたどり着く保証はないので、突然変異によって進化の途中でそれまでの進化と無関係な個体が発生し、これによって最適な形態にたどり着く可能性を得ることができる。
【００３９】これに対して本実施例の経路生成−経路特定サイクルは、所定の世代数進化を繰り返した後に、適合解を得ることができないときに、新たな経路候補染色体の集合を生成するので、経路候補染色体が多様化され、誤った解に収束することを防止することができる。
【００４０】本実施例によるネットワーク資源分配方法の処理の流れは以上の通りであるが、次に本実施例のネットワーク資源分配方法を実行するための計算機の入力画面について説明する。
【００４１】図４は、対象とするネットワークの構造を数値マトリックスとして表示し、使用者に必要に応じてそのネットワークの構造を変更させる入力画面である。図４において、縦と横の数字は各ノードを示しており、数値マトリックスの各数値は、その縦と横のノードを結ぶリンクの容量を示している。たとえば、図においてノード０とノード１を結ぶリンクの容量は２０であり、ノード０とノード２の間にはリンクが存在していない。この数値マトリックスの数値を使用者が入力することにより、任意のネットワークを形成することができる。
【００４２】図５は、実行すべきタスクのリストを示している。このタスクリストの各タスクは、左側からタスク番号、起点ノード、終点ノード、流量の順に記載されており、使用者がその数値を入力することによって、任意のタスクを設定することができる。
【００４３】図６は、本発明のネットワーク資源分配方法の実行の条件を定める入力画面を示している。図において、Number of individuals は、前記経路候補染色体生成工程２００で生成する集合サイズであり、Crossover Rateは、経路候補染色体を交叉させる確率である。また、Generate Path-GA Cycles は、上述した通り経路候補染色体の集合を生成させる回数であり、Number of Altenative Pathsは、経路候補を追加・削除する回数であり、Generation Stepsは、進化の世代数である。使用者は、この入力画面の数値を自由に設定することにより、おおよその計算時間や最適解の適応度を設定することができる。
【００４４】次に、本発明のネットワーク資源分配方法と従来のダイクストラ法によるネットワーク資源の分配の処理時間と最適解の適応度とを比較して説明する。
【００４５】図７(a) ，(b) は、要求資源量の割合に対する本発明のネットワーク資源分配方法と従来のダイクストラ法の処理時間と適応度を示したグラフである。ここで、図７のグラフの横軸のタスクの要求資源量は、下式(3) のように定義される。
図７(a) より明らかなように、タスク要求資源量の割合が０．４８以下の範囲ではダイクストラ法の方が先に最適解を発見するが、タスク要求資源量が０．４８以上の範囲では本発明のネットワーク資源分配方法の方が先に最適解を発見する。特に、タスク要求資源量の割合が０．５０を超える範囲では、従来のダイクストラ法は、実時間で最適解を求めることができなくなる。これに対して本発明のネットワーク資源分配方法では、タスク要求資源量の割合が０．６５までの範囲について、最適解を求めることができた。
【００４６】また、図７(b) に示すように、本発明のネットワーク資源分配方法の方が従来のダイクストラ法に比べて一般的に最適解の適応度が高い。
【００４７】
【発明の効果】以上の説明から明らかなように、本発明のネットワーク資源分配方法は、経路候補染色体生成工程と最適経路特定工程を有し、この経路候補染色体生成工程と最適経路特定工程を繰り返すことによって最適なタスクの経路を特定するので、ネットワークの規模に関わらず初期のタスクの経路候補の作成が簡単であり、かつ、これら経路候補に対して遺伝的アルゴリズムによって適応度が高い適合解を短い時間で求めることができる。
【００４８】これにより、大規模なネットワーク資源に対して、ネットワーク資源を効率よく、かつ、最適に所定のタスクに分配するネットワーク資源分配方法を得ることができる。
【図面の簡単な説明】
【図１】本発明のネットワークの処理の流れを示した流れ図。
【図２】モデル化されたネットワークを例示した図。
【図３】経路候補染色体とその交叉の様子を示した図。
【図４】ネットワーク構造の入力画面を示した図。
【図５】タスクの入力画面を示した図。
【図６】本発明のネットワーク資源分配方法の実行条件の入力画面を示した図。
【図７】本発明のネットワーク資源分配方法と従来のダイクストラ法の処理時間と適応度を比較して示したグラフ。
【符号の説明】
１ ラベル付きネットワーク
２ リンク
３ 適合解
２００ 経路候補染色体生成工程
３００ 最適経路特定工程
【０００１】
【産業上の利用分野】本発明は複数のノードと容量を有する複数のリンクからなるネットワーク資源を、所定の起点ノードと終点ノードと流量とを有する複数のタスクに最適に分配するネットワーク資源分配方法に係り、特に遺伝的アルゴリズムの手法によって最適解を得るようにしたネットワーク資源分配方法に関する。
【０００２】
【従来の技術】一般に、所定の通信ネットに所定数の通信回線を接続する場合や、所定の交通網に所定数の車両を走らせる場合は、如何に前記通信ネットや交通網を最大限に利用し、かつ、各通信回線あるいは各車両の運行がもっと効率良くなるかが問題となる。
【０００３】上記通信ネットや交通網は、ノードと容量を有するリンクからなるネットワークとして把握でき、また、上記通信回線や運行車両は、起点ノードと終点ノードと流量とを有するタスクとして把握できるので、上記問題は複数のタスクにネットワーク資源（ノードとリンク）を最適に分配する最適化問題となる。
【０００４】従来、このようなネットワーク資源の分配に対しては、一タスクずつ順番に経路を探索していく方法が用いられていた。
【０００５】上記方法は、予め決められた順番に従ってタスクごとに経路探索を行い、ｉ番目に探索する経路は、（ｉ−１）番目までのタスクで使用した経路は使用できないという条件の下で、順次最短経路を探索していく方法であった。
【０００６】上記従来の方法によるネットワーク資源分配方法は、ネットワークの規模やその負荷がある程度限られたものであるときは、比較的速く最適解を求めることができた。
【０００７】
【発明が解決しようとする課題】しかしながら、上記従来の方法によるネットワーク資源分配方法では、ネットワークの規模や負荷が大きくなると、経路の組合せが膨大になり、計算量の増加によって最適解を得ることが困難になる。
【０００８】また、最適解を得られる場合でも、経路探索するタスクの順番が得られる最適解の質に大きく影響するため、客観的に質のよい最適解を得られるネットワーク資源分配方法が求められていた。
【０００９】そこで、本発明の目的は、上記従来技術の問題を解決し、効率よく大規模なネットワーク資源を所定のタスクに最適に分配することができるネットワーク資源分配方法を提供することにある。
【００１０】
【課題を解決するための手段】上記目的を達成するために、本発明によるネットワーク資源分配方法は、複数のノードと容量を有する複数のリンクからなるネットワーク資源を、所定の起点ノードと終点ノードと流量とを有する複数のタスクに最適に分配するネットワーク資源分配方法において、前記各タスクを実現する複数の経路候補を生成し、各タスクの経路候補を直列的にコード化した経路候補染色体を所定の集合サイズの個数だけ生成する経路候補染色体生成工程と、前記経路候補染色体に対して交叉と選択と評価とからなる操作を繰り返して最適な経路を特定する最適経路特定工程とを有し、前記最適経路特定工程で特定した経路が所定の適合条件を満足しない時に、前記経路候補染色体生成工程と最適経路特定工程を繰り返すことを特徴とするものである。
【００１１】
【作用】上記経路候補染色体生成工程は、所定の数（集合サイズ）の経路候補染色体を生成する。この経路候補染色体の生成は、経路の競合が可能な限り少なくなるように経路の選択をするが、原則的には競合が生じても良いので、経路の作成順序に関わらずに経路候補を生成することができる。これにより、大規模のネットワークに対して容易に経路候補を生成することができる。
【００１２】上記経路候補染色体に対して、上記最適経路特定工程は、生物界における遺伝子染色体に類似した評価と選択と交叉という操作を繰り返し、与えられた条件（適合条件）により適合する最適経路を特定する。
【００１３】また、本発明のネットワーク資源分配方法で、最適経路特定工程で交叉と選択と評価を繰り返して求めた最適解が所定の適合条件を満たしていないとき、再度経路候補染色体生成工程に戻って新たな経路候補染色体の集合を生成する。これは、最初の経路候補染色体の集合が違った方向に進化することがあるからである。
【００１４】すなわち、本発明のネットワーク資源分配方法では、最初の経路候補染色体から求めた最適経路が適合条件を満たさない場合は経路候補染色体が違った方向に進化したとみなし、新たに別の経路候補染色体の集合から最適経路を求める。これは、生物界の進化における突然変異と同様にいわゆる個体の多様化と同一の作用を有し、経路候補染色体が違った方向に収束するのを防止することができる。
【００１５】
【実施例】以下、添付の図面を用いて本発明のネットワーク資源分配方法の一実施例について説明する。
【００１６】図１は、本発明によるネットワーク資源分配方法の処理の流れを示している。図１に示すように、本発明のネットワーク資源分配方法では、最初に対象とするネットワークに対してダイクストラ法によるラベル付けを行ってネットワークやタスクのモデル化を行う（ステップ１００）。このラベル付けによって、対象とする事象（ネットワークとタスク）をモデル化でき、計算機で取り扱うことができるようになるとともに、後述する確率的経路探索の方法で方向付けをすることが可能となる。
【００１７】ここで、ダイクストラ法によるラベル付けとは、所定の順番に従って、既にラベル付けをしたノードについてはラベル付けをしないという条件の下で、対象とするネットワークのすべてのノードにラベルを付すことである。このようにしてモデル化されたラベル付きネットワーク１の一例を図２に示す。
【００１８】図２はモデル化されたネットワークの具体例を示しており、全体を符号１で示したこの例のネットワークは、９個のノードＡ，Ｂ，Ｄ，Ｆ，…と、それらのノードを接続するリンクとからなり、各ノード間のリンクの本数はリンクの容量を示している。
【００１９】このネットワークに対して、タスクは下記のようになる。
今、上記タスク番号０のタスク（Ａ→Ｆ）を例にラベル付けについて説明すると、終点ノードＦはノード０となりノード０に隣り合うノード（ノードＤを含む）はラベル１とラベル付けされ、そのさらに隣りのノードはラベル２となり、起点ノードＡはラベル４となる。
【００２０】タスクに対するネットワーク資源の分配は換言すれば、各リンク容量の制約と各タスクの流量の保存という制約条件下で、上記ラベル付けされたネットワークの総ネットワーク資源使用量を最小にする最適化問題ということができる。
【００２１】次に上記最適化問題の解を求める本発明の方法について説明する。本発明による上記最適化問題の解法（ネットワーク資源分配方法）は、図１に示すように、経路候補染色体生成工程２００と最適経路特定工程３００とを有し、この経路候補染色体生成工程２００と最適経路特定工程３００を繰り返し実行することによって、ラベル付きネットワーク（タスクを含む）１を入力とし、最終的に適合解３を出力する。
【００２２】経路候補染色体生成工程２００における経路候補の生成は、経路候補間の競合（同一リンクを重複して使用する等）を考慮せずに経路候補を生成することも可能であるが、無作為に経路を生成すると一般的に計算時間は増加する。そこで、本実施例では、上記経路候補染色体生成工程２００において、確率的経路探索の手法を用いて経路候補を生成する。
【００２３】この確率的経路探索による経路候補生成では、経路を生成する途中で、所定のノードから進むことができる方向が複数存在するときに、終点ノードまでの距離とリンクの空き容量の期待値とによって重み付けをして正規化した確率を各方向に割り当て、その確率に基づいて方向選択をする。
【００２４】終点ノードまでの距離は、前記ダイクストラ法によって付けられたラベルを基に、ラベルの小さくなる方向に大きな値を割り当てる。また、リンクの空き容量の期待値は、まずタスクの要求状況に基づいて各リンクの資源使用量の期待値を算出し、各リンク容量からこれを差し引いたものを空き容量の期待値とする。
【００２５】上記確率的経路探索を用いた本実施例の経路候補染色体生成工程２００では、経路候補を生成する前にリンクの使用状況を計算し（ステップ２０１）、この計算結果を用いて上記方法で方向選択を行いながら、新しい経路候補を生成する（ステップ２０２）。生成された経路候補は、後述する方法でコード化され、経路候補の集合に加えられる（ステップ２０３）。このとき、経路候補の生成で経路間に競合が生じた場合は、必要に応じて経路候補の削除をして新たな経路候補を生成する。この繰り返しの処理を経路生成サイクル（Alternative Paths ）という。
【００２６】次に、生成された経路候補のコード化について説明する。コード化とは、各タスクを実現する一つずつの経路候補を直列的に羅列することであり、コード化によって生成される経路候補の羅列を経路候補染色体という。図３に経路候補染色体を具体的に示した。一つの経路候補染色体は、タスクを実現する経路の組を表している。経路候補染色体生成工程２００では、上記経路候補染色体は所定の集合サイズの個数ずつ生成される。
【００２７】次に、上記経路候補染色体の集合から、遺伝的アルゴリズムの手法によって最適な経路の組合せを有する経路候補染色体（最適解）を生成する最適経路特定工程３００について説明する。
【００２８】最適経路特定工程３００では、最初に各経路候補染色体の評価を行う（ステップ３０１）。この評価は、下記の適応度関数（式(1) ）と各リンクのオーバーフロー度（式(2) ）によって行う。
適応度関数＝１／（リンクの総使用量×リンクの総オーバーフロー度） (1) ただし、 リンクの総オーバーフロー度＝Πリンク各リンクのオーバーフロー度 各リンクのオーバーフロー度 ＝１ （オーバーフローなし） または、 リンク使用量／リンク容量 （オーバーフローあり） (2) 上記適応度関数は、リンクの総使用量が小さいほど経路候補染色体の適応度が大きくなることと、リンクの総オーバーフロー度が小さいほど染色体の適応度が大きくなることとを考慮して作成したものである。
【００２９】各リンクのオーバーフロー度は、最終的な経路候補の適合条件となり、求められた最適な経路の組合せで、オーバーフローするリンクが存在すれば、その経路の組合せは適合性がないということになる。
【００３０】次に、最適経路特定工程３００では、適合解があるか否かを判断し（ステップ３０２）、適合解でない場合は、適応度が高い（適応度関数の値が大きい）経路候補染色体を選択し（ステップ３０３）、選択された経路候補染色体同士を交叉させる（ステップ３０４）。全個体数に対して交叉させる個体の比率が交叉確率である。
【００３１】図３は、経路候補染色体の交叉の様子を示している。図３において、交叉する２つの経路候補染色体を親１および親２とすると、親１の経路候補染色体はＫ1,1-Ｋ2,2-Ｋ3,4-Ｋ4,1 の構成を有し、親２の経路候補染色体はＫ1,4-Ｋ2,1-Ｋ3,1-Ｋ4,3 の構成を有している。これら経路候補染色体を構成する構成部分Ｋn,mは、ｎ番目のタスクのｍ個目の経路候補を示している。
【００３２】交叉という操作では、上記親１と親２の経路候補染色体は、交叉点４で互いに構成部分Ｋ3,4 ，Ｋ4,1 とＫ3,1 ，Ｋ4,3 を入れ換える。この結果生成された子１および子２の経路候補染色体はそれぞれ、Ｋ1,1-Ｋ2,2-Ｋ3,1-Ｋ4,3 とＫ1,4-Ｋ2,1-Ｋ3,4-Ｋ4,1 となる。交叉点４は、意味のない経路の組合せ（致死遺伝子）を生じさせないように、各構成部分Ｋn,m の接続点となるように選択する。
【００３３】上記子１および子２の経路候補染色体は、前記適応度関数と各リンクのオーバーフロー度によって評価され（ステップ３０１，ステップ３０２）、適応度の高い経路候補染色体は選択され、再度交叉される。
【００３４】上記経路候補染色体の選択の代表的な選択方法として、ルーレット法とエリート保存法とがある。ルーレット法は、適応度に比例した確率を各個体に割り当て、これに従って個体のペアが順次生成する方法である。エリート保存法は、適応度が最大の個体を無条件に次の世代に残す方法である。
【００３５】ルーレット法の長所は、適応度の低い個体も選択され、進化の過程で結果的に適応度の高い個体を生成する可能性があることである。その反面、ルーレット法では、適応度の高い個体も淘汰される危険性がある。一方、エリート保存法の長所は、適応度の高い個体が必ず保存されることであるが、その反面、進化の過程で結果的に高い適応度を有することになる個体が進化の途中で淘汰される危険性を有している。
【００３６】本実施例における選択方法は、上記ルーレット法とエリート保存法の長所を組み合わせたものであり、所定数の適応度の高い個体を無条件に選択し、残るものについては、ルーレット法によって選択する。交叉によって制約に違反した経路候補染色体（たとえば、リンクの容量を超えるような場合）が発生しても、これを直ちに切り捨てるのではなく、制約に違反したレベルに応じてペナルティーを付けて保留する。これにより、適応度が高い経路候補染色体は必ず保存され、適応度が低い経路候補染色体も、進化の過程で良い適合解となることがある。
【００３７】上記最適経路特定工程３００における評価、選択、交叉の１サイクルは、進化の１世代という。本実施例のネットワーク資源分配方法では、予め最適経路特定工程３００で進化の世代数を指定しておき、この世代数進化を繰り返した後の解について適合条件（所定値以上の適応度を有し、リンクのオーバーフローがないという条件）を満足するか否か判断する。適合条件を満足すれば、その解を適合解３とし、満足しなければ経路候補染色体生成工程２００に戻って、別の経路候補染色体の集合を生成する。この経路候補染色体生成工程２００と最適経路特定工程３００の間の繰り返しのサイクルは、経路生成−経路特定サイクル（Generate Path - GA Cycles ）という。
【００３８】このように経路生成−経路特定サイクルを有しているのは、生物界の突然変異と同じ作用・効果を取り入れるためである。すなわち、生物界では、進化は必ずしも最適な形態にたどり着く保証はないので、突然変異によって進化の途中でそれまでの進化と無関係な個体が発生し、これによって最適な形態にたどり着く可能性を得ることができる。
【００３９】これに対して本実施例の経路生成−経路特定サイクルは、所定の世代数進化を繰り返した後に、適合解を得ることができないときに、新たな経路候補染色体の集合を生成するので、経路候補染色体が多様化され、誤った解に収束することを防止することができる。
【００４０】本実施例によるネットワーク資源分配方法の処理の流れは以上の通りであるが、次に本実施例のネットワーク資源分配方法を実行するための計算機の入力画面について説明する。
【００４１】図４は、対象とするネットワークの構造を数値マトリックスとして表示し、使用者に必要に応じてそのネットワークの構造を変更させる入力画面である。図４において、縦と横の数字は各ノードを示しており、数値マトリックスの各数値は、その縦と横のノードを結ぶリンクの容量を示している。たとえば、図においてノード０とノード１を結ぶリンクの容量は２０であり、ノード０とノード２の間にはリンクが存在していない。この数値マトリックスの数値を使用者が入力することにより、任意のネットワークを形成することができる。
【００４２】図５は、実行すべきタスクのリストを示している。このタスクリストの各タスクは、左側からタスク番号、起点ノード、終点ノード、流量の順に記載されており、使用者がその数値を入力することによって、任意のタスクを設定することができる。
【００４３】図６は、本発明のネットワーク資源分配方法の実行の条件を定める入力画面を示している。図において、Number of individuals は、前記経路候補染色体生成工程２００で生成する集合サイズであり、Crossover Rateは、経路候補染色体を交叉させる確率である。また、Generate Path-GA Cycles は、上述した通り経路候補染色体の集合を生成させる回数であり、Number of Altenative Pathsは、経路候補を追加・削除する回数であり、Generation Stepsは、進化の世代数である。使用者は、この入力画面の数値を自由に設定することにより、おおよその計算時間や最適解の適応度を設定することができる。
【００４４】次に、本発明のネットワーク資源分配方法と従来のダイクストラ法によるネットワーク資源の分配の処理時間と最適解の適応度とを比較して説明する。
【００４５】図７(a) ，(b) は、要求資源量の割合に対する本発明のネットワーク資源分配方法と従来のダイクストラ法の処理時間と適応度を示したグラフである。ここで、図７のグラフの横軸のタスクの要求資源量は、下式(3) のように定義される。
図７(a) より明らかなように、タスク要求資源量の割合が０．４８以下の範囲ではダイクストラ法の方が先に最適解を発見するが、タスク要求資源量が０．４８以上の範囲では本発明のネットワーク資源分配方法の方が先に最適解を発見する。特に、タスク要求資源量の割合が０．５０を超える範囲では、従来のダイクストラ法は、実時間で最適解を求めることができなくなる。これに対して本発明のネットワーク資源分配方法では、タスク要求資源量の割合が０．６５までの範囲について、最適解を求めることができた。
【００４６】また、図７(b) に示すように、本発明のネットワーク資源分配方法の方が従来のダイクストラ法に比べて一般的に最適解の適応度が高い。
【００４７】
【発明の効果】以上の説明から明らかなように、本発明のネットワーク資源分配方法は、経路候補染色体生成工程と最適経路特定工程を有し、この経路候補染色体生成工程と最適経路特定工程を繰り返すことによって最適なタスクの経路を特定するので、ネットワークの規模に関わらず初期のタスクの経路候補の作成が簡単であり、かつ、これら経路候補に対して遺伝的アルゴリズムによって適応度が高い適合解を短い時間で求めることができる。
【００４８】これにより、大規模なネットワーク資源に対して、ネットワーク資源を効率よく、かつ、最適に所定のタスクに分配するネットワーク資源分配方法を得ることができる。
【図面の簡単な説明】
【図１】本発明のネットワークの処理の流れを示した流れ図。
【図２】モデル化されたネットワークを例示した図。
【図３】経路候補染色体とその交叉の様子を示した図。
【図４】ネットワーク構造の入力画面を示した図。
【図５】タスクの入力画面を示した図。
【図６】本発明のネットワーク資源分配方法の実行条件の入力画面を示した図。
【図７】本発明のネットワーク資源分配方法と従来のダイクストラ法の処理時間と適応度を比較して示したグラフ。
【符号の説明】
１ ラベル付きネットワーク
２ リンク
３ 適合解
２００ 経路候補染色体生成工程
３００ 最適経路特定工程
【特許請求の範囲】
【請求項１】複数のノードと容量を有する複数のリンクからなるネットワーク資源を、所定の起点ノードと終点ノードと流量とを有する複数のタスクに最適に分配するネットワーク資源分配方法において、前記各タスクを実現する複数の経路候補を生成し、各タスクの経路候補を直列的にコード化した経路候補染色体を所定の集合サイズの個数だけ生成する経路候補染色体生成工程と、前記経路候補染色体に対して交叉と選択と評価とからなる操作を繰り返して最適な経路を特定する最適経路特定工程とを有し、前記最適経路特定工程で特定した経路が所定の適合条件を満足しない時に、前記経路候補染色体生成工程と最適経路特定工程を繰り返すことを特徴とするネットワーク資源分配方法。
【請求項２】前記経路候補染色体生成工程における経路候補の生成は、経路の進むべき方向が複数選択可能であるときに、終点ノードまでの距離と、リンクの空き容量の期待値とによって重み付けをして正規化した確率に基づいて進むべき方向を選択して経路候補を生成することを特徴とする請求項１に記載のネットワーク資源分配方法。
【請求項３】前記最適経路特定工程で特定した最適経路の評価は、リンクの総使用量とリンクの総オーバーフロー度をパラメータとする適応度関数によって行うことを特徴とする請求項１に記載のネットワーク資源分配方法。
【請求項４】複数のノードと容量を有する複数のリンクからなるネットワーク資源を、所定の起点ノードと終点ノードと流量とを有する複数のタスクに最適に分配するネットワーク資源分配方法において、ネットワークの構造を数値マトリックスとして表し、使用者に前記数値マトリックスの数値を入力させて資源分配するネットワーク構造を完成し、次に、使用者にタスク番号と起点ノードと終点ノードと流量とを入力させて分配すべきタスクを完成し、次に、使用者に集合サイズと交叉確率と経路生成サイクル数と世代数と経路候補染色体の集合の数とを所望によって入力させ、遺伝的アルゴリズムの手法によって最適なネットワーク資源の分配を求めることを特徴とするネットワーク資源分配方法。
【請求項１】複数のノードと容量を有する複数のリンクからなるネットワーク資源を、所定の起点ノードと終点ノードと流量とを有する複数のタスクに最適に分配するネットワーク資源分配方法において、前記各タスクを実現する複数の経路候補を生成し、各タスクの経路候補を直列的にコード化した経路候補染色体を所定の集合サイズの個数だけ生成する経路候補染色体生成工程と、前記経路候補染色体に対して交叉と選択と評価とからなる操作を繰り返して最適な経路を特定する最適経路特定工程とを有し、前記最適経路特定工程で特定した経路が所定の適合条件を満足しない時に、前記経路候補染色体生成工程と最適経路特定工程を繰り返すことを特徴とするネットワーク資源分配方法。
【請求項２】前記経路候補染色体生成工程における経路候補の生成は、経路の進むべき方向が複数選択可能であるときに、終点ノードまでの距離と、リンクの空き容量の期待値とによって重み付けをして正規化した確率に基づいて進むべき方向を選択して経路候補を生成することを特徴とする請求項１に記載のネットワーク資源分配方法。
【請求項３】前記最適経路特定工程で特定した最適経路の評価は、リンクの総使用量とリンクの総オーバーフロー度をパラメータとする適応度関数によって行うことを特徴とする請求項１に記載のネットワーク資源分配方法。
【請求項４】複数のノードと容量を有する複数のリンクからなるネットワーク資源を、所定の起点ノードと終点ノードと流量とを有する複数のタスクに最適に分配するネットワーク資源分配方法において、ネットワークの構造を数値マトリックスとして表し、使用者に前記数値マトリックスの数値を入力させて資源分配するネットワーク構造を完成し、次に、使用者にタスク番号と起点ノードと終点ノードと流量とを入力させて分配すべきタスクを完成し、次に、使用者に集合サイズと交叉確率と経路生成サイクル数と世代数と経路候補染色体の集合の数とを所望によって入力させ、遺伝的アルゴリズムの手法によって最適なネットワーク資源の分配を求めることを特徴とするネットワーク資源分配方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開平７−２６２１１５
【公開日】平成７年（１９９５）１０月１３日
【国際特許分類】
【出願番号】特願平６−５４０４１
【出願日】平成６年（１９９４）３月２４日
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成５年１１月１１日〜１１月１２日、社団法人計測自動制御学会主催の「第１９回システムシンポジウム、第１８回知能システムシンポジウム」において文書をもって発表
【出願人】（０００１５５４６９）株式会社野村総合研究所 (1,067)
【公開日】平成７年（１９９５）１０月１３日
【国際特許分類】
【出願日】平成６年（１９９４）３月２４日
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成５年１１月１１日〜１１月１２日、社団法人計測自動制御学会主催の「第１９回システムシンポジウム、第１８回知能システムシンポジウム」において文書をもって発表
【出願人】（０００１５５４６９）株式会社野村総合研究所 (1,067)
[ Back to top ]