| Item type |
Journal(1) |
| 公開日 |
2016-01-15 |
| タイトル |
|
|
タイトル |
巡回セールスマン問題に対する並列コンサルタント誘導型探索アルゴリズム |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Parallel Consultant-guided Search Algorithm for Traveling Salesman Problem |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
[一般論文] コンサルタント誘導型探索，PCクラスタ，並列処理，メタヒューリスティクス，組合せ最適化問題 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者所属 |
|
|
|
関西大学 |
| 著者所属 |
|
|
|
関西大学／現在，株式会社日立システムズ |
| 著者所属 |
|
|
|
関西大学 |
| 著者所属 |
|
|
|
関西大学 |
| 著者所属(英) |
|
|
|
en |
|
|
Kansai University |
| 著者所属(英) |
|
|
|
en |
|
|
Kansai University / Presently with Hitachi Systems, Ltd. |
| 著者所属(英) |
|
|
|
en |
|
|
Kansai University |
| 著者所属(英) |
|
|
|
en |
|
|
Kansai University |
| 著者名 |
榎原, 博之
中山, 弘基
飯田, 修平
長辻, 亮太
|
| 著者名(英) |
Hiroyuki, Ebara
Koki, Nakayama
Shuhei, Iida
Ryota, Nagatsuji
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
近年，メタヒューリスティクスは組合せ最適化問題を解く手法として多くの研究が行われている．最近の研究では，コンサルタント誘導型探索（CGS）と呼ばれる新しいメタヒューリスティクスが提案されている．本研究では，CGSを用いた巡回セールスマン問題（TSP）に対する並列アルゴリズムを提案する．アルゴリズムの並列化では，CGSにおける仮想人間をそれぞれの計算機の各プロ セッサコアに割り当てることで効率良く解の探索を行う．また，仮想人間の集団を複数のサブ集団に分割し，各サブ集団どうしで仮想人間の移住を行う島モデルをCGSに取り入れる．10台の計算機を用いた性能評価実験を行い，都市数が5,000のTSPLIBのベンチマーク問題例に対して5%未満の誤差率を達成することを示す． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN00116647 |
| 書誌情報 |
情報処理学会論文誌
巻 57,
号 1,
p. 331-342,
発行日 2016-01-15
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1882-7764 |
IPSJ-JNL5701037.pdf (981.1 kB)
