はじめに
こんにちは!keisukeです.
今回は,QUBOモデル(特に,二次割当問題)におけるエネルギー関数を詳しく見ていきます.
「アニーリングマシンで問題を解く!」の1個前の段階のお話です.
TL;DR
- 二次割当問題とは
- 二次割当問題をQUBOモデルに落とし込む
- 二次割当問題のエネルギー関数を展開して,エネルギー関数の中身を詳しく見る.
二次割当問題(QAP)
二次割当問題,通称QAPでは,複数の工場と,工場と同数の地区が与えられます.
任意の工場間には物流量が,任意の地区間には距離が定義されています.
二次割当問題とは,「各工場間の物流量」と「工場が割り当てられた各地区間の距離」の積の総和が最小となるような,工場の地区への割り当てを求める問題です.
ではここからは,QAPを定式化していきましょう.
F 個の工場の集合を Fac={f1,f2,...,fF},工場を割り当てるための F 個の地区の集合 Loc={l1,l2,...,lF} と定義します.
任意の工場間には物流量が与えられており,工場 fi,fj(1≤i,j≤F) 間の物流量を w(fi,fj) とします.
また,任意の地区間にも距離が与えられており,工場 fi が割り当てられた地区と工場 fj が割り当てられた地区間の距離を d(fi,fj) とします.
したがって,「各工場間の物流量」と「工場が割り当てられた各地区間の距離」の積の総和 C は,次の式(1)のように表せます.
C=i=1∑F−1j=1,i+1∑Fw(fi,fj)d(fi,fj)(1)
なお,QAPには以下の2つの制約があります.
- 工場配置制約:任意の工場はただ一つの地区にのみ必ず配置する
- 地区内工場制約:任意の地区にはただ一つの工場が割り当てられる
以上がQAPの問題定義および定式化(とその制約)です.
QUBOモデルに落とし込む
その前に
QAPをQUBOモデルに落とし込む際,以下のようなバイナリ変数を定義します.
xi,k={10(工場fiを地区lkに配置するとき)(上記以外)(2)
コスト関数
コスト関数は,「各工場間の物流量」と「工場が配置された各地区間の距離」の積の総和です.
エネルギー関数は次のように書けます.
HA=i=1∑Fj=1∑Fk=1∑Fl=1∑Fw(fi,fj)d(lk,ll)xi,kxj,l(3)
HA の最小値は ha をとります.
ha は問題に依存します.
制約項1:工場配置制約
これは,i 番目の工場 fi はただ一つの地区にのみ配置するという制約です.
本制約をある時刻 i 番目の工場 fi について定式化すると,次の式のようになります.
k=1∑Fxi,k=1 (1≤i≤F)(4)
全ての工場 fi が上の式(4)を満たすときに,最小値をとるようなエネルギー関数 HB を導入すると,エネルギー関数は次のように書けます.
HB=i=1∑F(k=1∑Fxi,k−1)2(5)
HB の最小値は 0 をとります.
制約項2:地区内工場制約
これは,k 番目の地区 lk にはただ一つの工場が配置されているという制約です.
本制約を k 番目の地区 lk について定式化すると,次の式のようになります.
i=1∑Fxi,k=1 (1≤k≤F)(6)
全ての地区 lk が上の式(6)を満たすときに,最小値をとるようなエネルギー関数 HC を導入すると,エネルギー関数は次のように書けます.
HC=k=1∑F(i=1∑Fxi,k−1)2(7)
HC の最小値は 0 をとります.
最終的なエネルギー関数
以上より,最終的なエネルギー関数は,正のハイパーパラメータα を用いて次のように表せます.
H=HA+α(HB+HC)(8)
エネルギー関数 H は最小値 ha を取り,このとき基底解となります.
基底解が得られたときのスピンが最適解となります.
なお,エネルギー関数 H には定数項が出現しますが,本質的にはあってもなくても変わらないので,今回は定数項は無視します.
エネルギー関数を展開する
再掲ですが,QAPのエネルギー関数は以下の3つから構成されています.
HAHBHC=i=1∑Fj=1∑Fk=1∑Fl=1∑Fw(fi,fj)d(lk,ll)xi,kxj,l=i=1∑F(k=1∑Fxi,k−1)2=k=1∑F(i=1∑Fxi,k−1)2
これらのエネルギー関数を何かしらのプログラミング言語で実装しようとしたとき,どうやって書けば良いか困ってしまうことはありませんか?
HA はfor
ループを4つ使って愚直に書けば良さそうですが,HB,HC はシグマの中にシグマの2乗が含まれています.これは難しそうだ…
でも大丈夫!!!
ここから下を読めば,一発で分かります.
ということで早速,HB,HC を展開していきましょう.
HB の展開
HB を展開します.
HB=i=1∑F(k=1∑Fxi,k−1)2=i=1∑F(2k=1∑F−1l=k+1∑Fxi,kxi,l−k=1∑Fxi,k+1)=2i=1∑Fk=1∑F−1l=k+1∑Fxi,kxi,l−i=1∑Fk=1∑Fxi,k+F
なぜ1行目から2行目になるのか?
これは簡単な例で試してみると,そうなることが分かります.
ここでは,工場数 F=4 の場合で考えてみましょう.
(以下,2乗の部分だけを計算するので,HB の一番外側のシグマ ∑i=1F は除外します)
(k=1∑F=4xk−1)2=((x1+x2+x3+x4)−1)2=x12+x22+x32+x42 +2x1x2+2x1x3+2x1x4 +2x2x3+x2x4+2x3x4 −2x1−2x2−2x3−2x4+1 (…変数xkはバイナリ変数なのでxk2=xkとなるから)=2(x1x2+x1x3+x1x4+x2x3+x2x4+x3x4) −x1−x2−x3−x4+1=2k=1∑4−1l=k+1∑4xkxl−k=1∑4xk+1=2k=1∑F−1l=k+1∑Fxkxl−k=1∑Fxk+1
ほら!これで展開ができました.
お前ホンマかいな…という人は,神ツールである
Wolfram alphaで計算させた結果もご覧になってください.
… というわけで,エネルギー関数に2乗が含まれている場合も,今回の展開で最終的に得られた式をプログラムに落とし込めば,うまく行きそうですね!(というかうまく行きます笑)
HC の展開も,扱う文字が違うだけで内容はほぼ全く同じなので,ぜひ練習として HC を展開してみてください.
おわりに
今回は,QUBOモデルで頻繁に出てくる2乗式を詳しく見ました.
このように,実際に手を動かすことが大事となってくるので,皆さんもQUBOと格闘する時はどんどん手を動かしていきましょう!