はじめに
先日，大人数十人規模のスポーツ（フットサル）の大会を仲間うちで主催する機会がありました．
これまでの経験で，こういったイベントにおいて，参加者それぞれの経験や技量も大きなばらつきがあるため，行き当たりばったりのチーム分けではチーム毎のパワーバランスに大きな偏りが生まれ，参加者の満足度も低減してしまうという予想がありました．
そこで，できるだけパワーバランスが平滑化され，経験者も未経験者も全力を出しながら楽しめるようにチーム分けを工夫してみることにしました．具体的には，参加者のこれまでのサッカー／フットサル経験を数値化し，組合せ最適化を用いてチーム分けを行ったので，その方法を紹介します．
なお，今回は，Google Colaboratory（以下Colab）でPythonを動かし，simannealというライブラリを主に使っています．
またこちらの記事（組合せ最適化でチーム分けする（焼きなまし法））を参考にしていますが，目的関数や制約条件，Googleのサービスを用いる上での工夫を新たにしています．
システムの概観
参加者の参加登録にGoogleフォームを用いたことから，参加者の管理にGoogleスプレッドシートを用い，その上でColab上でPythonを動かすことで，チーム分けを行っています．
今回使ったシステムの概観は以下の通りです．
なお，参加登録フォームでは，連絡先等の他に，チーム分けに重要な参加者の情報として「サッカー／フットサルの経験」についても聞いています．
問題設定
今回は以下の通り最適化問題を定式化しました．
（(1.1)〜(1.4)のjに関する合計を一定の条件の下で最小化する問題）
\begin{align}
\underset{\mathbf{x}\in \mathbb{R} ^{n \times m}}{\min}\; & \Biggl[ \sum_j \Biggl[\\
&\quad w_1 \left| \sum_i r_i x_{ij} - \mu_{\;1} \right| \tag{1.1} \\
&+ w_2 \left| \dfrac{\sum_i r_i x_{ij}}{\sum_i x_{ij}} - \mu_{\;2} \right| \tag{1.2}\\
&+ w_3 \left| \left( \dfrac{1}{\sum_k x_{kj}} \sum_i \left( r_i x_{ij} - \dfrac{\sum_k r_k x_{kj}}{\sum_k x_{kj}} \right)^2 \right)^{1/2} - \sigma \right| \tag{1.3}\\
&+ w_4 \sum_i \iota_{\,\,i} \Biggl] \Biggl]\tag{1.4}\\
\mathrm{s.t.} \quad
&lb \leq \sum_i x_{ij} \leq ub, \forall j \tag{1.5}\\
&\sum_i s_{\,i} x_{ij} \geq 1 , \forall j \tag{1.6}\\
&\sum_j x_{ij} = 1 , \forall i \tag{1.7}\\
&x_{ij} \in \{0, 1\} \tag{1.8}\\
\end{align}
ただし，それぞれの記号は以下の通りです．
\begin{align}
&n：参加者全体の数\\
&m：チームの数\\
&i,k = \{1, \dots, n \} \in \mathbb{N}\\
&j = \{1, \dots, m \} \in \mathbb{N}\\
&r_i：参加者iの経験値\\
&\mu_{\;1} = \dfrac{1}{m} \sum_i r_i ：1チームの経験値の合計の期待値\\
&\mu_{\;2} = \dfrac{1}{n} \sum_i r_i ：参加者全体の経験値の平均\\
&\sigma = \sqrt{\dfrac{1}{n}\sum_i ( r_i - \mu_{\;2})^2} ：参加者全体の経験値の標準偏差\\
&w_1, w_2, w_3, w_4：それぞれ第1〜4項の重み\\
&ub：1つのチームの最大参加者数\\
&lb：1つのチームの最小参加者数\\
&x_{\,ij} = \begin{cases} 1,\quad {参加者iがチームjに所属}\\ 0, \quad{otherwise} \end{cases}
\quad \qquad , \forall i,j \\
&s_{\,i} = \begin{cases} 1, \quad {参加者iが女性}\\ 0, \quad {otherwise} \end{cases} \quad , \forall i \\
&\iota_{\,\,i} = \begin{cases} 2^{\,l}, \quad {l: 異なるチーム分けで参加者iと同じチームにいる人数}\\ 0, \quad {otherwise} \end{cases} \qquad \qquad \qquad , \forall i
\end{align}
なお，「経験値」とは，参加登録の際に各参加者から得たサッカー／フットサルに関する経験を数値化したものです．
ここで，目的関数の$j$に関する$\Sigma$の中にある
- 第1項(1.1)は，あるチーム内の経験値の合計と１つのチームの経験値の合計期待値の差，
- 第2項(1.2)は，あるチーム内の経験値の平均と参加者全体の経験値の平均の差，
- 第3項(1.3)は，あるチーム内の標準偏差と参加者全体の標準偏差の差，
- 第4項(1.4)は，あるチーム内で異なるチーム分けで同じチームに配属された人数に応じて増加する項
を意味しています。
つまり，各チームの経験値の合計が均等になり，かつ各チーム内での経験値が平滑化され，更に各チーム内での標準偏差が参加者全体の標準偏差に近づき，また異なるチーム分けのパターンとはできるだけ同じ参加者が被らないような組合せ（チーム分け）$\mathbf{x}$を見つける最適化問題として定式化されています。
また、制約条件の
- 1つ目(1.5)は，各チームに配属される参加者数は上限と下限の間に収める
- 2つ目(1.6)は，各チームに女性が最低1人は配属される
- 3つ目(1.7)は，各選手が配属されるチーム数は1つである
- 4つ目(1.8)は，選手iがチームjに配属すれば1，そうでないと０となる
ことを示しています．
なお，今回実施した大会の参加者のバランスを鑑みて，女性が各チームに最低1人は配属されるような制約条件を設けていますが，実装する際には，その会の性質を鑑みて，特にこの部分は変更するべきだと考えています．
また，今回は経験値以外の別の軸によるチーム分けも行っていたため，目的関数の第４項(1.4)が存在していますが，これについても会の内容に応じて変更・削除して構わないと考えています．
Google Colaboratory上でPythonを使って解く
前提
今回は，焼きなまし法を用いて解くことにしました．
主な理由は2つあります．
一つは，この記事のようにPuLPで厳密解を探そうとすると莫大な時間が掛かってしまい，当日不参加などの可能性のあるこのような大会において，直前に計算し直すといったことが難しいのは運用上大きな課題となりうる一方で，焼きなまし法であれば計算時間が少なくできるため，直前までチーム分けの変更がしやすいということです．そもそも今回の目的関数が関数ではないので，このままではPuLPの適用ができないという問題もあります．
もう一つは，そもそもこのような大会において厳密解を求める必要性が小さく，初期値に応じて解が変わりうる焼きなまし法でも十分であるということです．（むしろリクリエーションという性質も考えるとランダム性があることもプラスと捉えられように思いました．）
焼きなまし法について詳しく知りたい方は，Wikipedia等をご覧ください．
簡単に解説すると，下記の図のように初期値から始まり，目的関数の値（エネルギー）がより小さくなる解を探索していくという方法です．
赤の点線のように，大域最適解に向かって進んでいけば大域最適解を見つけられますが，青い点線のように局所最適解に進んでいく可能性もあるのがこの手法です．探索のパラメータ設定次第で，局所最適解同士や局所最適解と大域最適解を隔てる山を飛び越えるような探索も可能です．
Python上の事前準備
今回，Googleフォームで登録された参加者情報をGoogleスプレッドシートで管理し，そのデータをColabで読み込み，Pythonのsimannealというライブラリを用いて最適化問題を解くことでチーム分けを行います．
そのデータを読み込むための事前準備です．
まずは下記を実行することで，GoogleドライブとColabを連携させます．
詳しくはこちら（参考2.）をご覧ください．
##事前準備①
#認証のためのコード
from google.colab import auth
auth.authenticate_user()
import gspread
from google.auth import default
creds, _ = default()
gc = gspread.authorize(creds)
続いて，以下を実行します．
これについても，詳しくはこちら（参考2.）をご覧ください．
##事前準備②
# スプレッドシートを開く（シートURLから）
url = "参加者の管理をしているGoogleスプレッドシートのファイルのURL"
ss = gc.open_by_url(url)
print(ss.title) #正しいファイルを読み込めているか確認するためにprintして確認
# シートを特定する（シートインデックスで特定）
st1 = ss.get_worksheet(参加者の情報がまとめてあるシートの番号) #参加者の情報がまとめてあるシート
st2 = ss.get_worksheet(チーム分けを出力したいシートの番号) #チーム分けを出力するシート
print(st1.title, st2.title) #正しいシートを読み込めているか確認するためにprintして確認
最適化問題を解く
これでColab上で最適化問題を解く準備ができました．
予め断っておくと，厳密解を求める必要はないということから，各チームに女性が最低1人という制約条件については，初期値の段階で各チームに女性を均等な人数だけ配属させ，その上で焼きなましを実行中に男性と女性では入れ替えが起きないようにするという処理を行っています．
なお現時点で，変数st1に参加者の情報まとめのシートが格納された状態です．
また，st1に読み込まれたシートは以下のような形をしていると仮定します．
| 氏名 | 経験値 | 性別 | 別のチーム分け |
|---|---|---|---|
| 田中 雄大 | 12 | 男性 | A |
| 山田 さくら | 8 | 女性 | D |
| 佐藤 光太郎 | 3 | 男性 | B |
| 鈴木 美咲 | 1 | 女性 | C |
| … | … | … | … |
| 高橋 健太 | 18 | 男性 | D |
（ちなみに名前はChatGPTで「日本人の名前をランダムに5個」と入力し作成してみました．）
この状況で，最適化問題を焼きなまし方で解くためのコードは以下の通りです．
#焼きなまし法
class GroupingProblem(Annealer):
def __init__(self, init_state):
super(GroupingProblem, self).__init__(init_state) # important!
# 探索点の移動ルール
def move(self):
##ランダムに選択した選手m1とm2を入れ替える
trig = 0
while trig == 0:
m1 = random.choice(list(range(nmembers))) #参加者のうち1人をランダムにm1として選ぶ
t1 = self.state[m1].index(1) #t1:m1のチーム番号
m2 = random.choice(list(range(nmembers))) #参加者のうち1人をランダムにm2として選ぶ
t2 = self.state[m2].index(1) #t2:m2のチーム番号
if (t2 == t1) or ((sex[m1] + sex[m2]) % 2 == 1):
continue #t1==t2 or 男性と女性を選んでしまったときはやり直し
else:
self.state[m1][t1], self.state[m1][t2] = self.state[m1][t2], self.state[m1][t1]
self.state[m2][t2], self.state[m2][t1] = self.state[m2][t1], self.state[m2][t2]
trig = 1
# 目的関数
def energy(self):
v = 0
mu1 = sum(scores)/nteams
mu2 = sum(scores)/nmembers
sigma = np.sqrt(pow(sum(scores[i] - mu2 for i in range(nmembers)), 2)/nmembers)
for j in range(nteams):
numj = sum(self.state[i][j] for i in range(nmembers))
numgirl = sum(sex[i] * self.state[i][j] for i in range(nmembers))
#目的関数第１項
v += w1 * abs(sum(scores[i] * self.state[i][j] for i in range(nmembers)) - mu1) * mu2/mu1
#目的関数第2項
v += w2 * abs(sum(scores[i] * self.state[i][j] for i in range(nmembers))/numj - mu2)
#目的関数第3項
sumscores_in_j = 0
for k in range(nmembers):
sumscores_in_j += scores[k] * self.state[k][j]
# print(sumscores_in_j)
sum_for_v = 0
for i in range(nmembers):
sum_for_v += pow(scores[i] * self.state[i][j] - sumscores_in_j/numj, 2)
v += w3 * abs(np.sqrt(sum_for_v/numj) - sigma)
#目的関数第4項
for i in range(nmembers):
if self.state[i][j] == 1:
t1 = self.state[i].index(1)
t1mem = [a[t1] for a in self.state]
t1num = []
temp = 0
for k in range(len(t1mem)):
if (t1mem[k] == 1) and (assigned1[i] == assigned1[k]):
temp = temp + 1
if (k == len(t1mem) - 1):
v += w4 * pow(2,temp)
return v
if __name__ == '__main__':
#data1として参加者の情報を読み込む
data1 = st1.get_all_values()
#membersに参加者の名前を格納
members = [r[0] for r in data1]
members.pop(0)
#scoresに参加者の経験値を格納
scores = [r[1] for r in data1]
scores.pop(0)
scores = [float(scores) for scores in scores]
#sexに参加者の性別を格納（女性なら1,男性なら0）
sex = [r[2] for r in data1]
sex.pop(0)
for i in range(len(sex)):
if (sex[i] == "女性"):
sex[i] = 1
else:
sex[i] = 0
skills = ['rate']
#assigned1に異なるチーム分けのチームを格納
assigned1 = [r[3] for r in data1]
assigned1.pop(0)
#目的関数の項毎の重み付け（い、ろ、は、に、に適当な数字を入れる）
w1 = い
w2 = ろ
w3 = は
w4 = に
#分類するチームを指定（ここでは4チームとしてA~Dを設定）
teams = ['A', 'B', 'C', 'D']
#チーム数等を格納
nteams = len(teams) # チーム数
nmembers = len(members) # メンバー数
lb = math.floor(nmembers/nteams) #1チームの最低人数
ub = math.ceil(nmembers/nteams) #1チームの最大人数
steps = 0
# 初期割当て
init_state = [[0 for j in range(nteams)] for i in range(nmembers)]
# 最初は均等に所属（男女の人数も均等に）
random.seed(1) #一応乱数のシードを固定（0以上の整数であればOK， 再現性を得られる）
rand = random.randrange(nteams)
prob = GroupingProblem(init_state)
prob.steps = 50000
prob.copy_strategy = "deepcopy"
prob.anneal() # 焼きなまし実行
#teamlistにチーム分けの結果を格納、printで出力
teamlist = []
print("\n結果：")
for i,s in enumerate(prob.state):
print(members[i], teams[s.index(1)])
teamlist.append([teams[s.index(1)]])
ここまでで，変数teamlistに焼きなまし法で解いたチーム結果が格納されました．
変数teamlistの各行には，変数membersの各行の参加者に対応したチーム名（上記ではA~Dのいずれか）が格納されています．
これをst2に出力することでGoogleスプレッドシートにも書き込みます．st2で指定しているシートの中身は以下のようなものです．
| A | B | C | D |
|---|---|---|---|
このシートの2行目以降に計算結果（各チームのメンバー）を書き込むためのコードが以下の通りです．
teamlist2 = []
#teamlist2にチームAから順に並び替えて参加者名を格納
for j in range(len(teams)):
tmp = []
for i in range(nmembers):
if teamlist[i] == teams[j]:
tmp.append(members[i])
teamlist2.append(t)
n = math.ceil(nmembers/len(teams))
mat_team = []
#mat_teamにチームAから列毎に参加者名を格納
for i in range(n) :
tmp = []
for v in team2s:
if (len(v) < n) and (i == n-1):
tmp.append("")
else:
tmp.append(v[i])
mat_team.append(tmp)
#mat_teamをst2で指定したシートのA2セル以降に書き込む
st2.update('A2','')
st2.append_rows(mat_team, table_range='A2')
これにより，最適化問題を焼きなまし法により解いて得られたチーム分けがst2で指定するシートに以下のように出力されます．
| A | B | C | D |
|---|---|---|---|
| 佐藤 光太郎 | 田中 雄大 | 山田 さくら | 鈴木 美咲 |
| 高橋 健太 | … | … | … |
| … | … | … | … |
終わりに
組合せ最適化問題をGoogle Colaboratory上でPythonによってsimannealを用いて焼きなまし法で解く方法を紹介しました．
焼きなまし法は数学的に厳密な最適解（大域最適解）を確実に求めたいときには不都合ですが，凸関数かどうかに関わらず解くこともできるため，実装も比較的直感的に行うことができ，非常に使い勝手が良いです．
また，Googleフォームなどとの連携のしやすさや環境設定の手間の掛からないといった理由でGoogle Colaboratoryを使う場合，焼きなまし法だと，計算時間が短くて済むことも利点です．（Colabは無料ユーザーだと計算時間の上限がある．）
これは今回のようにイベント主催などで，その場での計算が求められる場合にも生きてくる利点です．
また，大前提ですが，Colabにデータを読み込ませて処理する前後におけるスプレッドシート上での事前事後処理も重要です．Colabで処理するために各参加者の経験を数値化することを始め，読み込ませるシートの整理や計算結果の見せ方などもイベントの運営においては大事になってきます．
今回，この記事にまとめた手法のきっかけとなったイベント（フットサル大会）では，この手法によりチーム分けを行った結果，当日の参加者の体調不良等にも素早く対応ができ，拮抗した試合が多く，大きな盛り上がりに繋がったので，今回のように一定程度数学的にイベントを企画することは大きな意義があると感じられました．
Appendix
サッカー／フットサルの経験の数値化
今回，各参加者の経験は参加フォーム上で集めることとし，以下の選択肢（複数回答可）を表の通りに数値化しました．
| 経験時期 | 点数 |
|---|---|
| 未経験・応援 | 0.5 |
| 小学校 | 2 |
| 中学校 | 3 |
| 高校 | 5 |
| 大学・大学院（体育会系運動部） | 6 |
| 大学・大学院（サークル等） | 4 |
| 社会人（プロ） | 9 |
| 社会人（クラブチーム等） | 5 |
| 社会人（趣味） | 2 |
複数回答している場合は，合計することとし，女性の場合は，運動能力を鑑みて，一律1/2倍としました．
つまり，例えば，小学生の頃から中学，高校まで経験している男性であれば2+3+5で10，同様の時期に経験している女性であれば10×1/2で5となります．
これまで一緒にプレーしたことある人たちを鑑みて，直感的に数値化した表ではありますが，結果的には結構良い線だったようには思います．
参考
- 組合せ最適化でチーム分けする（焼きなまし法）, Qiita, 2018年05月07日更新
https://qiita.com/matsulib/items/bd50af2e2bc1e48522cd - 【Python】Google Colabからスプレッドシートに読み込み・書き出し。, でじらぼ, 2022年8月25日更新
https://www.teijitaisya.com/python-gspread/ - 焼きなまし法, wikipedia, 2020年12月10日更新
https://ja.wikipedia.org/wiki/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97%E6%B3%95
著作権等について
本記事に掲載されている文章や数式、コード、図表について著作権法及びQiitaの利用規約を越える利活用については，当ユーザーまでお問い合わせいただきますようお願いいたします．
基本的にURLの掲示等によって本記事を好意的にご紹介いただくことは歓迎です．