| Item type |
紀要論文(ELS) / Departmental Bulletin Paper(1) |
| 公開日 |
2011-09-30 |
| タイトル |
|
|
タイトル |
コストの変動するグラフにおける経路探索手法:AntNetの適用と改良 |
|
言語 |
ja |
| タイトル |
|
|
タイトル |
Path Search Method for Weighted Graphs with Weight Changes:Application and Improvement of AntNet |
|
言語 |
en |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題 |
経路探索, グラフ理論, ACO, AntNet, 群知能
Path Search, Graph Theory, ACO, AntNet, Swarm intelligence |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
departmental bulletin paper |
| ID登録 |
|
|
ID登録 |
10.15029/00000393 |
|
ID登録タイプ |
JaLC |
| ページ属性 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
P(論文) |
| 著者名(日) |
島影, 秀征
山口, 崇志
マッキン, ケネス ジェームス
永井, 保夫
Shimakage, Hideyuki
Yamaguchi, Takashi
Mackin, Kenneth James
Nagai, Yasuo
|
| 著者所属(日) |
|
|
|
ja |
|
|
東京情報大学大学院総合情報学研究科 |
| 著者所属(日) |
|
|
|
ja |
|
|
東京情報大学総合情報学部情報システム学科 |
| 著者所属(日) |
|
|
|
ja |
|
|
東京情報大学総合情報学部情報システム学科 |
| 著者所属(日) |
|
|
|
ja |
|
|
東京情報大学総合情報学部情報システム学科 |
| 著者所属(英) |
|
|
|
en |
|
|
Tokyo University of Information Sciences, Graduate School of Informatics |
| 著者所属(英) |
|
|
|
en |
|
|
Tokyo University of Information Sciences, Faculty of Informatics, Department of Information Systems |
| 抄録(日) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
本研究ではテーマパークやイベント会場において経路決定の支援を行うシステムを構築することを最終目標とし、その部分問題であるコストの変動する重み付きグラフにおける経路探索問題に対して、AntNetを適用した。AntNetとは蟻コロニー最適化の考えを応用して提案された経路探索手法である。AntNetのアルゴリズムは、複数の蟻が以下のステップを任意の回数まで繰り返す。まず、蟻が始点から目的頂点までフェロモンを参照しながら、確率的に経路を選択していく。次に、完成した経路の評価に応じてフェロモンを分泌する。実験の結果、AntNetはグラフの規模が大きくなるほど、探索時間の面で有効であることを示した。しかし、コストの変動間隔が長い場合に、フェロモンの過成熟によって経路が固定されてしまい、解の精度が下がってしまう問題が明らかになった。そこで、この問題を解決するために、フェロモンの過成熟を防ぐことで解の精度を上げる手法を提案し、その評価を行った。結果として、実験を行った環境においては解精度が通常のAntNetによる探索と比較して3.89倍の精度と非常に良い結果が得られることを示した。 |
|
言語 |
ja |
| 抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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. |
|
言語 |
en |
| 雑誌書誌ID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11155514 |
| 書誌情報 |
ja : 東京情報大学研究論集
巻 15,
号 1,
p. 100-117,
発行日 2011-09-30
|
| 出版者 |
|
|
出版者 |
東京情報大学 |
|
言語 |
ja |
KJ00007276439 (652.2 kB)
