こんにちは！初投稿です！
この記事が誰かに何かでためになれば幸いです！
背景
僕は先日、この記事↓↓を読んでふと思いました。
サイゼリヤ1000円ガチャをつくってみた(Heroku + Flask + LINEbot)
「サイゼリヤで1000円あったら最大で何kcal取ることができるんだろう？」と。
最近、最適化計算を得意とする量子アニーリングの勉強を始めたこともあって、ナップザック問題をそのまま使えば、計算できるんじゃないか？と思い、早速実験してみました。
ナップザック問題とは
ナップザック問題とは重量制限のあるリュックに、値段と重さが定義されたアイテムを詰め込むとき、値段を最大化させるアイテムの組み合わせは何か？というものです。
今回は、重量ではなく値段に制限があり、アイテムの価値でなくkcalを最大化させるので
・アイテムの重さ → メニューの値段
・アイテムの価値 → メニューのキロカロリー数
で置き換えて計算を進めます。
必要な知識
- Pythonの基本文法
- 量子アニーリングにおけるQUBOモデルの理解
- 量子アニーリングにおけるハミルトニアンの定式化方法
ハミルトニアンの定式化などを書くと、とても長い記事になってしまうので、僕が勉強する上でためになった論文やリンクを貼っておきますね。
QUBOモデルとハミルトニアンの定式化を理解する上で役立ったリンク
ハミルトニアンの定式化
ナップザック問題のハミルトニアンで最も有名なものが下のパターン１です。
パターン１
H = \lambda \Big(1 - \sum_{n=1}^W y_n \Big)^2 + \mu \Big(\sum_{n=1}^W n y_n - \sum_{i=1}^N w_i x_i \Big)^2 -\sigma \sum_{i=1}^{N}c_{i} x_{i}
| 文字 | 説明 |
|---|---|
| $W$ | リュックの重量 (定数) |
| $c$ | アイテムの価値。$i$番目にはアイテムiの価値が入る($N$次元ベクトル) |
| $y$ | リュックの重量をあらわすバイナリ変数。$y_i=1$かつ$y_j=0 (i \neq j)$のときリュックの重量は$i$ ($W$次元ベクトル) |
| $x$ | どのアイテムが選ばれたかを示すバイナリ変数。$x_i=1$のとき、$i$番目のアイテムは選択されている。($N$次元ベクトル) |
| $\lambda, \mu, \sigma, \omega$ | ハミルトニアンの重さを操作する定数 (ここの操作が超重要) |
しかし、これでうまくいかなかったことから、アレンジを加えてさらに３つのハミルトニアンを自分で作って実験をしてみました。
パターン２
H = \mu \Big(W - \sum_{i=1}^N w_i x_i \Big)^2 - \sigma \sum_{i=1}^{N}c_{i} x_{i}
パターン３
H = \lambda \Big(W - \sum_{n=1}^W n y_n \Big)^2 + \mu \Big(\sum_{n=1}^W n y_n - \sum_{i=1}^N w_i x_i \Big)^2 -\sigma \sum_{i=1}^{N}c_{i} x_{i}
パターン４
H = \omega \Big(1 - \sum_{n=1}^W y_n \Big)^2 + \lambda \Big(W - \sum_{n=1}^W n y_n \Big)^2 + \mu \Big(\sum_{n=1}^W n y_n - \sum_{i=1}^N w_i x_i \Big)^2 -\sigma \sum_{i=1}^{N}c_{i} x_{i}
これをもとに最適解を求めます。
プログラムとハミルトニアンの式変形
プログラムとハミルトニアンの式変形は、ここで説明するのにはあまりにも長くなってしまうので、こちらにまとめておきました。より技術的な話や私の考察もここに書いておきました。もしお時間があればご覧ください。
https://github.com/hodaka0714/saize_calory_maxmization
数式がGitHub上では少々読みにくくなっているので、git cloneをすると確認しやすくなります。
量子アニーリングでは確率的に計算をするので、古典的なコンピュータとは違い、これが正解ですと断定することはできません。プログラムの実行結果にはムラができてしまいます。
count : 1
y=1のindexは []番目.
selected : #71 (name : アラビアータ(Wサイズ), weight : 770, cost : 1182)
selected : #106 (name : シナモンフォッカチオ, weight : 169, cost : 246)
total price : 939
total kcal : 1428
count : 2
y=1のindexは []番目.
selected : #25 (name : ポテトのグリル, weight : 199, cost : 366)
selected : #71 (name : アラビアータ(Wサイズ), weight : 770, cost : 1182)
total price : 969
total kcal : 1548
count : 3
y=1のindexは []番目.
selected : #65 (name : タラコソースシシリー風, weight : 399, cost : 605)
selected : #67 (name : パルマ風スパゲッティ, weight : 399, cost : 700)
selected : #101 (name : ライス, weight : 169, cost : 303)
total price : 967
total kcal : 1608
.
.
.
あらかじめご了承ください。
実験結果
最終的に300回ほど計算を行い、その中からうまくいった結果をランキング形式で発表します。
「1000円で高カロリーが取れるメニューの組み合わせランキング！！！」
さあいってみましょう!!
第3位
コンセプト： 「パスタをおかずに飯を食う」
イメージ図：
| メニュー | 値段 | 熱量 |
|---|---|---|
| ライス | 169円 | 303kcal |
| ラージライス | 219円 | 454kcal |
| アーリオ・オーリオ(Wサイズ) | 574円 | 1120kcal |
| 合計 | 962円 | 1877kcal |
第2位
コンセプト： 「アーリオ・オーリオ3人前にフォッカチオをそえて」
イメージ図：
| メニュー | 値段 | 熱量 |
|---|---|---|
| フォッカチオ | 119円 | 214kcal |
| アーリオ・オーリオ | 299円 | 560kcal |
| アーリオ・オーリオ(Wサイズ) | 574円 | 1120kcal |
| 合計 | 992円 | 1894kcal |
第1位
コンセプト： 「炭水化物オールスターズ」
イメージ図：
| メニュー | 値段 | 熱量 |
|---|---|---|
| ポテトのグリル | 199円 | 366kcal |
| ラージライス | 219円 | 454kcal |
| アーリオ・オーリオ(Wサイズ) | 574円 | 1120kcal |
| 合計 | 992円 | 1940kcal |
まとめ
炭水化物が選ばれやすいということがわかりました。個人的にはピザが選ばれるのかなと予想していましたが、アーリオ・オーリオがカロリーのコスパ最強であることを発見しました。
この結果はあくまで確率的に得られた結果なので、必ずしも正しいランキングとはならないことをご了承ください。
厳密にナップザック問題を解こうとお考えの方は動的計画法などのアルゴリズムを参考に計算することをおすすめします。
最後に
「最適化問題とWildqatを用いた量子アニーリング計算入門」というタイトルの本を下のリンクで販売しています。もし興味がございましたらご一読ください。
https://hodaka.booth.pm/items/1415833
この記事に関して、プログラムや計算式に間違いがございましたら、ご指摘いただけると幸いです。
最後までお付き合いいただき、ありがとうございました。