Posted at

イジングモデルでシフトを組むなど


はじめに

イジングモデルと呼ばれるモデルで社会問題を組み立てるといろいろな使い方ができます。これまではあまり具体的なノウハウは表に出してきませんでしたが、仕事が落ち着いてきたので、片っ端から社会問題をイジングモデルに落とし込んでみます。

問題のパターンを見れば大体の落とし方のコツがわかるはずです。


シフトを組む

シフトを組んでみます。仕事をする上では制約条件と呼ばれる満たすべき条件があります。また、コスト面での条件もありますのでその両方を満たすものを考えてみます。

今回のシフトは制約条件面の要請が強いのでいくつか考えて当てはめてみます。


シフト総数10のシフトをとりあえずうめる

3名のシフトに対して10時間のシフトを埋めてみます。下記のような状況で10時間の労働を埋めてみます。大きな問題はこれを一般化すれば解けます。

スクリーンショット 2019-08-24 21.32.29.png

Aさん、Bさん、Cさんのシフトがあり、グレーは入れないところです。入れるところをq0からq13を割り振りました。ここで、入れたいシフトは、10こですので、上記のq0からq13までのうちで、10が1に残りが0になればOKです。

14の量子ビットから10選ぶ問題と同じです。ハミルトニアン、コスト関数は、

H = (\sum_{i=0}^{13}q_i -10)^2

blueqatで解いてみます。

from blueqat.opt import Opt

Opt().add('(q0+q1+q2+q3+q4+q5+q6+q7+q8+q9+q10+q11+q12+q13-10)**2').run()

答えは、

 [1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1]

こうなりました。数ある答えがありますので、上記そのものでなくても、10こ1で4こ0が出てくればOKです。

スクリーンショット 2019-08-24 21.38.10.png

このように解けました。


なるべく少ない人でシフトを組む

上記は適当に振りました。2人でも組めなくもないシフトです。人数を減らすには、制約条件をつけます。

制約条件は上記同様ですが、そこにコスト関数を加えます。加えるコスト関数は、

H = -(q0+q1+q2+q3+q4)^2 + -(q5+q6+q7+q8+q9)^2 + -(q10+q11+q12+q13)^2

こうなります。こうすると少ない人数で解いた方がコストが低くなります。この式にハイパーパラメータをかけて実行します。今回は0.5をかけて実行してみました。

Opt().add('(q0+q1+q2+q3+q4+q5+q6+q7+q8+q9+q10+q11+q12+q13-10)**2 - 0.5*((q0+q1+q2+q3+q4)**2 +(q5+q6+q7+q8+q9)**2 +(q10+q11+q12+q13)**2)').run()

答えが出ました。

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0]

blueqatももちょい使いやすくしてもいいですね。

スクリーンショット 2019-08-24 21.48.04.png

二人だけでシフトを回せました。


無駄をなくす

上記は無駄が多かったり、入ってない時間があります。今回は、9時から17時まで全部埋めるようなシフトを考えてみます。使う条件は、q5,q6,q3,q4は入らないといけないことが自明なのでのぞいたとして、その他を考えてみます。各時間ごとに制約条件を作って、

H = (q8+q10-1)^2+(q0+q9+q11-1)^2+(q1+q12-1)^2+(q2+q13-1)^2

これでいけます。

Opt().add('-q5-q6-q7-q3-q4+(q8+q10-1)^2+(q0+q9+q11-1)^2+(q1+q12-1)^2+(q2+q13-1)^2').run()

とくと、、、

[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1]

こうなりました。

スクリーンショット 2019-08-24 21.54.19.png


まとめ

このようにシフトの総数や縦横の条件を組み合わせることで複雑な条件を作って解くことができます。以上です。