遗传算法在排课系统中探讨与运用

1999年,我国高校扩招,在校生人数不断增加。课程表的编排面临巨大的挑战。一方面,教师、教室资源有限,另一方面排课是学校教学管理工作中非常重要的一个环节,它直接影响着教学质量和学生培养质量。传统的人工排课已经不能满足教学管理工作的需求。因此,众多专家学者尝试利用计算机来解决排课问题。排课问题是一个有约束的、多目标的组合优化问题,并且已经被证实是一个NP完全问题。遗传算法(GeneticAlgorithm,GA)是一种全局优化算法。1962年霍兰德(Holland)教授在世界范围内第一次提出了遗传算法的思想,它借用仿真生物遗传学和自然选择机理,通过自然选择、遗传、变异等作用机制,实现各个个体适应性的提高。从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。遗传算法在解决NP完全问题上表现优异。因此,鉴戒以往成功经验并结合本单位实际情况,本文尝试将遗传算法引入到排课问题的求解。首先概括说明了遗传算法理论,其次先容排课问题,阐述了该问题的国内外研究现状,着重分析了排课问题中的约束规则,将其分为不可违反的红线规则和黄线弹性规则,并分析了约束规则对最优解的影响。最后结合我单位实际情况,研究了染色体编码方式,设计了遗传算子,提出适应度函数的计算方法,确定了排课问题的算法设计并对其进行了仿真,仿真实验证实了遗传算法在解决排课问题中具有很高的效率,是解决排课问题很好的途径。【关键词】：遗传算法排课问题组合优化
【论文提纲】：摘要6-7Abstract7-9第一章绪论9-141.1本文的研究背景9-101.2排课问题的国内外研究现状10-131.2.1国外研究现状10-121.2.2国内研究现状12-131.3本文的研究目的及内容13-14第二章遗传算法简介14-232.1遗传算法的简介14-172.1.1遗传算法的产生与发展14-152.1.2遗传算法的现状15-162.1.3遗传算法的上风16-172.2遗传算法的基本术语17-182.3遗传算法的基本操纵18-212.4遗传算法的基本流程212.5遗传算法的应用21-23第三章排课系统23-303.1排课问题概述23-243.2解决排课问题常见算法24-253.2.1遗传算法243.2.2模拟退火算法24-253.2.3专家系统方法253.3排课问题约束条件25-263.4排课问题的组合爆炸与不确定性26-293.5排课问题的求解目标29-30第四章基于遗传算法的排课系统研究30-424.1系统需求分析30-314.2系统数据需求分析31-334.2.1教室和课程因素31-324.2.2时间因素32-334.2.3班级问题334.2.4教室和教学区域的问题334.3排课的约束规则33-344.4排课问题的数学模型34-354.4.1排课系统因素的数学描述344.4.2排课问题的基本规则的数学描述34-354.5排课问题的遗传算法设计35-424.5.1单目标排课问题的遗传算法设计35-394.5.2多目标排课问题的遗传算法设计39-42第五章排课系统应用分析42-495.1排课系统的数据库分析42-455.2数据输入45-465.3参数设置46-475.4系统运行流程475.5结果分析47-49第六章研究总结49-516.1本文总结496.2展望49-51参考文献51-54攻读硕士学位期间发表的学术论文54-55致谢55