イジングモデルでナップサック問題を解く工夫

Yuichiro Minato

はじめに

イジングモデルというモデルを使って量子アニーリングなどはナップサック問題を解きます。

弊社の開発したWildqatを使ってサイゼリア計算をしてくれた若者の記事が量子界隈で比較的バズりましたが、

「「サイゼリヤで1000円あれば最大何kcal摂れるのか」を量子アニーリング計算(Wildqat)で解いてみた。」 https://qiita.com/hodaka0714/items/cf44b4ece992a39b5be4

こちらが公開されているイジングのハミルトニアン式です。 https://github.com/hodaka0714/saize_calory_maxmization/blob/master/saize_calory_maxmization.ipynb

何が難しいのか

イジングの制約条件に不等式が入ると難しくなります。制約条件が増えると解が出にくくなります。ナップサック問題には不等式が出ます。

ナップサック問題とは？

ナップサック問題（ナップサックもんだい、Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、「容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合（xi ∈ {0, 1}）や、同じ品物をいくつでも入れてよい場合（xi ∈ 0以上の整数）など、いくつかのバリエーションが存在する。

https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C

結構大事な問題の気がしますが、イジングマシンで解けないというのはもったいないです。

不等式を使わない

ということで不等式を使うのを止めると制約項が減ると思いますので、容量Cのナップサックに物体を入れますが、最初から１個、２個というように中に入れる数を決めてしまって解きます。

上記のblueqatのチュートリアルから問題を拝借して、

items = []
items.append(Item(number=0, weight=1, cost=10))
items.append(Item(number=1, weight=2, cost=15))
items.append(Item(number=2, weight=2, cost=55))
items.append(Item(number=3, weight=3, cost=50))
items.append(Item(number=4, weight=4, cost=40))
items.append(Item(number=5, weight=5, cost=50))
items.append(Item(number=6, weight=7, cost=30))
items.append(Item(number=7, weight=8, cost=35))
items.append(Item(number=8, weight=7, cost=60))
items.append(Item(number=9, weight=8, cost=80))

# 重さの上限(問題設定)
wlimit = 10

こちらでコスト最大となるものを解いてみたいと思います。結局たくさん失敗するんだったら、より確実な方法を探したいものです。

H = -\sum_i c_i x_i + B\left(10- \sum_i w_i x_i \right)^2

式の前半が全体のコストで、後半が重さを超えない制約条件です。不等式を除いたらかなり楽になりました。本来はこれに、xの個数を制限する制約条件がつきますが、別途開発した制約条件を回避する術がありますので、そちらを使ったシミュレータでやってみます。

今回は１０を超えない範囲でやってみました。多分重さが10でコストが155の時に最大を取ると思います。


import numpy as np
import copy

B = 10

#最初に定式化を行います。
def Hamiltonian(x):
  return -10*x[0] -15*x[1] -55*x[2] -50*x[3] -40*x[4] -50*x[5] -30*x[6] -35*x[7] -60*x[8] -80*x[9] + B*(4*x[0]*x[1] + 4*x[0]*x[2] + 6*x[0]*x[3] + 8*x[0]*x[4] + 10*x[0]*x[5] + 14*x[0]*x[6] + 16*x[0]*x[7] + 14*x[0]*x[8] + 16*x[0]*x[9] - 19*x[0] + 8*x[1]*x[2] + 12*x[1]*x[3] + 16*x[1]*x[4] + 20*x[1]*x[5] + 28*x[1]*x[6] + 32*x[1]*x[7] + 28*x[1]*x[8] + 32*x[1]*x[9] - 36*x[1] + 12*x[2]*x[3] + 16*x[2]*x[4] + 20*x[2]*x[5] + 28*x[2]*x[6] + 32*x[2]*x[7] + 28*x[2]*x[8] + 32*x[2]*x[9] - 36*x[2] + 24*x[3]*x[4] + 30*x[3]*x[5] + 42*x[3]*x[6] + 48*x[3]*x[7] + 42*x[3]*x[8] + 48*x[3]*x[9] - 51*x[3] + 40*x[4]*x[5] + 56*x[4]*x[6] + 64*x[4]*x[7] + 56*x[4]*x[8] + 64*x[4]*x[9] - 64*x[4] + 70*x[5]*x[6] + 80*x[5]*x[7] + 70*x[5]*x[8] + 80*x[5]*x[9] - 75*x[5] + 112*x[6]*x[7] + 98*x[6]*x[8] + 112*x[6]*x[9] - 91*x[6] + 112*x[7]*x[8] + 128*x[7]*x[9] - 96*x[7] + 112*x[8]*x[9] - 91*x[8] - 96*x[9] + 100
)

w = np.array([1,2,2,3,4,5,7,8,7,8])  
c = np.array([10,15,55,50,40,50,30,35,60,80]) 

def run(H):

  #パラメータ初期化
  T = 10
  ite = 1000
  N = 10
  targetT = 0.02
  red = 0.97

  #量子ビットの初期化
  q = [1,1,1,1,0,0,0,0,0,0]

  while T>targetT:
    x_list = np.random.randint(0, N, ite)
    for x in x_list:
      q2 = copy.copy(q)
      y = np.random.randint(0, N)
      q2[x] = q[y]
      q2[y] = q[x]
      dE = H(q2) - H(q)
      if np.exp(-dE/T) > np.random.random_sample():
        q[x] = q2[x]
        q[y] = q2[y]
    T *= red

  return q

a = run(Hamiltonian)
weight = np.sum(a*w)
cost = np.sum(a*c)
print("weight:" + str(weight))
print("cost:" + str(cost))

print("energy:" + str(cost*(-1)+B*weight))
print(a)

weight:10

cost:155

energy:-55

[1, 0, 1, 1, 1, 0, 0, 0, 0, 0]

準備ができました。ハミルトニアンは、式展開をしてまとめてあります。Bはハイパーパラメータなので様子を見て変えます。

数を1から10まで順番にやってみる。

とりあえず初期の量子ビットの設定を変えるだけでナップサックを順番にできます。とりあえず量子ビットに1を立てるところからやってみます。

量子ビットを1つだけ1にするとき

簡単です。量子ビットの初期化部分を1つだけ1にします。

  #量子ビットの初期化
  q = [1,0,0,0,0,0,0,0,0,0]

出てくるのは、

weight:8
cost:80
energy:0
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

重さ、コスト、エネルギー関数、量子ビットの配列の順で出てきました。

順番にやってみます。

面倒なので順番に書きますね。

#2つ
weight:10
cost:135
energy:-35
[0, 0, 1, 0, 0, 0, 0, 0, 0, 1]

#3つ
weight:10
cost:155
energy:-55
[0, 0, 1, 1, 0, 1, 0, 0, 0, 0]

#4つ
weight:10
cost:155
energy:-55
[1, 0, 1, 1, 1, 0, 0, 0, 0, 0]

#5つ
weight:12
cost:170
energy:-50
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0]

#6つ
weight:17
cost:220
energy:-50
[1, 1, 1, 1, 1, 1, 0, 0, 0, 0]

#7つ
weight:24
cost:280
energy:-40
[1, 1, 1, 1, 1, 1, 0, 0, 1, 0]

#8つ
weight:31
cost:310
energy:0
[1, 1, 1, 1, 1, 1, 1, 0, 1, 0]

#9つ
weight:39
cost:390
energy:0
[1, 1, 1, 1, 1, 1, 1, 0, 1, 1]

#10こ
weight:47
cost:425
energy:45
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

重さは10を超えてはいけないので、コスト155が最大となり、結構簡単に解けました。

#3つ
weight:10
cost:155
energy:-55
[0, 0, 1, 1, 0, 1, 0, 0, 0, 0]

#4つ
weight:10
cost:155
energy:-55
[1, 0, 1, 1, 1, 0, 0, 0, 0, 0]

まとめ

不等式を使わない方がいいと思います。