应用遗传算法编排和优化课表

论文摘要

本文首先分析了课表问题中的各种因素，以及前人对此的研究成果及其不足，确定了课表问题是一个具有不确定性、NP完全的，有约束的、多目标的组合优化问题。为了能够有效地解决课表问题，我们采用了基于遗传算法的一种排课算法。遗传算法(Genetic Algorithm)是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，其主要特点是群体搜索策略和群体中个体之间的信息交换，尤其适用于处理传统搜索方法难以解决的复杂和非线性优化问题。本文将遗传算法应用于排课问题的求解，进行了以下几个方面研究工作：●系统完整地讨论了排课问题中的影响因素、主要约束条件、求解目标和难点，并提出了相应的指导策略和具体的解决办法。●根据对排课情况的分析设计了编码方式，对课表中常见的教师、课程、班级、教室、时段5维对象作了合理的安排。令其能够很好的用基因、染色体等遗传算法概念来表示，为将排课问题转化为时间表排序问题打下了良好的基础。●结合实际情况设计了遗传方式，达到了避免回溯，趋避硬冲突，满足约束三重目的。●把排课问题转化为有约束的TSP问题来处理。●采用Java语言及Access和SQL Server数据库等工具设计和实现了应用遗传算法编排和优化课表的软件，并使用现实案例进行了测试取得了良好效果，排课满意度大为提高。软件智能化程度有较大提升。

论文目录

• 内容提要
• 第一章 绪论
• 1.1 排课问题的产生及对其研究的意义
• 1.2 对于排课问题研究目的
• 1.3 遗传算法概要
• 1.4 遗传算法与其他搜索技术的比较
• 1.4.1 常用搜索求解技术
• 1.4.2 遗传算法与其他搜索技术的比较
• 第二章 排课问题的详细分析
• 2.1 排课问题的研究现状
• 2.2 排课时必须考虑的约束
• 2.3 排课问题所涉及到的对象
• 2.4 计算机排课问题的本质
• 2.4.1 课表的衡量标准
• 2.4.2 排课问题的本质
• 2.4.3 排课过程中的组合爆炸和不确定性
• 第三章 遗传算法原理的介绍
• 3.1 遗传算法的生物遗传学基础
• 3.2 遗传算法的特点
• 3.3 遗传算法的基本操作
• 3.3.1 复制
• 3.3.2 交叉
• 3.3.3 变异
• 3.4 遗传算法的主要步骤
• 第四章 遗传算法排课的原理分析
• 4.1 本文中常用词语解析
• 4.2 遗传算法排课的基本思想
• 4.3 基因池的生成
• 4.4 基因序列生成
• 4.5 导致排课失败的因素
• 4.5.1 资源不足导致排课失败
• 4.5.2 硬冲突导致排课失败
• 4.6 满意度评估的策略
• 4.7 编写课表与TSP
• 4.7.1 基因序列的另一种形式
• 4.7.2 是否可以采用TSP的交叉方式
• 4.8 初始化策略
• 4.9 遗传过程策略
• 4.9.1 交叉策略
• 4.9.2 变异策略
• 第五章 排课实现
• 5.1 排课过程中所用到的数据表
• 5.2 程序简介
• individual类'>5.2.1 Gene_individual类
• 5.2.2 Chromosome类
• 5.2.3 Arrangetable类
• 5.3 遗传过程的实现
• 5.3.1 种群初始化的实现
• 5.3.2 适应度评估实现
• 5.4 选择算子实现
• 5.5 交叉算子的实现
• 5.6 变异算子的实现
• 5.7 冲突检测
• 5.8 输出
• 5.9 时例测试及分析
• 5.9.1 排课测试
• 5.9.2 本算法的特点及与其他排课算法的比较
• 第六章 结论
• 参考文献
• 摘要
• Abstract
• 致谢