前回記事(以下)では、ナップサック問題を定式化し、量子アニーリングを用いて最適解を算出しましたが、n=5というまだ簡単な条件の時点で解が求まらなくなるという結果となりました。本記事では、最適化変数を減らすために、不等式制約を厳しくした条件で求解させてみて、どのような傾向になるかを確認しました。前回記事ではナップサックの重量制限という不等式制約は以下式のように扱っていました。α以降が制約を表し、xが最適化対象、wがそれぞれの重量、mは重量の制約値(l)に最も近い整数になります。{eq7}$$上記式では、重量が0〜lの時全てでペナルティが0となるようにスラック変数の数(m)を決めていたため、最適化変数の対象が増える+冗長になり、量子アニーリングで解が求まらなくなったと考えられます。そこで、対策として最適解における重量はlまたは少なくともl-3の値には収まると仮定し、不等式の範囲を狭めることでスラック変数の数を低減することを検討することにしました。{eq5'}$$のように狭めることになります。このようにすると、eq7は以下のようになり、スラック変数の数をm個⇒2個へと大幅に低減できるようになります。{eq7′}$$実装と検証スクリプトは前回同様の作りで、eq7’と合うようにQUBO部分を変えています。GitHubで公開しています。https://github.com/Rosyuku/Dwave_leap_trial/blob/master/knapsack%20problem/quantum_case2.pyn=5の結果n=5として計算すると、以下の結果が得られました。x4=1]が求まっており、不等式制約の改良により問題が解けるようになったことが確認できました。n=10の結果n=10として計算すると、3回目くらいで以下の結果が得られました。us価値と重量の条件は前回同様乱数で設定していて以下になっています。5])この結果も厳密解(Value合計32、Weight合計20)と一致しています。1回3000回の計算を実施させていたので、量子アニーリングの検討回数を10000回くらいにしないと、本値は得られませんでした(計算時間として500ms×3で1.5s位を消耗する)。なってくると、計算時間の制約である1分がネックに感じる用になってきます。n=15の結果n=15として計算した場合も、同様に3回目で厳密解(Value合計70、Weight合計29)と一致する以下の結果が得られました。nを増やしても量子アニーリングの計算時間が増えていない(500ms程度で変わっていない)点は、単に時間で計算を打ち切っているだけでなければ特筆できる点と言えます。usn=20の結果n=20として計算した場合、20回目程度計算しましたが厳密解(Value合計90、Weight合計40)と一致する解は得られませんでした。近かった例を以下に記載します。Value合計は90となっていますが、Weight合計が41と制約を逸脱しており、正しい解ではないです。usまとめ不等式制約を改良し、最適化変数を減らすことでn=15まで厳密解と一致する解が得られたことを確認できました。このことから、問題の範囲を絞り込み、変数を減らすアプローチは有効であることは分かります。一方で以下は課題であり、量子アニーリングの理論やD-Waveの仕様をもう少し理解してから再度取り組む必要があると感じました。コメントをキャンセルメールアドレスが公開されることはありません。*サイト上に表示された文字を入力してください。プロフィール兵庫県在住の30代データサイエンティスト。Pythonを使った機械学習等によるデータ分析や、ウェブアプリ等のシステム開発に取り組んでいます。