はじめに

初めましてtyと申します。「学校のクラス分け」って聞くと、どきどきした甘酸っぱい幼少？青春？時代を思い出す人もいるのではないでしょうか。

そのクラス分けを行うのは教員なわけですが、実は相当難しいことを行っているのです。

例えば100人を3クラスに分けるとき、その組合せの総数はなんと$10^{26}$もあります。それを毎年行なっている教員ってすごい！

日々大変な教員方の負担を少しでも削減したいと思い、私たちはクラス分けを自動化するアプリケーションを製作しました。本記事ではその定式化およびAmplifyでの実装に絞って紹介します！

※ある程度イジングマシンや量子アニーリングをわかっている方向けの記事となっております。もしQUBOやイジングモデルと聞いてピンと来ない方は一度他のサイトや書籍で学ばれることをお勧めいたしますm(_ _)m

クラス分けに考慮される事項

クラス分けで満足させたい事項は色々あると思います。例えば、、

• 男女比を一緒にしたい
• クラス間の学力を同じにしたい
• クラス間の居住地域の偏りを少なくしたい
• 仲の悪い生徒は別のクラスにしたい
• 運動能力の差をなくしたい
• 学力の差をなくしたい
• 特別な支援を要する生徒を振り分けたい
• ピアノを弾ける生徒を振り分けたい
• 相性の悪い親は別のクラスにしたい

ちなみに最後のは実際にあるそうm(_ _)m

QUBO変数の設定

上記の事項をQUBOに落とし込む分けですが、QUBO変数は {0, 1} のどちらかを取る変数です。2つの状態しか表せないためクラス数が3以上の場合を考慮し工夫する必要があります。

今回は生徒一人につきクラス数分のQUBO変数を用意します。このQUBO変数を$n_{i,a}$と表記するものとします。$i$ は生徒、$a$ はクラスを表します。

• $n_{i,a}=1$ のとき生徒 $i$ がクラス $a$ に属する
• $n_{i,a}=0$ のとき生徒 $i$ がクラス $a$ に属さない

とすることでクラス数が3以上の場合も対応できます。

QUBOの定式化

今回は以下の6つの制約を導入することにします。

• クラス重複禁止制約
• クラス人数均等化制約
• 男女均等化制約
• 学力均等化制約
• 地域分散化制約
• 不仲最小化制約

クラス重複禁止制約は一人が複数のクラスに属したり、どこのクラスにも属さなかったりするのを避けるための制約です。

早速ですがこれらを定式化すると以下のようになります。
$s$は生徒数、$c$はクラス数です。

なお右側の定式化に使用する値は予め元データから抽出・整形しておきます。

Amplifyにおけるコーディング

上記の定式化を実装します．使用言語はPythonです。

Amplifyライブラリを使用します。Amplifyライブラリの使い方は公式サイトにありますのでそちらをご覧ください。

from amplify import BinaryPoly, gen_symbols, sum_poly, pair_sum

q = gen_symbols(BinaryPoly, class_num, student_num)

HA = sum([equal_to(sum_poly([q[i][j] for i in range(class_num)]), 1) for j in range(student_num)])
HB = sum_poly(class_num, lambda i: (sum_poly(student_num, lambda j: q[i][j]) - student_num_average) ** 2)
HC = sum_poly(class_num, lambda i: (sum_poly(student_num, lambda j: sex[j] * q[i][j]) ** 2))
HD = sum_poly(class_num, lambda i: (sum_poly(student_num, lambda j: grades[j] * q[i][j]) - grades_average) ** 2)
HE = sum_poly(class_num, lambda i: (pair_sum(student_num, lambda j, k: area[j][k] * q[i][j] * q[i][k])))
HF = sum_poly(class_num, lambda i: (pair_sum(student_num, lambda j, k: dislike[j][k] * q[i][j] * q[i][k])))

# ハイパーパラメータ
aA, aB, aC, aD, aE, AF = 20, 1, 1, 10, 5, 20
# H = エネルギー関数
H = aB*HB + aC*HC + aD*HD + aE*HE + aF*HF   
H = H + aA*HA

# ※amplifyの仕様上 H=HA+HB+HC+HD+HE+HF はできない模様．HAはBinaryConstraintsクラスで，HB~HFはBinaryPolyクラス．

こんな感じでかけました。シグマが入り乱れた制約を一行で書けるのすごいです！

なお各制約のハイパーパラメータは試行錯誤して仮決めしました。この値によってどの制約を重視するか調節できます。

おわりに

簡単にですが定式化とAmplifyを用いた実装を紹介しました。イジングマシンや量子アニーリングの実社会への応用が進むといいですね！