基于遗传算法的排课软件设计开题报告

1. 研究目的与意义

遗传算法是一个黑箱算法，能够解决很多NP-hard问题，本课题拟采用遗传算法设计一个排课软件，能解决一个中小学的排课问题。

尤其在网络不断发展的今天，在线的排课系统更能给教务人员带来更多的便利。

2. 国内外研究现状分析

国外：1963年，gotlieb第一次提出了课表编排的数学模型。

1975年，even.s证明了排课问题是一个np完全问题,无法用计算机实现，从理论上对时间表问题有了全新的认识。

因而，众多的研究者们又开始考虑用其他方法来解决这一问题，比如使用组合逻辑、禁忌搜索、决策系统、贪心算法、图论、模拟退火算法、遗传算法[2,3]、免疫网络[4]等。

3. 研究的基本内容与计划

研究内容： （1）理解遗传算法的理论（2）排课问题的建模 （3）遗传算法在自动排课中的应用方法，包括基因编码、初始种群的产生、适应度函数、控制参数的设定等。

（4）排课算法的实现研究计划：（1）大量阅读关于遗传算法的相关文献，理解算法原理。

（2）研究排课问题，对排课问题进行建模。

4. 研究创新点

（1）遗传算法对所求解的优化问题没有太多的数学要求，由于他的进化特性，搜素过程中不需要问题的内在性质，对于任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续的都可处理。

（2）遗传算法不需要求导或其他辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数。

（3）具有可扩展性，容易与其他算法结合