特許
J-GLOBAL ID：200903024758534644
経路選択方法及び装置
発明者：
出願人/特許権者：
代理人 (1件)：
若林 忠
公報種別：公開公報
出願番号（国際出願番号）：特願平7-010313
公開番号（公開出願番号）：特開平8-202675
出願日： 1995年01月26日
公開日（公表日）： 1996年08月09日
要約：
【要約】【目的】巡回セールスマン問題に代表される経路選択問題の最適解または準最適解を短時間で探索する。【構成】遺伝アルゴリズムを使用する。交叉を行う際に(ステップ106)、都市数Nと同じ長さのビット列をランダムに生成し、このビット列の第i番目のビットの0,1にしたがって1対の親の個体のうちの一方を選択し、選択結果に応じて子の個体のi番目の要素(i番目に訪問する都市)を決定するようにして巡回路を計算し(ステップ107)、親の形質が子に受け継がれるようにする。
請求項（抜粋）：
配置された位置と他のノードとの距離が既知であるN個のノードに対し、重複することなく全てのノードをできるだけ短い距離で通過して最初のノードに戻る経路を探索する方法であり、各要素がそれぞれ1個のノードに対応し要素の配列順によって対応するノードの通過順を示すN次元ベクトルを個体とし、各個体の表わす経路の距離を評価値として個体群の淘汰を行うとともに、個体群からランダムに選択された親となる2個体から新たに子となる2個体を生成して個体群を更新する交叉を行う遺伝アルゴリズムを使用する経路選択方法において、前記交叉を行うステップが、Nビットのビット列をランダムに生成する第1のステップと、前記ビット列における第i番目のビットの値に応じて親となる個体のうちの一方を選択する第2のステップと、選択結果に応じて子となる個体の第i番目の要素の決定する第3のステップとを有し、前記第2のステップ及び前記第3のステップを繰り返し実行することによって、1つの子の個体が生成されることを特徴とする経路選択方法。
IPC (2件)：
G06F 15/18 550
, G06F 9/44 550
