LoginSignup
2

More than 3 years have passed since last update.

論文arxiv1302.5843 実装その1

Last updated at Posted at 2019-07-07

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は以下から借用しました。

NumberPartitining
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方法教えてください!

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2