定式化
概要
組合せ最適化問題をアニーリングマシンで解くためには、イジングモデルの定式化と呼ばれる作業が必要です。本記事ではその手順を解説します。
ここでは考えやすいシンプルなイジングモデルとして、数分割問題をテーマにします。そのため、ここでも問題の確認と要件定義を行いましょう。
テーマ：「数分割問題」とは
数分割問題とは、いくつかの数が与えられたときに、それらを2つのグループ$A, B$に分ける問題です。ただし、2つのグループそれぞれに含まれる数の和がなるべく同じになるようにすることが求められます。
現実世界では、例えば「2つのトラックに荷物をどう分けるか？」を考える際に活用することができます。その際、数の和がなるべく同じになるようにするというルールは「2台のトラックに積む荷物の重さを同じにする」「トラックに荷物を積む作業時間を同じにする」といった考慮に応用できます。
STEP1. 要件定義
ここでは単純な数分割問題として、以下の集合$S$が与えられたという前提で、イジングモデルの定式化を検討しましょう。まずは問題の要件定義を行います。
要件
- 整数の集合$S$を$A, B$の2グループに分ける際、2つのグループの整数の合計がなるべく等しくなる組み合わせを求める
グループ$A$に入った数の和を$S_A$、グループ$B$に入った数の和を$S_B$とすると、$S_A=S_B$となる組合せを求めます。
STEP 2. 定式化
$S_A=S_B$となる組合せを求めるということがコスト関数として表現されるように、イジングモデルを組み立てていきます。
$S_A=S_B$を満たすコスト関数を立てるために $S_A-S_B=0$を書き表していきます。
まず、それぞれの整数に番号をつけます。$i,j$といった指数は$S$の中の$i$番目$,j$番目の要素という意味です。この例題では数字が19個あるので$i=1,2,3,…,19$となります。$j$も同様です。
イジングモデルでは、要素の状態をスピンと呼び、$+1$あるいは$-1$のどちらかの値をとります。
数分割問題では、整数が$A$グループに入る場合を$+1$、$B$グループに入る場合を$-1$と定義します。
スピンを表す変数を$\sigma_i$と表すことにします。$\sigma_i$のことをイジング変数と呼びます。
先ほど定義した$i$番目の数字$a_i$が、$A$・$B$いずれかのグループに入ることを、$a_i\sigma_i$と表現することにしましょう。$a_i\sigma_i$の値は、$A$グループに入る場合は$+a_i$、$B$グループに入る場合には$-a_i$となります。すべての数を$A$か$B$のグループに分けた場合、プラスの項が$A$のグループに属する整数、マイナスの項が$B$のグループに属する整数を意味するので、$a_i\sigma_i$をすべて足したものが$S_A-S_B$を表します。
$$ \sum a_i \sigma_i = S_A - S_B \to 0 $$
$S_A-S_B$すなわち$a_i\sigma_i$を$i=1$から$i=N$まで足した和が$0$になるような $\sigma_1,\sigma_2,...,\sigma_N$を見つけたらそれが最適解です。
STEP3. コスト関数をもうひと捻り
しかし、アニーリングマシンで解くためのイジングモデルとしてはもう一工夫必要です。
アニーリングマシンはいくつかの組み合わせを作ってみてコストを計算し、最もコストが小さいものを解として出力します。最も小さいということを表現するには、2乗するのがセオリーです。数分割問題では$S_A-S_B$を2乗すれば、$(S_A-S_B)^2$が$0$に近づくほど最適解に近くなり、$0$となった時が最適解となります。
つまり$(S_A-S_B)^2=(\sum a_N\sigma_N)^2$を最小化する問題として、数分割問題はイジングモデルに定式化できます。
式を立てたものの、数学的にどう評価するか、あまり慣れていない場合は書き下してみてみましょう。
2乗の式の展開がよくわからないという人は、二乗の展開公式を検索して調べてみてください。最下部参照リンクも参照ください。
$$ \begin{align*} (S_A-S_B)^2 &=(\sum a_i\sigma_i)^2 \quad \scriptsize \text{\# 仮にiが1～3（数字3個からなる集合）の場合} \\ &=(a_1\sigma_1 + a_2\sigma_2 + a_3\sigma_3)^2 \\ &={a_1\sigma_1}^2 + {a_2\sigma_2}^2 + {a_3\sigma_3}^2 + 2a_1a_2\sigma_1\sigma_2 + 2a_1a_3\sigma_1\sigma_3 + 2a_2a_3\sigma_2\sigma_3 \\ &={a_1}^2 + {a_2}^2 +{a_3}^2 + 2a_1a_2\sigma_1\sigma_2 + 2a_1a_3\sigma_1\sigma_3 + 2a_2a_3\sigma_2\sigma_3 \quad \scriptsize \text{\# σ \textasciicircum2=1なので消える} \end{align*} $$
さてこの式では$a$は定数なのでエネルギーを高くすることも低くすることもできません。
つまりイジングモデル化してエネルギーを観測するのはイジング変数$\sigma$が残されたままの項のみで差し支えありません。これら項だけを、$\sum$の式で置き換えると次のように表されます。
（$\sum$にわざわざ直すのは、短く表現できるためです。プログラムを使う際に便利です。）
さらに2はあってもなくても最適解を得る上では影響がないため、取ってしまっても同じことです。
以上で、今回の数分割問題を求めるためのイジングモデルのコスト関数の定式化が完成しました。
$$ H = \sum(a_ia_j\sigma_i\sigma_j) $$
まとめ
- イジングモデルでは、要素の状態をスピンと呼び、$+1$あるいは$-1$のどちらかの値をとる
- 問題をスピンを使って表現する
- アニーリングマシンで解けるよう、2乗の式でコスト関数を表現する
