论文部分内容阅读
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