遗传算法的一些技术分析及在排课问题中的应用

论文摘要

在排课问题中,主要的考虑因素是时间、教师、教室、班级以及课程。一名教师可能同时担任几门课程的教学,同一门课程有时也由几名教师同时讲授。编排课表时要尽可能做到教师与课程之间的合理搭配,同时必须避免时间和地点(教室)的冲突。在满足以上要求后,还可以进一步优化课表结构,使得班级听课次数和教师讲课次数在时间和地点(教室)上合理分布,避免过于集中或过于分散。因而,排课问题是一个多目标的优化问题。求解此类优化问题已有遗传算法、蚁群算法、模拟退火算法、人工神经网络算法等,而遗传算法由于对所求问题的条件转化步骤较少,对目标函数也无特殊要求,求解过程相对于其它优化算法直观性强,对问题的依赖条件少。本文介绍了遗传算法的基本求解过程,分析了与位爬山法相结合的混合遗传的结构、收敛性及欺骗性问题,将该方法作为求解排课问题的算法。对排课问题的各种约束条件和求解目标做了详细分析,选取了较主要的目标作为求解对象,用线性加权法处理个目标之间的关系,将加权后的结果作为方案的最终目标。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 遗传算法的产生与发展
• 1.2 研究现状
• 1.3 遗传算法的基本思想
• 1.4 排课表问题概述
• 1.5 本文的主要工作
• 第二章 遗传算法求解步骤
• 2.1 遗传编码
• 2.2 适应函数
• 2.3 遗传算子
• 2.4 群体设定
• 2.5 初始化群体
• 2.6 终止运算的条件
• 2.7 控制参数的选择
• 第三章 混合遗传算法
• 3.1 遗传算法的收敛性
• 3.2 遗传算法的欺骗问题
• 3.3 与位爬山法相结合的混合遗传算法结构
• 第四章 排课问题的遗传算法
• 4.1 课表编排的约束条件
• 4.2 排课目标的选取
• 4.3 排课问题的遗传算子
• 第五章 结论
• 参考文献
• 致谢