概要
前回記事(以下)では、ナップサック問題を定式化し、量子アニーリングを用いて最適解を算出しましたが、n=5というまだ簡単な条件の時点で解が求まらなくなるという結果となりました。本記事では、最適化変数を減らすために、不等式制約を厳しくした条件で求解させてみて、どのような傾向になるかを確認しました。
不等式制約の変更
前回記事ではナップサックの重量制限という不等式制約は以下式のように扱っていました。α以降が制約を表し、xが最適化対象、wがそれぞれの重量、mは重量の制約値(l)に最も近い整数になります。
$$Minimize(P’) \\ P’ = -x^{T} v + \alpha (x^{T} w – \lambda_1 – \lambda_2 – … – \lambda_m)^2\\ \lambda_{i} \in [0, 1] \tag {eq7}$$上記式では、重量が0〜lの時全てでペナルティが0となるようにスラック変数の数(m)を決めていたため、最適化変数の対象が増える+冗長になり、量子アニーリングで解が求まらなくなったと考えられます。
そこで、対策として最適解における重量はlまたは少なくともl-3の値には収まると仮定し、不等式の範囲を狭めることでスラック変数の数を低減することを検討することにしました。
つまり、元々
$$Minimize(P’) \\ P’ = -x^{T} v \\ \text{subject to } x^{T} w < l \tag {eq5}$$だったものを、
$$Minimize(P’) \\ P’ = -x^{T} v \\ \text{subject to } l-3 < x^{T} w < l \tag {eq5'}$$のように狭めることになります。このようにすると、eq7は以下のようになり、スラック変数の数をm個⇒2個へと大幅に低減できるようになります。
$$Minimize(P’) \\ P’ = -x^{T} v + \alpha (x^{T} w – l + \lambda_1 + 2 \lambda_2)^2\\ \lambda_{i} \in [0, 1] \tag {eq7′}$$実装と検証
スクリプトは前回同様の作りで、eq7’と合うようにQUBO部分を変えています。GitHubで公開しています。
https://github.com/Rosyuku/Dwave_leap_trial/blob/master/knapsack%20problem/quantum_case2.py
n=5の結果
n=5として計算すると、以下の結果が得られました。
Sample(sample={'x0': 0, 'x1': 1, 'x2': 0, 'x3': 1, 'x4': 1, 'x5': 1, 'x6': 1, 'x7': 0}, energy=-7.0, num_occurrences=8, chain_break_fraction=0.75) Total_real_time 499544 us
この問題の厳密解である、[x0=0, x1=1, x2=0, x3=1, x4=1]が求まっており、不等式制約の改良により問題が解けるようになったことが確認できました。
n=10の結果
n=10として計算すると、3回目くらいで以下の結果が得られました。
Sample(sample={'x0': 1, 'x1': 1, 'x2': 0, 'x3': 0, 'x4': 1, 'x5': 0, 'x6': 0, 'x7': 0, 'x8': 0, 'x9': 1, 'x10': 1, 'x11': 0, 'x12': 0}, energy=-32.0, num_occurrences=1, chain_break_fraction=0.9230769230769231) Total_real_time 499622 us
価値と重量の条件は前回同様乱数で設定していて以下になっています。
weight:array([5, 6, 8, 4, 7, 5, 4, 8, 7, 2]) value:array([9, 9, 7, 3, 9, 8, 3, 2, 6, 5])
この結果も厳密解(Value合計32、Weight合計20)と一致しています。ただし、1回3000回の計算を実施させていたので、量子アニーリングの検討回数を10000回くらいにしないと、本値は得られませんでした(計算時間として500ms×3で1.5s位を消耗する)。こうなってくると、計算時間の制約である1分がネックに感じる用になってきます。
n=15の結果
n=15として計算した場合も、同様に3回目で厳密解(Value合計70、Weight合計29)と一致する以下の結果が得られました。nを増やしても量子アニーリングの計算時間が増えていない(500ms程度で変わっていない)点は、単に時間で計算を打ち切っているだけでなければ特筆できる点と言えます。
weight:array([13, 5, 6, 8, 4, 7, 5, 11, 12, 4, 8, 7, 11, 2, 11]) value:array([ 9, 14, 9, 7, 12, 3, 12, 9, 8, 3, 2, 12, 6, 11, 5]) Sample(sample={'x0': 0, 'x1': 1, 'x2': 1, 'x3': 0, 'x4': 1, 'x5': 0, 'x6': 1, 'x7': 0, 'x8': 0, 'x9': 0, 'x10': 0, 'x11': 1, 'x12': 0, 'x13': 1, 'x14': 0, 'x15': 1, 'x16': 1, 'x17': 0}, energy=-70.0, num_occurrences=1, chain_break_fraction=1.0) Total_real_time 499685 us
n=20の結果
n=20として計算した場合、20回目程度計算しましたが厳密解(Value合計90、Weight合計40)と一致する解は得られませんでした。最も近かった例を以下に記載します。Value合計は90となっていますが、Weight合計が41と制約を逸脱しており、正しい解ではないです。
weight:array([ 8, 7, 11, 2, 4, 6, 5, 15, 7, 3, 17, 15, 13, 19, 5, 16, 18, 8, 15, 9]) value:array([ 9, 16, 14, 9, 12, 19, 12, 9, 8, 3, 18, 12, 16, 6, 8, 4, 7, 5, 11, 12]) Sample(sample={'x0': 0, 'x1': 1, 'x2': 0, 'x3': 1, 'x4': 1, 'x5': 1, 'x6': 1, 'x7': 0, 'x8': 0, 'x9': 1, 'x10': 0, 'x11': 0, 'x12': 0, 'x13': 0, 'x14': 1, 'x15': 0, 'x16': 0, 'x17': 0, 'x18': 0, 'x19': 1, 'x20': 1, 'x21': 0, 'x22': 0}, energy=-90.0, num_occurrences=1, chain_break_fraction=0.9565217391304348) Total_real_time 499774 us
まとめ
不等式制約を改良し、最適化変数を減らすことでn=15まで厳密解と一致する解が得られたことを確認できました。このことから、問題の範囲を絞り込み、変数を減らすアプローチは有効であることは分かります。一方で以下は課題であり、量子アニーリングの理論やD-Waveの仕様をもう少し理解してから再度取り組む必要があると感じました。
- 問題をQUBOモデルに変換し実装するのが非常に手間である、特に非線形は解くことも出来ない可能性が高い
- QUBOモデルを実装できても、量子アニーリングの計算結果は局所解に落ち易く、nを増やす(問題を複雑にする)と試行回数が必要になる(1分ではもの足りない)
- 量子アニーリングで欲しい解が得られない、又は望ましい特性が得られない時に、原因や調整方法が分からない
- 量子アニーリング自体の計算時間は短く(今回の例では3000回の計算で500ms)、さらにnが増えても計算時間が増加しないなど優れた可能性を感じる一方で、(本文では触れられなかったが)QUBOモデルを量子アニーリングで処理できる形式に変換する処理はnに依存して増加しており、量子アニーリング以外のところの計算時間も考慮する必要がある