Path Search Method for Weighted Graphs with Weight Changes:Application and Improvement of AntNet
| Autor: | Hideyuki, Shimakage, Takashi, Yamaguchi, Kenneth James, Mackin, Yasuo, Nagai |
|---|---|
| Přispěvatelé: | 東京情報大学大学院総合情報学研究科, 東京情報大学総合情報学部情報システム学科, Tokyo University of Information Sciences, Graduate School of Informatics, Tokyo University of Information Sciences, Faculty of Informatics, Department of Information Systems |
| Jazyk: | japonština |
| Rok vydání: | 2011 |
| Předmět: | |
| Zdroj: | 東京情報大学研究論集. 15(1):100-117 |
| Popis: | 本研究ではテーマパークやイベント会場において経路決定の支援を行うシステムを構築することを最終目標とし、その部分問題であるコストの変動する重み付きグラフにおける経路探索問題に対して、AntNetを適用した。AntNetとは蟻コロニー最適化の考えを応用して提案された経路探索手法である。AntNetのアルゴリズムは、複数の蟻が以下のステップを任意の回数まで繰り返す。まず、蟻が始点から目的頂点までフェロモンを参照しながら、確率的に経路を選択していく。次に、完成した経路の評価に応じてフェロモンを分泌する。実験の結果、AntNetはグラフの規模が大きくなるほど、探索時間の面で有効であることを示した。しかし、コストの変動間隔が長い場合に、フェロモンの過成熟によって経路が固定されてしまい、解の精度が下がってしまう問題が明らかになった。そこで、この問題を解決するために、フェロモンの過成熟を防ぐことで解の精度を上げる手法を提案し、その評価を行った。結果として、実験を行った環境においては解精度が通常のAntNetによる探索と比較して3.89倍の精度と非常に良い結果が得られることを示した In this research, we applied AntNet to shortest path problems in weighted graphs with weight changes. AntNet is a previously proposed method applying ant colony optimization. In the AntNet algorithm multiple ants repeat the following steps. First, each ant selects a path stochastically while referring to pheromone values from the source vertex to destination vertex. Next, pheromone is secreted according to the evaluation of each completed route. Through experiment it was verified that AntNet showed strong advantage over compared methods in calculation time for very large graphs. On the other hand, when the time interval between weight changes is extended, over-maturation of pheromone trails caused the search route to be fixed, leading to an increase in error. In order to overcome this problem, a new method to improve the accuracy by preventing over-maturation was proposed. It was verified by experiment that under the same conditions, the proposed method showed approximately 3.89 times search accuracy compared to normal AntNet. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|