Experience the CMOS Annealing Machine

入力データ作成

概要

「定式化」を行った数分割問題について、入力データを作成します。機械的な操作ですが、本記事では基本的な事項をおさえていきます。

STEP1. 入力データは$J_{ij}$のリスト

定式化ではイジングモデルを考え、コスト関数$H$を定義しました。

$i,j$といった指数は$S$の中の$i$番目,$j$番目の要素という意味です。この例題では数字が19個あるので$i=1,2,3,…,19$となります。$j$も同様です。(ただし$i≠j$)

イジング変数$\sigma_i$(スピンとも呼ばれます)は、$i$番目の要素を$S_A$に入れたか$S_B$に入れたかを表すもので、$S_A$に入れた場合に$\sigma_i=+1$と、$S_B$に入れた場合に$\sigma_i=-1$とすることと定式化しました。

このとき、ある組合せ$\sigma_1,\sigma_2,...,\sigma_N$に対するコスト関数$H$を計算するためには、$a_ia_j$の部分が分かっている必要があります。つまり、すべての$i,j$の組み合わせに対する$a_ia_j$の計算値が、アニーリングマシンに対する入力データとなります。$a_ia_j$の部分は、$J_{ij}$とも呼ばれます。

$$ \text{数分割問題の入力データ} \\ J_{ij} = a_ia_j $$

ところで、$J_{ij}$は、どのような意味があるのでしょうか。

下図左がイジングモデル全体だとした場合、ひとつの$J_{ij}=a_ia_j$は右側の拡大図であらわされるように、イジング変数$\sigma_i$と$\sigma_j$の間に働く影響の強さを表していると考えられます。このスピンとスピンの間に働く力を相互作用といいます。

コスト関数とイジングモデルの関係のイメージ

アニーリングマシンの最適化処理とは、$\sigma_1,\sigma_2,...,\sigma_{19}$のそれぞれに$+1$か$-1$を当てはめた組合せのうち最もコストの低いものを見つけ出すことです。コストを計算するために与える情報は $J_{ij}=a_ia_j$、つまり相互作用です。アニーリングマシンが必要としている入力データとは相互作用のことなのです。

STEP 2. 数分割問題での$J_{ij}$を計算してみよう

数分割問題での相互作用$J_{ij}$を具体的に計算していきましょう。

以下のように、要素1から要素19までまんべんなく掛け合わせることで与えるべき相互作用がすべて得られます。

$$ J_{12} = a_1 \centerdot a_2 = 3 \times 1=3 \\ J_{13} = a_1 \centerdot a_3 = 3 \times 4=12 \\ J_{14} = a_1 \centerdot a_4 = 3 \times 15=45 \\ \centerdot \\ \centerdot \\ \centerdot \\ J_{1819} = a_{18} \centerdot a_{19} = 28 \times 84=2,352 $$

図では省略してありますが、相互作用の総数は $19×(19-1)/2=152$個あります。$152$個の値をアニーリングマシンに入力する必要があります。

STEP3. 要素が増えると大量のデータが必要となる

要素数の2乗に比例して計算量が増える場合、数学的な表現では$\mathcal{O}$(オーダ:計算量のこと)が$N^2$であるという言い方をします。つまり、数分割問題ではイジングモデルの相互作用のオーダは$N^2$と言えます。

上の図に示す通り、要素数が19個の場合でも、イジングモデルの相互作用の係数が$152$個も必要であることがわかりました。もし要素の数が100個であった場合には、$100(100-1)/2=4950$個にも上ります。$\mathcal{O}(N^2)$となったのはどうしてでしょう。数分割問題の定式化では、すべての要素同士がつながっているので(全結合)、その相互作用は要素$x$要素分だけ必要となるためです。

定式化を要素間の関係をシンプルに、つまり掛け合わせが出てこないようにできれば、その分だけ相互作用の数が減り、入力データも減らすことができます。ちなみに、どの要素同士も相互作用できる場合に全結合と言います。

まとめ

  • 入力データの作成とは、$J_{ij}$をすべて計算すること
  • 入力データとは相互作用を表す数値であり、要素数が増えると2乗のオーダで増える可能性がある
  • 要素間の関係がシンプルな場合には、相互作用の数はそれほど多くない場合もある

参考文献

ACWスキルロードマップ

記事を読みましたか?スキルロードマップに印を付けましょう。

この記事はACWスキルロードマップの一部です。スキルロードマップを使ってACWを学んでみてください。

SNS共有

記事が役に立ちましたか?他の人に共有してみてください。

組合せ最適化問題をアニーリングマシンで解決する具体的な事例を知りたい人は

組合せ最適化問題とは

組合せ最適化を身近な組合せ最適化問題として分かりやすい2つの例を用いて解説します。また、IoT社会における組合せ最適化処理の高速解法の重要性について述べます。

COVID-19感染対策を考慮し研究員シフトを最適化する

COVID-19の流行に伴い、感染リスクを考慮した制約条件の下、研究員のシフト作成をアニーリングマシンで行うユースケースを紹介しています。

保険会社の再保険ポートフォリオを最適化する

自然災害リスクに対応するため、保険会社が保有する膨大なデータを活用した再保険ポートフォリオ策定をアニーリングマシンで行うユースケースを紹介しています。

アニーリングマシンの使い方が知りたい人は

アニーリングマシンのための数学

アニーリングマシンが得意とする問題の特徴である「二次」「離散」を中心に、知っておくべき数学的前提を易しく解説します。