@yuichirominato 2019.01.19更新 678views

【コーヒー】量子コンピュータでコーヒーブレンド最適化

イジング 最適化

はじめに

弊社MDRは量子コンピュータを作ったり活用している企業ですが、そんな中アルゴリズムを使ってなんかできないかということで、最適化のネタを探していましたが、身近にあります。そんな試みを勉強会として実行しましたのでここに報告します。

コーヒーブレンド最適化勉強会

MDRでは、1800名以上のグループのメンバーを抱える量子コンピュータの勉強会を毎週行っています。2年半で開発の傍ら毎週勉強会を行ってきましたが、より実践的なものをしたいということで、コーヒーブレンドの最適化を実行しました。

https://qnn.connpass.com/event/113875/
勉強会自体は終わりました。

こんな感じです。実際にコーヒーを入れました。早速概要を見てみましょう。

きっかけはドレッシング

手順は1/18にMDR株式会社に人が集まりました。人は10名。まずは簡単な説明から。

量子コンピュータを活用してコーヒー最適化をしますが、これには元ネタがあります。実は以前ABCクッキングスタジオさんという料理教室でドレッシングのレシピを使ってそこから新しいドレッシングを機械学習(人工知能)で作るということをやりました。

https://www.abc-cooking.co.jp/

その時は美味しいドレッシングができたので、それを量子コンピュータを使いたいなというのが元ネタです。

最適化に使うマシン

マシンは最適化ができるD-Waveマシンか量子ゲートマシンをつかいます。使い方は量子アニーリングと呼ばれる最適化アルゴリズムやQAOAと呼ばれる量子ゲートマシン向けのアルゴリズムが使えます。

最近Blueqatと呼ばれるツールにこういう計算をする機能がついています。しかも!最近は量子アニーリングも量子ゲートも計算できますので、どのように最適化計算をするかは下記を参照くださいませ。。。

早速チーム分け

まずはチーム分けです。チームを分けて進めます。簡単にいうとコーヒー準備係とアルゴリズム係に別れました。

チーム1:コーヒーの調達、水の調達など
チーム2:アルゴリズムの開発

チーム1は6人。チーム2は4人。

物品調達

ということで調達が始まりました。調達チームは、紙コップ、コーヒー5種類、カップ、ロート、ペーパーフィルター、口直しの水、混ぜるはしなどです。百円ショップやスーパーへ。

手際がいいです。

アルゴリズム

肝心のアルゴリズムはその場で作ります。まずは全体の手順を考えます。近くにアルゴリズム名人がいましたので、ざっくり聞きました。

最適化は一番低いところを見つけるアルゴリズムです。今回は一番低いところを選ぶと一番美味しくなるようにします。今回は少しずつ美味しさを改善していきます。

まず入れるコーヒーの量を考えました。こちらは経験的に五種類のコーヒーをブレンドすることにしました。

次にどのように混ぜるかですが、これも経験的に一度に三種類のコーヒーを混ぜることになりました。二種類でもいいらしいです。

さらに混ぜ方を工夫した方がいいようです。こちらは「メジャー」と「マイナー」をつくって、メジャーは分量多め、マイナーは分量少なめにするようです。分量はメジャー1種類2に対して、マイナー2種類を1ずつ混ぜることになりました。2:1:1です。

初期のコーヒーはブレンドはランダムでできます。ただ、初期はグラフを探すためになるべく満遍なく偏りがないブレンドがいいようです。その方が低い値を探すときにいいようです。最初は頭で考えてやってもらいました。大体人間の頭でやると10分くらいかかるようです。五種類の中から三種類選ぶと全部で十種類できます。さらに、その十種類の中で分量にメジャー、マイナーがあるので、全部で30通りあります。その中で十種類を評価することになりました。

こちらが初期生成です。

ABCDEは粉の種類です。

こちらでやりました。

最適化をどこで使うかに議論となりました。基本的には最適化の探索でまずはブレンドするものにばらつきを作るために使おうということになりました。

ばらつきを作る

ブレンドするときに、色々な味を味わいたいのでばらつきを持ってやりたいです。しかし適当にランダムでやるとどうしてもばらつきがでます。なぜなら選んだブレンドのコーヒーは好みや先入観が付いていて、もともとデータは偏りがあるからです。

より良い探索をするために、まずいい「ばらつき」をつくろうということになりました。まず必要なばらつきは「メジャー」と「マイナー」の分量を決めるアルゴリズムが必要となりました。

コーヒーを三種類選んだ上で混ぜる分けですが、そのなかで一種類は多く注ぎます。その1つを選びますが、十種類のブレンドされたコーヒーはどうしてもメジャーとして選ばれたコーヒーがたくさん注がれますので、メジャーがかぶると味が同じになってしまう可能性があるので、なるべくばらつきをつくります。

まず最初に五種類から三種類選ぶのは全部で十種類あります。そのなかで、選ばれた3つの中から1つだけ選びます。その際に制約条件があります。1つのコーヒーの組み合わせに対して選ばれる量子ビットは1なので、条件式は、

$$\sum(\sum x_n – 1)^2 = 0$$

こうなります。3量子ビットから1選ぶアルゴリズムです。

次にコスト関数です。小さくしたいのは混雑なので、混雑緩和のコスト関数は、ABCDEそれぞれ選ばれたコストを二乗すると混雑コストになりますので、

$$(\sum y_A)^2+(\sum y_B)^2+(\sum y_C)^2+(\sum y_D)^2+(\sum y_E)^2$$

となります。これで一応やってみることにしました。

コスト関数と制約条件をハイパーパラメータ$\lambda$でつなぎます。

$$E = \sum(\sum x_n-1)^2+\lambda \sum(\sum y_n)^2$$

ばらつきを作る2

どうやら最適化名人によるともう1つばらつきを作る必要があります。今回は飲んで評価がよかったものから2つを選んで次の世代のコーヒーを作ります。選んだ2つのうち共通するコーヒーがあったら必ず採用します。

たとえば、ABCとABDが選ばれた場合には、AB共通なので、つぎのコーヒーもABを使います。最後の1つはCとDのどちらを使うかですが、これも全体の中でばらつきがあった方がいいです。

式は、

$$\sum(\sum x_n -k)^2 + \lambda_2 \sum(\sum y_n)^2$$

となりました。横方向は選んだ組み合わせによってkが変わります。縦はすべて足し合わせてコスト関数を作ります。

また、突然変異で多少ランダム性をいれてもいいのではということで少し局所磁場というパラメータをいじりながらランダム性を入れてみます。

注ぐ

コーヒーを注ぎ始めますが、美味しいお水を購入し、お湯を作って注ぎます。もちろんトラブル起きます。

いれます。。。

こなが落ちました。。。

改善してたまりました。混ぜます。

いれました。こちらの元ブレンドコーヒーを少しずつ自分のコップに注いでいきます。コップは大量にあります。

飲んでみると、、、

飲んでみるとみんなで?????となりました。どうやらAのコーヒーが濃い。

Aだけインスタントでした。インスタントコーヒーは分量間違えたぽくて味が濃いです。

さて、実際には10名のなかから代表2名を選び、その人たちは全部を飲んできちんと評価してもらいました。

一人目です。評価が相対評価でも、絶対評価でも順位をつけてもらいます。どうやらやっぱりAが入ってると、、、のようです。4>1>3>2>8の順になりました。

二人目です。4>2>3>1>最後は8?になりました。結構一人目と似てますね。

どうやら飲んでみた人によると4が美味しかったようです。

たくさんコーヒー飲むのめちゃ大変です。口直しのお水必須です。

早速最適化

評価が良かった上位は、、、一人目は、41328、二人目は42318、、、全く一致しました。こちらをもとに新しい組み合わせを作ってみます。

12348は、

参考の表

ECD
DBE
EBC
BCD
BAE

この辺りが選ばれました。早速次世代を作ってみます。ちょっと並べ替えます。

CDE
BDE
BCE
BCD
ABE

次に組み合わせを作ります。

上記選ばれた組み合わせから次世代を作ります。共通した項目はそのまま残し、三種類の選択をするために、制約式を作ります。ここでは量子ビットの節約のために複雑なことをしていますが、節約しないで50量子ビット使う場合には、下記のようでも大丈夫です。

横に足し合わせて制約条件、縦に足し合わせて二乗するとコスト関数になるmatrixです。

利用する量子ビットに通し番号を振ります。今回は特別に突然変異を考えてローカルミニマムからの脱出も考慮に入れて、白いマス目も突然変異枠として使います。突然変異枠の白枠と選択肢のオレンジは局所磁場hの値を微妙に変更して優先度を変更します。

まずは制約条件を1行ずつ横に見ていくと下記の通りに。青いところはすでに選ばれているので考慮しません。

E2 = (q0+q10+q14-1)^2+(q1+q11+q15+q22-2)^2+(q2+q12+q29-1)^2+(q3+q13+q16+q23-2)^2+(q4+q17+q24-1)^2+(q5+q18+q30-1)^2+(q6+q19+q25-1)^2+(q7+q26+q31-1)^2+(q8+q20+q27-1)^2+(q9+q21+q28+q32-2)^2

次にコスト関数。ABCDEとそれぞれ縦に足し合わせて2乗します。ここで注意は、青い部分は無視できないので、算入する必要があります。コスト関数は下記の通り、

E1=(q0+q1+q2+q3+q4+q5+q6+q7+q8+q9)^2+(q10+q11+q12+q13+6)^2+(q14+q15+q16+q17+q18+q19+q20+q21+2)^2+(q22+q23+q24+q25+q26+q27+q28+3)^2+(q29+q30+q31+q32+6)^2

このコスト関数を最小にすることでうまく次世代のコーヒーブレンド組み合わせを最もスパースにできます。

突然変異枠もいれてみます。こちらには突然変異枠と選択枠の間に局所磁場で重みを変えてみました。

コード実装

これを足し合わせてコード化して計算します。今回はつい先日統合されたBlueqatを使います。このためにちょっと関数作りました。

from blueqat import opt

a = opt.opt()

E1 = opt.optm("(q0+q10+q14-1)^2+(q1+q11+q15+q22-2)^2+(q2+q12+q29-1)^2+(q3+q13+q16+q23-2)^2+(q4+q17+q24-1)^2+(q5+q18+q30-1)^2+(q6+q19+q25-1)^2+(q7+q26+q31-1)^2+(q8+q20+q27-1)^2+(q9+q21+q28+q32-2)^2",33)

E2 = opt.optm("(q0+q1+q2+q3+q4+q5+q6+q7+q8+q9)^2+(q10+q11+q12+q13+6)^2+(q14+q15+q16+q17+q18+q19+q20+q21+2)^2+(q22+q23+q24+q25+q26+q27+q28+3)^2+(q29+q30+q31+q32+6)^2",33)

E3 = opt.diag([1,1,1,0,1,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0])

a.qubo = 0.05*E2+E1+0.1*E3
result = a.sa()

print(result)                                                                                                                                                                         
#=> [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]

結果

選ばれた量子ビットは赤いところです。青いところと合わせるとすべての列で6量子ビットずつ選ばれて、偏りなくきちんと疎になっているのがわかります。ということで、次世代の組み合わせは、

CDE
ACE
BCD
ADE
BDE
BCD
ABE
BCD
ABE
ABE

被ってるのを除くと、、、

ABE
ACE
ADE
BCD
BDE
CDE

ちょっと種類が少なすぎたかな。。。もうちょい最適化の種類が多くても大丈夫のようですね。

続いてメジャー、マイナーを決める

続いて上記の六種類において、分量の調合のバランスを決めるアルゴリズムです。

メジャーマイナーを決めるために再度表にまとめました。

制約条件はメジャーを1つ選ぶので行ごとに

E1 = (q0+q3+q13-1)^2+(q1+q6+q14-1)^2+(q2+q9+q15-1)^2+(q4+q7+q10-1)^2+(q5+q11+q16-1)^2+(q8+q12+q17-1)^2

コスト関数はできるだけばらけるように、

E2 = (q0+q1+q2)^2+(q3+q4+q5)^2+(q6+q7+q8)^2+(q9+q10+q11+q12)^2+(q13+q14+q15+q16+q17)^2

全部で18量子ビット使います。

実装

実装します。Blueqatつかって、

from blueqat import opt 

a = opt.opt()
E1 = opt.optm("(q0+q3+q13-1)^2+(q1+q6+q14-1)^2+(q2+q9+q15-1)^2+(q4+q7+q10-1)^2+(q5+q11+q16-1)^2+(q8+q12+q17-1)^2",18) 

E2 = opt.optm("(q0+q1+q2)^2+(q3+q4+q5)^2+(q6+q7+q8)^2+(q9+q10+q11+q12)^2+(q13+q14+q15+q16+q17)^2",18) 

a.qubo = 0.05*E2+E1 
result = a.sa() 

print(result)                                                                            
#=>[1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0]

結果は、

赤いのがメジャー(分量2)、その他のオレンジがマイナー(分量1)です。

ですので、次世代ブレンドは、、、(メジャー):(マイナー)ブレンドをとって、

A:BE
E:AC
D:AE
D:BC
B:DE
C:DE

このようになりました!

今後の展開

コーヒーブレンドはとても面白かったです!

色々アクシデントや予想外のことがありながら、イジング計算と最適化について新しい知見を得ることができました。

実際に組み合わせを考えるときに、一番最初に人間の手でやった際には頭を使い時間もかかりましたが、イジング計算では一瞬で出ます。

また、今後の展開ですが準備の時間などが大変で混ぜるのも大変なので、その辺りをファクトリーオートメーションの技術を使って、自動ブレンドと自動最適化を組み合わせながら、最適化工程の時間のかかるところを高速化してみます!

今回はこんな感じで一旦お開きでしたが、引き続きどんどん改善していきます!

みなさまおつかれさまでした!

Recommended


CONTACT

info@mdrft.com

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方