班決め最適化(エッジ総和最適化)
課題
どうやってコストハミルトニアンを定義する？
定義
グループの集合$ G、各グループを$ gと表記
グループの人数は$ n人
全ての人は集合$ V、各人を$ v
人間関係は重み$ w_{i,j}
/icons/hr.icon
定式化
$ Hc= P_g \sum_{v\in V} \left( \left(\sum_{g\in G} x_{v,g}\right)-1 \right)^2 + P_n \sum_{g\in G} \left( \left(\sum_{v\in V} x_{v,g}\right)-n \right)^2 - \sum_{g\in G}\sum_{(i,j)\in V} x_{i,g}x_{j,g}w_{i,j}
コスト
(1) グループ所属制約
各人は、1つのみグループに属する
$ \sum_{g\in G} x_{v,g}=1, \quad (\forall_v\in V)
このため、以下が成立する
$ x_{i,g}x_{j,g} = \begin{cases}1 \quad \text{(同グループ)} \\ 0 \quad \text{(異グループ)} \end{cases}
ペナルティ項は以下の通り
$ P_g\sum_{v\in V} \left( \sum_{g\in G} x_{v,g}-1 \right)^2
$ P_g：任意のペナルティ係数
(2) グループ人数制約
各グループの人数は$ n人である
$ \sum_{v\in V} x_{v,g}=n, \quad (\forall_g\in G)
$ P_n \sum_{g\in G} \left( \sum_{v\in V} x_{v,g}-n \right)^2
$ P_n：任意のペナルティ係数
(3) 目的関数
目的関数である各人間のペナルティスコアは、以下のように評価される
$ \sum_{(i,j)\in V} w_{i,j}
つまり、総合のペナルティスコアは以下のように評価される
$ -\sum_{g\in G}\sum_{(i,j)\in V} x_{i,g}x_{j,g}w_{i,j}
QUBO形式
コスト(1)〜(3)より、
$ H= P_g \sum_{v\in V} \left( \left(\sum_{g\in G} x_{v,g}\right)-1 \right)^2 + P_n \sum_{g\in G} \left( \left(\sum_{v\in V} x_{v,g}\right)-n \right)^2 - \sum_{g\in G}\sum_{(i,j)\in V} x_{i,g}x_{j,g}w_{i,j}
イジングモデル
$ x_{v,g} = \begin{cases}1 \\ 0 \end{cases}を量子状態にエンコードするため、Ising-QUBO変換を使用して1,-1に二値化。 第1項は、
$ P_g \sum_{v\in V} \left( \left(\sum_{g\in G} x_{v,g}\right)-1 \right)^2
$ = P_g\sum_{v\in V} \left( \left(\sum_{g\in G}x_{v,g}\right)^2 - 2\sum_{g\in G}x_{v,g} +1 \right)
$ = P_g\sum_{v\in V} \left( \sum_{g\in G}\sum_{g'\in G}x_{v,g}x_{v,g'} - 2\sum_{g\in G}x_{v,g} +1 \right) (シグマ二乗展開) $ =P_g \sum_{v\in V} \left( \sum_{(g,g')\in G} \frac{(1-\sigma_{v,g}^z)(1-\sigma_{v,g'}^z)}{4} - \sum_{g\in G}(1-\sigma_{v,g}^z) + 1 \right)
$ =P_g \sum_{v\in V} \left( \sum_{(g,g')\in G} \frac{(1-\sigma_{v,g}^z)(1-\sigma_{v,g'}^z)}{4} - \sum_{g\in G}(1-\sigma_{v,g}^z) \right) + P_g|V| $ ...(i)
第2項は、同様に
$ P_n \sum_{g\in G} \left( \left(\sum_{v\in V} x_{v,g}\right)-n \right)^2
$ =P_n \sum_{g\in G} \left( \sum_{(i,j)\in V} \frac{(1-\sigma_{i,g}^z)(1-\sigma_{j,g}^z)}{4} - n\sum_{v\in V}(1-\sigma_{v,g}^z)\right)＋P_nn^2|G| $ ...(ii)
第3項は、これ以上展開できないのでOK。
$ -\sum_{g\in G}\sum_{(i,j)\in V} x_{i,g}x_{j,g}w_{i,j} $ ...(iii)
(i)〜(iii)より、
$ H=$ P_g \sum_{v\in V} \left( \sum_{(g,g')\in G} \frac{(1-\sigma_{v,g}^z)(1-\sigma_{v,g'}^z)}{4} - \sum_{g\in G}(1-\sigma_{v,g}^z) \right) + P_g|V|
$ +P_n \sum_{g\in G} \left( \sum_{(i,j)\in V} \frac{(1-\sigma_{i,g}^z)(1-\sigma_{j,g}^z)}{4} - n\sum_{v\in V}(1-\sigma_{v,g}^z)\right)＋P_nn^2|G|
$ -\frac{1}{4}\sum_{g\in G}\sum_{(i,j)\in V} (1-\sigma_{i,g}^z)(1-\sigma_{j,g}^z)w_{i,j}
定数項はパラメータに依存しないので、
$ H=$ P_g \sum_{v\in V} \left( \sum_{(g,g')\in G} \frac{(1-\sigma_{v,g}^z)(1-\sigma_{v,g'}^z)}{4} - \sum_{g\in G}(1-\sigma_{v,g}^z) \right)
$ + P_n \sum_{g\in G} \left( \sum_{(i,j)\in V} \frac{(1-\sigma_{i,g}^z)(1-\sigma_{j,g}^z)}{4} - n\sum_{v\in V}(1-\sigma_{v,g}^z)\right)
$ -\frac{1}{4}\sum_{g\in G}\sum_{(i,j)\in V} (1-\sigma_{i,g}^z)(1-\sigma_{j,g}^z)w_{i,j}
/icons/hr.icon
結論どうすればいいの？
PyQUBOを使って、関数をそのままメソッドに入れる
code: qubo.py
x = {(v, g): Binary(f"{v},{g}") for v in V for g in G}
H = (
P_g
* Constraint(
sum((sum(xv, g for g in G) - 1) ** 2 for v in V), label="group_constraint" )
+ P_n
* Constraint(
sum((sum(xv, g for v in V) - n_group_verts) ** 2 for g in G), label="node_constraint",
)
- sum(
for g in G
for (i, j) in itertools.combinations(V, 2)
)
)