疎結合と全結合（前編）
概要
アニーリングマシンは、イジングモデルの基底状態（エネルギーが最も低い状態）が最適解になる前提条件を設定することで、基底状態が最適解を与えるという仕組みにより組合せ最適化問題を解く技術です。アニーリングマシンを使うためには、まず課題をイジングモデルとして定式化しなければなりません。
その際に、使うアニーリングマシンがどのようなイジングモデルの構造に基づいているかを把握する必要があります。あるいは、解きたい課題を解くことができるアニーリングマシンであるかどうかを見極めて、マシンを選定しなければなりません。
今回のコラムでは、前編と後編に分けて、定式化とアニーリングマシン選定の段階で考慮が必要な、モデルの構造について解説していきます。まず前編では、解きたい問題についてどうイジングモデルを適用するのか（数学的な論理）について解説し、後編ではアニーリングマシンの仕様（実装上の仕様）について解説します。
どのスピン間に相互作用があるか
アニーリングマシンを選ぶ際は、「疎結合」「全結合」を考慮しなければなりません。イジングモデルは、スピンと呼ばれる要素（頂点）が相互作用（辺）で結合されたグラフの形をしています。結合とは、イジングモデルのスピンが繋がっているかどうかのことを指しています。コスト関数の式で見れば、あるスピンと他のスピンの積が存在していれば、そのスピン間は「相互作用がある」つまり「スピン間はつながっている」といいます。
疎結合と全結合のイメージ
全結合は密結合とも呼ばれる？
疎結合イジングモデルは、各スピンが一部のスピンと結合しています。全結合イジングモデルは、各スピンがその他の全てのスピンと結合されています。ちなみに、密結合という言葉が使われることもあり、これは、あるスピンが全てのスピンではないが多くのスピンと結合されていることを表しています。ただし、どれくらいのスピンとつながると疎なのか、または、密なのかという明確な定義はありません。あえて言えば、スピンの数が増えた時に1つのスピンが結合する数が定数の場合には疎結合、スピンの数のオーダで増えていく場合を密結合と言われることもありますが、一方で10%程度のスピンとつながっている状態は疎結合と言うイメージを持たれることもあり、どの程度のことを言っているか場面によって基準を確認するのがよいでしょう。
全結合の問題の例：数分割問題およびその他
定式化では数分割問題の定式化を行い、コスト関数$H = \sum(a_ia_j\sigma_i\sigma_j)$を導きました。この式は、異なる要素同士をすべて掛け合わせなければならないことを意味しています。これが全結合であり、要素数$n$個について$n(n-1)/2$個の相互作用を入力しなければならないため$O(n^2)$で相互作用が増えるということがわかりました。この時点で、相互作用の数から、アニーリングマシンに入力できるかどうかの判断ができることにも触れました。
それ以外にも、時間割を作成する問題や金融分野での株のポートフォリオ作成問題なども全結合の問題と言えます。例えば、課題整理と要件定義で取り上げた時間割作成問題では、それぞれの授業のコマで他のコマとの関係を考えながらどの教科のどの先生が入るかという関係を考慮しています。また、ポートフォリオ作成の問題でも、すべての株の銘柄間に相互の関係が入るため全結合の問題です。
疎結合の問題の例：信号制御問題およびその他
イジングモデルの一部のスピン間にしか相互作用のないことを疎結合といいます。では、具体的には疎結合の問題にはどのようなものがあるでしょうか。
信号制御最適化では、格子状の道路に配置された信号が赤なのか、青なのか、の2値をスピンに充てています。（正確な定義としては、垂直方向の信号を青とする場合を$+1$、水平方向の信号を青とする場合を$-1$としています。）
その交差点同士が実際に縦と横にのみ道路で繋げられているのですから、一つのスピンは隣の交差点を表す限られたスピンとしかつながっていないため、疎結合で関係が表現できます。たとえ格子状の道路が無限に広がっていても、交差点が1つ増えるごとに隣接する道路は2本増えるとわかっているので、必要な相互作用の数は1つの交差点を$n$としても$2n$より多くなりません。縦10×横10=100交差点であっても相互作用は200以下です。数分割問題では100個の数を分割するのに4,950個の相互作用が必要になるので、イジングモデルの構造の違いがいかに大きいかがわかるでしょう。
さて、コスト関数上ではあるスピンがつながっているのに、アニーリングマシンの実装に採用されているイジングモデル上はそれに対応しているスピン同士がつながっていない（疎結合である）場合は、そのままでは解くことが出来ません。ある課題を最適化する必要が訪れた時に、イジングモデルのネットワーク構造を判断する手がかりについて次の段落でお話しします。
イジングモデルの構造は概念的な事象／物理的な事象いずれかに基く
数分割問題が関係式の全体を2乗することによってすべての項どうしの積が出現し、つまりすべてのスピン間に相互作用がある全結合のイジングモデルが成り立ったという事実から、全結合のイジングモデルは変数という概念的な要素間の結合に見られるということが言えます。このようなケースでは、イジングモデルの構造が全結合であると確定する判断のタイミングは定式化の途中にあると言えます。具体的には、数分割問題の場合は「関係式を立てた後、イジングモデルのエネルギー関数にする時」であることがわかります。
一方、信号制御問題の場合は、道路の形状が問題として与えられた時点で疎結合のイジングモデルを採用することが決まるという事実から、疎結合のイジングモデルは格子状の道路といった物理的な事象の結合に基づくということが言えます。つまり、格子状道路の信号制御を最適化したいという課題が与えられた時点で、疎結合のイジングモデルと相性がいいことがわかります。
イジングモデルの構造を考慮し、選択しよう
問題によって、イジングモデルの構造に違いがあることがわかって頂けたでしょうか。イジングモデルにさえできれば最適解を得るまでの時間を劇的に短縮できるアニーリングマシンですが、問題によって選択されるイジングモデルの形に違いがあることは、最大限に考慮すべき項目の一つです。
今後、新たな課題を組合せ最適化問題としてアニーリングマシンを用いる時、どのような構造のイジングモデルが選択されるかを意識してみてください。その観点を持つことが、アニーリングマシンを使うという試みの最初の一歩といえるでしょう。
まとめ
- イジングモデルの全結合とは、すべてのスピンが自分以外の他の全てのスピンとつながっていることを表す。
- イジングモデルの疎結合とは、スピンが特定のスピンとしかつながっていないことを表す。
- 全結合イジングモデルは概念的な事象の結合を表し、疎結合イジングモデルは物理的な事象の結合を表すと言える。
関連リンク
- 易しく学ぶ最適化フロー「課題整理と要件定義」
- 易しく学ぶ最適化フロー「定式化」
- 渋滞解消のための信号制御最適化
