情報処理学会第 75 回全国大会 3S-6 遺伝的アルゴリズムを用いた対話型時間割編成システムの開発濱崎拓† 筑波大学情報学群情報科学類† 狩野均‡ 筑波大学システム情報系‡ 1 はじめに時間割編成問題[1]とは、開設される科目が実施される学年および時限を決定する問題である。時間割編成問題を解くためにはカリキュラムに対する専門的な知識が必要であり、その多くは計算機内で表現しにくい。従来、研究開発されてきた時間割編成システム [2]は、GUIを通して時間割の修正ができるが、修正に時間がかかりすぎるという問題があった。そこで本研究では、探索の途中でユーザが介入することにより探索効率を上げ、さらに、GUIの機能を改良することにより、修正時間の短縮を図った。問題点2. 編成をすべて計算機に任せてしまうと、ユーザの希望が反映されにくい。対策1. ユーザによる科目配置の固定を行うことで、探索範囲を狭める。対策2. 科目配置の修正・固定をユーザに任せることで、よりユーザの好みに近い時間割の作成を可能にする。 3 提案システム 3.1 処理手順提案するシステムの処理手順を以下に示す。 Step1. 科目データを入力 Step2. 初期集団生成 Step3. 世代ループ 1) 評価・交叉・突然変異・エリート保存 2) 指定世代でユーザによる科目固定・修正 Step4. ユーザによる科目配置の修正 Step5. 時間割を出力 2 研究概要 2.1 対象とする問題本研究では実例として平成25年度以降の筑波大学情報学群情報科学類の時間割編成問題を扱う。この学類は4学年3専攻2学期からなり、各学期は前半と後半の2つのモジュールに分かれている。このため、①1年生、②2年生、③専攻A・3,4年、④専攻B・3,4年、⑤専攻C・3,4年の5種類の学年・専攻をそれぞれ各学期とも前半・後半の2モジュールに分割した計20種類の時間割を同時に編成する必要がある。本研究における制約条件(全10制約)の例を表1に示す。各制約条件には、その制約の強弱に応じて制約違反点数を設定してある。 3.2 コード化図1のように遺伝子座を「科目ID」、遺伝子を「その科目が実施される時限」とする。2時限以上にわたって実施される科目は、遺伝子座を必要数用意する。表 1 制約条件の例制約条件特定の曜日に集中して科目を割り当てないある学年の必修科目と別の学年の必修科目を同時間帯に割り当てない履修順序の通りに科目を割り当てなければならない違反点数 2点図 1 コード化 10点 20点 2.2 問題点と対策以下に問題点と対策を示す。問題点1. 探索空間が膨大であるために、通常の厳密解法では対処しきれない。また、通常の近似解法のみだと、収束に時間がかかりすぎる。 Development of Interactive System for Constructing Timetables Using Genetic Algorithm †Taku Hamasaki †College of Information Sciences, University of Tsukuba ‡Hitoshi Kanoh ‡Faculty of Engineering, Information and Systems, University of Tsukuba 2-365 3.3 対話型インタフェースによる科目配置の固定と修正本システムでは探索前、探索中、探索後の任意のタイミングにおいて、簡単なマウス操作のみで時間割内の科目配置を固定・修正することができる。固定した科目配置は集団中の全ての個体に適用され、その部分は以後、探索の対象から除外される。ただし、科目修正に関しては表示している個体のみの変更で、集団中には影響しない。時間割内の科目にマウスを乗せることで、その科目がどの制約に違反しているか表示できるので、それを見ながら修正することになる。その様子を図3に示す。時間割内の「プログラミング入門Ⅱ」にマウスを乗せると、左下に違反情報が表示される。 Copyright 2013 Information Processing Society of Japan. All Rights Reserved. 情報処理学会第 75 回全国大会 4 評価実験 3.1節の処理手順からユーザによる修正を除いたものに対して、探索途中における科目固定の有効性を確認するため、科目固定を行わなかった場合との比較実験を行った。科目固定は500世代ごとに、違反点数0点の科目の中で他科目に影響を及ぼさないと考えられるものを固定した。また5000世代を超えたところで、それまで固定していた全ての科目の固定を外し、残りの探索を行った。科目の固定回数は1試行あたり130回前後で、固定解除を含めると260回程度になった。以下に示すデータは 30試行の結果である。実験結果を図2と表2に示す。図2より、探索途中に科目固定を行った方が、固定を行わない方より収束が早いことがわかる。また、表2より、今回探索を行った時間割は手動のものに比べ大きく改善が見られた。科目固定ありの場合となしの場合を比較すると、固定を行った方が良い結果が得られた。これらより、科目固定機能の有効性が確認できる。また、上記の固定ありの時間割において、探索終了後、GUI上で科目配置の修正を行った。その結果、違反点数の最小値は4点まで減少した。修正にかかった時間も4.5分だった。なお、この時間割で違反していた制約は「6限に科目を割り当てない(1 点)」が4つであった。機能により、よりユーザの好みに近い時間割への修正を可能にした。今後の課題としては、探索時間の短縮ならびに探索途中における科目修正の結果を集団中へ反映することなどが挙げられる。参考文献 [1] Rhydian Lewis, survey of metaheuristic-based techniques for University Timetabling problems, OR Spectrum, Vol.30, No.1, pp.167-190 (2008). [2] 坂元, 狩野, 知識に基づく遺伝的アルゴリズムを用いた対話型時間割編成システムの開発, 情報処理学会第65回全国大会 3K-1 (2003.3). 図 2 各世代における違反点数表 2 比較実験結果手法手動固定なし固定あり修正後 5 おわりに科目固定機能による時間割編成システムを提案し、その有効性を示した。また、科目配置の修正最小値 153 9 6 4 違反点数平均値 26.7 13.7 - 標準偏差 15.3 7.0 - 図 3 ユーザとの対話画面 2-366 Copyright 2013 Information Processing Society of Japan. All Rights Reserved.