コストの変動するグラフにおける経路探索手法:AntNetの適用と改良

概要

論文の詳細を見る
本研究ではテーマパークやイベント会場において経路決定の支援を行うシステムを構築することを最終目標とし、その部分問題であるコストの変動する重み付きグラフにおける経路探索問題に対して、AntNetを適用した。AntNetとは蟻コロニー最適化の考えを応用して提案された経路探索手法である。AntNetのアルゴリズムは、複数の蟻が以下のステップを任意の回数まで繰り返す。まず、蟻が始点から目的頂点までフェロモンを参照しながら、確率的に経路を選択していく。次に、完成した経路の評価に応じてフェロモンを分泌する。実験の結果、AntNetはグラフの規模が大きくなるほど、探索時間の面で有効であることを示した。しかし、コストの変動間隔が長い場合に、フェロモンの過成熟によって経路が固定されてしまい、解の精度が下がってしまう問題が明らかになった。そこで、この問題を解決するために、フェロモンの過成熟を防ぐことで解の精度を上げる手法を提案し、その評価を行った。結果として、実験を行った環境においては解精度が通常のAntNetによる探索と比較して3.89倍の精度と非常に良い結果が得られることを示した
2011-09-30