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

その他

本論文では，遺伝的アルゴリズム(GA : Genetic Algorithm)と焼きなまし法(SA : Simulated Annealing)を，学校時間割アルゴリズムとして中学校時間割作成に適用し，その結果について比較検討している。ＧＡを使用した時間割アルゴリズムは，新規に提案する手法を含めて４種類の手法，ＳＡについては２種類の手法を採用し，それぞれアルゴリズムのオペーレータ，及びパラメータを変化させて実験している。そして，得られた結果をコスト値として評価し比較検討を行った結果，ＧＡによる改良されたアルゴリズムの効果は認められたが，ＳＡ法を採用した場合と比較するとやや劣る結果が得られることが分かった。
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.