著者

狩野 均

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告高度交通システム(ITS) (ISSN:09196072)

巻号頁・発行日

vol.2002, no.21, pp.51-58, 2002-03-05

被引用文献数

3

---

本研究では、自動車用ナビゲーション装置(カーナビ)の経路探索に着目し、その機能を拡張するための手法を提案する。本手法は、GAの個体集団の他に2つの知識集団を生成し、この知識を個体に適用する手段として感染演算子を導入するものである。知識の集団として、主要道路の集団と立ち寄り候補地の集団を生成し、感染演算によって、運転の快適性の向上と立ち寄り昨日の実現の両方を達成するところに特徴がある。実際のカーナビで使われているナビ研S規格地図を用いた評価実験により、本手法の有効性を確認した。本手法は、問題領域の知識をウイルスと見なすことにより、遺伝的アルゴリズムの枠組みの中に知識を利用するための演算を実現したところに特徴がある。この考え方は、一般に遺伝的アルゴリズムを実用規模の問題に適用するとき有効であると考える。This paper addresses the problem of selecting a route to a given destination that traverses several non-specific sites (e.g. a book, a gas station) as requested by a driver. The proposed solution uses a genetic algorithm that includes viral infection. The method is to generate two populations of viruses as domain specific knowledge in additon to a population of routes. A part of an arterial road is regarded as a main virus, and a road that includes a site is regarded as a site virus. An infection occurs between two points common to a candidate route and the virus, and involves the substitution of the intersections carried by the virus for those on the existing candidate route. Crossover and infection detemine the easiest-to-drive and quasi-shortest route through the objective landmarks. Experiments using actual road maps show that this infection-based mechanism is an effective way of soloving the problem. Our strategy is general, and can be effectively used in othe optimization problems.