| 講演名 | 1999/11/18 時間割作成問題への遺伝アルゴリズムの適用 大内 大輔, 上田 祐彰, 高橋 健一, 宮原 哲浩, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では,大学を対象とした時間割作成問題への遺伝アルゴリズムの適用手法について考察する.大学における時間割では,開講される教室が決まっている授業が存在する,あるいは受講者数に応じて開講する教室のサイズを決定しなければならないなど,教室に関連する制約条件が数多く存在する.このような場合,授業の時間割表への配置と授業への教室の割当てを同時に行う単純GAを応用した解法では,実行可能な時間割表の作成が困難になる.本稿では,単純GA用いた時間割作成手法を改良(拡張)し,分割処理という手法を提案した.この手法では,授業の時間割表への配置のみを扱う遺伝子操作,授業で使用する教室の割当てのみを扱う遺伝子操作,及びこれら二種類の個体の組合せによる教室の衝突の検査と再評価を逐次的に繰り返す.この分割処理と単純GAを実験により比較,検討する. |
| 抄録(英) | In this paper, we apply genetic algorithms (GA) to the timetabling problem for universities. There exist many constraints in the timetabling problem for universities regarding the size and the kind of rooms for classes. It is difficult to obtain an acceptable solutionby the simple genetic algorithm (SGA) which performs timetabling of classes and allocation of rooms to classes at the same time. In this paper, we present a method which employs GA in two phases. In the first phase, the method performs gene manipulations for timetabling and room allocation seperately. In the second phase, combinations of genes for timetabling and room allocation are evaluated. These two phases are iterated until we get satisfiable solution. Through computer simulations, we compare the performance of SGA with that of our method. |
| キーワード(和) | 時間割作成問題 / 遺伝アルゴリズム / 単純GA |
| キーワード(英) | Timetable Problem / Genetic Algorithms / SGA |
| 資料番号 | AI99-53 |
| 発行日 |
| 研究会情報 | |
| 研究会 | AI |
|---|---|
| 開催期間 | 1999/11/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Artificial Intelligence and Knowledge-Based Processing (AI) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 時間割作成問題への遺伝アルゴリズムの適用 |
| サブタイトル（和） | |
| タイトル（英） | Genetic algorithms for the school timetabling problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 時間割作成問題 / Timetable Problem |
| キーワード(2)（和/英） | 遺伝アルゴリズム / Genetic Algorithms |
| キーワード(3)（和/英） | 単純GA / SGA |
| 第 1 著者 氏名（和/英） | 大内 大輔 / Daisuke Ouchi |
| 第 1 著者 所属（和/英） | 広島市立大学大学院情報科学研究科 Hiroshima,City University Graduate School |
| 第 2 著者 氏名（和/英） | 上田 祐彰 / Hiroaki Ueda |
| 第 2 著者 所属（和/英） | 広島市立大学大学院情報科学研究科 Hiroshima,City University Graduate School |
| 第 3 著者 氏名（和/英） | 高橋 健一 / Kenichi Takahashi |
| 第 3 著者 所属（和/英） | 広島市立大学大学院情報科学研究科 Hiroshima,City University Graduate School |
| 第 4 著者 氏名（和/英） | 宮原 哲浩 / Tetuhiro Miyahara |
| 第 4 著者 所属（和/英） | 広島市立大学大学院情報科学研究科 Hiroshima,City University Graduate School |
| 発表年月日 | 1999/11/18 |
| 資料番号 | AI99-53 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 446 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |