Pat

J-GLOBAL ID：200903024758534644

経路選択方法及び装置

Inventor： 山田 武士
Applicant, Patent owner： 日本電信電話株式会社
Agent (1)： 若林 忠
Gazette classification：公開公報
Application number (International application number)：1995010313
Publication number (International publication number)：1996202675
Application date： Jan. 26, 1995
Publication date： Aug. 09, 1996
Summary：

【要約】【目的】巡回セールスマン問題に代表される経路選択問題の最適解または準最適解を短時間で探索する。【構成】遺伝アルゴリズムを使用する。交叉を行う際に(ステップ106)、都市数Nと同じ長さのビット列をランダムに生成し、このビット列の第i番目のビットの0,1にしたがって1対の親の個体のうちの一方を選択し、選択結果に応じて子の個体のi番目の要素(i番目に訪問する都市)を決定するようにして巡回路を計算し(ステップ107)、親の形質が子に受け継がれるようにする。

Claim (excerpt)：

配置された位置と他のノードとの距離が既知であるN個のノードに対し、重複することなく全てのノードをできるだけ短い距離で通過して最初のノードに戻る経路を探索する方法であり、各要素がそれぞれ1個のノードに対応し要素の配列順によって対応するノードの通過順を示すN次元ベクトルを個体とし、各個体の表わす経路の距離を評価値として個体群の淘汰を行うとともに、個体群からランダムに選択された親となる2個体から新たに子となる2個体を生成して個体群を更新する交叉を行う遺伝アルゴリズムを使用する経路選択方法において、前記交叉を行うステップが、Nビットのビット列をランダムに生成する第1のステップと、前記ビット列における第i番目のビットの値に応じて親となる個体のうちの一方を選択する第2のステップと、選択結果に応じて子となる個体の第i番目の要素の決定する第3のステップとを有し、前記第2のステップ及び前記第3のステップを繰り返し実行することによって、1つの子の個体が生成されることを特徴とする経路選択方法。

IPC (2)：

G06F 15/18 550 ,  G06F 9/44 550