はじめに
前回巡回セールスマン問題について同様の記事を書きましたが、
様々な最適化問題についても数式を深追いしないような形で理解するような記事が書ければと学習も兼ねて投稿します！
ナップサック問題とは
0‒1 ナップサック問題（Knapsack Problem）は、容量制限のあるカバン（ナップサック）にどのアイテムを詰めるかを選び、
- 総価値を最大化（＝コストを最小化）
-
総重量は容量を超えない
ようにする組合せ最適化問題です。都市の順列を探す TSP と違い、各アイテムを入れるか / 入れないかの 0/1 選択が状態になります。
ナップサック問題の定式化（整数重み）
- 物品数：$N$
- バイナリ変数：$x_\alpha$ ― 物品 $\alpha$ を選ぶとき 1、選ばないとき 0
- バイナリ変数：$y_n$ ― 重さ $n$ を選ぶとき 1、選ばないとき 0
- 重量：$w_\alpha \in \mathbb{Z}_{>0}$
- 価値：$c_\alpha \in \mathbb{Z}_{>0}$
- 容量上限：$W \in \mathbb{Z}_{>0}$
$\text{maximize}$（目的関数）：
$$
\sum_{\alpha=1}^{N} c_\alpha\ x_\alpha
$$
$\text{subject to}$（制約）：
$$
\sum_{\alpha=1}^{N} w_\alpha\ x_\alpha \le W
$$
バイナリ制約
$$
x_\alpha \in {0, 1}
$$
ハミルトニアンの分解
$$
H = H_A + H_B
$$
制約項
$$
H_A
= A\left(1-\sum_{n=1}^{W} y_n\right)^{2}
+
A\left(\sum_{n=1}^{W} n\ y_n
- \sum_{\alpha=1}^{N} w_\alpha\ x_\alpha\right)^{2}
$$
目的関数項
$$
H_B
= -\sum_{\alpha=1}^{N} c_\alpha\ x_\alpha
$$
ざっくりと各項を咀嚼してみる
今回も前回記事と同様に小さいデータを例として各項の中身を見ていこうと思います。
以下のような5つの果物の組み合わせと重量制限の中で価値が最大の組み合わせを見ていきます。
-
果物の重さと価値：
-
重量制限：12以下
図解する
TSPの時もそうでしたが、詰まるところ果物の評価から組み合わせとして選択したものに1が入ったバイナリ変数から価値が算出され、if文でその組み合わせの重量が超えていないかを確認する関数を想定するようなイメージとなります。
例えば、ぶどうとばななとももを選んだ時のバイナリ変数は上の表のような方になるかと思います。
こちらを用いて以下の各項の説明をしてきます。
目的項
目的項では単純にバイナリ変数で選択された果物の価値の総和を算出します。
目的項は上記のように単純に各果物の価値と、その果物が選択されている(1) / いない(0)を掛けた値の総和として算出されています。
ナップサック問題は価値を最大化する問題ですが、前回のTSPは最小化の問題でした。この手の最適化問題は基本的にエネルギーを最小化するように処理が働くため、このままでは価値が低い組み合わせが最適な状態となってしまいます。
そのため、価値を最大化する問題については、目的項に$-$(マイナス)をつけることが一般的です。
プログラミング的に表現すると以下のような形になるかと思います。
N = 5 # 果物の総数
weight_list = [400, 700, 300, 200, 500] # 重さのリスト
cost_list = [300, 600, 400, 500, 700] # 価値のリスト
x_a = [0, 1, 1, 1, 0] # 果物のバイナリ変数x_a
cost = 0
for i in range(N):
cost += cost_list[i] * x_a[i]
目的項のみの状態では、全ての果物を選択したバイナリ変数の状態=[1, 1, 1, 1, 1]が価値が最大となりますが、重量制限に引っかかっています。次に制約項にて重さの制限を設定していきます。
制約項1(重さの制限)
制約項では$x_a$とは別に、$y_n$という新たなバイナリ変数が設定されています。
このバイナリ変数$y_n$は以下のような1から重さまでの大きさの配列として認識すると良いかと思います。
例えば、この状態のバイナリ変数は12番目に1が付いているため、重さが12であることがわかります。
nの部分には1から重さまでの数値が入り、重さのバイナリ変数から0 or 1が入るので今までの総和と同じように算出され、重さのバイナリ変数で1になった部分の重さが分かります。
右の$w_a\ x_a$については、目的項の時と同様に今度はどの果物を選択するかを決めるバイナリ変数$x_a$と重さの表から重さの合計値を算出します。
重さの合計と、$y_n$の状態の時の重さを計算すると0となり、ペナルティーがない状態が分かります。
プログラムで表現すると以下のようになるかと思います。
N = 5 # 果物の総数
W = 12 # 重さの制限
weight_list = [4, 7, 3, 2, 5] # 重さのリスト
x_a = [0, 1, 1, 1, 0] # 果物のバイナリ変数x_a
y_n = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] # 重さのバイナリ変数
weight = 0 # x_aでの組み合わせの総和
weight_check = 0 # y_nでの重さの確認用
# 重さの総和
for i in range(N):
weight += weight_list[i] * x_a[i]
# y_nの状態での重さ
for i in range(W):
n = (i+1)
weight_check += n * y_n[i]
もちろん$n$と$y_n$は1~制限重量までの重さを表すことができますので、重量の総和が1~12の時であればペナルティーが0となりペナルティが発生しなくなります。
例えば重さの総和が10となった場合を考えると、上の図のようなイメージですが重さのバイナリ変数$y_n$とnの積算で総和が10となる組み合わせいくつか存在すると思います。
10の組み合わせであれば同じようにペナルティが0となりますが、重さの総和が13でとなった場合も考えると[1,0,0,0,0,0,0,0,0,0,0,1]のような形でバイナリ変数y_nも13が表現できてしまいます。こうなると重量制限の意味がなさなくなってしまいます。
これを防ぐために、以下のone-hot制約というものを設定します。
制約項2(one-hot制約)
one-hot制約は、TSPの制約項で用いた各都市に1回だけや同じ時刻に1都市のみのようなバイナリ変数のどこか1箇所だけが1になるような制約を示します。
そのため、式にあるように$y_n$の総和がかならず1、つまり1箇所のみ1となることを確かめるものとなります。
こうすることによって、制約項1で説明したような重さのバイナリ変数$y_n$の複数箇所が1となって別の重さの表現が無効となり、1~重量制限までしか表現できないようにすることができます。
おわりに
最終的なコストは式の通りに目的項($H_B$)と制約項の($H_A$)の加算結果となります。
目的項は-の数値を取るため、ペナルティーがかかると大きな数値になるため、これで目的項をより小さくする目的が図れます。
係数AとBの説明は前回同様省きましたが、TSPと似たような概念も出てきているので問題の解き方というか、ルールがわかってくると他の問題の理解もしやすくなってくるのかなと感じました。
前回も同じようなことを書いていたかもしれませんが、今回もバイナリ変数の組み合わせを入れたらコストが返ってくるような関数をイメージすると良さそうです。
プログラム的には以下のような形になると思います。
N = 5 # 果物の総数
W = 12 # 重さの制限
weight_list = [4, 7, 3, 2, 5] # 重さのリスト
cost_list = [300, 600, 400, 500, 700] # 価値のリスト
x_a = [0, 1, 1, 1, 0] # 果物のバイナリ変数x_a
y_n = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] # 重さのバイナリ変数
# コスト計算をする関数(A, Bは係数)
def calc_cost(x_a, A, B):
weight = 0 # x_aでの組み合わせの総和
weight_check = 0 # y_nでの重さの確認用
weight_count = 0 # y_nの1をカウントする
cost = 0
# 価値の総和
for i in range(N):
cost += cost_list[i] * x_a[i]
# 重さの総和
for i in range(N):
weight += weight_list[i] * x_a[i]
# y_nの状態での重さ
for i in range(W):
n = (i+1)
weight_check += n * y_n[i]
weight_count += y_n[i] # y_nが1つだけであるか
# H = H_B + H_Aの形に
return -cost + A*(weight_check - weight)**2 + B*(1 - weight_count)**2
こんな感じで次回も別の問題にもトライしていければと思います。