時間割最適化
黒沢 彩乃

1(指導教員：工藤和恵)

はじめに重ならずに時間割が組める。

大学の時間割は、必修科目、教職科目、語学など、同じ時間帯に重なってほしくない科目が複数あり、時間割を組むのが大変である。そこで本研究は、重なってほしくない科目が重ならないような時間割を、簡単に作成するための方法を考案することを目的とする。

2

第２項は各コマに関する制約の項である。

• i: 頂点 (科目)、k: 色 (コマ)• qi : 頂点 i の色 (科目が入れられているコマ)• n slot: 色の数、n node: 頂点数

時間割ネットワーク

時間割をグラフで表す。頂点が科目に対応しており、重なってほしくない科目、すなわち、対象学年または教員が同じ、計算機室を使う授業同士を結んだ。科目を頂点とし、同じ時間帯に重なってほしくない科目を辺で結んでできるネットワークを、時間割ネットワー
クと呼ぶことにする (図 1)。

頂点 (科目)i が避けたい色 (コマ)k に対しては正の重み (ωik ＞ 0) を、塗りたい色 (コマ)k に対しては負の重み (ωik ＜ 0) を与える。つまり、頂点の重みが最小になるように色を塗り分けることで、制約を満たせる。
このエネルギー E が最小のとき、時間割は最適な状態である。E が最小である状態を探すために、本研
究ではシミュレーテッド・アニーリング法を用いる。

4アルゴリズム

シミュレーテッド・アニーリング法を使った時間割
最適化アルゴリズムは、以下の通りである [2]。
ステップ 0 初期値設定
すべての頂点にランダムに色を塗る。
ステップ 1 次の色配置設定
ランダムに選んだ１つの頂点の色を塗り替える。
塗り替える前の状態を X (t) 、後の状態を X ′とする。

図 1: 時間割ネットワークの例
この時間割ネットワークを無向グラフとし、頂点彩色を行う。繋がった頂点同士は違う色で塗り分けられるので、重なってはいけない科目が重ならずに時間割が組める [1]。しかし、頂点彩色のみでの時間割作成では解けない制約がある。例えば、月曜日の１限は避けるなど、個別のコマに対する制約を課す場合である。この問題点を解決するために、時間割グラフに関してエネルギーを定義し、最適化問題を解く方法を採用する。

3ステップ 2 エネルギー変化率の計算′
エネルギー変化率 : ∆ = exp ( E−ET )E: 状態 X (t) のときのエネルギーE ′ : 状態 X ′ のときのエネルギー
T : 温度のパラメータステップ 3 状態更新
一様乱数 r ∈ [0, 1] を生成し、以下のように次の状態 X (t+1)
 を決める。
X ′r ≤ ∆ （状態更新）
X (t+1) =X (t) otherwise (状態更新なし)
ステップ 1〜3 を何回か繰り返す。

モデル

時間割グラフ上の反強磁性的ポッツ模型のエネルギーを次のように定義する。

E=∑Jij δqi ,qj +(i,j)

n∑slot n∑node
k=1

ωik δqi ,k(1)ステップ 4 パラメーター T の更新状態更新 → T を下げる: T = T ・dT
T
状態更新なし → T を上げる: T = dT
(dT は温度変化率、0 < dT < 1)i=1

第１項は辺で結ばれた頂点 (i, j) の間に生じるエネルギーである。

ステップ 5 繰り返し
ステップ１に戻って、同じ操作を繰り返す。

• i, j:頂点 (科目)• qi , qj :それぞれの頂点の色 (それぞれの科目のコマ)

5• Jij :枝の重み (ここでは Jij = 1 とする)

PHP への実装と実行

本研究では、実際の運用を考え、Web を通して時間割作成ができるよう PHP での実装を行った [3]。上記のアルゴリズムを使用し、情報科学科前期の授業について PHP 上で実行した。実行結果は図 2 のようになった。学年・教員・教室が重ならずに組めている。

qi = qj ならば、δqi ,qj =1、qi ̸= qj ならば、δqi ,qj = 0である。つまり、結ばれた頂点同士の色が同じ色ならば、1 であり、違う色ならば 0 である。したがって、第1 項の合計が０になれば、重なってはいけない科目が5

表 2: 重みのつけ方
月 1,2 限 月 3,4 限 … 金 9,10 限
科目 10

1…

1科目 2

10…

0…

…

…

…

…に示す。
2 コマ連続科目がない場合の前期情報・後期情報・前
図 2: PHP での実行結果。緑：1 年生、青：2 年生、赤：3, ４年生対象のもの。

6ネットワークの特徴量成
功率

情報科学科前期 (前期情報)・情報科学科後期 (後期情報)・数学科前期 (前期数学)・数学科後期 (後期数学)
それぞれの時間割について時間割ネットワークを作成し、以下の特徴量を調べた。特徴量について調べた結果を表 1 に示す。

重みの割合

• クラスター係数…ネットワークの結びつきの強さ• ネットワーク直径…ノード間距離の最大値

図 3: 重みをつけた場合の成功率• 平均ノード間距離…すべてのノード間距離の平均

期数学・後期数学のグラフはほとんど重なっており、成功率にほとんど差がないことが分かった。また、2コマ連続が有る場合の前期情報・前期数学・後期数学はほとんど重なっているが、それと比較して後期情報の成功率が高いという結果になった。これは後期情報に 2 コマ連続科目が少ないことが原因であると考えられる。以上より、成功率はネットワークの特徴量の差には起因せず、主に 2 コマ連続科目の数に影響されて下がる、ということが分かった。
次に、シミュレーテッド・アニーリング法においてdT を 0.9 としていたのを 0.99 へ増加させることで、解を見つけやすくした。前期情報・後期情報・前期数
学・後期数学について調べたが、結果は dT = 0.9 の場合と dT = 0.99 の場合で変わらなかった。よって、時間割作成に失敗した場合は解が無いと考えられる。

• 平均次数…頂点から出る枝の数の平均• ネットワーク密度…辺の数を、辺の数の最大値（完全グラフの辺の数）で割ったもの

表 1: それぞれの特徴量
ク ラ ス
ター係数
ネット
ワ ー ク
直径
平均ノード間距離
平均次数
ノード数
ネット
ワ ー ク
密度

7前期情報

後期情報

前期数学

後期数学

0.818

9.809

0.817

0.807

33651.889

1.787

2.584

2.245

8.846

9.44

5.6

7.63262520270.23

0.309

0.255

0.386

8

まとめ

最適な時間割を組むために、時間割グラフの頂点彩色問題を解き、ポッツ模型 (式 (1)) を用いてシミュレーテッドアニーリング法で最適解を見つけた。PHPへの実装を行い Web 上で実行ができるようにすることで、さらに実用性を高めることができた。また、特徴量を調べ、成功率との関係を調べた。

重みをつけた場合の成功率

これまで、「この科目はこの時限で実施したい」という重みを考えずに実行してきた。そこで、重みのある科目の割合を増やしていった場合、前期情報・後期情報・前期数学・後期数学それぞれの成功率がどうなるか確かめる。2 コマ連続で科目を入れるという制約(例：数値計算と数値計算演習) がある場合とない場合についても確かめる。重みのつけ方は、表 2 のように、避けたい時間帯を 1、指定がない場合を 0 として設定する。
1 の入っている割合を 10% , 20% , 30%... と増加させ、エネルギーが 0 となったら成功とし、それぞれ 100回実行した場合の成功率を確かめた。その結果を図 3

参考文献[1] R.J. ウィルソン (原著), 西関 隆夫 (翻訳)・西関裕子 (翻訳), 「グラフ理論入門」, 近代科学社,(2001)[2] 福島孝治, 「モンテカルロ法の前線」, 若手研究者・学生向けに最新技術をわかりやすく紹介する
講演会「確率的アルゴリズムによる情報処理」講義ノート, (2003)[3] たにぐちまこと, 「よくわかる PHP の教科書
PHP5.5 対応版」, マイナビ, (2014)6