More than 3 years have passed since last update.

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

Last updated at 2020-11-11Posted at 2019-05-15

こんにちは！初投稿です！
この記事が誰かに何かでためになれば幸いです！

背景

僕は先日、この記事↓↓を読んでふと思いました。
サイゼリヤ1000円ガチャをつくってみた(Heroku + Flask + LINEbot)

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

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

ナップザック問題とは

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

今回は、重量ではなく値段に制限があり、アイテムの価値でなくkcalを最大化させるので
・アイテムの重さ　→　メニューの値段
・アイテムの価値　→　メニューのキロカロリー数
で置き換えて計算を進めます。

必要な知識

Pythonの基本文法
量子アニーリングにおけるQUBOモデルの理解
量子アニーリングにおけるハミルトニアンの定式化方法

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

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

ハミルトニアンの定式化とQUBOモデルのチュートリアル。 [https://arxiv.org/abs/1811.11538](https://arxiv.org/abs/1811.11538 "A Tutorial on Formulating and Using QUBO Models")

最適化問題のQUBOモデルへの落としかた [https://arxiv.org/abs/1302.5843](https://arxiv.org/abs/1302.5843 "Ising formulations of many NP problems")

ナップザック問題のハミルトニアン [https://quantum.fixstars.com/introduction_to_quantum_computer/quantum_computer_research/np_problem_ising/knapsack/](https://quantum.fixstars.com/introduction_to_quantum_computer/quantum_computer_research/np_problem_ising/knapsack/ "整数重みナップサック問題")

ナップザック問題のハミルトニアンの式変形[ https://github.com/Wildqat/Wildqat/blob/master/examples_ja/tutorial011_knapsack_with_integer_weights.ipynb]( https://github.com/Wildqat/Wildqat/blob/master/examples_ja/tutorial011_knapsack_with_integer_weights.ipynb "Knapsack With Integer Weights問題")

ハミルトニアンの定式化

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

パターン１

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