蟻コロニー最適化手法による快適性を考慮したナビゲーションシステム
2009SE248 里見優
指導教員：高見勲

1

はじめに近年，安全で快適なドライブを考えてカーナビゲーションシステム (以下カーナビ) を搭載する車が一般的になってきている．現在のカーナビの経路探索技術は，出発地や目的地を得る「探索基点の設定技術」，最短経路を確実に探す「主経路の探索技術」，渋滞回避の為に最適な巡回路を探す「補助経路の探索技術」，探索された経路上の危険個所を抽出する「経路情報の作成技術」で構成されている．
本研究では，Ant Colony Optimization(蟻コロニー最適化，以下 ACO) に，他のアルゴリズムを融合して性能を向上させ，ドライバーのストレスを軽減させる快適性を考慮したナビゲーションシステムを実現し，実際の地図を用いて最短経路探索を目的とする．ACO とは，蟻がコロニー (群れ) から餌までの経路を見つける際の，群れで経路を形成する方法を元に開発された最適化手法である．蟻はフェロモン通信と単純な行動規則だけで効率的に集団最採餌行動を行う．
ドライバーが快適だと感じるドライブを考慮するために必要な項目として挙げられるのは，右折および左折が少ない経路選択，信号の数が少ない経路選択，高速道路を通らない経路選択等である．

E(t) = −Σx Σy px,y (t) log px,y (t)px,y (t) =τx,y (t)Σx Σy τx,y (t)

(1)
(2)

E(t) の最大は，フェロモン濃度が一様に分布している
τx,y (0) のときで，その値は log n である．n は通行可能なノードの数である．そこで，式 (3) のような正規化エントロピー EN (t) を用いる．EN (t) は，[0, 1] の区間の値となる．
EN (t) =4E(t)log n(3)多様性の維持ACO による探索は，それまでの探索結果の蓄積を用いて，より良い解を構成する部分を探し出し集めていくということによりなされる．これは，Genetic Algorism(遺伝的アルゴリズム，以下 GA) においても同様である．その際，良い解の近くを集中的に探索しようという集中化(intensification) とこれまで探索してきた解とは構造の異なる解を探索しようという多様化 (diversification) はきわめて重要となってくる．両者をどのようにバランスさせるかという点は探索の改善に関してきわめて重要である．
2 PSO による学習機能強化
そこで，蟻の経路選択において，GA の突然変異に相当過去の行動履歴に従って動的にフェロモンを調整する する提案法を適用し，積極的に多様性をコントロールすことによって，ACO の学習機能の向上を目指す．そこで， ることにした．これまでの探索結果のフェロモンを損なParticle Swarm Optimization(粒子群最適化，以下 PSO) わない程度に，平均値を基準としてフェロモンを平均化との融合アルゴリズムを考える．
させる．提案法を以下に示す．
PSO とは，鳥の群れ，魚の群れ，昆虫の群れなど集団試行回数 m 回毎にでの探索行動に基づいた多点型最適化手法である．PSO 1 フェロモン濃度の平均値 M を計算する．の基本原理は群れを構成する固体である Particle(探索点)
2 すべてのノードについてが自由に行動するのではなく，Particle の独自情報と，群M より小さいフェロモン濃度を M にする．
全体の共有情報を組合せ，一定の規則に従って行動するという概念をもつことである [1]．
MAX-MIN Ant System(MMAS) では，各ノードに分3

エントロピーの定義

泌されるフェロモンの総量に制限があり，多様性の維持を促す．同時に，その時点における最良の巡回路にフェロモンが分泌され，集中化を促進する．

エントロピーとは「無秩序の度合いを示す物質量」である．エントロピーを観測することによって，ACO の収束特性を解析することが可能である．例えば，エントロ 5 C# プログラムによるシミュレーション
ピーが高いとは，フェロモンが均一に分布していること
図 1 のような最短経路 208 の横 130 縦 80 の迷路を考えを示し，多様性がある状態である．また，エントロピー る．1 マスを座標 (x, y) としてとらえ，その座標をノードが低いとは，フェロモン分布が近寄っていることを示し， とする．蟻 100 匹を試行回数 200 回繰り返し，その過程解が収束していることを示す．
を 10 回行った．
本研究では，学習経過の情報はフェロモン濃度 τx,y (t)その結果，最短経路長の平均は，提案法を用いたときに保持されている．τx,y (t) のエントロピーの式を式 (1)， に最も最適解に近づいた．また，ACO と PSO のみのと(2) と定義する．
きと比べて提案法では誤差率を 10 ％以上減少させること

(a) 最短経路 A

図 1 横 130 縦 80 の迷路

図 2 提案法で得た最短経路ができた．ACO と PSO に MMAS を用いた場合，エントロピーが非常に高い値 0.9 付近で収束しており，最適解に収束しないことがわかった．
なお，提案法を用いたときに限り，10 回の過程中に最短経路を得ることができた．

6(b) 最短経路 B

快適性を考慮したナビゲーションシステム
本研究では，• 右折および左折を少なくする (ただし，左折より右折を少なくさせることを優先させる)• 信号の少ない道を選択する

図 3 yahoo マップで得た最短経路 C• 高速道路を選択しない
表 1 は，提案法で得た最短経路 A，B，Yahoo マップで以上の 3 つをドライバーが快適だと感じる価値観とし，提案法を用いて快適性を考慮したナビゲーションシステム 得た最短経路 C の快適性の条件を比較している．google
マップで得た最短経路は，高速道路を通っているので比を実現する．
まず，右折および左折を少なくする方法を以下に示す． 較対象から外した．最短経路 A では，他の最短経路に比べて，右折および左折の回数が上回るが，通る信号数を目標値に到着するまで1 進行方向は，各ノードにおける蟻の通過回数が最小の 大幅に減らすことができた．最短経路 B では，提案法を方向である．選ばれた方向のノードに対して評価す 用いたことにより左折をなくし最短経路 C より通る信号る数値として，そのノードのフェロモン濃度 τ を与 数を減らすことができた．
える．
表 1 快適性の条件の比較

2 評価値についてa 前または後を選んだ場合
b 右または左を選んだ場合

提案法

ττ × a(0 < a < 1)

3 各ノードにおける前後左右のノードの評価値に比例して，進行方向を決定する．
また，信号のある交差点と高速道路の部分のノードのフェロモン濃度を他の通行可能なノードより少なく初期設定することにより，信号の少ない道を選択するよう促し，高速道路を選択させにくくする．

7

快適性を考慮したナビゲーションシステムの検証

8

yahoo マップ

最短経路 A

最短経路 B

最短経路 C

右折した回数211

左折した回数

201

信号の数

3810

おわりに

ACO と PSO，さらにフェロモンを平均値を基準として平均化させ，そこで新たな経路を発見する提案法を組み合わせたアルゴリズムを用いて，ドライバーの快適性を考慮したナビゲーションシステムの実現を図った．

実際の地図を例にとり，提案法によるナビゲーション
システムの検証を行う．大阪府大阪市中央区南久宝寺町 参考文献
3 丁目付近の地図を検証に用いた．四ツ橋駅 (1, 1) から堺 [1] 森直樹：熱力学的遺伝アルゴリズムによる多目的最筋本町駅 (39, 43) までの最短経路を考える．
適化，システム制御情報学会，vol.11，No.3，pp.103提案法で蟻 100 匹を試行回数 200 回繰り返して得た最111，1998.
短経路，yahoo マップで得た最短経路，図 2，3 に示す．