基于遗传算法高校排课系统探讨

为了保证教学质量,在制定规范的教学计划的同时,排课是教学计划顺利执行的重要环节,随着高校规模的急剧扩大,在有限的教学资源情况下排课问题变得越来越复杂,人工排课不仅工作量大,而且各种因素交联复杂,已不能完善的进行课表的编排工作。因此利用计算机智能排课是高校教务管理的迫切需要。排课是一个组合优化问题,它不仅要多种条件的约束、多种目标的制约,并且在70年代,排课就被证实为一个NP完全问题。遗传算法是是一类鉴戒生物界的进化规律(适者生存,优越劣汰遗传机制)演化而来的随机化搜索方法。具有良好的并行性和更好的全局寻优能力,是目前能比较有效的解决NP完成的组合优化问题的方法。当今,排课问题影响着高校教务工作的效率,所以越来越多的研究机构和高校开始热衷于排课问题的研究。本文提出了排课问题使用遗传算法的求解求解策略,分别从以下几个方面进行了研究：首先,本文从完整地讨论了排课问题产生的背景,该问题的影响因素、主要约束该问题的条件、以及求解该问题的难点和目标,之后完整地设计了排课问题的数学模型。接着概括说明遗传算法的结构、功能、特征,并研究其在排课系统中的应用,考虑到遗传算法很快收敛到局部最优而非全局最优解,综合各种排课方案优缺点基础上,设计更为适合的排课方法。设计了遗传算法排课问题的算法,并给出了算法的描述和流程图。最后,结合排课问题具体数学模型,以VisualC++为主要开发工具,SQLSERVER2000为数据库实现了基于改进型遗传算法的自动排课系统。分析显示该系统达到了预期要求,结果比较满足。【关键词】：排课问题遗传算法影响因素
【论文提纲】：摘要3-4Abstract4-81绪论8-141.1排课问题的概述8-101.2目前排课问题的概况10-131.2.1排课问题的理论研究101.2.2排课问题的求解方法10-131.3本文研究内容13-142遗传算法的相关概念14-232.1遗传算法的基本思想14-152.2遗传算法的结构15-172.3遗传算法的基本操纵17-182.3.1选择(selection)182.3.2交叉或重组基因(crossover/recombination)182.3.3变异(mutation)182.4遗传算法的特点18-192.5遗传算法的改进求解问题19-232.5.1选择算子的改进19-202.5.2自适应的交叉概率和变异概率改进202.5.3交叉和变异算子的改进202.5.4初始种群的均匀化改进202.5.5并行遗传算法20-233基于遗传算法的排课问题23-323.1遗传算法与排课的对应233.2排课问题的解决方案23-273.2.1随机可行排课方案的求解23-253.2.2基于遗传算法的优化随机排课方案25-273.3遗传算法排课问题算法概述27-323.3.1算法的基本步骤283.3.2算法的流程图28-293.3.3遗传算法的描述29-303.3.4算法分析30-324排课系统的算法设计32-454.1排课系统基本数据库32-354.2初始化种群35-384.2.1结构类型35-364.2.2外部调用函数36-374.2.3填充一条染色体374.2.4检查染色体的公道性374.2.5冲突检测和消除37-384.2.6建立种群384.3染色体的特征值38-394.4遗传操纵39-404.4.1选择操纵394.4.2交叉操纵394.4.3变异操纵39-404.4.4求可行解及遗传404.5填充结果表404.6课元排序404.7排课的实现40-455排课结果分析45-475.1时间参数分析455.2排课结果遗传算法分析45-465.2.1种群大小455.2.2交叉概率45-465.2.3变异概率465.3排课质量分析46-476研究工作结论与展望47-486.1研究工作结论476.2研究工作展望47-48参考文献48-50攻读硕士学位期间发表的论文50-51致谢51-53