講演抄録/キーワード |
講演名 |
2019-05-15 13:55
レプリカ交換イジングモデルソルバにおけるレプリカトポロジーと温度割当方法に関する検討 ○党 璋・佐藤高史(京大) VLD2019-1 |
抄録 |
(和) |
組合せ最適化問題の近似解を効率的に求める手法として,イジングモデルを用い
る解法が近年注目を集めている.特に,レプリカ交換法を応用したイジングモデ
ルソルバは,高精度の解を高速に得られることが知られている.本稿では,最適
解をより高い確率で求めることができるレプリカトポロジーとレプリカ温度を,
最大カット問題を例に評価する.直線型トポロジー及び提案レプリカ温度割当方
法によって,既存のレプリカ温度割当方法と比較して最適解を得る確率を最大で
9.6¥,¥%向上できることを確認した. |
(英) |
Ising-model based solver {¥sato{is gaining increasing}} attention
{¥sato{for its efficiency in}} finding approximate solutions for
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¥,¥%. |
キーワード |
(和) |
組合せ最適化問題 / 最大カット問題 / イジングモデル / アニーリング / レプリカ交換法 / / / |
(英) |
Combinatinal optimization problem / max-cut problem / ising model / annealing / parallel tempering / / / |
文献情報 |
信学技報, vol. 119, no. 25, VLD2019-1, pp. 7-12, 2019年5月. |
資料番号 |
VLD2019-1 |
発行日 |
2019-05-08 (VLD) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
VLD2019-1 |