Toshiba SQBM+ の AUTOISING ソルバを使う

2020年の記事「シミュレーテッド分岐マシン(SBM)で巡回セールスマン問題を解く」 では、Toshiba SBM を用いて巡回セールスマン問題を解きました。現在は Toshiba SBM は Toshiba SQBM+ に改名されており、性能や使い勝手もアップグレードされています。

今回は、同じ問題を題材に、 Toshiba SQBM+ の新しい機能である AUTOISING ソルバについてご紹介します。

Tohsiba SQBM+ とは

Toshiba SQBM+ とは、東芝デジタルソリューションズ株式会社が提供している、組み合わせ最適化問題を解くためのソルバです。SQBM+ の AUTOISING ソルバは、二次制約なしバイナリ最適化問題という形式の問題を解くことができ、ハイパーパラメータを自動で調整する機能を備えています。

ここで、二次制約なしバイナリ最適化問題 (以下 QUBO ) とは、バイナリ変数からなる 2 次多項式の最小化問題のことを指します。つまり、${Q_{ij}}$ を実数の定数として

$$
\text{minimize} \sum_{0 \leq i, j < n} Q_{ij}x_ix_j \quad (x_0, x_1, \ldots, x_{n-1} \in {0, 1})
$$

の形で表される最小化問題のことです。

巡回セールスマン問題とは

巡回セールスマン問題 (Traveling Salesman Problem, TSP) とは、セールスマンが都市を訪問する際、すべての都市を 1 度ずつ訪問する最短経路を求める問題です。この問題は、都市の数が大きくなると厳密解を探索するのが難しくなる問題として知られています。

今回は、都市数 $N$ を 30 として、以下のように正方形の中にランダムに配置された 30 都市に対して巡回セールスマン問題を解きます。

定式化～モデルの作成

2020年の記事 では問題をマシンに送るのに Matrix Market 形式のファイルを手動で作成していましたが、 今回は Amplify SDK を用います。Amplify SDK は、株式会社フィックスターズが開発するイジングマシン向けミドルウェア Python ライブラリです。Amplify SDK を用いると、バイナリ変数の多項式や制約式を生成する、高次多項式や制約条件を QUBO に落とし込む、QUBO を SQBM+ に解かせる、といったことができます。

さて、都市数が $N$ であり、都市 $i$ と都市 $j$ 間の距離が $d_{i,j}$ である巡回セールスマン問題は、$N \times N$ 個のバイナリ変数 $q$ を用いて、以下のように最適化問題として表すことができます。$q_{k, i}$ は、$i$ 番目の都市を $k$ 番目に通るときに $1$、それ以外のときに $0$ となるバイナリ変数となっています。

$$
\text{minimize} \ \sum d_{i,j} q_{k, i} q_{k+1, j} \
\text{subject to} \ \sum_{i=0}^{N-1}q_{k, i} = 1, \sum_{k=0}^{N-1}q_{k, i} = 1
$$

この式を QUBO に変形すると以下のような問題となります。$K$ は制約条件の重みを表すハイパーパラメータです。ただし、この変形は、今回は Amplify SDK が自動で行うため、以下の式を直接コードに落とし込む必要はありません。

$$
\text{minimize} \ \sum d_{i,j} q_{k, i} q_{k+1, j} + K \left( \sum_k(\sum_i q_{k, i} – 1)^2 + \sum_i(\sum_k q_{k, i} – 1)^2 \right)
$$

巡回セールスマン問題のさらなる定式化の詳細については、こちら のページ を参照してください。

Amplify SDK を用いると、上記の組み合わせ最適化問題を Python で以下のように表現できます。

import amplify
import numpy as np

NUM_CITIES = 30
LOCATIONS = np.random.uniform(size=(NUM_CITIES, 2))  # 各都市の x 座標と y 座標
K = 1.0  # 制約条件の重み

# バイナリ変数 q を作成
q = amplify.BinarySymbolGenerator().array(NUM_CITIES, NUM_CITIES)

# 各 i,j について、都市 i と都市 j の間の距離 d_{i,j} を計算する
all_diffs = np.expand_dims(LOCATIONS, axis=1) - np.expand_dims(LOCATIONS, axis=0)
distances = np.sqrt(np.sum(all_diffs**2, axis=-1))

# 目的関数は $\sum d_{i, j} q{k, i} q{k+1, j}$
objective_func = amplify.einsum("ij,ki,kj->", distances, q, q.roll(-1, axis=0))

# q の各行各列の和がすべて 1 である必要がある
constraints = sum(amplify.constraint.one_hot(q[n]) for n in range(NUM_CITIES)) + sum(
    amplify.constraint.one_hot(q[:, i]) for i in range(NUM_CITIES)
)

# 問題の作成
model = amplify.BinaryQuadraticModel(objective_func, K * constraints)

SQBM+ のパラメータの設定～実行

Amplify SDK の ToshibaClient を用いて SQBM+ を実行します。タイムアウト値や各種ハイパーパラメータなど、実行に必要なパラメータも Amplify SDK から設定することができます。

今回は AUTOISING ソルバを使うので、solver 名に autoising を指定します。

2020年の記事 では、dt や C 、steps などマシンのハイパーパラメータを指定する必要があり、さらに、性能を求める場合は最適なパラメータの探索を行わなければなりませんでした。しかし、今回使用する AUTOISING ソルバはマシンのハイパーパラメータのほとんどを自動で調整するので、ハイパーパラメータを指定する必要はありません。

実行時間を 10 秒にして、SQBM+ が稼働しているマシンの URL を指定すれば準備は完了です。

client = amplify.client.ToshibaClient()
client.url = "[ip]:[port]" # 適切な値を設定してください
client.solver = "autoising"
client.parameters.timeout = 10

作成したクライアントをAmplify SDK の Solver クラスに渡せば、上で作ったモデルを solve() 関数で解くことができるようになります。

solver = amplify.Solver()
solver.client = client
result = solver.solve(model)
solution = q.decode(result[0].values)

最後の行で得られた solution は $30 \times 30$ の numpy 配列で、solution[k][i] = 1 であるとき $i$ 番目の都市を $k$ 番目に通ることを表します。

solution を図示すると、以下のような巡回路になりました。

良さそうな経路が求められていることが分かります。

性能評価

2020年 と比較してどのくらいの性能向上があったのかを見てみましょう。

問題セットとして、TSPLIB の gr24 を使用します。gr24 は 24 都市に対する巡回セールスマン問題であり、最適解の値は 1272 であることが知られています。

巡回セールスマン問題の定式化においては、ハイパーパラメータである制約条件の重み $K$ を 2 都市間の距離の最大値の半分とし、SQBM+ が解く QUBO が 2020 年のものと同一となるようにしました。

結果は以下のようになりました。いずれも 10 回実行して得られた解の平均値と最良値をとっており、2020 年のものについては最も良いパラメータでの結果を採用しています。

タイムアウト値を 1 秒とした場合でも、2020 年のタイムアウト値 20 秒の場合と比較して平均的にはるかに良い結果が得られ、タイムアウト値を 20 秒とした場合には高い確率で最適解である 1272 が得られました。2020 年の結果を出すためには、数十種類のパラメータセットについて実行してパラメータ調整を行わなければならなかったこともあわせて考えると、マシンの性能が飛躍的に向上したことがうかがえます。

まとめ

Toshiba SQBM+ と Amplify SDK を使って巡回セールスマン問題を解く方法をご紹介しました。以前の記事 と比べると、問題を定式化してマシンを実行するまでに必要な作業がはるかに簡単になり、性能もずいぶんと良くなったことがお分かりいただけると思います。今後のさらなる進歩にも期待が持てそうです。

また、Toshiba SQBM+ では AUTOISING ソルバの他に巡回セールスマン問題に特化した TSP ソルバも提供されています。TSP ソルバを用いる方法については、こちら をご覧ください。

リンク

Toshiba SQBM+ ホームページ
Fixstars Amplify ホームページ
シミュレーテッド分岐マシン(SBM)で巡回セールスマン問題を解く – Fixstars Tech Blog
TSPLIB

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。