遺伝的アルゴリズムによる経路探索

カテゴリ: 部門大会

論文No: OS7-3

グループ名: 【C】平成19年電気学会電子・情報・システム部門大会講演論文集

発行日: 2007/09/04

タイトル(英語): The Shortest Path Searching System with Genetic Algorithm

著者名: 松本 未生(関東学院大学),神野健哉 (関東学院大学)

著者名(英語): Mio Matsumoto(Kanto Gakuin University),Kenya Jinno(Kanto Gakuin University)

キーワード: 遺伝的アルゴリズム|経路探索|genetic algorithm|shortest path searching

要約(日本語): 最短経路を探索する方法として、全解探索法である深さ優先探索、幅優先探索、幅優先探索の一種であるダイクストラ法がある。
　これらの方法は、確実に最短である経路を得ることができるが、地点数が多ければ多いほど探索に時間がかかるという欠点がある。
　また、最短経路に満足できず、それに近い距離である経路を探索したい場合、上記の方法では新たに探索をやり直さなければならない。そのうえ、新たに得られた解が、第２位に短い経路であるとは限らない。
　遺伝的アルゴリズムは、生物の進化の過程に似せて作られたアルゴリズムで、実用時間内にできるだけ優れた解を求めることができることや、解を評価するにあたっての評価関数を柔軟に設定できる等の長所を持つ。
　また、処理していく過程で多くの解候補を生成し、保存することができるので、一度の探索で複数の経路を探索することが可能である。
　本報告では、この遺伝的アルゴリズムを用いて経路探索を行う方法について考察を行う。

　提案するシステムでは以下のような処理手順を用いる。

　今回用いる遺伝子型は、経由する地点の番号を遺伝子とする。
　遺伝子型の先頭に出発地点を設定し、そこから先は接続している地点からランダムに決定するこれを終着点まで繰り返す。
　そして経路長の逆数を適応度とする。
　初期集団を設計する段階で終着点まで辿り着けない遺伝子型の経路長は、大きな数値(99999)に設定した。
　選択淘汰には、２つの方法を用いることにする。
　まず、生成された遺伝子型のうち、もっとも適応度の高いものを無条件に残すエリート保存戦略と、適応度に基づいた確率を用いてランダムに選択するルーレット戦略である。
　交叉は、ルーレット戦略によって選ばれた２つの個体を用いた。

PDFファイルサイズ: 1,773 Kバイト