| 講演名 | 2010-12-17 ノード配置問題に対するアント最適化法(モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般) 大倉 慶一, 片山 謙吾, 舩曵 信生, 南原 英生, 西原 典孝, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ネットワークに関連する組合せ最適化問題の一つとして,ノード配置問題(Node Placement Problem, NPP)がある.このNPPに対しては,これまでに代表的なメタ戦略である遺伝的アルゴリズムやタブサーチ,アニーリング法,反復局所探索法などが提案されている.その他,代表的なメタ戦略としてアント最適化法(Ant Colony Optimization, ACO)があるが,NPPに対する適用例は報告されていない.本論文では,k-swap局所探索法を組み込んだACOにもとづく近似解法を提案する.提案法の性能を評価するためにNPPのベンチマーク問題例に適用し,最先端の近似解法である反復局所探索法,Memeticアルゴリズムとの比較を行う. |
| 抄録(英) | We address a problem of finding an optimal node placement that minimizes the amount of traffics reducing the weighted hop distances in multihop lightwave networks. The problem is called Node Placement Problem (NPP). For the NPP, several metaheuristic algorithms have been proposed so far such as genetic algorithm, tabu search, simulated annealing, iterated local search, and memetic algorithm. However, ant colony optimization (ACO) approach, one of the most representative metaheuristics, has not been presented for the NPP yet. In this paper we present an ACO algorithm incorporating k-swap local search (KLS) based on variable depth search for the NPP. To evaluate the performance of the ACO, we tested it on the benchmark problem instance of the NPP. We showed the performance of the ACO with KLS through comparisons with those of the iterated local search and the memetic algorithm that are known to be the highly effective metaheuristics for the NPP. |
| キーワード(和) | 組合せ最適化 / ノード配置問題 / k-swap局所探索法 / アント最適化法 |
| キーワード(英) | Combinatorial Optimization / Node Placement Problem / k-swap Local Search / Ant Colony Optimization |
| 資料番号 | NS2010-134 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NS |
|---|---|
| 開催期間 | 2010/12/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Network Systems(NS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ノード配置問題に対するアント最適化法(モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般) |
| サブタイトル（和） | |
| タイトル（英） | Ant Colony Optimization for the Node Placement Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 組合せ最適化 / Combinatorial Optimization |
| キーワード(2)（和/英） | ノード配置問題 / Node Placement Problem |
| キーワード(3)（和/英） | k-swap局所探索法 / k-swap Local Search |
| キーワード(4)（和/英） | アント最適化法 / Ant Colony Optimization |
| 第 1 著者 氏名（和/英） | 大倉 慶一 / Keiichi OHKURA |
| 第 1 著者 所属（和/英） | 岡山理科大学大学院工学研究科 Graduate School of Engineering, Okayama University of Science |
| 第 2 著者 氏名（和/英） | 片山 謙吾 / Kengo KATAYAMA |
| 第 2 著者 所属（和/英） | 岡山理科大学工学部情報工学科 Department of Information and Computer Engineering, Okayama University of Science |
| 第 3 著者 氏名（和/英） | 舩曵 信生 / Nobuo FUNABIKI |
| 第 3 著者 所属（和/英） | 岡山大学大学院自然科学研究科 Graduate School of Natural Science and Technology, Okayama University |
| 第 4 著者 氏名（和/英） | 南原 英生 / Hideo MINAMIHARA |
| 第 4 著者 所属（和/英） | 岡山理科大学工学部情報工学科 Department of Information and Computer Engineering, Okayama University of Science |
| 第 5 著者 氏名（和/英） | 西原 典孝 / Noritaka NISHIHARA |
| 第 5 著者 所属（和/英） | 岡山理科大学工学部情報工学科 Department of Information and Computer Engineering, Okayama University of Science |
| 発表年月日 | 2010-12-17 |
| 資料番号 | NS2010-134 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | 339 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |