Edited at

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

こんにちは!初投稿です!

この記事が誰かに何かでためになれば幸いです!


背景

僕は先日、この記事↓↓を読んでふと思いました。

サイゼリヤ1000円ガチャをつくってみた(Heroku + Flask + LINEbot)

サイゼリヤで1000円あったら最大で何kcal取ることができるんだろう?」と。

最近、最適化計算を得意とする量子アニーリングの勉強を始めたこともあって、ナップザック問題をそのまま使えば、計算できるんじゃないか?と思い、早速実験してみました。


ナップザック問題とは

ナップザック問題とは重量制限のあるリュックに、値段と重さが定義されたアイテムを詰め込むとき、値段を最大化させるアイテムの組み合わせは何か?というものです。

今回は、重量ではなく値段に制限があり、アイテムの価値でなくkcalを最大化させるので

アイテムの重さ → メニューの値段

アイテムの価値 → メニューのキロカロリー数

で置き換えて計算を進めます。


必要な知識


  • Pythonの基本文法

  • 量子アニーリングにおけるQUBOモデルの理解

  • 量子アニーリングにおけるハミルトニアンの定式化方法

ハミルトニアンの定式化などを書くと、とても長い記事になってしまうので、僕が勉強する上でためになった論文やリンクを貼っておきますね。

QUBOモデルとハミルトニアンの定式化を理解する上で役立ったリンク




ハミルトニアンの定式化とQUBOモデルのチュートリアル。

https://arxiv.org/abs/1811.11538





最適化問題のQUBOモデルへの落としかた

https://arxiv.org/abs/1302.5843



ハミルトニアンの定式化

ナップザック問題のハミルトニアンで最も有名なものが下のパターン1です。


パターン1

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$
ハミルトニアンの重さを操作する定数 (ここの操作が超重要)

しかし、これでうまくいかなかったことから、アレンジを加えてさらに3つのハミルトニアンを自分で作って実験をしてみました。


パターン2

H = \mu \Big(W - \sum_{i=1}^N w_i x_i \Big)^2  - \sigma \sum_{i=1}^{N}c_{i} x_{i}


パターン3

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}


パターン4

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


まとめ

炭水化物が選ばれやすいということがわかりました。個人的にはピザが選ばれるのかなと予想していましたが、アーリオ・オーリオがカロリーのコスパ最強であることを発見しました。

この結果はあくまで確率的に得られた結果なので、必ずしも正しいランキングとはならないことをご了承ください。

厳密にナップザック問題を解こうとお考えの方は動的計画法などのアルゴリズムを参考に計算することをおすすめします。


最後に

この記事に関して、プログラムや計算式に間違いがございましたら、ご指摘いただけると幸いです。

最後までお付き合いいただき、ありがとうございました。