Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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

背景

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

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

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

ナップザック問題とは

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

backpack.png

今回は、重量ではなく値段に制限があり、アイテムの価値でなく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位

コンセプト: 「パスタをおかずに飯を食う」

イメージ図:
3_third.png

メニュー 値段 熱量
ライス 169円 303kcal
ラージライス 219円 454kcal
アーリオ・オーリオ(Wサイズ) 574円 1120kcal
合計 962円 1877kcal

第2位

コンセプト: 「アーリオ・オーリオ3人前にフォッカチオをそえて」

イメージ図:
2_second.png

メニュー 値段 熱量
フォッカチオ 119円 214kcal
アーリオ・オーリオ 299円 560kcal
アーリオ・オーリオ(Wサイズ) 574円 1120kcal
合計 992円 1894kcal

第1位

コンセプト: 「炭水化物オールスターズ」

イメージ図:
1_first.png

メニュー 値段 熱量
ポテトのグリル 199円 366kcal
ラージライス 219円 454kcal
アーリオ・オーリオ(Wサイズ) 574円 1120kcal
合計 992円 1940kcal

まとめ

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

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

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

最後に

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

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

hodaka0714
名古屋大学大学院情報学研究科M1。1年半ほど人工知能スタートアップでエンジニアとして働いていました。興味のある分野は、AI / 量子コンピュータ(アニーリング) です。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした