(57)【要約】【課題】複数の線路およびこれらの線路を結ぶ中継点をどこに配置すれば有効であるかを実用的な時間内に求める。【解決手段】経路立案装置は、中継点の数に基づいた配列を持ち、中継点と線路の配置の複数の候補をそれぞれ示す複数の初期の遺伝コードに対して、評価、選択、交叉、突然変異を含む遺伝的アルゴリズムを適用する。遺伝コードの各々が示す中継点と線路の配置から遺伝コード評価部３は、中継点および線路の総コストに対応する指標または線路の総コストに対応する指標を求め、これらの指標を遺伝的アルゴリズムの評価値として使用する。【選択図】        図１
2004272454.tif 000002
【特許請求の範囲】
【請求項１】
複数の線路およびこれらの線路を結ぶ中継点の配置を立案する経路立案装置において、
中継点の数に基づいた配列を持ち遺伝的操作の母集団となり上記中継点と上記線路の配置の複数の候補をそれぞれ示す複数の初期の遺伝コードをランダムに生成する初期コード化部と、
入力された遺伝コードの各々に評価関数を適用して遺伝コードの各々の評価値を得る評価部と、
上記評価値の各々に基づいて適切な遺伝コードを選択する選択部と、
上記選択部で選択された遺伝コードの各々に交叉処理を施す交叉処理部と、
上記交叉が施された遺伝コードの一部に突然変異処理を施して、上記突然変異処理後の遺伝コードの各々を上記評価部に供給する突然変異処理部と、
遺伝的操作が終了条件を満たした場合に、上記突然変異処理後の遺伝コードの少なくとも一つを上記中継点と上記線路の配置候補の最適解または準最適解である最終遺伝コードとして出力し、上記遺伝的操作が終了条件を満たさない場合に、上記突然変異処理後の遺伝コードの各々を上記選択部に供給する終了判定部とを備え、
上記評価部は、遺伝コードの各々が示す中継点と線路の配置から、上記中継点および上記線路の総コストに対応する指標または上記線路の総コストに対応する指標を上記評価値として算出することを特徴とする経路立案装置。
【請求項２】
選択部は遺伝コードの評価値そのものをしきい値と比較し、比較結果に応じて遺伝コードを選択することを特徴とする請求項１記載の経路立案装置。
【請求項３】
評価部または選択部は遺伝コードの評価値に応じて予め割り振られた確率を評価値に乗算し、選択部はこの計算結果をしきい値と比較し、比較結果に応じて遺伝コードを選択することを特徴とする請求項１記載の経路立案装置。
【請求項４】
突然変異処理部は、一部の遺伝コードに任意の数値を追加することにより、交叉処理が施された遺伝コードが示す中継点の数よりも多い数の中継点を示す遺伝コードを生成することを特徴とする請求項１から請求項３のいずれか１項記載の経路立案装置。
【請求項５】
突然変異処理部は、一部の遺伝コードから任意の部分を削除することにより、交叉処理が施された遺伝コードが示す中継点の数よりも少ない数の中継点を示す遺伝コードを生成することを特徴とする請求項１から請求項３のいずれか１項記載の経路立案装置。
【請求項６】
評価部には、線路を配置することができない部分を示す情報が与えられ、この情報に基づいて評価部は遺伝コードが示す線路が線路を配置することができない部分に該当する場合に、線路を配置することができないことを示す評価値を算出することを特徴とする請求項１から請求項５のいずれか１項記載の経路立案装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、制約条件の下、複数の線路およびこれらの線路を結ぶ中継点の配置を立案する経路立案装置に関する。
【０００２】
【従来の技術】
遺伝的アルゴリズムは、生物が環境に適応して進化してゆく遺伝過程を工学的に模倣した学習アルゴリズムであり、現実の事象に適応した最適解または準最適解を短時間で求めるために利用されている。例えば、巡回セールスマン問題に代表される経路選択問題の最適解または準最適解を探索する経路選択方法が提案されている（例えば特許文献１）。特許文献１に記載された方法では、既知の地点間を通過する経路を短時間で算出することが可能である。
【０００３】
【特許文献１】
特開平８−２０２６７５号公報
【０００４】
【発明が解決しようとする課題】
しかし、未知の複数の線路およびこれらの線路を結ぶ未知の中継点の配置を有効に立案するための遺伝的アルゴリズムは開発されていない。例えば、送電線と送電線を結ぶ鉄塔の配置や、鉄道線路と鉄道線路の途中の屈曲点の配置にあたっては、中継点すなわち鉄塔または屈曲点の位置は未知であり、これらを総合的に勘案した経路立案が必要となる。
【０００５】
この発明は、上述のような課題を解決するためになされたものであり、複数の線路およびこれらの線路を結ぶ中継点をどこに配置すれば有効であるかを実用的な時間内に求める経路立案装置を得ることを目的とする。
【０００６】
【課題を解決するための手段】
この発明に係る経路立案装置は、複数の線路およびこれらの線路を結ぶ中継点の配置を立案する経路立案装置において、中継点の数に基づいた配列を持ち遺伝的操作の母集団となり上記中継点と上記線路の配置の複数の候補をそれぞれ示す複数の初期の遺伝コードをランダムに生成する初期コード化部と、入力された遺伝コードの各々に評価関数を適用して遺伝コードの各々の評価値を得る評価部と、上記評価値の各々に基づいて適切な遺伝コードを選択する選択部と、上記選択部で選択された遺伝コードの各々に交叉処理を施す交叉処理部と、上記交叉が施された遺伝コードの一部に突然変異処理を施して、上記突然変異処理後の遺伝コードの各々を上記評価部に供給する突然変異処理部と、遺伝的操作が終了条件を満たした場合に、上記突然変異処理後の遺伝コードの少なくとも一つを上記中継点と上記線路の配置候補の最適解または準最適解である最終遺伝コードとして出力し、上記遺伝的操作が終了条件を満たさない場合に、上記突然変異処理後の遺伝コードの各々を上記選択部に供給する終了判定部とを備え、上記評価部は、遺伝コードの各々が示す中継点と線路の配置から、上記中継点および上記線路の総コストに対応する指標または上記線路の総コストに対応する指標を上記評価値として算出するものである。
【０００７】
【発明の実施の形態】
以下、この発明の実施の一形態を説明する。
実施の形態１．
図１は、この発明に係る経路立案装置の構成を示すブロック図である。図示のように、この経路立案装置は、入力部１、初期コード化部２、遺伝コード評価部（終了判定部）３、遺伝的操作部（選択部、交叉処理部、突然変異処理部）４および出力部５を備える。初期コード化部２、遺伝コード評価部３および遺伝的操作部４は、プログラムに従ってコンピュータの中央演算処理装置が行う動作のモジュールを表しており、実際には一体として中央演算処理装置を構成する。
【０００８】
入力部１には、所要の中継点（例えば鉄塔）の数、線路（例えば送電線）の両端点の位置、および後述するコスト情報を操作者が入力する。所要の中継点の数および線路の両端点の位置は、中央演算処理装置の初期コード化部２に通知され、線路の両端点の位置、およびコスト情報は遺伝コード評価部３に供給される。
【０００９】
初期コード化部２は、入力部１から所要の中継点の数および線路の両端点の位置を通知されると、遺伝的操作の母集団を構成する第一世代の遺伝コードである複数の初期の遺伝コードをランダムに生成する。これらの初期の遺伝コードの各々は、次に図２および図３を参照しながら説明するように、中継点の数に基づいた配列を持ち、中継点と線路の配置の候補を示す。
【００１０】
図２は、初期コード化部２で生成された初期の遺伝コードの一例を示す模式図である。遺伝コードは様々な法則に基づいて配列されてよく、具体的な配列の法則は経路立案装置の設計に依存するが、図示の簡略な例では遺伝コードは二つの所要の中継点の配置を４桁の配列で表す。第１桁および第２桁（１，１）が第１の中継点のＸ座標およびＹ座標をそれぞれ示し、第３桁および第４桁（２，１）が第２の中継点のＸ座標およびＹ座標をそれぞれ示す。なお、スタート地点およびゴール地点は、入力部１を介して入力された線路の両端点の位置として既知であるので、遺伝コードには含められない。
【００１１】
図２の遺伝コードに対応する中継点の配置候補を平面上に示すのが図３である。図３に示すように、この配置候補では、符号▲２▼で表された第１の中継点は位置（１，１）に配置され、符号▲３▼で表された第２の中継点は位置（２，１）に配置されている。また、図３では、参考のために、符号▲１▼で表された既知のスタート地点の位置（０，０）および符号▲４▼で表された既知のゴール地点の位置（２，２）も示されている。このように線路の両端点が既知であることと相まって、遺伝コードは、中継点を示す位置と中継点の序数により線路の候補も間接的に示している。
【００１２】
初期コード化部２は、経路立案装置の設計に依存する数の初期の遺伝コードを例えば乱数を用いてランダムに作成する。遺伝コードの作成では、上記の線路の両端点の位置で画定される矩形の範囲から一定距離以内、さらに好ましくはこの矩形の範囲内に中継点が存在することを条件とする。これらの初期の遺伝コードはそれぞれ異なる配置候補を示すが、経路立案装置の設計に依存する同じ法則に基づく配列を持つ。また、初期の遺伝コードを後述の遺伝的操作で改変した後の世代の遺伝コードも同様の法則で所要の中継点の配置の候補を表すので、生成された遺伝コードから同様の法則で配置計画案を解釈することができる。
【００１３】
ただし、初期コード化部２は、入力部１で通知された中継点の数と異なる数の中継点を示す遺伝コードを生成してもよい。例えば中継点の数が一つであることを示す２桁の遺伝コードや中継点の数が三つであることを示す６桁の遺伝コードを、４桁の遺伝コードに交えて作成してよい。これによれば、中継点の数のバリエーションを増加させることができ、探索空間を広げることが可能であり、後の遺伝的操作での局所解への収束を回避することが可能である。
【００１４】
遺伝コード評価部３は、初期コード化部２または遺伝的操作部４から入力された遺伝コードの各々に評価関数を適用して遺伝コードの各々の評価値を得る。遺伝的操作部４には、遺伝コード評価部３から遺伝コードと評価値が入力され、各々の遺伝コードに遺伝的操作を施す。
【００１５】
図４は、遺伝的操作部４の動作を示すフローチャートである。遺伝コードと評価値が入力されると、ステップＳＴ１で遺伝的操作部４は選択部として機能し、評価値の各々に基づいて適切な遺伝コードを選択する。次にステップＳＴ２で遺伝的操作部４は交叉処理部として機能し、選択された遺伝コードの各々に交叉処理を施す。さらにステップＳＴ３で遺伝的操作部４は突然変異処理部として機能し、交叉が施された遺伝コードの一部に突然変異処理を施して、突然変異処理後の遺伝コードの各々を遺伝コード評価部３に供給する。
【００１６】
遺伝コード評価部３は、終了判定部としても機能し、遺伝的操作が終了条件を満たした場合に、突然変異処理後の遺伝コードの少なくとも一つを中継点の配置候補の最適解または準最適解である最終遺伝コードとして出力部５に出力し、遺伝的操作が終了条件を満たさない場合に、突然変異処理後の遺伝コードの各々を選択部としての遺伝的操作部４に供給する。従って、遺伝的操作が終了条件に達するまで、評価、選択、交叉処理および突然変異処理から構成されるサイクルが繰り返される。
【００１７】
図５はこの経路立案装置の処理を視覚で理解できるように描写した模式図である。まず、初期コード化部２では、初期の四つの遺伝コード（１，１）、（０，２，１，２），（１，０，２，１），（２，０）を生成する。図５中、符号▲１▼はスタート地点、最大の丸付き数字▲３▼または▲４▼はゴール地点、中間の丸付き数字は遺伝コードで位置が示された中継点を示す。
【００１８】
遺伝コード評価部３は、遺伝コードの各々が示す中継点と線路の配置から、入力部１を介して入力された両端点の位置とコスト情報を参照し、中継点および線路の総建設コストを評価値として算出する。すなわち、評価値Ｐは評価関数としての式（１）に従って算出される。
【数１】
2004272454.tif 000003
【００１９】
ここで、添え字ｉは個々の中継点に与えられる通し番号であり、数ｎは全中継点の数であり、従って、０＜ｉ≦ｎである。ＣＩ（ｉ）は中継点ｉを該当位置に建設するのに要するコストであり、ここには該当位置に施設の材料を運搬するのに要するコストおよび施設を組み立てるのに要するコストが含まれる。従って、コストＣＩ（ｉ）は例えば中継点の道路からの距離、標高や地質などの環境に依存する。コストＣＩ（ｉ）は、中継点が例えば鉄道線路の単なる屈曲点に過ぎない場合には比較的軽微なパラメータでありうるが、中継点に例えば鉄塔や駅舎などの施設を建設する場合には重要なパラメータでありうる。
【００２０】
また、ＣＭ（ｉ）は中継点ｉそのものの材料コストである。従って、コストＣＭ（ｉ）は、中継点が例えば鉄道線路の単なる屈曲点に過ぎない場合には比較的軽微なパラメータでありうるが、中継点が鉄塔等の施設を持つ場合には中継点の個数ｎがコストＣＭ（ｉ）に乗算されて評価値Ｐの重要なパラメータになりうる。
【００２１】
さらに、ＣＰ（ｉ）は中継点ｉから次の中継点ｉ＋１までの各線路の配備に要するコストであるが、第１の中継点のコストＣＰ（１）はスタート地点から最初の中継点を経て第２の中継点に至る線路の配備に要するコストであり、最後の中継点のコストＣＰ（ｎ）は最後の中継点からゴール地点までの線路の配備に要するコストである。コストＣＰ（ｉ）は、各線路の材料のコスト、および各線路を運搬および敷設するのに要するコストを含む。線路が鉄塔に架設される送電線である場合には、送電線の一般的な架設方法によれば、コストＣＰ（ｉ）は各線路の材料のコスト、従って各線路の距離に最大の影響を受ける。一方、線路が鉄道線路である場合には、各線路の材料を運搬・敷設するのに要するコストなども無視できなくなる。
【００２２】
これらのコストを示す情報またはコストを計算するために必要な情報は、上記のコスト情報として入力部１を介して遺伝コード評価部３にあらかじめ供給されている。なお、中継点間の間隔には限界がある、中継点が送電鉄塔の場合には鉄塔同士が見通し外の位置には建設できない等の理由により、そもそも建設できない経路計画案を示す遺伝コードについては、算出される評価値Ｐが無限大になるように、入力部１への入力においてコスト情報にも無限大を指定しておく。つまり、遺伝コード評価部３には、線路を配置することができない部分を示す情報が与えられ、この情報に基づいて遺伝コード評価部３は遺伝コードが示す線路が線路を配置することができない部分に該当する場合に、線路を配置することができないことを示す評価値を算出する。
【００２３】
上記のようにして、遺伝コード評価部３は評価関数を適用して、図５に示すように入力された遺伝コードの各々の評価値Ｐ（Ｐ１，Ｐ２，Ｐ３，Ｐ４）を得る。式（１）から明らかなように、この実施の形態での評価値Ｐは小さいほど好ましい。
【００２４】
遺伝的操作部４での選択工程では、これらの遺伝コードの評価値Ｐのうち二以上の最も低い評価値を選択し、これらの最も低い評価値に対応する遺伝コードを交叉処理工程に供する。図６はこの選択工程の具体的手法を示す。この選択工程で選択すべき評価値の個数はしきい値として中央演算処理装置に予め記憶されている。例えば、このしきい値は予めパラメータファイルに設定しておき、システム起動時に遺伝的操作部４がこれを参照するようにしてもよい。
【００２５】
図６に例示する選択工程では、まず遺伝コード評価部３で算出された評価値群を順位付けする（ステップＳＴ１０）。ステップＳＴ１０では、低い評価値ほど、高い順位すなわち若い順位序数を持つように、各評価値に順位序数が割り振られる。例えば最低の評価値には１位、次点の評価値には２位というようにである。
【００２６】
次に、これらの評価値群のうち一つの評価値を取り出し（ステップＳＴ１１）、ループカウンタＩをＩ＋１に設定する（ステップＳＴ１２）。このループカウンタＩの初期値はゼロである。
【００２７】
さらに、取り出した評価値Ｐ（Ｉ）の順位序数を、上位何番まで選択するかを示すしきい値と比較する（ステップＳＴ１３）。そして、しきい値より大きい順位序数の場合にはこの評価値Ｐ（Ｉ）を選択しないが、しきい値以下の順位序数を持つ場合にはこの評価値Ｐ（Ｉ）ひいてはこれに対応する遺伝コードを選択する（ステップＳＴ１４）。
【００２８】
この後、ループカウンタＩを全評価値の数Ｍと比較する（ステップＳＴ１５）。ここでＩ＝Ｍであれば選択処理を終了し、Ｉ＜Ｍであれば、別の評価値を選択すべきか否か判断するために処理はステップＳＴ１１に戻る。このようにして全評価値について選択すべきか否かの判断の試行を行い、しきい値分の個数の低い評価値を選択する。以上のように、しきい値までの順位序数を持つ二以上の評価値ひいては評価値に対応する遺伝コードを選択することにより、より良い遺伝コードが着実に生成される。
【００２９】
遺伝的操作部４での交叉処理工程では、図５に示すような一様交叉を行ってもよい。すなわち、選択工程で選択された遺伝コード中の数値を部分的にランダムに交換することにより、交叉が施された所定の数の遺伝コードを得てもよい。
【００３０】
あるいは、遺伝的操作部４での交叉処理工程では、図７に示すような一点交叉を行ってもよい。すなわち、選択工程で選択された遺伝コード中の交叉点（ある桁）以下の数値を互いに交換することにより、交叉が施された遺伝コードを得てもよい。このように一点交叉を行うことにより、評価値の低い遺伝コードの一部分を引き継いだ、より評価値の低い遺伝コードの生成を迅速に可能にすることができる。
【００３１】
遺伝的操作部４での突然変異処理工程では、交叉処理後の遺伝コードから突然変異処理を実行する確率に従って一部の遺伝コードをランダムに取り出し、取り出された遺伝コード中の一部を図５および図８に示すように任意に変更する。突然変異処理を実行する確率は、中央演算処理装置に予め記憶されている。例えば、この確率は予めパラメータファイルに設定しておき、システム起動時に遺伝的操作部４がこれを参照するようにしてもよい。一つの遺伝コード中の突然変異処理で変更する部分はランダムであり、どの数に変更するかもランダムである。このように、突然変異を行うことで局所解から回避するという効果がある。
【００３２】
突然変異処理工程では、突然変異処理を実行する確率に従って一部の遺伝コードに突然変異処理を施す。従って、図５に示すように、突然変異処理後の遺伝コードには、交叉処理工程後の遺伝コードと同じものと、実際に変異させられたものが混在する。
【００３３】
このようにして遺伝的操作部４により、選択、交叉および突然変異を施された次の世代の遺伝コードが生成される。次の世代の遺伝コードの各々は、終了判定部としての遺伝コード評価部３に供給され、遺伝的操作が終了条件に達するまで、評価、選択、交叉処理および突然変異処理から構成されるサイクルが繰り返される。すなわち、遺伝コード評価部３は、遺伝的操作後（突然変異処理後）の遺伝コードの各々に上記と同様に式（１）の評価関数を適用して遺伝コードの各々の評価値を得て、遺伝的操作が終了条件を満たさない場合に、遺伝的操作後の遺伝コードの各々を選択部としての遺伝的操作部４に供給する。遺伝的操作部４は低い評価値を持つ二以上の遺伝コードを選択して、選択された遺伝コードの各々に交叉処理を施し、交叉が施された遺伝コードの一部に突然変異処理を施して、突然変異処理後の遺伝コードの各々を遺伝コード評価部３に供給する。
【００３４】
この実施の形態において、遺伝的操作の終了条件は、遺伝コード評価部３が算出した評価値の一つまたは全てがあるしきい値を下回ったこととしてもよい。あるいは、遺伝的操作の終了条件は、上記の評価、選択、交叉処理および突然変異処理から構成されるサイクルが規定の回数まで達したこと、すなわち規定の世代の遺伝コードが生成されたこととしてもよいし、初期の遺伝コードの生成からカウントを開始した経過時間が規定の許容時間を上回ったこととしてもよい。この終了条件が満たされると、遺伝コード評価部３は、突然変異処理後の遺伝コードのうち、少なくとも一つの最も評価値が低いものを中継点の配置候補の最適解または準最適解である最終遺伝コードとして出力部５に出力する。出力部５は、ディスプレイに最終遺伝コードを表示させる表示制御部でもよいし、プリンタに最終遺伝コードを印刷させる印刷制御部でもよい。
【００３５】
以上のようにこの実施の形態１によれば、遺伝的アルゴリズムを適用し、中継点および線路の総建設コストを遺伝的アルゴリズムの評価値Ｐとして使用することによって、複数の線路およびこれらの線路を結ぶ中継点をどこに配置すれば有効であるかを実用的な時間内に求めることが可能である。
【００３６】
上記の実施の形態１では、評価値Ｐは式（１）に従って算出される。ただし、評価値Ｐの逆数を評価値として使用してもよい。このような場合には、選択工程では、最も高い二以上の評価値に対応する遺伝コードが選択される。また、このような場合には、終了条件としては、評価値の一つまたは全てがあるしきい値を上回ったこととしてもよい。
【００３７】
実施の形態２．
次に上記の遺伝的操作部４で行う選択工程の変形例をこの発明の実施の形態２に係る選択工程として説明する。実施の形態２で、経路立案装置の構成要素および選択工程以外の工程は、実施の形態１と同じでよい。
【００３８】
図９は、実施の形態２に係る選択工程の具体的手法を示す。この選択工程では、あるしきい値以下の評価値およびこのような評価値を持つ遺伝コードを選択する。このしきい値は中央演算処理装置に予め記憶されている。例えば、このしきい値は予めパラメータファイルに設定しておき、システム起動時に遺伝的操作部４がこれを参照するようにしてもよい。
【００３９】
図９に示す選択工程では、まず遺伝コード評価部３で算出された評価値群のうち一つの評価値を取り出し（ステップＳＴ２０）、ループカウンタＩをＩ＋１に設定する（ステップＳＴ２１）。このループカウンタＩの初期値はゼロである。
【００４０】
さらに、取り出した評価値Ｐ（Ｉ）そのものを上記のしきい値と比較する（ステップＳＴ２２）。そして、しきい値より大きい場合にはこの評価値Ｐ（Ｉ）を選択しないが、しきい値以下の場合にはこの評価値Ｐ（Ｉ）ひいてはこれに対応する遺伝コードを選択する（ステップＳＴ２３）。
【００４１】
この後、ループカウンタＩを全評価値の数Ｍと比較する（ステップＳＴ２４）。ここでＩ＝Ｍであれば選択処理を終了し、Ｉ＜Ｍであれば、別の評価値を選択すべきか否か判断するために処理はステップＳＴ２０に戻る。このようにして全評価値について選択すべきか否かの判断の試行を行い、しきい値以下の評価値を選択する。以上のように、しきい値以下の評価値ひいては評価値に対応する遺伝コードを選択することにより、より良い遺伝コードが着実に生成される。
【００４２】
なお、評価値Ｐの逆数（１／Ｐ）を評価値として使用する場合には、選択工程では、しきい値以上の評価値に対応する遺伝コードが選択される。
【００４３】
実施の形態３．
次に上記の遺伝的操作部４で行う選択工程の他の変形例をこの発明の実施の形態３に係る選択工程として説明する。実施の形態３で、経路立案装置の構成要素および選択工程以外の工程は、実施の形態１と同じでよい。
【００４４】
図１０は、実施の形態３に係る選択工程の具体的手法を示す。この選択工程では、評価値に応じて予め割り振られた確率を評価値に乗算して得られた副次的評価値があるしきい値以下であれば、その評価値およびこれに対応する遺伝コードを選択する。確率およびしきい値は中央演算処理装置にあらかじめ記憶されている。例えば、確率およびしきい値はあらかじめパラメータファイルに設定しておき、システム起動時に遺伝的操作部４がこれを参照するようにしてもよい。
【００４５】
図１０に示す選択工程では、まず遺伝コード評価部３で算出された評価値群のうち一つの評価値を取り出し（ステップＳＴ３０）、ループカウンタＩをＩ＋１に設定する（ステップＳＴ３１）。このループカウンタＩの初期値はゼロである。
【００４６】
さらに、取り出した評価値Ｐ（Ｉ）に基づいてパラメータファイルから確率Ｏ（Ｉ）を読み出し（ステップＳＴ３２）、評価値Ｐ（Ｉ）に確率Ｏ（Ｉ）を乗算することにより副次的評価値Ａ（Ｉ）を算出する（ステップＳＴ３３）。確率Ｏ（Ｉ）は、評価値の大きさに応じて予め割り振られている。例えば、評価値が１０以上２０未満であれば確率は０．１、評価値が２０以上３０未満であれば確率は０．２というように、評価値Ｅが低いほど低い確率を予め割り振ってある。
【００４７】
次に副次的評価値Ａ（Ｉ）を上記のしきい値と比較する（ステップＳＴ３４）。そして、副次的評価値Ａ（Ｉ）がしきい値より大きい場合にはこの評価値Ｐ（Ｉ）を選択しないが、副次的評価値Ａ（Ｉ）がしきい値以下の場合にはこの評価値Ｐ（Ｉ）ひいてはこれに対応する遺伝コードを選択する（ステップＳＴ３５）。
【００４８】
この後、ループカウンタＩを全評価値の数Ｍと比較する（ステップＳＴ３６）。ここでＩ＝Ｍであれば選択処理を終了し、Ｉ＜Ｍであれば、別の評価値を選択すべきか否か判断するために処理はステップＳＴ３０に戻る。このようにして全評価値について選択すべきか否かの判断の試行を行い、副次的評価値Ａ（Ｉ）がしきい値以下の評価値Ｐ（Ｉ）を選択する。
【００４９】
生物の遺伝過程において個体の環境への適合度が高い場合には、自然淘汰される確率が低くなる（換言すれば生き残る確率が高くなる）と考えられる。従って、個体の環境への適合度の逆数に相当する遺伝コードの評価値Ｐ（Ｉ）に、個体が生き残る確率の逆数に相当する確率Ｏ（Ｉ）を乗算することにより得られた副次的評価値Ａ（Ｉ）は、元の評価値Ｐ（Ｉ）よりもさらに、選択されるべき適合度を示す指標として的確であると考えられる。遺伝コードの評価値Ｐ（Ｉ）の相違は、確率Ｏ（Ｉ）を乗じることにより、副次的評価値Ａ（Ｉ）の相違として拡大される。以上のように、遺伝コードの評価値Ｐ（Ｉ）に応じて予め割り振られた確率Ｏ（Ｉ）を乗算して副次的評価値Ａ（Ｉ）を得ることで、上述した他の実施の形態による経路立案装置よりも、さらにより良い遺伝コードが着実に生成されるという効果がある。
【００５０】
なお、副次的評価値Ａ（Ｉ）の算出は、中央演算処理装置が行う動作のモジュールのうち、遺伝コード評価部３に相当するモジュールが行ってもよいし、選択部としての遺伝的操作部４に相当するモジュールが行ってもよい。
【００５１】
また、評価値Ｐの逆数（１／Ｐ）を評価値として使用する場合には、評価値１／Ｐが高いほど、高い確率を予め割り振っておき、選択工程では、しきい値以上の副次的評価値Ａ（Ｉ）に対応する遺伝コードが選択される。
【００５２】
実施の形態４．
次に上記の遺伝的操作部４で行う突然変異工程の変形例をこの発明の実施の形態４に係る突然変異工程として説明する。実施の形態４で、経路立案装置の構成要素および突然変異工程以外の工程は、実施の形態１から実施の形態３と同じでよい。
【００５３】
図１１は、実施の形態４に係る突然変異工程の具体的手法を示す。この突然変異工程では、突然変異処理部としての遺伝的操作部４は、一部の遺伝コードに任意の数値を追加することにより、交叉処理が施された遺伝コードが示す中継点の数よりも多い数の中継点を示す遺伝コードを生成する。図において、交叉処理が施された元の遺伝コード１，０，１，２は、符号▲２▼で表された第１の中継点が位置（１，０）に配置され、符号▲３▼で表された第２の中継点が位置（１，２）に配置されることを表す。他方、突然変異処理が施された遺伝コード１，０，１，１，１，２は、符号▲２▼で表された第１の中継点が位置（１，０）に配置され、符号▲３▼で表された第２の中継点が位置（１，１）に配置され、符号▲４▼で表された第３の中継点が位置（１，２）に配置されることを表す。
【００５４】
このように遺伝コードの桁数を変更することにより、中継点の数のバリエーションを増加させることができ、探索空間を広げることが可能であり、局所解への収束を回避することができるという効果がある。特に、中継点の数が増加しても、コストが低減する可能性は存在するので、このような可能性のある配置候補の試行ができる点で有効である。
【００５５】
実施の形態５．
次に上記の遺伝的操作部４で行う突然変異工程の他の変形例をこの発明の実施の形態５に係る突然変異工程として説明する。実施の形態５で、経路立案装置の構成要素および突然変異工程以外の工程は、実施の形態１から実施の形態３と同じでよい。
【００５６】
図１２は、実施の形態５に係る突然変異工程の具体的手法を示す。この突然変異工程では、突然変異処理部としての遺伝的操作部４は、一部の遺伝コードから任意の数値を削除することにより、交叉処理が施された遺伝コードが示す中継点の数よりも少ない数の中継点を示す遺伝コードを生成する。図において、交叉処理が施された元の遺伝コード１，０，１，１，１，２は、符号▲２▼で表された第１の中継点が位置（１，０）に配置され、符号▲３▼で表された第２の中継点が位置（１，１）に配置され、符号▲４▼で表された第３の中継点が位置（１，２）に配置されることを表す。他方、突然変異処理が施された遺伝コード１，０，１，２は、符号▲２▼で表された第１の中継点が位置（１，０）に配置され、符号▲３▼で表された第２の中継点が位置（１，２）に配置されることを表す。
【００５７】
このように遺伝コードの桁数を変更することにより、中継点の数のバリエーションを増加させることができ、探索空間を広げることが可能であり、局所解への収束を回避することができるという効果がある。特に、中継点の数が減少すれば、コストが低減する可能性が高いので、このような可能性のある配置候補の試行ができる点で有効である。
【００５８】
実施の形態６．
次に上記の遺伝的操作部４で行う評価工程の変形例をこの発明の実施の形態５に係る評価工程として説明する。実施の形態６で、経路立案装置の構成要素および評価工程以外の工程は、実施の形態１から実施の形態５と同じでよい。
【００５９】
上記の実施の形態１では、評価値Ｐは、式（１）に従って中継点および線路の総建設コストとして算出される。ただし、中継点が単なる鉄道線路の分岐点である場合のように、中継点の建設コストが相対的に線路の建設コストよりも非常に小さい場合には、評価値Ｐは式（２）に従って線路の総建設コストとして算出してもよい。
【数２】
2004272454.tif 000004
【００６０】
ここで、ＣＰ（ｉ）は中継点ｉから次の中継点ｉ＋１までの各線路の配備に要するコストであるが、第１の中継点のコストＣＰ（１）はスタート地点から最初の中継点を経て第２の中継点に至る線路の配備に要するコストであり、最後の中継点のコストＣＰ（ｎ）は最後の中継点からゴール地点までの線路の配備に要するコストである。コストＣＰ（ｉ）は、各線路の材料のコストＣＰ１（ｉ）、および各線路を運搬および敷設するのに要するコストＣＰ１（２）の合計である。コストＣＰ１（ｉ）は、各線路の距離に最大の影響を受ける。一方、コストＣＰ２（ｉ）は、線路が配備される地点間の標高差または勾配に影響を受ける。例えば鉄道線路の敷設計画などの場合、なるべく勾配が少なく、なるべく全線路の距離が短くなるように線路を敷設するのが好ましい。
【００６１】
これらのコストを示す情報またはコストを計算するために必要な情報は、上記のコスト情報として入力部１を介して遺伝コード評価部３にあらかじめ供給されている。なお、勾配があまりに大きいと鉄道車両が通れないので、距離に対する標高差が一定以上でそもそも建設できない経路計画案を示す遺伝コードについては、算出される評価値Ｐが無限大になるように、入力部１への入力においてコスト情報にも無限大を指定しておく。つまり、遺伝コード評価部３には、線路を配置することができない部分を示す情報が与えられ、この情報に基づいて遺伝コード評価部３は遺伝コードが示す線路が線路を配置することができない部分に該当する場合に、線路を配置することができないことを示す評価値を算出する。なお、この実施の形態でも、評価値Ｐの逆数を評価値として使用してもよい。
【００６２】
以上のようにこの実施の形態６によれば、遺伝的アルゴリズムを適用し、線路の総建設コストを遺伝的アルゴリズムの評価値Ｐとして使用することによって、複数の線路およびこれらの線路を結ぶ中継点をどこに配置すれば有効であるかを実用的な時間内に求めることが可能である。特に、鉄道線路の敷設計画において最適解または準最適解を算出する場合に、この実施の形態は有効である。
【００６３】
【発明の効果】
以上のように、この発明によれば、複数の線路およびこれらの線路を結ぶ中継点の配置を立案する経路立案装置において、中継点の数に基づいた配列を持ち遺伝的操作の母集団となり上記中継点と上記線路の配置の複数の候補をそれぞれ示す複数の初期の遺伝コードをランダムに生成する初期コード化部と、入力された遺伝コードの各々に評価関数を適用して遺伝コードの各々の評価値を得る評価部と、上記評価値の各々に基づいて適切な遺伝コードを選択する選択部と、上記選択部で選択された遺伝コードの各々に交叉処理を施す交叉処理部と、上記交叉が施された遺伝コードの一部に突然変異処理を施して、上記突然変異処理後の遺伝コードの各々を上記評価部に供給する突然変異処理部と、遺伝的操作が終了条件を満たした場合に、上記突然変異処理後の遺伝コードの少なくとも一つを上記中継点と上記線路の配置候補の最適解または準最適解である最終遺伝コードとして出力し、上記遺伝的操作が終了条件を満たさない場合に、上記突然変異処理後の遺伝コードの各々を上記選択部に供給する終了判定部とを備え、上記評価部は、遺伝コードの各々が示す中継点と線路の配置から、上記中継点および上記線路の総コストに対応する指標または上記線路の総コストに対応する指標を上記評価値として算出するので、複数の線路およびこれらの線路を結ぶ中継点をどこに配置すれば有効であるかを実用的な時間内に求めることが可能である。
【図面の簡単な説明】
【図１】この発明に係る経路立案装置の構成を示すブロック図である。
【図２】この発明に係る経路立案装置の初期コード化部で生成された初期の遺伝コードの一例を示す模式図である。
【図３】図２の遺伝コードに対応する中継点の配置候補を平面上に示す模式図である。
【図４】この発明に係る経路立案装置の遺伝的操作部の動作を示すフローチャートである。
【図５】この発明に係る経路立案装置の処理を視覚で理解できるように描写した模式図である。
【図６】この発明の実施の形態１による経路立案装置の選択工程の具体的手法を示すフローチャートである。
【図７】この発明に係る経路立案装置の交叉処理工程の具体的手法を示す模式図である。
【図８】この発明に係る経路立案装置の突然変異処理工程の具体的手法を示す模式図である。
【図９】この発明の実施の形態２による経路立案装置の選択工程の具体的手法を示すフローチャートである。
【図１０】この発明の実施の形態３による経路立案装置の選択工程の具体的手法を示すフローチャートである。
【図１１】この発明の実施の形態４に係る突然変異工程の具体的手法を示す模式図である。
【図１２】この発明の実施の形態５に係る突然変異工程の具体的手法を示す模式図である。
【符号の説明】
１  入力部、２  初期コード化部、３  遺伝コード評価部、４  遺伝的操作部（選択部、交叉処理部、突然変異処理部）、５  出力部。
【図１】
2004272454.tif 000005
【図２】
2004272454.tif 000006
【図３】
2004272454.tif 000007
【図４】
2004272454.tif 000008
【図５】
2004272454.tif 000009
【図６】
2004272454.tif 000010
【図７】
2004272454.tif 000011
【図８】
2004272454.tif 000012
【図９】
2004272454.tif 000013
【図１０】
2004272454.tif 000014
【図１１】
2004272454.tif 000015
【図１２】
2004272454.tif 000016