[3L4-GS-1] 基礎・理論：

[3L4-GS-1-04] 温度並列シミュレーテッドアニーリング による大域的な解探索

〇川瀬 英治¹、玉井 秀明¹ (1. 沖電気工業株式会社)

キーワード：シミュレーテッドアニーリング、イジングモデル、組合せ最適化問題

シミュレーテッドアニーリング（Simulated Annealing、以下SA）は、様々な組合せ最適化問題に適用可能なメタヒューリスティックアルゴリズムの一つである。SAは任意の初期状態から探索を開始し、状態を少しずつ変化させる。変化後の状態が現在の状態よりも良い場合、それを採用し、悪い場合は確率的に変化後の状態を受理する。これを一定時間繰り返して計算し、最終的な状態を確定させる。SAは、探索結果がパラメータ（特に温度）に大きく依存するため、問題設定ごとにパラメータの試行錯誤による調整が必要となる。そのようなSAの課題に対する様々な改良手法が提案されている。その一例として、温度並列シミュレーテッドアニーリング（Temperature Parallel Simulated Annealing，以下TPSA）と呼ばれる手法が挙げられる。TPSAは、異なる温度でのプロセスに異なる初期状態を与え同時並列にアニーリングを行い、特定の交換周期で解の交換を確率的に行う手法である。本稿では、TPSAに与える初期条件などによる評価実験を行った結果を報告する。