はじめに
この記事は前回の記事 (東芝SBMでTSPを解く（TSPは量子アニーリングで解けるのか? その1） の続きです。
前回の記事では東芝シミュレーテッド分岐マシン（SBM）を用いてTSPを解いてみましたが、15頂点ぐらいで解けなくなりました。今回の記事では、（量子）アニーラー用にイジングモデルに変換されたTSPを、シミュレーテッド・アニーリングを用いて解いてみます。
東芝SBMは厳密には量子アニーラーではありませんが、ここでは簡単のため同じような働きが期待されるこれらのアニーラーをまとめて量子アニーラーと呼ぶことにします。
TSPのイジングモデル変換
ざっくりとイジングモデルとQUBO、TSPの表現について説明します。
量子アニーラーでは、コスト関数が以下のイジングモデルと呼ばれる形式で表される必要があります。
\mathcal{H} = \sum_{i,j} J_{ij} x_i x_j + \sum_{i} h_i x_i
ここで、$x_i, x_j \in \{-1,+1\}$です。ここで、変数を置き換えることで、$x_i, x_j \in \{0,1\}$ にすることができます。0も1も何乗しても値は変わらないので、$x_i = x_i^2$と置き換えることができ、以下の形式に書き換えられます。
\mathcal{H} = \sum_{i \ge j} Q_{ij} x_i x_j
この形式をQUBO (Quadratic Unconstrained Binary Optimization)と呼びます。東芝SBMでは問題をこの形式に変換して入力する必要があります。
TSPは$N$個の頂点とその頂点間の距離$d_{u,v}$に対し、$N$個の頂点すべてを1度ずつ巡り、最初の頂点に戻るルートのうち、総移動距離が最小となるものを求める問題です。QUBO形式で表現するにあたり、以下の変数を導入します。
x_u^i = \begin{cases}
1 & (頂点uをi番目に通る) \\
0 & (otherwise)
\end{cases}
このとき、総距離は以下のコスト関数で計算できます。
\mathcal{H}_d = \sum_{u, v} \sum_{i} d_{u,v} x_u^i x_v^{i+1}
しかし、このままだと一般に正の距離しかない場合、すべての変数を0にするのが最適解となりますが、それはTSPの解とはなりません。したがって以下の制約が必要となります。
\forall u \ \sum_i x_u^i = 1, \forall i \ \sum_u x_u^i = 1
現在の量子アニーラーにおいては、制約はコスト関数に組み込むことによって表現するしかありません。したがって、以下の項をコスト関数に足し上げます。
\mathcal{H}_c = A \sum_u \left( \sum_i x_u^i - 1\right)^2 + A \sum_i \left( \sum_u x_u^i -1\right)^2
ここで、Aが制約項にかかる十分大きい正の係数です。以上より、TSPは以下のQUBO形式で表されます。
\mathcal{H} = \mathcal{H}_d + \mathcal{H}_c = \sum_{u, v} \sum_{i} d_{u,v} x_u^i x_v^{i+1} + A \sum_u \left( \sum_i x_u^i - 1\right)^2 + A \sum_i\left( \sum_u x_u^i -1\right)^2
この係数をMatrix Marketと呼ばれる形式で表現し、東芝SBMに入力すると、アニーラーが動いて解を出力してくれます。制約をコスト関数に載せる以上、アニーラーはあくまで近似解しか出力できないので、出力された解が制約を満たすかは確認する必要があります。
シミュレーテッド・アニーリング
量子アニーリングが登場する前にも、「アニーリング」（焼きなまし法）と呼ばれる手法がありました。ある状態からその近くにあるコストの小さい方向に遷移していけば、いつかはそれ以上小さくならない状態に至ります。ただし、それは局所最適解であり、全体最適解であるかは保証されません。シミュレーテッド・アニーリングでは、近くの状態がもし現在よりもコストが高い場合でも、「温度が高」ければ遷移し、だんだんとその温度を下げていく手法になります。これにより、局所最適解に陥っても最初のうちは抜け出しながら、よりよい最適解を目指して探索することができます。シミュレーテッド・アニーリングは古典コンピュータで実装可能なので、これを古典アニーラーと呼ぶことにしましょう。
擬似コードはWikipediaにも載っているので参考にしてください（焼きなまし法 - Wikipedia）。今回は量子アニーラー用にQUBO形式に変換された多項式コスト関数に対し、0/1変数の値の組を状態として持ち、コスト関数を計算できるように実装しました。量子アニーラー関係なくTSPをシミュレーテッド・アニーリングで解く場合には、もう少し別の状態表現・（より高速な）コスト計算が可能になるでしょう。
実験・結果
前回の記事と同じグラフに対してシミュレーテッド・アニーリングを行います。シミュレーテッド・アニーリングにはイテレーション回数・初期温度・最終温度（初期温度×xのxとして）がパラメータになります。いくつか試してみたなかで良かったものの結果を示すことにします（すなわち割とパラメータに結果が影響されます）。
| 頂点数 | 計算時間 | イテレーション | 初期温度 | 最終温度パラメータ |
|---|---|---|---|---|
| 10 | 0.018sec | 45/100 | 1.0 | 0.0001 |
| 15 | 0.3sec | 1270/1500 | 1.0 | 0.99 |
いずれも東芝SBMを用いたときよりも良い結果が得られました。
まとめ
- 量子アニーラーはイジングモデル (QUBO形式) で表現された問題を解くことができる
- TSPはイジングモデル (QUBO形式) で表現できる
- シミュレーテッド・アニーリングを用いてTSPを解いたところ、東芝SBMを用いたときより良い結果が得られた
次回の記事でなぜこのような結果が得られたかについて考察していこうと思います。