イジング計算機で組合せ最適化問題の「真の最適解」を高精度に探索

局所最適解から効率よく脱出する技術を開発

2022年5月30日
早稲田大学
科学技術振興機構(JST)

 本発表の詳細は、早稲田大学のホームページ (リンク ») をご覧ください。
(リンク »)

発表のポイント
現状のイジング計算機は、真の最適解を探索する途中に局所最適解から抜け出せないという問題があった。
本研究では、二つあるいはそれ以上のスピンを結合して一つのスピンとして扱う手法を開発することで、局所最適解から脱出し真の最適解を得やすくする仕組みを構築し、この仕組みをイジング計算機に組み込むためのアルゴリズムを開発した。
本技術をさまざまなイジング計算機に適用することで、高精度に現実世界の組合せ最適化問題を解くことができ、同時に将来のイジング計算機アーキテクチャの発展にも大きく寄与する。

イジング計算機 ※1 は、真の最適解を探索する途中に局所最適解※2から抜け出せないという問題がありました。これを解消するため、早稲田大学理工学術院 (リンク ») の白井達彦（しらい たつひこ）氏 (リンク ») 、同大学理工学術院教授の戸川望（とがわ のぞむ）氏 (リンク ») らの研究グループは、二つあるいはそれ以上のスピン（イジング計算機の計算の単位、各スピンは＋１あるいは−１の値をもつ）を結合して一つのスピンとして扱うこと（図１）で、局所最適解から抜け出し真の最適解を得やすくする仕組みを開発しました。さらに、本研究グループは、この仕組みをイジング計算機に適用するためのアルゴリズムを開発し、計算機シミュレータおよび既存イジング計算機でその有効性を確認しました。

【画像： (リンク ») 】

本研究成果は、米国のIEEE Computer Societyが発行する『IEEE Transactions on Computers (リンク ») 』online版（Early Access）に2022年5月27日（金）付（現地時間）で掲載されました。
　　　　　　　　　　　　　　　　　　　　　　　　　　　
論文名：Multi-spin-flip engineering in an Ising machine (リンク »)

※1　イジング計算機
●組合せ最適化問題を「イジングモデル」で表現し、組合せ最適化問題を解決する計算機の総称。イジングモデルはもともと磁性を説明するモデルとして統計力学の分野で導入された。

※2　局所最適解
●イジング計算機が探索可能である解のうち、その周囲の解と比較して、局所的に目的関数の値が小さい（または大きい）解。局所最適解は解空間の中にいくつも存在し、その中で目的関数の値を最小（または最大）とする解が真の最適解となる。