基于遗传算法的排课系统研究

论文摘要

排课问题是一个有约束的、多目标的组合优化问题,并且已经被证明为一个NP难问题。遗传算法是一种借鉴于生物界自然选择和进化机制发展起来的高度并行、自适应的随机搜索算法,是近视求解NP难问题的一种有效方法。本文研究如何将遗传算法应用于求解排课问题,进行了以下几个方面工作:①系统完整地讨论了排课问题中的影响因素、主要约束条件、求解目标和难点,用数学模型完整地描述了排课问题,并提出了排课问题求解方法的总体框架和技术路线。②对多个模糊排课目标进行定量分析,建立了排课优化目标空间。③针对排课问题研究了染色体编码方式以及遗传操作算子的设计,并引入多目标协调决策模型,提出了一种基于多目标决策协调模型的适应度计算方法,并改进了遗传算法一般结构,形成了一套多目标协同优化的排课算法。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 排课问题的目标和意义
• 1.2 排课问题研究
• 1.2.1 排课问题的理论研究
• 1.2.2 排课问题的求解方法
• 1.3 本文研究内容
• 2 遗传算法简介
• 2.1 遗传算法的发展
• 2.2 遗传算法的基本术语
• 2.3 遗传算法的基本思想
• 2.4 遗传算法的基本操作及其特点
• 2.4.1 遗传算法的基本操作
• 2.4.2 遗传算法的特点
• 2.5 遗传算法基本原理
• 2.6 传算法在组合优化中的应用
• 2.7 遗传算法与其他搜索技术的比较
• 2.8 传算法研究的新领域
• 3 基于遗传算法的排课问题
• 3.1 排课问题概述
• 3.1.1 排课问题涉及的要素
• 3.1.2 排课问题的约束条件
• 3.1.3 排课问题的组合爆炸和不确定性
• 3.1.4 排课的求解目标
• 3.2 排课问题的数学模型
• 3.2.1 排课问题的数学描述
• 3.2.2 排课问题的优化求解模型
• 3.3 排课问题的求解方案
• 4 基于遗传算法的优化排课
• 4.1 排课问题的多目标分析
• 4.1.1 节次优度
• 4.1.2 班级课时日分布均匀度
• 4.1.3 班级日组合度
• 4.2 遗传算法设计
• 4.2.1 编码
• 4.2.2 选择操作
• 4.2.3 交叉操作
• 4.2.4 变异操作
• 4.2.5 冲突检验
• 4.2.6 系统实现
• 5 总结与展望
• 5.1 总结
• 5.2 展望
• 致谢
• 参考文献
• 附录
• 攻读硕士学位期间发表的论文目录