ワークショップのチーム分けを組合せ最適化問題として解く

背景

ワークショップをするにあたってチーム分けは重要。得意技が違うメンバーと力を合わせてアウトプットを出すのが醍醐味なので、チーム内のメンバーは偏らないのが望ましい。また、特定のチームだけズバ抜けて能力が高かったり低かったりする不公平も避けたい。
一方で、膨大な組み合わせの中からイケてるチーム分けを考えるのは結構大変な作業である。例えば、36人を6チームに分ける組み合わせを考えると、36C6 * 30C6 * ... * 6C6 / 6! = 3.71*10^(21) とのことで、聞き慣れない「37垓通り」なる組み合わせから選ばなければならない。なんとか上手く対処できる方法はないかと考えた。

やりたいこと

人工知能が将棋で人間に勝つよう、膨大な組み合わせの中から最もイケてる手を選ぶのはコンピューターの得意とするところ。そこで、ワークショップのチーム分けを組合せ最適化問題として定式化し、解決しようと試みる。
アプローチとして、事前に参加者から「実践コーチング」でタイプ診断してもらい、その点数を使ってチーム分けのイケている度合いの求め方や、チーム分けの表現を行列計算でモデリングし、データサイエンティスト御用達のR言語で実装して解く。

コミュニケーションタイプとイケてるチーム分けの関係性

「実践コーチング」は、コミュニケーションの図り方の４タイプ「コントローラー」「プロモーター」「サポーター」「アナライザー」それぞれ点数で診断してくれる。各タイプがまんべんなく集まったチームは、多様性があって良いチームに違いないという憶測のもと進める。

例えば私の診断結果は以下の通り。

コントローラーの点数:3
プロモーターの点数:3
サポーターの点数:2
アナライザーの点数:0

タイプは「コントローラー/プロモーター」です

チームメンバーの点数をタイプごとに合計し、各タイプの点数が均一であれば、バランスの良いチームだと言えそう。図の例ではチーム合計10,3,4,8であり「コントローラー」タイプに偏ったチームといえる。

また、チーム内のすべての点数をさらに合計した値（例だと25）がチームの能力であるとし、他のチームと比べてばらつきが少なければ、公平なワークショップになると言えそう。

行列で表現してみる

説明が乱暴ながら、以下のような行列で表現する。

左の行列がチーム分けで、例えば4番目の参加者に注目すると、チームBの要素が「1」になっていて、チームBに属することを意味する。右の行列がコミュニケーションタイプで、アンケートで得た診断結果を参加者ごとに並べている。

行列の積を計算すると、各チームが各コミュニケーションタイプに対して何点かが表現できている。横方向の合計値どうしのバラツキを小さくすることが「公平性」、横方向の各要素のバラツキを小さくすることが「チーム内のバランス」となる。

「公平性」と「チーム内バランス」を両立させたいところ、組み合わせ最適化問題では最小化すべき目的関数を1つにまとめる必要があり、まずは安直に足してみた。優先度があれば重み付けしてから足せばよい。

# 目的関数
objectiveFunction <- function(teamMatrix, memberMatrix) {
x <- t(teamMatrix) %*% memberMatrix
fairness <- cv(rowSums(x)) # 各チームの公平さ
balance <- max(apply(x, 1, cv)) # チーム内の能力バランス
fairness + balance # 戻り値
}

バラツキについては、変動係数CVを使用することで正規化も兼ねている。使い方が乱暴なので、ちゃんと知ってる人からは怒られるかもしれない。

# 変動係数 = 標準偏差 / 平均
cv <- function(x) {
sd(x)/mean(x) # 戻り値
}

コミニュケーションタイプ診断のアンケート結果は、スプレッドシート等から流し込むことを考慮して、CSVを介してR言語に食わせる。

# csv読み込み
csvRead <- function(filename) {
x <- read.csv(filename, header=FALSE, skip=0)
data.matrix(x) # 戻り値
}

反復法で解を求める

目的関数を小さくすることを目指し、最初の暫定チームからメンバーのトレードを繰り返して、イケてる状態を目指す。そんな、最初のチームを生成するプログラム。

# チーム割当の初期値を作成する
makeInitTeam <- function(nMember, nTeam) {
initTeamMatrix <- matrix(0, nMember, nTeam)
for(i in 1:nTeam) {
beginMember <- trunc(nMember/nTeam*(i-1)+1)
endMember <- trunc(nMember/nTeam*i)
initTeamMatrix[beginMember:endMember, i] <- numeric(endMember-beginMember+1)+1
}
initTeamMatrix # 戻り値
}

7人を3チームに分ける割り切れない場合でも、上手く2人チームと3人チームを作れている。

> makeInitTeam(7,3)
     [,1] [,2] [,3]
[1,]    1    0    0
[2,]    1    0    0
[3,]    0    1    0
[4,]    0    1    0
[5,]    0    0    1
[6,]    0    0    1
[7,]    0    0    1

繰り返すメンバーのトレードについては、以下のようなイメージ。Aチームに属する2人目の参加者と、Cチームに属する5人目の参加者を入れ替えている。

R言語のプログラムは以下の通り。

# i番目とj番目のメンバーを入れ替える処理
swapMatrix <- function(teamMatrix, i, j) {
nTeam = ncol(teamMatrix)
tmp <- teamMatrix[i,1:nTeam]
teamMatrix[i,1:nTeam] <- teamMatrix[j,1:nTeam]
teamMatrix[j,1:nTeam] <- tmp
teamMatrix # 戻り値
}

乱数で誰と誰をトレードするのか候補を決めて、イケてるチーム分けに近付く場合に限り実際にトレードする。これを20000回くらい繰り返す。

 # ヒルクライムによる最適化
hillClimbOpt <- function(memberMatrix, nTeam, maxCount=20000) {
teamMatrix <- makeInitTeam(nrow(memberMatrix), nTeam)
randomSwap(teamMatrix, 10000) # 乱数で初期値をかき混ぜる
currentVal <- objectiveFunction(teamMatrix, memberMatrix)
for(i in maxCount:1) {
tmpTeamMatrix <- randomSwap(teamMatrix, 1)
tmpVal <- objectiveFunction(tmpTeamMatrix, memberMatrix)
if (tmpVal < currentVal) {
teamMatrix <- tmpTeamMatrix
currentVal <- tmpVal
cat(i, currentVal, "\n")
}
}
currentVal <- objectiveFunction(teamMatrix, memberMatrix, catResult=TRUE)
teamMatrix # 戻り値
}

実行結果はこんなイメージ。10^(21) と比べると20000回の反復では少ないような気がしつつも、それなりの答えに収束している。

> csvRead("sample.csv")
     V1 V2 V3 V4
[1,]  6  0  1  3
[2,]  2 -1  3  5
[3,]  2  4  0  0
[4,]  3  4  5  0
[5,]  0  2  1  4
[6,]  2  3 -1  1
> memberMatrix<-csvRead("C:\\Users\\sysmex\\Desktop\\team\\sample.csv")
> hillClimbOpt(memberMatrix,3)
fairness:  15 17 17
balance:  0.2553139 0.5882353 0.6188131
     [,1] [,2] [,3]
[1,]    0    0    1
[2,]    1    0    0
[3,]    1    0    0
[4,]    0    1    0
[5,]    0    0    1
[6,]    0    1    0

今後の課題

システム数理的に言えば「局所最適に陥るよね？」に話が向かったり、計算量を小さくするため別のアプローチをとったりするところ、まぁワークショップは一期一会だし、そこまで完璧なチーム分けを目指すものでも無いっすよねと弁解する。

プログラムを書いていて「想った通りには動くのではなく、書いた通りに動く」を思い知らされることが多い。世の中が便利になってコンピューターが空気を読んでくれるのも、空気を読んでくれるようなプログラムを作る人がいるから。人が想うコトの世界と、コンピューター内の世界には隔たりがあって、橋渡しするのがシステム屋の仕事だと考えている。技術力を磨きつつも、半分は人間を見ていないといけない。

今回の問題で言うと、かなり単純化した検討なので、まだ実用に耐えるものではない。実際のチーム分けでは男女比の考慮や、同じ職種の人は避けること、人数が少ないチームはどうするかなど、他に考慮すべきこともある。ワークショップを運営する人々が、どんなことを考慮してチーム決めしているか、人に寄り添って想いを深堀りするシステム屋さんが必要に違いない。

後述

本記事を参照して、反復法ではなく厳密解で解いてくださっている方がいらっしゃった！
http://qiita.com/SaitoTsutomu/items/f4478dfbc3c1cf6425e3
こちとら、適当な思い付きと勢いで書き上げてスミマセンという気持ちになる。