Approximate相互結合網を用いた巡回セールスマン問題の並列蟻コロニー最適化による解法の高速化

• Item type: SIG Technical Reports(1)
• 公開日: 2019-03-10
• タイトル: Approximate相互結合網を用いた巡回セールスマン問題の並列蟻コロニー最適化による解法の高速化
• タイトル / 言語: en
• タイトル: Accelerating solution method by parallel ant colony optimization of traveling salesman problem using Approximate interconnection network
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: アルゴリズム
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 慶應義塾大学
• 著者所属: 国立情報学研究所
• 著者所属: 国立情報学研究所
• 著者所属: 慶應義塾大学
• 著者所属(英): en
• 著者所属(英): Keio University
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): Keio University
• 著者名: 丹羽, 直也; 平澤, 将一; 鯉渕, 道紘; 天野, 英晴
• 著者名(英): Naoya, Niwa; Shoichi, Hirasawa; Michihiro, Koibuchi; Hideharu, Amano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 我々は，通信路上で一定のビット誤りを許容することで，相互結合網の広帯域化と低遅延化を両立し，その結果，データセンターやスーパーコンピュータにおいて並列計算アプリケーション高速化を達成する Approximate ネットワークを提案している．誤りを許容する相互結合網を活用した上で正しい (許容誤差範囲内の) 計算結果を得られるかどうかは，アプリケーションの性質に依存する．本報告では，ケーススタディとして，NP 困難である巡回セールスマン問題の近似解を並列蟻コロニー最適化で求める手法を用いて Approximate ネットワークの高速化を効果を評価した．その結果，解の精度にほとんど影響を与えずに，問題サイズが 100 以上の場合は 5% 前後の高速化ができることがわかった．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 研究報告システムとLSIの設計技術（SLDM）; 巻 2019-SLDM-187, 号 27, p. 1-6, 発行日 2019-03-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8639
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会