WEKO3
アイテム
巡回セールスマン問題に対する並列コンサルタント誘導型探索アルゴリズム
http://hdl.handle.net/10112/10153
http://hdl.handle.net/10112/1015331b28e1d-0dd2-4305-bd17-b681053b0e0c
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
KU－1100-20160100-01.pdf (981.1 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2016-06-01 | |||||
| タイトル | ||||||
| タイトル | 巡回セールスマン問題に対する並列コンサルタント誘導型探索アルゴリズム | |||||
| 言語 | ||||||
| 言語 | jpn | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | journal article | |||||
| その他のタイトル | ||||||
| その他のタイトル | Parallel Consultant-Guided Search Algorithm for Traveling Salesman Problem | |||||
| 著者 |
榎原, 博之
× 榎原, 博之× 中山, 弘基× 飯田, 修平× 長辻, 亮太 |
|||||
| 著者別名 | ||||||
| 識別子Scheme | WEKO | |||||
| 識別子 | 24370 | |||||
| 姓名 | Ebara, Hiroyuki | |||||
| 著者別名 | ||||||
| 識別子Scheme | WEKO | |||||
| 識別子 | 24371 | |||||
| 姓名 | Nakayama, Koki | |||||
| 著者別名 | ||||||
| 識別子Scheme | WEKO | |||||
| 識別子 | 24372 | |||||
| 姓名 | Iida, Shuhei | |||||
| 著者別名 | ||||||
| 識別子Scheme | WEKO | |||||
| 識別子 | 24373 | |||||
| 姓名 | Nagatsuji, Ryota | |||||
| 概要 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 近年，メタヒューリスティクスは組合せ最適化問題を解く手法として多くの研究が行われている．最近の研究では，コンサルタント誘導型探索（CGS）と呼ばれる新しいメタヒューリスティクスが提案されている．本研究では，CGS を用いた巡回セールスマン問題（TSP）に対する並列アルゴリズムを提案する．アルゴリズムの並列化では，CGS における仮想人間をそれぞれの計算機の各プロセッサコアに割当てることで効率良く解の探索を行う．また，仮想人間の集団を複数のサブ集団に分割し，各サブ集団同士で仮想人間の移住を行う島モデルをCGS に取り入れる．10 台の計算機を用いた性能評価実験を行い，都市数が5000 のTSPLIB のベンチマーク問題例に対して5%未満の誤差率を達成することを示す．Metaheuristic algorithms have been studied as a method for solving combinatorial optimization problems. Recently, the Consultant-Guided Search (CGS) for solving the Traveling Salesman Problem(TSP) has been proposed. In this paper, we propose a parallel method which assigns virtual consultants and virtual clients of the CGS to processes of computers, and calculates an approximation solution effectively for the TSP. In addition, we introduce the island model to increase the diversity of the solution. We execute computer experiments with the benchmark instances (TSPLIB) by 10 quad-core computers. Our algorithm provides a solution with less than 5% error rate for problem instances of 5,000 cities. | |||||
| 書誌情報 |
情報処理学会論文誌 巻 57, 号 1, p. 331-342, 発行日 2016-01 |
|||||
| ISSN | ||||||
| 収録物識別子タイプ | ISSN | |||||
| 収録物識別子 | 03875806 | |||||
| 書誌レコードID | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AA11464803 | |||||
| 権利 | ||||||
| 権利情報 | 一般社団法人 情報処理学会（利用は著作権の範囲内に限られる。） | |||||
| 著者版フラグ | ||||||
| 出版タイプ | VoR | |||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
| 出版者 | ||||||
| 出版者 | 一般社団法人 情報処理学会 | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | コンサルタント誘導型探索 | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | PC クラスタ | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | 並列処理 | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | メタヒューリスティクス | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | 組合せ最適化問題 | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | consultant-guided search | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | PC cluster | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | parallel processing | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | metaheuristics | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | combinatorial potimization problem | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | 関西大学（Kansai University） | |||||
| 出版者（他言語） | ||||||
| 値 | IPSJ Journal | |||||
