前述した1次式は他の方法で簡単に解けるのに対し、2次式の最適化問題についてはアニーリングマシンで効率的に解くことができると考えられます。第1節で説明した通り、2次式とは変数を2個かけあわせた項があるというものです。第1章で説明した画像のノイズリダクションの定式化では$s_i$と$s_j$をかけた項$s_is_j$や$h_is_i$が存在するので、2次式ですね。では、この$s_is_j$があるとアニーリングマシンによってどのような効果が得られるのでしょう。
第1章では、アニーリングによりエネルギーが最も低くなる$s_i$(スピン)の状態を探すという話をしました。この時、$a_is_i$($a_i$は係数)といういわゆる1次の項しかなかった場合、係数が正の値なら$s_i$が$-1$の方がコスト関数が低くなります。一方で係数が負の値なら$s_i$が$+1$の方がコスト関数が低くなります。つまり1次の項では係数は固定なので、$s_i$の値次第($+1$か$-1$)で最適かどうかが決まるのです。一方で、$a_{ij}s_is_j$という2次の項では、係数$a_{ij}$が正であれば、$s_is_j$が負となる場合にエネルギーが負となり(低くなり)ます。$s_is_j$が負になるのは、$s_i$が正かつ$s_j$が負の場合、もしくは$s_i$が負かつ$s_j$が正の場合の2パターンとなりますね。逆に係数$a_{ij}$が負であれば$s_is_j$が正の場合がエネルギーが負となりますので、この場合は$s_i$が正かつ$s_j$が正、もしくは$s_i$が負かつ$s_j$が負の場合に最適解となります(イジングモデルでも説明の通り)。つまり、2次の$a_{ij}s_is_j$という項がある場合、$s_i$と$s_j$のペアは相手次第によりエネルギーを低くするか高くするか、すなわち最適解になるか否かが変わるということです。これは、$s_i$の値を決める時に非常に厄介です。相手の$s_j$も$s_i$の状態が決まらなければどっちの値になるのが最適かわからないわけで、お互いにらみ合った状態と言えるでしょうか。よって、従来の手法で解こうとするとこの2次の項を総当たりでシミュレーションするようなことが必要になり難しいのです。
記事が役に立ちましたか?他の人に共有してみてください。
組合せ最適化を身近な組合せ最適化問題として分かりやすい2つの例を用いて解説します。また、IoT社会における組合せ最適化処理の高速解法の重要性について述べます。
COVID-19の流行に伴い、感染リスクを考慮した制約条件の下、研究員のシフト作成をアニーリングマシンで行うユースケースを紹介しています。
自然災害リスクに対応するため、保険会社が保有する膨大なデータを活用した再保険ポートフォリオ策定をアニーリングマシンで行うユースケースを紹介しています。
初級者向けに、アニーリングマシンで最適化問題を解く工程を、「課題整理と要件定義」「定式化」「入力データ作成」「アニーリングマシン実行」の4段階に分けて手順やポイントを解説します。