レプリカ交換イジングモデルソルバにおけるレプリカトポロジーと温度割当方法に関する検討

• Item type: SIG Technical Reports(1)
• 公開日: 2019-05-08
• タイトル: レプリカ交換イジングモデルソルバにおけるレプリカトポロジーと温度割当方法に関する検討
• タイトル / 言語: en
• タイトル: A study on replica topology and temperature assignment for Ising-Model based Solver via Parallel Tempering
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学大学院情報学研究
• 著者所属: 京都大学大学院情報学研究
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者名: 党, 璋; 佐藤, 高史
• 著者名(英): Akira, Dan; Takashi, Sato
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 組合せ最適化問題の近似解を効率的に求める手法として，イジングモデルを用いる解法が近年注目を集めている．特に，レプリカ交換法を応用したイジングモデルソルバは，高精度の解を高速に得られることが知られている．本稿では，最適解をより高い確率で求めることができるレプリカトポロジーとレプリカ温度を，最大カット問題を例に評価する．直線型トポロジー及び提案レプリカ温度割当方法によって，既存のレプリカ温度割当方法と比較して最適解を得る確率を最大で 9.6％ 向上できることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Ising-model based solver is gaining increasing attention for its efficiency in finding approximate solutions for combinatorial optimization problems. In particular, it is known that Ising-model based solver via parallel tempering can obtain the optimal solutions with high probability in a short time. In this paper, we evaluate how the replica topology and the replica temperatures affect the probability of obtaining the optimal solution. Through the experiments on the maximum cut problems, we found that the linear topology gives the best result. With the proposed temperature allocation strategy, the probability of finding the optimal solution has been improved up to 9.6%.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 研究報告システムとLSIの設計技術（SLDM）; 巻 2019-SLDM-188, 号 2, p. 1-6, 発行日 2019-05-08
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8639
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会