Saitekika
開発目的
身近なファミレスをお得で健康に楽しむ方法を開発する
システム概要
予算内で高カロリー・低塩分に注文するメニューの組み合わせを探す
システム詳細
1 . 対象店舗の決定
よりこのシステムを意義ものあるためにするには、対象店舗が多くの人々にとって馴染みのものにする必要性がある。そこで全国的に展開されていて日本人に最も親しみの深いファミレスの1つと言えるサイゼリヤを今回の対象とする。
サイゼリヤのグランドメニューがネット上で公開されているため、そこにj掲載されているメニューを本システムの対象として扱う。
2 . 予算の設定
学生間で執り行われる飲み会代として一般的と考えられる
¥3,000
を今回の使用可能な予算に設定する。
3 . 定式化
この問題は以下のように定式化できる
上限金額 ]
上限塩分量 ]
番目の注文メニューの金額
]
番目の注文メニューの塩分
]
番目の注文メニューのカロリー
]
としたとき
制約関数
において
評価関数
を最大にする注文の組み合わせを見つける。
ここで評価関数について
・塩分量は少なく
・総カロリーは多く
・金額は多く使った方が多くの料理を注文できる
という点を考慮して以下のように定義した。
4 . 使用するアルゴリズムの決定
ここで注文した各料理に対しての評価関数を
と置くと
と書ける。
ここまでを踏まえると以上は
重量制限を総金額,総塩分の制限に、
総価値の最大化を評価関数の合計の最大化に置き換えたナップサック問題1の応用であるとみなすことが出来る。以下、サイゼリヤ問題と呼ぶこととする。
以上より、今回の問題は制約関数が一つ多いナップサック問題の応用に帰着することができた。ナップサック問題はNP困難2であるため、最適解を求めるのに今回は遺伝的アルゴリズムを用いて最適解に近い組み合わせを求めることに決める。
結果
上記で定めたサイゼリヤ問題を遺伝的アルゴリズムで解くとtable1のような近似最適解が得られた。
table1
考察
table1を見るとアルコールがあり実に楽しそうな結果が得られた。
このようになった理由は評価関数にあると考えられる。
いまは以下のように定義されている。
塩分の総量が分母にあるため
になるような注文方法だと評価関数が無限大に発散してしまう。
また、塩分のオーダーは高々なのに対して金額やカロリーのオーダーは高々
である。
これでは評価関数内でそれぞれのパラメータを同等に扱えていない。
今回のケースでは、分母にあるオーダーの小さい塩分が他の二つよりも大きな影響を与えてしまっていることになる。
以上二つの理由より、評価関数の見直しが必要である。
ここで以下のように改めて評価関数を定める。
こうすることにより ・0除算による評価関数の発散 ・金額/カロリー/塩分 のパラメータのオーダー違い を解決することが出来る。
上の場合と同様に
とすることで
と書けるので、相変わらず遺伝的アルゴリズムによって近似解が求められる。サイゼリヤ問題に新しい評価関数を適用した問題をサイゼリヤ問題(改)と呼ぶことにする。
このサイゼリヤ問題(改)に対して再度遺伝的アルゴリズムを適用して最適なメニューの組み合わせを求める。
結果 その2
サイゼリヤ問題(改)に対して遺伝的アルゴリズムを用いたところ、table2のような近似最適解が求められた。
table2
結論
サイゼリヤを健康に楽しむためには酒類と炭水化物を大量に注文することが有効であることが本システムによって解明された。
これは他のファミリーレストランチェーンに対しても言えるのではないかと考えられるが、その一般性についての検証は今後の課題としたい。
1 . ナップサック問題
重量と価値の2つのパラメータを持つ色々な種類のお宝が目の前にある。
重量制限があるナップサックを用意し、総重量の制限内で価値最大となるお宝の持ち帰りの組み合わせを求める問題である。
NP困難であることが証明されている。
2 . NP困難
正面から戦うと時間がかかり過ぎてとても解けない問題
