(57)【特許請求の範囲】
【請求項１】
配置可能な設備候補の情報、予測デマンド及び設計パラメータの入力を行う設計情報入力手段と、前記設計情報入力手段から入力された配置可能な設備候補を用いて予測デマンドを収容する経路の候補を複数設計して遺伝子配列を生成する経路候補設計手段と、前記遺伝子配列に対して遺伝的操作を行って与えられた問題に対する最適解を求める遺伝的アルゴリズムを用いて経路候補設計で設計された経路の候補から適切な経路の組合せを選択する経路候補組合せ設計手段とを有し、
前記経路候補組合せ設計手段の選択結果を基にＷＤＭ（Ｗａｖｅｌｅｎｇｔｈ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ）網の設計を行うことを特徴とするＷＤＭ網設計装置。
【請求項２】
前記経路候補組合せ設計手段で選択された経路の組合せを収容する設備配置を出力する設備配置出力手段を含むことを特徴とする請求項１記載のＷＤＭ網設計装置。
【請求項３】
前記遺伝的アルゴリズムにおいて、個体の評価値としてネットワークのコストを利用することを特徴とする請求項１または請求項２記載のＷＤＭ網設計装置。
【請求項４】
前記経路候補設計手段は、前記経路の候補として現用及び予備の２経路を組で設計することを特徴とする請求項１から請求項３のいずれか記載のＷＤＭ網設計装置。
【請求項５】
配置可能な設備候補の情報、予測デマンド及び設計パラメータの入力を行うステップと、その入力された配置可能な設備候補を用いて予測デマンドを収容する経路の候補を複数設計して遺伝子配列を生成するステップと、前記遺伝子配列に対して遺伝的操作を行って与えられた問題に対する最適解を求める遺伝的アルゴリズムを用いて経路候補設計で設計された経路の候補から適切な経路の組合せを選択するステップとを有し、
前記適切な経路の組合せを選択するステップの選択結果を基にＷＤＭ（Ｗａｖｅｌｅｎｇｔｈ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ）網の設計を行うことを特徴とするＷＤＭ網設計方法。
【請求項６】
前記適切な経路の組合せを選択するステップで選択された経路の組合せを収容する設備配置を出力するステップを含むことを特徴とする請求項５記載のＷＤＭ網設計方法。
【請求項７】
前記遺伝的アルゴリズムにおいて、個体の評価値としてネットワークのコストを利用することを特徴とする請求項５または請求項６記載のＷＤＭ網設計方法。
【請求項８】
前記遺伝子配列を生成するステップは、前記経路の候補として現用及び予備の２経路を組で設計することを特徴とする請求項５から請求項７のいずれか記載のＷＤＭ網設計方法。
【請求項９】
コンピュータに、配置可能な設備候補の情報、予測デマンド及び設計パラメータの入力を行う処理と、その入力された配置可能な設備候補を用いて予測デマンドを収容する経路の候補を複数設計して遺伝子配列を生成する処理と、前記遺伝子配列に対して遺伝的操作を行って与えられた問題に対する最適解を求める遺伝的アルゴリズムを用いて経路候補設計で設計された経路の候補から適切な経路の組合せを選択する処理とを実行させ、
前記適切な経路の組合せを選択するステップの選択結果を基にＷＤＭ（Ｗａｖｅｌｅｎｇｔｈ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ）網の設計を行わせるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はＷＤＭ網設計装置及びそれに用いるＷＤＭ網設計方法並びにそのプログラムに関し、特にパスの経路設計の方法に関する。
【０００２】
【従来の技術】
従来、パスの経路設計方式としては、特開平７−２５０３５６号公報に開示されているように、経路収容数を最小となるような経路を光パスの経路に設定する方法（以下、第１の従来技術とする）がある。
【０００３】
上記のようなパスの経路設計を行うと、パスが１ヶ所に偏ることなく分散して収容されるため、既存設備にパスを収容しようとする場合には、必要な波長数が削減され、より多くのパスを収容することができる。
【０００４】
また、特開平７−２０２８４４号公報には、経路候補を複数作成し、それらの経路の最適な組合せを求める方法（以下、第２の従来技術とする）が開示されている。
【０００５】
【発明が解決しようとする課題】
しかしながら、上述した従来のパスの経路設計方式では、第１の従来技術を用いる場合、新規に設備を投入し、ネットワークを構築しようとすると、投入する設備が分散して配備され、より多くの設備が必要となり、経済的ではない。
【０００６】
また、第２の従来技術を用いる場合には、経路をランダムに組合せているため、繰り返し回数を多くしなければ最適により近い解にならず、設計時間が非常に長く掛かるという問題がある。
【０００７】
そこで、本発明の目的は上記の問題点を解消し、大規模な問題でもより最適な組合せを高速に設計することができるＷＤＭ網設計装置及びそれに用いるＷＤＭ網設計方法並びにそのプログラムを提供することにある。
【０００８】
【課題を解決するための手段】
本発明によるＷＤＭ網設計装置は、配置可能な設備候補の情報、予測デマンド及び設計パラメータの入力を行う設計情報入力手段と、前記設計情報入力手段から入力された配置可能な設備候補を用いて予測デマンドを収容する経路の候補を複数設計して遺伝子配列を生成する経路候補設計手段と、前記遺伝子配列に対して遺伝的操作を行って与えられた問題に対する最適解を求める遺伝的アルゴリズムを用いて経路候補設計で設計された経路の候補から適切な経路の組合せを選択する経路候補組合せ設計手段とを備え、
前記経路候補組合せ設計手段の選択結果を基にＷＤＭ（Ｗａｖｅｌｅｎｇｔｈ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ）網の設計を行っている。
【０００９】
本発明によるＷＤＭ網設計方法は、配置可能な設備候補の情報、予測デマンド及び設計パラメータの入力を行うステップと、その入力された配置可能な設備候補を用いて予測デマンドを収容する経路の候補を複数設計して遺伝子配列を生成するステップと、前記遺伝子配列に対して遺伝的操作を行って与えられた問題に対する最適解を求める遺伝的アルゴリズムを用いて経路候補設計で設計された経路の候補から適切な経路の組合せを選択するステップとを備え、
前記適切な経路の組合せを選択するステップの選択結果を基にＷＤＭ（Ｗａｖｅｌｅｎｇｔｈ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ）網の設計を行っている。
【００１０】
本発明によるプログラムは、コンピュータに、配置可能な設備候補の情報、予測デマンド及び設計パラメータの入力を行う処理と、その入力された配置可能な設備候補を用いて予測デマンドを収容する経路の候補を複数設計して遺伝子配列を生成する処理と、前記遺伝子配列に対して遺伝的操作を行って与えられた問題に対する最適解を求める遺伝的アルゴリズムを用いて経路候補設計で設計された経路の候補から適切な経路の組合せを選択する処理とを実行させ、
前記適切な経路の組合せを選択するステップの選択結果を基にＷＤＭ（Ｗａｖｅｌｅｎｇｔｈ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ）網の設計を行わせている。
【００１１】
すなわち、本発明のＷＤＭ網設計装置は、予測デマンドを収容するにあたり、安価なＷＤＭ（Ｗａｖｅｌｅｎｇｔｈ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ：波長分割多重）網を設計可能な構成を提供するものである。
【００１２】
より具体的に説明すると、本発明のＷＤＭ網設計装置では、設計情報入力で配置可能な設備候補の情報、予測デマンド及び設計パラメータの入力を行い、経路候補設計で配置可能な設備候補を用いて予測デマンドを収容する経路の候補を複数設計し、経路候補組合せ設計で安価なＷＤＭ網を構築可能なように、遺伝的アルゴリズムを用いて経路候補設計で設計された経路の候補から適切な経路の組合せを選択している。尚、経路候補組合せ設計で選択された経路の組合せを収容する設備配置は設備配置出力から出力される。
【００１３】
このように、本発明のＷＤＭ網設計装置では、経路候補設計で複数の経路の候補を設計し、経路候補組合せ設計で最適な経路の組合せを選択するので、安価な設備配置によるＷＤＭ網を設計することが可能となる。
【００１４】
また、経路候補組合せ設計は組合せ問題を解くことになるが、遺伝的アルゴリズムを利用することで、大きなトポロジにおいても比較的良い解が比較的高速に発見可能である。
【００１５】
ここで、遺伝的アルゴリズムとは、生物の進化過程にヒントを得た遺伝的操作（ｇｅｎｅｔｉｃ  ｏｐｅｒａｔｉｏｎ）を使って、与えられた問題に対する最適解を求める手法である。そこで、本発明では、遺伝子配列の生成を可能とすることで、遺伝的アルゴリズムを利用可能とし、最適解の発見の高速化を図っている。
【００１６】
【発明の実施の形態】
次に、本発明の一実施例について図面を参照して説明する。図１は本発明の一実施例によるＷＤＭ（Ｗａｖｅｌｅｎｇｔｈ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ：波長分割多重）網設計装置の構成を示すブロック図である。図１において、ＷＤＭ網設計装置１は主にコンピュータで構成され、設計情報入力手段１１と、経路候補設計手段１２と、経路候補組合せ設計手段１３と、設備配置出力手段１４と、記録媒体１５とを備えている。これら各手段はコンピュータが記録媒体１５のプログラムを実行することで実現される。
【００１７】
設計情報入力手段１１には配置可能な設備候補の情報、予測デマンド及び設計パラメータの入力が行われる。経路候補設計手段１２はその入力された情報を基に、配置可能な設備候補を用いて予測デマンドを収容する経路の候補を複数設計する。
【００１８】
経路候補組合せ設計手段１３は安価なＷＤＭ網を構築することができるように、遺伝的アルゴリズムを用いて経路候補設計手段１２で設計された経路の候補から適切な経路の組合せを選択する。設備配置出力手段１４は経路候補組合せ設計手段１３で選択された経路の組合せを収容する設備配置を出力する。
【００１９】
ここで、遺伝的アルゴリズムとは、生物の進化過程にヒントを得た遺伝的操作（ｇｅｎｅｔｉｃ  ｏｐｅｒａｔｉｏｎ）を使って、与えられた問題に対する最適解を求める手法である。
【００２０】
この遺伝的アルゴリズムを用いることで、どれ程複雑な問題に対しても、原理的には最適あるいは最適に近い解が得られるため、計画問題を中心に多くの応用研究が進められており、実用化されたシステムもある。また、遺伝的アルゴリズムではアルゴリズムが並列処理に適することから、超並列コンピュータを利用することも多い。
【００２１】
遺伝的アルゴリズムでは、（１）解候補（個体と呼ぶ）の集団を生成し、（２）それぞれの個体について適応度を評価し、（３）評価値の高い個体を選択し、（４）それらに対して交叉（ｃｒｏｓｓｏｖｅｒ）、突然変異（ｍｕｔａｔｉｏｎ）等の操作を加えて次の世代の個体集団を生成する。
【００２２】
上記の（２）〜（４）の操作を繰返して世代を重ねることで、適応度の高い個体が増えていくと同時に、より最適解に近い個体が現れる確率も高くなっていく。このようにして、評価値がある値に達した時の解が求める最適値となる。
【００２３】
上記の各個体は染色体（ｃｈｒｏｍｏｓｏｍｅ）上に１次元的に並んだ遺伝子（ｇｅｎｅ）の列として表現する。上記の交叉とは染色体を途中で切断し、切断した部分に他の染色体の一部を接続する操作である。これに対し、突然変異とは文字列中の一部を別の文字で置換えることである。
【００２４】
図２は本発明の一実施例によるＷＤＭ網設計装置１の動作を示すフローチャートであり、図３は図１の経路候補組合せ設計手段１３の動作を示すフローチャートである。これら図１〜図３を参照して本発明の一実施例によるＷＤＭ網設計装置１の動作について説明する。図２及び図３に示す処理はコンピュータが記録媒体１５のプログラムを実行することで実現される。
【００２５】
設計情報入力手段１１では、設計する設備配置候補リスト、予測デマンドリスト及び設計パラメータが入力される（図２ステップＳ１）。設備配置候補リストはノード間を結ぶ際に配置可能なリンクを列挙したものである。リンクは多重することができる波長数の最大値（最大多重数）と、配置に要するコスト（配置コスト）とを属性に持つ。
【００２６】
予測デマンドリストは発生が予測されるデマンドのリストである。また、設計パラメータとしては、目標コスト、最大経路候補数、世代当たりの個体数、設計世代数、世代当たりの交叉数、世代当たりの突然変異数、突然変異率（＝遺伝子配列の１要素当たりの値を変更する確率）が与えられる。
【００２７】
経路候補設計手段１２では、本願出願人から提案されている「最小コスト経路探索装置及びそれに用いる最小コスト経路探索方法」等を用いて予測デマンドの両端を結ぶ経路を最大ｎ本（ｎは正の整数）設計する（図２ステップＳ２）。
【００２８】
続いて、経路候補組合せ設計手段１３では遺伝的アルゴリズムを用いて経路候補設計手段１２で設計された経路の候補から適切な経路の組合せを選択する（図２ステップＳ３）。
【００２９】
この動作を詳細に説明すると、まず経路候補組合せ設計手段１３は遺伝的アルゴリズムの第１世代の個体として、世代当たりの個体数の個体を生成する（第１世代集団生成）（図３ステップＳ１１）。
【００３０】
経路候補組合せ設計手段１３は各個体の評価値として設備配置コストを算出する（評価）（図３ステップＳ１２）。最優秀の評価値（ここでは設備配置コストが最小）を持つ個体の評価値が目標コストを下回っている場合、あるいは世代数が設計世代数を超えた場合には経路候補組合せ設計手段１３の処理を終了とし、設備配置出力手段１４の処理に進む。
【００３１】
この評価において終了条件を満足しなければ、経路候補組合せ設計手段１３は各個体の評価値を比較し、優秀でない個体、すなわち評価値の高い個体を削除し、世代当たりの個体数のみを残す（選択）（図３ステップＳ１３）。
【００３２】
経路候補組合せ設計手段１３は上記の選択の処理で残った個体の中から任意の２個体を選択し、遺伝子配列の交叉を行う（交叉）（図３ステップＳ１４）。この処理は世代当たりの交叉数だけ行われる。
【００３３】
経路候補組合せ設計手段１３は上記の選択の処理で残った個体の中から任意の１個体を選択し、突然変異を行う（突然変異）（図３ステップＳ１５）。突然変異の処理では遺伝子列の配列の各要素に対して、予め設定された変異確率によって要素の値をランダムに変更する。この処理は世代当たりの突然変異数だけ行われる。
【００３４】
経路候補組合せ設計手段１３は選択の処理で残った個体、交叉の処理で生成された個体と、突然変異の処理で生成された固体を加えた集合を、次の世代の個体集合とし、上記の評価の処理を再実行する。
【００３５】
最後に、設備配置出力手段１４では、経路候補組合せ設計手段１３の処理が終了した時点で評価値が最も良い個体による設備配置を出力し（図２ステップＳ４）、ＷＤＭ網の設計を終了する。
【００３６】
図４は本発明の一実施例によるトポロジの例を示す図であり、図５は図４のトポロジ上でのリンクの配置候補を示す図であり、図６及び図７は図４のトポロジ上で予測されるデマンドの例を示す図である。
【００３７】
また、図８は図１の経路候補組合せ設計手段１３の交叉の処理を示すフローチャートであり、図９は図１の経路候補組合せ設計手段１３の突然変異の処理を示すフローチャートである。これら図１〜図９を参照して本発明の一実施例によるＷＤＭ網設計の処理について具体的に説明する。図８及び図９に示す処理はコンピュータが記録媒体１５のプログラムを実行することで実現される。
【００３８】
図４では、ノードＡ〜Ｄを波長多重装置（ＷＤＭ）を両端に備えたリンクで接続するトポロジを構築しようとしている。ここで、ノードＡ〜Ｄ間を直接接続するリンクの配置候補を図５に示すように仮定している。
【００３９】
リンクの配置候補には、そのリンクに多重できる波長数の最大値およびリンクの配置コストを設定する。つまり、配置候補「Ａ−Ｃ間リンク」は最大多重数が「４」、配置コストが「３」であり、配置候補「Ａ−Ｄ間リンク」は最大多重数が「４」、配置コストが「３」であり、配置候補「Ｂ−Ｃ間リンク」は最大多重数が「４」、配置コストが「２」であり、配置候補「Ｃ−Ｄ間リンク」は最大多重数が「４」、配置コストが「２」である。
【００４０】
また、図４に示すトポロジ上で予測されるデマンドの例を図６に示すように、ノードＡ―ノードＢ間、ノードＡ―ノードＤ間、ノードＢ―ノードＤ間と仮定している。図５及び図６に示す内容と、設計パラメータとが設計情報入力手段１１の入力となる。
【００４１】
次に、経路候補設計手段１２は図６に示す予測デマンドのそれぞれに対し、図５に示すリンクの配置候補を利用して複数の経路候補を設計する。ここでは最大経路候補数を２として、各デマンドに経路候補を２本ずつ設計した場合の経路候補の設計結果の例を図７に示す。
【００４２】
経路候補組合せ設計手段１３は第１世代集団生成の処理（図３ステップＳ１１）において、遺伝的アルゴリズムの個体を生成する。各個体の遺伝子配列としては予測デマンド数だけの要素をもつ配列を用意する。この例では、図７に示すように、予測デマンドが３個存在するので、要素を３つ持つ配列を用意する。
【００４３】
第１要素には予測デマンド番号「１」のＡ−Ｂ間のデマンドの経路候補番号を値として持つ。予測デマンド番号「１」のデマンドには経路候補が「Ａ−Ｃ−Ｂ」，「Ａ−Ｄ−Ｃ−Ｂ」の２つが経路候補設計手段１２で設計されているので、１，２の値のいずれかをランダムで利用する。ここでは、経路候補＃１（Ａ−Ｃ−Ｂ）が選ばれたとして、第１要素の値を「１」とする。
【００４４】
同様に、予測デマンド番号「２」のＡ−Ｄ間のデマンドには経路候補＃２（Ａ−Ｃ−Ｄ）が、予測デマンド番号「３」のＢ−Ｄ間のデマンドには経路候補＃１（Ｂ−Ｃ−Ｄ）が選ばれたとすると、この個体の遺伝子配列は［１，２，１］となる。
【００４５】
このように、経路候補組合せ設計手段１３では遺伝子配列の値をランダムに決定しながら世代当たりの個体数だけの個体を生成し、これらの個体集合を第１世代とする。
【００４６】
経路候補組合せ設計手段１３は評価の処理（図３ステップＳ１２）において、各個体の評価値として、設備配置コストを算出する。例えば、遺伝子配列［１，２，１］を持つ個体の設備配置コストは、以下の通りとなる。
【００４７】
第１要素の値が「１」であることから、予測デマンド（Ａ−Ｂ）に対して経路（Ａ−Ｃ−Ｂ）が選択されている。したがって、この予測デマンド（Ａ−Ｂ）を収容するにはＡ−Ｃ間リンク及びＢ−Ｃ間リンクの配置が必要となり、それらの配置コストの合計は、３＋２＝５となる。
【００４８】
第２要素の値が「２」であることから、予測デマンド（Ａ−Ｄ）に対して経路（Ａ−Ｃ−Ｄ）が選択されている。Ａ−Ｃ間には既にＡ−Ｃ間リンクが敷設してあり、かつ利用しているデマンドが予測デマンド（Ａ−Ｂ）だけなので、予測デマンド（Ａ−Ｄ）を追加しても最大多重数の４よりも小さく、追加配置の必要はない。Ｃ−Ｄ間には既存のリンクが存在しないので、新たにＣ−Ｄ間リンクの配置が必要となり、その追加コストは２である。したがって、ここまでの配置コスト合計は、３＋２＋２＝７である。
【００４９】
最後に、第３要素の値が「１」であることから、予測デマンド（Ｂ−Ｄ）に対して経路（Ｂ−Ｃ−Ｄ）が選択されている。この時、Ｂ−Ｃ間、Ｃ−Ｄ間にはともに既存のリンクが存在し、多重数にも余裕があるため、追加配置の必要はない。したがって、全体の配置コスト合計は、３＋２＋２＝７となり、この値「７」が遺伝子配列［１，２，１］を持つ個体の評価値となる。
【００５０】
経路候補組合せ設計手段１３は全ての個体の評価値を算出した後、終了条件を確認する。この世代の中の個体の最小の評価値がパラメータとして与えられた目標コストを下回っている場合には、経路候補組合せ設計手段１３の処理を終了する。あるいは、今回の世代数がパラメータとして与えられた設計世代数に達した場合も、経路候補組合せ設計手段１３の処理を終了する。
【００５１】
経路候補組合せ設計手段１３は選択の処理（図３ステップＳ１３）において、評価の処理で算出された各個体の評価値に基づき、評価値の上位、すなわち値の小さい個体から順に、パラメータとして与えられた世代当たりの個体数分だけを選択し、その他の個体を削除する。
【００５２】
経路候補組合せ設計手段１３は交叉の処理（図３ステップＳ１４）において、選択の処理で選択された個体の中から２個体（親Ａ，親Ｂ）をランダムに選択し、その２個体を使って、新たに２個体（子Ａ，子Ｂ）を生成する。この交叉の処理は図８に示すようにして行われる。
【００５３】
経路候補組合せ設計手段１３は交叉の処理において、まずマスク用配列を作成する（図８ステップＳ２１）。配列長は各個体の遺伝子配列と同じで、各要素の値は“０”，“１”のどちらかの値をランダムに設定する。また、経路候補組合せ設計手段１３は選択の処理で選択された個体の中から２個体（親Ａ，親Ｂ）を選択する（図８ステップＳ２２）。
【００５４】
次に、経路候補組合せ設計手段１３はｎ＝１として（図８ステップＳ２３）、子の遺伝子配列の第ｎ要素をマスクの第ｎ要素に基づいて決定していく（図８ステップＳ２４）。
【００５５】
値が“１”の場合には、子Ａの第ｎ要素の値を親Ａの第ｎ要素からコピーし、子Ｂの第ｎ要素の値を親Ｂの第ｎ要素からコピーする（図８ステップＳ２５）。値が“０”の場合には、子Ａの第ｎ要素の値を親Ｂの第ｎ要素からコピーし、子Ｂの第ｎ要素の値を親Ａの第ｎ要素からコピーする（図８ステップＳ２６）。
【００５６】
経路候補組合せ設計手段１３はこのステップＳ２４〜Ｓ２６の操作を遺伝子配列の末端まで繰り返し（図８ステップＳ２７，Ｓ２８）、さらに、これらステップＳ２１〜Ｓ２８の操作を、世代当たりの交叉数分だけ繰り返す（図８ステップＳ２９）。
【００５７】
今回の例において、マスク用配列は長さが「３」であり、例として［１，０，１］となったとする。また、親Ａの遺伝子配列を［１，２，１］、親Ｂの遺伝子配列を［２，１，１］とすると、子Ａの第１要素はマスク用配列の第１要素の値が“１”であるので、親Ａの第１要素の値「１」を採用する。第２要素はマスク用配列の第２要素の値が“０”であるので、親Ｂの第２要素の値「１」を採用する。同様に、第３要素の値は親Ａの第３要素の値「１」となり、子Ａの遺伝子配列は［１，１，１］となる。また同様に、子Ｂの遺伝子配列は［２，２，１］となる。
【００５８】
上記の交叉の操作によって、新たに「（世代当たりの交叉数）×２」の個体が生成される。
【００５９】
経路候補組合せ設計手段１３は突然変異の処理（図３ステップＳ１５）において、選択の処理で選択された個体の中から１個体（親Ｃ）をランダムに選択し、その１個体を使って、新たに１個体（子Ｃ）を生成する。この突然変異の処理は図９に示すようにして行われる。
【００６０】
経路候補組合せ設計手段１３は突然変異の処理において、まず選択の処理で選択された個体の中から１個体（親Ｃ）をランダムに選択し（図９ステップＳ３１）、ｎ＝１として選択された個体（親Ｃ）の遺伝子配列を第ｎ要素から操作する（図９ステップＳ３２）。
【００６１】
経路候補組合せ設計手段１３はパラメータとして与えられた突然変異率に基づいて第ｎ要素の値を変化させるかどうかを決定し（図９ステップＳ３３）、変化させる場合には子Ｃの遺伝子配列の第ｎ要素の値をランダムに決定する（図９ステップＳ３４）。変化させない場合には、親Ｃの遺伝子配列の第ｎ要素を子Ｃにそのままコピーする（図９ステップＳ３５）。
【００６２】
経路候補組合せ設計手段１３はこれらステップＳ３３〜Ｓ３５の操作を親Ｃの遺伝子配列の末端まで繰り返し（図９ステップＳ３６，Ｓ３７）、さらにこれらステップＳ３１〜Ｓ３７の操作を世代当たりの突然変異数分だけ繰り返す（図９ステップＳ３８）。
【００６３】
上記の突然変異の操作によって、新たに世代当たりの突然変異数の個体が生成される。
【００６４】
経路候補組合せ設計手段１３は選択の処理で選択された個体に、交叉の処理で生成された個体及び突然変異の処理で生成された個体を加えた集合を次世代の個体集合として、再び評価の処理を行う。
【００６５】
設備配置出力手段１４は経路候補組合せ設計手段１３の処理が終了すると、評価値が最も良い個体による設備配置を出力し（図２ステップＳ４）、ＷＤＭ網の設計を終了する。
【００６６】
このように、本実施例では、予測デマンドの経路候補を複数設計し、設備配置コストが安価になるように経路候補から経路を選択することで、安価なＷＤＭ網を設計することができる。
【００６７】
また、経路候補組合せ設計手段１３は組合せ問題を解くことになるが、第１世代集合生成の処理（図３ステップＳ１１）で遺伝子配列の作成を実現することによって、以降のステップＳ１２〜Ｓ１５に示す遺伝的アルゴリズムの仕組みを利用可能となっている。遺伝的アルゴリズムを使うことによって、大規模な問題でもより最適な組合せを高速に設計することができる。
【００６８】
図１０は本発明の他の実施例による経路候補設計手段の処理を示すフローチャートである。本発明の他の実施例によるＷＤＭ網設計装置は経路候補設計手段の処理動作が異なる以外は図１に示す本発明の一実施例によるＷＤＭ網設計装置１の構成と同様の構成となっているので、図１及び図１０を参照して本発明の他の実施例の動作について説明する。図１０に示す処理はコンピュータが記録媒体１５のプログラムを実行することで実現される。
【００６９】
経路候補設計手段１２は、図１０に示すように、現用経路と予備経路とをペアで設計することによって、予備経路まで考慮した設備配置の設計を行うことができる。
【００７０】
経路候補設計手段１２は、まず各予測デマンドに対し、経路を最大ｎ本ずつ設計する（図１０ステップＳ４１）。経路候補設計手段１２はステップＳ４１で設計された経路から１本を選び、その経路が利用したノード、リンクを削除して経路を設計する（図１０ステップＳ４２）。
【００７１】
ここで設計された経路は、選択された経路と同じノード、リンクを全く利用していないので、選択された経路に障害が発生した場合の迂回経路として利用することができる。そこで、経路候補設計手段１２は選択された経路を現用経路、ここで設計された経路を予備経路として経路のペアを作成する。
【００７２】
経路候補設計手段１２はステップＳ４２で削除したノード、リンクを元に戻し（図１０ステップＳ４３）、最後にステップＳ４１で設計した全ての経路の予備経路の設計が終了すれば（図１０ステップＳ４４）、経路候補設計を終了し、予備経路を未設計の経路が残っていれば、ステップＳ４２に戻る。
【００７３】
【発明の効果】
以上説明したように本発明は、配置可能な設備候補を用いて予測デマンドを収容する経路の候補を複数設計して遺伝子配列を生成し、この遺伝子配列に対して遺伝的操作を行って与えられた問題に対する最適解を求める遺伝的アルゴリズムを用いて経路候補設計で設計された経路の候補から適切な経路の組合せを選択することによって、大規模な問題でもより最適な組合せを高速に設計することができるという効果が得られる。
【図面の簡単な説明】
【図１】本発明の一実施例によるＷＤＭ網設計装置の構成を示すブロック図である。
【図２】本発明の一実施例によるＷＤＭ網設計装置の動作を示すフローチャートである。
【図３】図１の経路候補組合せ設計手段の動作を示すフローチャートである。
【図４】本発明の一実施例によるトポロジの例を示す図である。
【図５】図４のトポロジ上でのリンクの配置候補を示す図である。
【図６】図４のトポロジ上で予測されるデマンドの例を示す図である。
【図７】図４のトポロジ上で予測されるデマンドの例を示す図である。
【図８】図１の経路候補組合せ設計手段の交叉の処理を示すフローチャートである。
【図９】図１の経路候補組合せ設計手段の突然変異の処理を示すフローチャートである。
【図１０】本発明の他の実施例による経路候補設計手段の処理を示すフローチャートである。
【符号の説明】
１  ＷＤＭ網設計装置
１１  設計情報入力手段
１２  経路候補設計手段
１３  経路候補組合せ設計手段
１４  設備配置出力手段
１５  記録媒体
【図１】
0003937896.tif 000002
【図２】
0003937896.tif 000003
【図３】
0003937896.tif 000004
【図４】
0003937896.tif 000005
【図５】
0003937896.tif 000006
【図６】
0003937896.tif 000007
【図７】
0003937896.tif 000008
【図８】
0003937896.tif 000009
【図９】
0003937896.tif 000010
【図１０】
0003937896.tif 000011