Research and Implementation of　Genetic Algorithm in University Course Scheduling System

摘要

排课问题是一个有约束、多目标的组合优化问题，并且已经被证明为一个NP完全问题。遗传算法是一种借鉴于生物界自然选择和进化机制发展起来的高度并行、自适应的随机搜索算法，是一种非常有效的解决NP的组合问题的方法。本文将遗传算法应用于排课问题的求解，进行以下几下方面研究工作： 1、系统完整地讨论了排课问题中的影响因素、主要约束条件、求解目标和难点。 2、给出了排课问题的ER图,提出了一个具有局部回溯和启发能力的、易于快速生成可行方案的随机安排算法。 3、提出了课程拆分算法、课程安排算法、冲突转移算法、教室资源维护算法、教室安排算法等主要子算法。 4、针对排课问题研究了染色体编码方式。 5、以...