ネットワーク堅牢性構築

このチュートリアルは、デモアプリ「ネットワーク堅牢性構築」でアニーリングマシンが行っている処理を解説したものです。

概要

グラフの頂点カバー問題と呼ばれる問題を例にとって、組合せ最適化問題をアニーリングマシンで解くことを考えます。

以下の図のように、サーバがネットワーク(図の緑の線)で接続されている状況を考えます。 このような状況で、サーバにセキュリティ対策を施すことにします。すべてのサーバに同じように対策を施すのが一番なのですが、費用もかかるのでなるべく少ない台数にしぼりたいところです。そこで、対策されていないサーバであっても、少なくとも隣には対策済みのサーバがあるようにサーバを選定することにします。図中の青丸で囲まれた部分がそのような組合せの一例です。

このように、グラフ中のどの辺をとってみても少なくとも一方の頂点が含まれているような頂点の部分集合を「頂点カバー」と呼びます。頂点カバーはたくさんの組合せが存在しますが、その中で頂点数が最小のものをとくに最小頂点カバーと呼びます。

今回の問題は、この最小頂点カバーを求める問題ということができます。

コスト関数の作成

ここでは、グラフの各頂点について、頂点がカバーに「含まれる」「含まれない」をスピンの「+1」「-1」に対応させることにします。
最小頂点カバーを得るためには以下の2つの条件を満たす必要があります。

• (a) +1となるスピン(頂点カバーに含まれる頂点)はなるべく少ない方が良い
• (b) グラフの各辺の両側の頂点が-1であってはならない

(a)に関するコスト関数は下記のようになります。

$$ \tag*{式(1)} \sum_{i \in V}s_i $$

ここで$V$は入力グラフの全ての頂点の集合です。(b)について、辺の両側の頂点に対応するスピンを $s_i$ , $s_j$ とします。このとき、いずれも -1 のときだけコストが高く、それ以外の場合は同じコストであるような関数を考えれば良いのですが、そのままだと考えにくいので、$s$ のかわりに0か1の2値をとる変数 $x_i$ , $x_j$ を使って考えます。このとき、頂点カバーに含まれる場合は $x_i$ , $x_j$ の値が1となり、そうでない場合は0となるものとします。この場合は、$x_i$ と $x_j$ が両方0のときだけコストが高くなれば良いことになります。

$$ \tag*{式(2)} (1−x_i)(1-x_j) $$

というコスト関数を考えると、$x_i$ と $x_j$ の両方が0のときだけ式の値が1となり、それ以外の場合は0となるため、所望の条件を満たすことになります。
アニーリングマシンで扱うのはあくまでも±1の値をとるスピンなので、式(2)を変換する必要があります。 $s_i$ , $s_j$ も $x_i$ , $x_j$ も2値の値しかとらないので、下記のような式でお互いに変換する事が出来ます。

$$ x_i=\frac{s_i+1}2 $$

これを式(2)に代入して整理すると

$$ \tag*{式(3)} −s_i−s_j+s_i s_j $$

の形が出てきます。ちなみに、式(3) では全体の係数 1/4 を落としましたが、これはエネルギーのスケール（単位）を変えたことに相当すると見ることができます。 このとき、定数項は基底状態を与えるスピン値の組合せに影響しないので無視しています。
式(3)を入力グラフの全ての辺について足し合わせると

$$ \tag*{式(4)} \sum_{(i,j)\in E}(-s_i-s_j+s_is_j) $$

になります。ただし𝐸は入力グラフの全ての辺の集合です。
式(1)と式(4)を足し合わせると、頂点カバー問題に対応する下記のようなコスト関数が得られます。

$$ H(s)=\eta\sum_{i \in V}s_i+\sum_{(i,j)\in E}(-s_i-s_j+s_is_j) $$

$ s_i \in \{\pm1\} $: スピン値。入力グラフの頂点iが頂点カバーに含まれるとき $+1$

第一項の前に($\eta$>0)というパラメータを導入しています。これは2つの条件の強さを調整するためのものです。$\eta$=0のとき、コスト関数は第二項のみになります。この場合、頂点カバーに含まれる頂点数を抑える効果はなくなります。逆に$\eta$を非常に大きくすると、実質的に第一項のみになるので、頂点カバーに含まれる頂点数はゼロのときにコスト関数が最小になります。本サイトのデモでは、$\eta$=1としています。