確率ビットを用いたシミュレーテッドアニーリングの最大カット問題における挙動の観測

カテゴリ：研究会(論文単位)

論文No：ST25068

グループ名：【C】電子・情報・システム部門 システム研究会

発行日：2025/11/25

タイトル(英語)：Observation of Behavior of Simulated Annealing Using Probabilistic Bits for Maximum Cut Problem

著者名：清水 達也(八戸工業大学),鬼沢 直哉(東北大学),越田 俊介(八戸工業大学)

著者名(英語)： Tatsuya Shimizu(Hachinohe Institute of Technology),Naoya Onizawa(Tohoku University),Shunsuke Koshita(Hachinohe Institute of Technology)

キーワード：確率ビット,ｐＳＡ,ＳＳＡ,ハミルトニアン,最大カット問題,probabilistic bit,pSA,SSA,Hamiltonian,maximum cut problem

要約(日本語)：本稿では，確率ビットを用いたシミュレーテッドアニーリングとして提案されているpSAアルゴリズムおよびSSAアルゴリズムを対象として，最大カット問題におけるそれぞれのアルゴリズムの挙動を解析することを目的とする。本稿では非常に簡単な例を扱い，4ノードの最大カット問題に限定して，pSAおよびSSAの挙動を計算機実験によって観測する。実験の結果として，pSAではイジングモデルのエネルギーが発散し，SSAでは収束して最適解が得られることを示す。

要約(英語)：This paper aims to analyze the behavior of the pSA and the SSA algorithms, which are variants of simulated annealing using probabilistic bits, for the maximum cut problem. This paper handles a very simple example, limiting the analysis to the maximum cut problem on a 4-node graph. We observe the behavior of the pSA and the SSA through computational experiments. The experimental results show that the energy of the Ising model diverges in pSA, while SSA converges and obtains the optimal solution.

本誌：2025年11月28日システム研究会

本誌掲載ページ：17-22p

原稿種別：日本語

PDFファイルサイズ：1,642Kバイト