遺伝的アルゴリズムの時間割作成問題への適用に関する一考察

URI http://harp.lib.hiroshima-u.ac.jp/hiroshima-cu/metadata/6556
ファイル
タイトル
遺伝的アルゴリズムの時間割作成問題への適用に関する一考察
別タイトル
Comparisons of Genetic Algorithms for Timetabling Problems
著者
氏名 上田 祐彰
ヨミ ウエダ ヒロアキ
別名 UEDA Hiroaki
氏名 大内 大輔
ヨミ オオウチ ダイスケ
別名 OUCHI Daisuke
氏名 高橋 健一
ヨミ タカハシ ケンイチ
別名 TAKAHASHI Kenichi
氏名 宮原 哲浩
ヨミ ミヤハラ テツヒロ
別名 MIYAHARA Tetsuhiro
キーワード
遺伝的アルゴリズム
時間割作成問題
時間割作成問題生成
抄録

大学を対象とした時間割作成問題への遺伝的アルゴリズム(GA)の適用について考察する.本論文で対象とする問題は,授業の時間割表への配置と各授業で使用する教室の割当ての双方を扱い,実施可能かつ教員の要望を充足した時間割表の導出が目的である.実施可能な時間割表を効率的に探索する手法として,授業の時間割表への配置を扱う遺伝子操作と教室の割当てに関する遺伝子操作を分割して実施する手法(分割GA)が提案されているが,様々な規模,複雑さをもった問題に対して分割GAが有効であるか否かは検証されていない.本論文では,分割GA,単純GAを応用した手法(SGA),授業の時間割表への配置を決定した後に教室の割当てを行う手法(逐次GA),教室の割当てを行う代わりに授業配置に対して適切な教室の割当てが行えるか否かを検査する手法(SGA2),焼なまし法を応用した手法(SA),及びタブサーチを応用した手法(TS)の6手法を実装し,比較実験を行った.時間割作成問題生成プログラムによって生成された問題と現実の時間割作成問題とを用いた実験の結果,ほとんどの問題に対してSGA2が良好な結果を導出できることが示された.また,授業の開講率が高い問題に対しては分割GA,問題の規模が大きく複雑性の高くない問題に対しては逐次GA,規模が小さく制約条件の多い問題に対してはSAが適していることも示された.

査読の有無
掲載雑誌名
電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理
J86-D-I
9
開始ページ
691
終了ページ
701
出版年月日
2003-09-01
出版者
社団法人電子情報通信学会
ISSN
0915-1915
NCID
AA11341020
NAID
110003171272
本文言語
日本語
資料タイプ
学術雑誌論文
著者版フラグ
出版社版
権利情報
copyright©2003 IEICE
関連URL
旧URI
区分
hiroshima-cu