疎結合と全結合（前編）

概要

アニーリングマシンは、イジングモデルの基底状態（エネルギーが最も低い状態）が最適解になる前提条件を設定することで、基底状態が最適解を与えるという仕組みにより組合せ最適化問題を解く技術です。アニーリングマシンを使うためには、まず課題をイジングモデルとして定式化しなければなりません。

その際に、使うアニーリングマシンがどのようなイジングモデルの構造に基づいているかを把握する必要があります。あるいは、解きたい課題を解くことができるアニーリングマシンであるかどうかを見極めて、マシンを選定しなければなりません。

今回のコラムでは、前編と後編に分けて、定式化とアニーリングマシン選定の段階で考慮が必要な、モデルの構造について解説していきます。まず前編では、解きたい問題についてどうイジングモデルを適用するのか（数学的な論理）について解説し、後編ではアニーリングマシンの仕様（実装上の仕様）について解説します。

どのスピン間に相互作用があるか

アニーリングマシンを選ぶ際は、「疎結合」「全結合」を考慮しなければなりません。イジングモデルは、スピンと呼ばれる要素（頂点）が相互作用（辺）で結合されたグラフの形をしています。結合とは、イジングモデルのスピンが繋がっているかどうかのことを指しています。コスト関数の式で見れば、あるスピンと他のスピンの積が存在していれば、そのスピン間は「相互作用がある」つまり「スピン間はつながっている」といいます。

疎結合と全結合のイメージ

全結合の問題の例：数分割問題およびその他

定式化では数分割問題の定式化を行い、コスト関数$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乗することによってすべての項どうしの積が出現し、つまりすべてのスピン間に相互作用がある全結合のイジングモデルが成り立ったという事実から、全結合のイジングモデルは変数という概念的な要素間の結合に見られるということが言えます。このようなケースでは、イジングモデルの構造が全結合であると確定する判断のタイミングは定式化の途中にあると言えます。具体的には、数分割問題の場合は「関係式を立てた後、イジングモデルのエネルギー関数にする時」であることがわかります。

一方、信号制御問題の場合は、道路の形状が問題として与えられた時点で疎結合のイジングモデルを採用することが決まるという事実から、疎結合のイジングモデルは格子状の道路といった物理的な事象の結合に基づくということが言えます。つまり、格子状道路の信号制御を最適化したいという課題が与えられた時点で、疎結合のイジングモデルと相性がいいことがわかります。

イジングモデルの構造を考慮し、選択しよう

問題によって、イジングモデルの構造に違いがあることがわかって頂けたでしょうか。イジングモデルにさえできれば最適解を得るまでの時間を劇的に短縮できるアニーリングマシンですが、問題によって選択されるイジングモデルの形に違いがあることは、最大限に考慮すべき項目の一つです。

今後、新たな課題を組合せ最適化問題としてアニーリングマシンを用いる時、どのような構造のイジングモデルが選択されるかを意識してみてください。その観点を持つことが、アニーリングマシンを使うという試みの最初の一歩といえるでしょう。

まとめ

• イジングモデルの全結合とは、すべてのスピンが自分以外の他の全てのスピンとつながっていることを表す。
• イジングモデルの疎結合とは、スピンが特定のスピンとしかつながっていないことを表す。
• 全結合イジングモデルは概念的な事象の結合を表し、疎結合イジングモデルは物理的な事象の結合を表すと言える。

関連リンク

• 易しく学ぶ最適化フロー「課題整理と要件定義」
• 易しく学ぶ最適化フロー「定式化」
• 渋滞解消のための信号制御最適化

SNS共有

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

関連記事

組合せ最適化問題とは

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

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

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

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

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

易しく学ぶ最適化フロー

初級者向けに、アニーリングマシンで最適化問題を解く工程を、「課題整理と要件定義」「定式化」「入力データ作成」「アニーリングマシン実行」の４段階に分けて手順やポイントを解説します。

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

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