一种基于遗传算法的时间表问题求解算法

Algorithm for Sloving Time Table Questions Based on GA

排课问题是一个多因素的优化决策问题,是组合规划中的典型问题,其属于NP完全类问题。给出了该问题的数学模型。遗传算法借鉴生物界自然选择和遗传机制,使用群体搜索技术,处理传统搜索方法难以解决的复杂的非线性问题。针对时间表问题,提出一种基于遗传算法的解决方法,定义了一个新颖的染色体编码方式,基于该编码,进一步分析并设计出交叉和变异2个遗传操作,运行结果显示该方法可行。

Timetable problem is a multifaetor optimized decision problem and is typical problem in constitution and planning. It has been proved as a kind of NP - complete problem. Genetic Algorithm（GA） is based on the biological mechanism of natural selection and heredity,leveraging colony searching technology,and is particularly applicable for the resolution of complicatednon - linear problems intractable with traditional searching methods. This paper designs the genetic arithmetic about the time table problems, a new method chromosome encoding is designed, based on which Genetic operations crossover and mutation are proposed. The experimental result shows the algorithm works well.