1. 本記事の概要
NPな色々な問題に対してIsingで定式化した論文arxiv1302.5843があります。
D-waveの勉強がてら、それを実装してみようというもの。
2. 本記事の想定読者
- 最適化がなんとなくわかっている
- 理屈はいいから使えればいいや
- Pythonなんとなくわかる
レベルの人
3. 対象の問題
その1で対象とするのは、論文の「2.1 Number Partitioning」。
N個の正の整数が $ S = {n_1, . . . , n_N }$で与えられる。 この時、2つの集合$R$ と$S-R$を作成する。要素の合計が同値となる集合$R$を求めよ。
イジングモデルで考えると(具合がよく)、Nこの正の整数を$n_i$、どちらの集合に属するかをスピン$s_i$で決定すると、
$$ n_1*s_1 + n_2*s_2 ... n_N*s_N = 0 $$
の時、分割できたと定義できる。同値でない場合は、0以外の何らかの数値となる。つまり、$ n_1*s_1 + n_2*s_2 ... n_N*s_N$2乗することで、最小値(0)を求める最適化問題と定義することができる。
これを数式で簡潔に記すと
$$ H=(\sum_{i=1}^{n} n_is_i )^2$$
4. D-waveを使用する最適化プログラム
いきなり実装ですが、以下になります。
なお、Normalizeは以下から借用しました。
from pyqubo import Array, Sum
from dwave.system.samplers import DWaveSampler
from dwave.system.composites import EmbeddingComposite
import random
def normalize(exp, vtype='SPIN'):
if vtype != 'SPIN' and vtype != 'BINARY': # 変数のタイプがイジング・QUBO表現でない場合、終了
print("vtype must be 'SPIN' or 'BINARY'.")
return
model = exp.compile()
if vtype == 'SPIN':
compiled_h, compiled_J, offset = model.to_ising()
norm = max(abs(max(compiled_h.values())),
abs(max(compiled_J.values())),
abs(min(compiled_h.values())),
abs(min(compiled_J.values())))
else:
compiled_qubo, offset = model.to_qubo()
norm = max(abs(max(compiled_qubo.values())), abs(min(compiled_qubo.values())))
# 絶対値が最大の係数で各成分を割ることで、[0,1.0]に正規化
return exp / norm * 1.0
## 問題を定義
P_SIZE = 40
n = [random.randint(1,20) for i in range(P_SIZE)]
## ハミルトニアンを定義
s = Array.create('s',P_SIZE,'SPIN')
H = Sum(0,P_SIZE, lambda i: n[i] * s[i])**2
#ISINGを作成
model_i = normalize(H).compile()
compiled_h, compiled_J, offset = model_i.to_ising()
##Dwaveで実行
sampler_i = EmbeddingComposite(DWaveSampler(solver='DW_2000Q_VFYC_5'))
response_i = sampler_i.sample_ising(compiled_h, compiled_J, num_reads=200)
##サンプリングした中の最良解
print(response_i.first)
##定義した問題形式へDecode
result_i = []
result_i = model_i.decode_dimod_response(response_i)
結果確認
for j in (-1,1):
tmp=0
for i in range(P_SIZE):
if(result_i[1][0]["s"][i] == j):
print(n[i], end=" ")
tmp += n[i];
print(":{}".format(tmp))
19 18 7 9 11 20 12 8 5 4 19 1 10 8 17 5 16 10 7 20 3 2 13 10 1 9 :264
18 20 12 16 16 15 16 4 20 13 12 18 5 10 15 8 5 16 8 13 4 4 3 4 :275
うーむ、どうやらOceanを使って何も考えずに埋め込むと精度が悪いというのは本当のようですね。
楽でいい結果がでるEmbedding方法教えてください!