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

摘要

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

目录

文摘

英文文摘

声明

第一章绪论

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排课问题的遗传算子

第五章结论

参考文献

致谢