Memoirs of the Faculty of Education, Shimane University. Natural science

number of downloads : ?
Memoirs of the Faculty of Education, Shimane University. Natural science 36
2002-12-01 発行

遺伝的アルゴリズムと焼きなまし法による学校時間割作成について

A Class-Teacher Timetabling using Genetic Algorithm and Simulated Annealing
Fukushima, Makoto
File
Description
本論文では,遺伝的アルゴリズム(GA : Genetic Algorithm)と焼きなまし法(SA : Simulated Annealing)を,学校時間割アルゴリズムとして中学校時間割作成に適用し,その結果について比較検討している。GAを使用した時間割アルゴリズムは,新規に提案する手法を含めて4種類の手法,SAについては2種類の手法を採用し,それぞれアルゴリズムのオペーレータ,及びパラメータを変化させて実験している。そして,得られた結果をコスト値として評価し比較検討を行った結果,GAによる改良されたアルゴリズムの効果は認められたが,SA法を採用した場合と比較するとやや劣る結果が得られることが分かった。
This paper presents an experimental result on automated class-teacher timetablings using Genetic Algorithm (GA) and Simulated Annealing (SA). The experiments are performed by using four types of GA including a currently enhanced one and two types of SA with varying their operators, such as crossover methods in GA and permutation methods in SA. From the results, the enhanced GA using a preferential assignment of hardly constrained tuples with the tournament of building blocks is effectively improves the reproduced offsprings in a cost measure, compared to other GAs under the assumed timetabling conditions. It is, however, also found that the best result of the GA is still slightly inferior to those of the SA in reducing the timetabling costs.