1963年，C. C. Gotlieb在文章《The Construction of Class-Teacher Time-Tables》中提出了课表编排的数学模型，它标志着课表编排课题的研究正式跨入了庄严的科学殿堂。1976年，S. Even在论文《On The Complexity of Timetable And Mul...
详细信息
1963年，C. C. Gotlieb在文章《The Construction of Class-Teacher Time-Tables》中提出了课表编排的数学模型，它标志着课表编排课题的研究正式跨入了庄严的科学殿堂。1976年，S. Even在论文《On The Complexity of Timetable And Multi
Commodity Flow Problems》，第一次证明了课表问题是NP完全的。在国内，清华大学于1984年在《清华大学学报(自然版)》上发表了林漳希和林尧瑞在该课题上的实验性研究成果，接着国内部分高等院校相继开展了这方面的研究工作。本文主要探讨课表编排问题，完成的主要工作如下：
1．本文首先分析了课表问题中的各种因素，以及人工排课的模拟过程，讨论了课表问题是一个具有不确定性、NP完全的组合优化问题。同时，为了能够有效地解决课表问题，我们分析了遗传算法的产生、发展和现状等各种因素。
2．提出了时间安排算法
本论文设计的时间安排算法是基于经典的遗传算法。针对本课题，我们对遗传算法做了多个方面的改进和优化。在初始种群的平均化、采用自适应的交叉概率和变异概率、分解种群为多个子种群等方面进行了改进。这些改进能很好地避免遗传算法出现未成熟收敛等一系列问题。遗传算法在课表问题中应用在了两个层面上，第一个层面是针对某一门课程，从课表空间中找到近似最优的几个组合方案；第二个层面是针对一个课程集合，搜索这些课程以什么样的先后顺序进行排课，排出来的课表具有较高的满意度。
3．设计了教室安排算法
课表问题中除了遗传算法的使用以外，针对教室的安排，我们还设计了教室安排算法，该算法依据“优先教室集”，综合考虑资源分布优化度等因素，为课程找到合理的教室安排。针对排课过程中出现的“甩课”问题(无法安排教室的课程)，我们设置了3个子算法，它们有效地避免和解决这个问题。算法一是在时间安排算法中的一个子模块，它通过计算资源优化度来降低出现“甩课”的概率：算法二是一种回溯调整方法，它对可能出现的“甩课”进行有目的的时间调整，通过改变当前课程的时间安排，来满足教室的要求；算法三也是一种回溯调整方法，与算法二不同的是，它调整的对象是其它课程的时间或者教室安排，而
山东师范大学硕士毕业论文
为当前课程寻找有效的教室安排。通过这些工作，基本能够保证不出现或者极少
出现“甩课”.的现象。
4.系统的实现
针对本文所设计的模型，我们对主要算法进行了实现，效果良好。
本文所讨论的模型是遗传算法在课表问题中非常有效的一种应用，随着它的
发展和对课表问题越来越多的关注，相信遗传算法一定可以更好的解决课表问
题。
关键词:课表问题、遗传算法、知识库、策略库、组合优化
分类号:TP 1 82
暂无评论