| 講演名 | 2019-05-15 レプリカ交換イジングモデルソルバにおけるレプリカトポロジーと温度割当方法に関する検討 党 璋(京大), 佐藤 高史(京大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 組合せ最適化問題の近似解を効率的に求める手法として，イジングモデルを用いる解法が近年注目を集めている．特に，レプリカ交換法を応用したイジングモデルソルバは，高精度の解を高速に得られることが知られている．本稿では，最適解をより高い確率で求めることができるレプリカトポロジーとレプリカ温度を，最大カット問題を例に評価する．直線型トポロジー及び提案レプリカ温度割当方法によって，既存のレプリカ温度割当方法と比較して最適解を得る確率を最大で9.6￥,￥%向上できることを確認した． |
| 抄録(英) | Ising-model based solver {￥sato{is gaining increasing}} attention {￥sato{for its efficiency in}} finding approximate solutions forIsing-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￥,￥%. |
| キーワード(和) | 組合せ最適化問題 / 最大カット問題 / イジングモデル / アニーリング / レプリカ交換法 |
| キーワード(英) | Combinatinal optimization problem / max-cut problem / ising model / annealing / parallel tempering |
| 資料番号 | VLD2019-1 |
| 発行日 | 2019-05-08 (VLD) |
| 研究会情報 | |
| 研究会 | VLD / IPSJ-SLDM |
|---|---|
| 開催期間 | 2019/5/15(から1日開催) |
| 開催地（和） | 東京工業大学 大岡山キャンパス |
| 開催地（英） | Ookayama Campus, Tokyo Institute of Technology |
| テーマ（和） | システム設計および一般 |
| テーマ（英） | System Design, etc. |
| 委員長氏名（和） | 峯岸 孝行(三菱電機) / 田宮 豊(富士通研) |
| 委員長氏名（英） | Noriyuki Minegishi(Mitsubishi Electric) / Yutaka Tamiya(Fujitsu Lab.) |
| 副委員長氏名（和） | 戸川 望(早大) |
| 副委員長氏名（英） | Nozomu Togawa(Waseda Univ.) |
| 幹事氏名（和） | 新田 高庸(NTT) / 小平 行秀(会津大) / 柴田 誠也(NEC) / 密山 幸男(高知工科大) / 細谷 英一(NTT) |
| 幹事氏名（英） | Koyo Nitta(NTT) / Yukihide Kohira(Univ. of Aizu) / Seiya Shibata(NEC) / Yukio Mitsuyama(Kochi Univ. of Tech.) / Eiichi Hosoya(NTT) |
| 幹事補佐氏名（和） | / 岩崎 裕江(NTT) |
| 幹事補佐氏名（英） | / Hiroe Iwasaki(NTT) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on VLSI Design Technologies / Special Interest Group on System and LSI Design Methodology |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | レプリカ交換イジングモデルソルバにおけるレプリカトポロジーと温度割当方法に関する検討 |
| サブタイトル（和） | |
| タイトル（英） | A study on replica topology and temperature assignment for Ising-Model based Solver via Parallel Tempering |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 組合せ最適化問題 / Combinatinal optimization problem |
| キーワード(2)（和/英） | 最大カット問題 / max-cut problem |
| キーワード(3)（和/英） | イジングモデル / ising model |
| キーワード(4)（和/英） | アニーリング / annealing |
| キーワード(5)（和/英） | レプリカ交換法 / parallel tempering |
| 第 1 著者 氏名（和/英） | 党 璋 / Akira Dan |
| 第 1 著者 所属（和/英） | 京都大学(略称：京大) Kyoto University(略称：Kyoto Univ.) |
| 第 2 著者 氏名（和/英） | 佐藤 高史 / Takashi Sato |
| 第 2 著者 所属（和/英） | 京都大学(略称：京大) Kyoto University(略称：Kyoto Univ.) |
| 発表年月日 | 2019-05-15 |
| 資料番号 | VLD2019-1 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | VLD-25 |
| ページ範囲 | pp.7-12(VLD), |
| ページ数 | 6 |
| 発行日 | 2019-05-08 (VLD) |