分组遗传算法优化大学考试时间表

Study of application of grouping genetic algorithm in examination timetabling problem

大学考试时间表是一个多约束条件下的优化问题。传统遗传算法寻优的计算量是指数级的规模,而寻优的操作有可能会破坏时间表的硬约束条件,从而最终得到的解并不一定理想甚至不可行。该文从某高校的实际应用出发,对用图着色模型得到的已经满足了硬约束条件的初始考试时间表,用改进的分组遗传算法在既不破坏硬约束条件也不延长考试周的条件下扩大并平均分配了学生的复习时间,并且还大大减少了寻优的计算量。

University exam timetabling problem belongs to optimization problem based on many constraints.The caculation of tradional genetic algorithm reached to index-size and the operation maybe break the hard constraints and can not find an ideal or feasible solution.This paper optimizes initial solution which satisfies hard constraints and concludes from relationship color algorithm by grouping genetic algorithm from practical applications.Maximize students＇ study time under fixed examination week,cut down the caculation and don＇t break the hard constraints.