| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2010-09-29 10:00 文脈依存コスト下の最廉パスに対する蟻コロニー最適化の実行時間解析 ○村田 淳・武井由智（長岡技科大）  COMP2010-24 |
|
| 抄録 | （和） | 蟻コロニー最適化（Ant Colony Optimization : ACO）は1990年代初頭にDorigoらによって提案され，計算困難な組み合わせ最適化問題に対するヒューリスティックアルゴリズムとしてその有効性が示されてきた．その一方で，ACOの本質を理解するためには，既に効率的なアルゴリズムが知られている問題の上でACOアルゴリズムを解析することも重要である．有向非巡回グラフ上の単一終点最短経路問題（Single Destination Shortest Path : SDSP）に対するACOアルゴリズムの実行時間上界は，Attiratanasunthron と Fakcharoenphol によって初めて提示され，後にその上界は Horoba と Sudholt により反復回数にして$O(n^{3}+(n\log n)/\rho)$と改善された．ここで$n$はグラフの頂点数，$\rho$はフェロモン蒸発率と呼ばれるパラメータである．最短経路問題では，辺の通過コストは距離と呼ばれる辺固有の定数である．しかしながら，その拡張問題の中には辺の通過コストをその辺に至るまでの文脈に依存するようにしているものも存在する． 本論文では，辺の通過コストを以前に通過した辺に応じて重み付けする一般化したSDSPに対し，Horoba と Sudholt のACOアルゴリズムを適用することを考える．そして，もし重みの文脈への依存が乗法的であり，終点へのコストが最廉であるどのパスも有限長ならば，その実行時間は，アルゴリズムの主要な変更なしに問題の一般化の前後で本質的に同じであることを示す． |
| （英） | Since Ant Colony Optimization (ACO) was introduced by Dorigo and his colleagues in the early 1990s, it has been worked as a scheme for finding (heuristic) algorithms for a number of hard combinatorial optimization problems. On the other hand, even to a problem which has a known efficient algorithm, it is important to analyze the application of ACO algorithm for understanding intrinsic nature of ACO. For the single destination shortest path problem (SDSP), Attiratanasunthron and Fakcharoenphol presented the first ACO algorithm with an explicit run-time upper bound, for directed acyclic graphs. For the problem, Horoba and Sudholt showed an improved upper bound $O(n^{3}+(n\log n)/\rho)$ iterations, where $n$ is the number of vertices in the graph, $\rho$ is a parameter called as the pheromone evapolation rate. In the shortest path problem, the cost of passing an edge is constant for that edge, usually called as distance. However, in some application, it is required that the cost of passing an edge depends on the context that the edge is used as a part of the path. In this paper, we consider the application of ACO algorithm of Horoba and Sudholt to a generalized SDSP in which the cost of an ant traversing an edge is weighted in a certain manner depending on the path that the ant used to approach the edge. We show that, without major change of the algorithm, the run-time for the generalized case is essentially the same as that of the original shortest path problem if the dependence of the weight on the context satisfies a certain multiplicative functional equation and any cheapest path with respect to the cost is of finite length. |
|
| キーワード | （和） | 蟻コロニー最適化 / メタヒューリスティクス / 実行時間 / 最短経路問題 / / / / |
| （英） | ant colony optimization / metaheuristics / run-time / shortest path problem / / / / | |
| 文献情報 | 信学技報, vol. 110, no. 214, COMP2010-24, pp. 1-8, 2010年9月. | |
| 資料番号 | COMP2010-24 | |
| 発行日 | 2010-09-22 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2010-24 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2010-09-29 - 2010-09-29 |
| 開催地（和） | 長岡技術科学大学 |
| 開催地（英） | Nagaoka Univ. of Tech. |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2010-09-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 文脈依存コスト下の最廉パスに対する蟻コロニー最適化の実行時間解析 |
| サブタイトル（和） | |
| タイトル（英） | Run-time Analysis of Ant Colony Optimization over the Cheapest Path with a Context-dependent Cost |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 蟻コロニー最適化 / ant colony optimization |
| キーワード(2)（和/英） | メタヒューリスティクス / metaheuristics |
| キーワード(3)（和/英） | 実行時間 / run-time |
| キーワード(4)（和/英） | 最短経路問題 / shortest path problem |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 村田 淳 / Atsushi Murata / ムラタ アツシ |
| 第1著者 所属（和/英） | 長岡技術科学大学 (略称： 長岡技科大) Nagaoka University of Technology (略称： Nagaoka Univ. of Tech.) |
| 第2著者 氏名（和/英/ヨミ） | 武井 由智 / Yoshinori Takei / |
| 第2著者 所属（和/英） | 長岡技術科学大学 (略称： 長岡技科大) Nagaoka University of Technology (略称： Nagaoka Univ. of Tech.) |
| 講演者 | 第1著者 |
| 発表日時 | 2010-09-29 10:00:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2010-24 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | no.214 |
| ページ範囲 | pp.1-8 |
| ページ数 | 8 |
| 発行日 | 2010-09-22 (COMP) |
[研究会発表申込システムのトップページに戻る]