平均場アニーリングに基づく高性能な全並列型アニーリングアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2024-03-21
• タイトル: 平均場アニーリングに基づく高性能な全並列型アニーリングアルゴリズム
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京工業大学
• 著者所属: 東京工業大学
• 著者所属: 東京工業大学
• 著者所属: 東京工業大学
• 著者所属: 東京工業大学
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者名: 黒木, 響; 神保, 聡; Thiem, Van Chu; 本村, 真人; 川村, 一志
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年，量子アニーリングを契機として，様々な組合せ最適化問題をスピングラス理論に基づくイジングモデルにマッピングして解くアニーリング手法の研究が活発に行われている．特に，古典熱力学に根ざしたシミュレーテッドアニーリングの拡張として，あるいは量子論に着想を得たアルゴリズムとして，全変数を同時に更新できる並列型アニーリングアルゴリズム（PAA: Parallel Annealing Algorithm）は，並列計算機を用いて高速に最適化できる手法として注目されている．本稿では，アナログ変数を決定論的に更新するというユニークな特徴を持つ平均場アニーリングに基づく新しい PAA を提案し，提案 PAA は従来 PAA に比べて高いロバスト性と高速性を兼ね備えていることを示す．典型的な 3 種類の組合せ最適化問題（最大カット問題，最大独立集合問題，巡回セールスマン問題）を用いて実験を行い，提案 PAA の高い性能を実証する．近年量子論に基づくアルゴリズムが発展しており，古典熱力学に基づくアルゴリズムよりも優れるものとして成果が報告されている．しかし，提案 PAA は古典的熱力学に基づいているにも関わらず最先端 PAA と同等以上の性能を誇り，この結果は，実際の物理現象が利用されない限りは量子論に基づくアルゴリズムが古典的な熱力学に基づくアルゴリズムよりも優れる訳ではないことを示唆する．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12894105
• 書誌情報: 研究報告量子ソフトウェア（QS）; 巻 2024-QS-11, 号 7, p. 1-10, 発行日 2024-03-21
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2435-6492
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会