《毕业设计论文基于遗传算法的课程安排优化设计》由会员分享，可在线阅读，更多相关《毕业设计论文基于遗传算法的课程安排优化设计（24页珍藏版）》请在金锄头文库上搜索。
1、题 目： 基于遗传算法的课程安排优化设计 摘要课程表规划问题是一个NP 完全问题，其规划策略可以通过多种方法实现，一般启发式搜索算法是通过在全局区间找到可行结果，通常适合于简单的例子，对于多参数输入和结果要求，寻找一个相当好的解决方案可能需要耗费很多时间，甚至是不可能的。遗传算法(GAs) 是基于启发式方法的种群，该方法已经成功应用于人工智能、搜索和优化的各个领域，遗传算法的原理是由Holland设计并进行开发的，遗传算法具有以下特性：（1）从种群中选择个体的机制;（2）创造新个体的运算;（3）通过将以前的单个方案随机打乱，生成新解决方案的过程（4）更新个体的规则，这些特性分别被称为选择，杂交
2、，变异，更新。本论文拟将遗传算法应用于课程表的多参数优化，寻找满足约束条件的课程规划。关键字：课程表规划，遗传算法，选择，杂交，变异，更新AbstractMaking a class schedule is one of those NP-complete problems which can be solved by many methods. The normal heuristic search algorithm finds the optimal solution based local search procedure, but it only works for simple c
3、ases. For more complex inputs and requirements, finding a considerably good solution can take a while, or it may be impossible. Genetic algorithms (GAs) are population based heuristic approaches. They have been applied successfully in various domains of artificial intelligence, search, and optimizat
4、ion. The promising results were obtained for many difficult optimization problems. The principles of GAs were developed by Holland .Very briefly, GAs can be characterized by the following features: (1) a mechanism for selecting individuals from the population; (2) an operator for creating new indivi
5、duals; (3) a procedure for generating new solution by random perturbations of the single previous solutions; (4) a rule for updating the population. These features are referred to as selection, crossover, mutation, and updating. In this paper, GAs will be applied to optimizing the multi-parameter of
6、 schedule and searching the schedule which satisfies the requirements . Key words: class schedule planning，genetic algorithms，selection，crossover，mutation， updating.目录摘要1Abstract2第一章 绪 论41.1研究目的及意义41.2研究现状41.3研究内容4第二章 排课问题研究的概述52.1课程表问题的描述52.1.1时间表问题概述52.1.2课程表问题概述52.2大学课程表问题的研究情况62.2.1大学课程表问题的理论研究6
7、2.2.2大学课程表问题解决方法62.3排课的各种算法的比较7第三章 课程表的类对象93.1课程表的类对象93.2Chromosome 染色体93.2.1 Representation 表示93.2.2 Fitness 适应度103.2.3 Crossover 杂交113.2.4 Mutation 突变12第四章 基于遗传算法的课程规划124.1遗传算法的来源和研究发展124.2具体操作134.3课表观察员164.4配置164.4.1 配置文件164.4.2 配置文件的例子174.4.3 解析一个配置文件184.5程序运行示意图19第五章 结 论21致谢23参考文献24第一章 绪 论 1.1
8、研究目的及意义排课问题的本质是将课程、教师和学生在合适的时间段内分配到合适的教室中，涉及到的因素较多，是一个多目标的调度问题，即NP（Nondeterministic Polynomial，非确定的多项式）完全问题。NP-完全问题的简单与否，取决于问题的难易程度，只能用启发式算法找出最优解。然而这种算法太慢了，根本无法在计算机上实现。因此众多研究者提出了多种其他排课算法，如模拟退火、禁忌搜索、进化算法等。其中，遗传算法(Genetic Algorithm, 简称GA)是很有效的求最优解的算法。本课题的主要目的是通过综合研究、分析现有的排课优化的解决方法，实现基于遗传算法的自动排课优化。本课题的
9、研究意义在于，实现基于遗传算法的排课优化问题，可以提高优化的满意度和灵活度。实践证明，这种算法设计得出的课程安排可以达到了师生的高度满意。1.2 研究现状大学课程表问题（University Timetable Problem-UTP）或者时间表问题（Time Table Problem-TTP）是一个一直困扰各个学校的令人头疼问题，它是运筹学典型的组合优化问题之一。教师，教室，时间，课程和班级是五个制约该问题解决的重要因素。19世纪60年代，开始有学者从事计算机辅助排课的研究，Appleby等人开始使用简单的经验法，来解决小规模的排课问题。遗传算法是由美国芝加哥大学Holland教授于197
10、5年所提出。其基本观念源自于达尔文的进化论（Darwins Theory of Evolution）中适者生存的理论，是一种通过模拟自然界生物进化过程求解极值的自适应人工智能技术。遗传算法借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制来提高各个个体的适应性，体现了自然界中“物竞天择、适者生存”的进化过程。1975年，经过对该问题进行证明，S.Even提出它是一个NP完全问题。这意味着普通的方法比如图着色，整数规划，对复杂的学校排课问题并不能进行良好的解决。从70年代到90年代，有些学者开始了利用矩阵向量方法来对排课问题进行研究，能够解决规模稍大的问题，但是仍然存在缺陷。到了90年代
11、后，国内外很多学者转而采用遗传算法对排课问题进行了研究，随着遗传算法的发展，有了一定的结果，但是仍然未能解决满意度的问题。1.3 研究内容第一步：了解遗传算法的概念及其对于排课优化的重要意义。第二步：研究现有的排课优化方案及存在问题。第三步：利用遗传算法建立数学模型，定义染色体编码方案和适应度函数。第四步：通过初始化种群、选择、交叉、变异等过程不断进化，最后得到最优解。第五步：结果分析及其优化。第二章 排课问题研究的概述22.1 课程表问题的描述2.1.1时间表问题概述时间表问题（TimeTableProblem）既是一个理论方面的问题也是一个来源于实践的问题，它是实际生活中人们可以遇到的问题
12、，甚至对于我们来说很常见。比如说交通时间表问题1112（transportationTimetabling)，这个问题是如何设计城市中公交车或者有轨电车的时间表问题,使其能够良好的运行，减缓城市交通的压力；比赛时间表问题13(employeetimetabling)是如何设计一项大型赛事的时间表，来保证大型赛事能够良好的进行；还有雇员工作时间表问题(employeetimetabling)，研究得是如何来安排雇员的工作，使其工作能够达到最高的效率；当然还有我们要研究的大学课程表问题，这个问题研究的主要目的是提出一种优秀的算法最大程度上使学校课程安排人性化、合理化。 时间表问题是一类具有多约束的
13、将有限时间资源分配给多个事件组合优化问题。通常，一个时间表问题会有一系列事件(event)和一组有限的时空单元(time-space slot)和一组具体地点，并且还要受到一系列约束的限制，这些约束又分为硬约束和软约束。硬约束就是我们在进行时间表安排的情况下必须无条件满足的一系列限制，不能有任何违反，而软约束也是一系列的限制，但是我们不一定要全部满足，但是这些软约束的满足情况却决定了我们时间表安排的合理情况。当你排一个课程表时，你必须考虑很多要求（教授、学生、班级和教室的数目，教室的大小，教室里的实验器材等等）。这些需求可通过其重要性被分成若干组。硬约束（如果你不能解决其中一个，这个排课计划就
14、是不可行的）：l 一个班级只能放在一个空教室里l 没有教授和学生可以在同一时间上一门以上的课l 一个教室要有足够的位子安排所有的学生l 如果要在一个教室排课，此教室要有这门课程所需要的设备（例如电脑）软约束（即使不能解决，计划仍是可行的）l 一些教授对上课时间的偏好l 一些教授对上课地点的偏好l 学生或教授的在时间和地点上的班级分配当然，硬的和软的约束取决于有关情况。在这个程序中，只有硬约束落到了实处。2.1.2课程表问题概述本文主要研究的是时间表问题中的课程表问题。这个问题是来源于学校日常生活，和学生的日常生活息息相关。随着学校规模扩大，学生的数量急剧增加，学校的教育资源显得越来越有限，这个
15、问题就显得越发突出。所以对这个问题的研究具有现实意义，但是它又不缺乏理论性，1975年，S.Even对该问题进行了研究，并指出大学课程表问题是一个NP完全问题，这就说明了该问题没有真正意义上的最优解，人们的求解只有可能是相似最优解，也就是说求解获得的答案只可能不断接近最优解，但是不可能是最优解。于是人们就尝试用各种方法去解决这个问题，如图着色、分支定界、整数规划等，经过实践证明，遗传算法和模拟退火算法是两种解决该问题比较理想的方法。本文在后面主要介绍了遗传算法。 那什么是课程表问题？虽然已经从感性上已经了解了这个问题，但是下面将给出一个较为严格的定义方便深入理性的理解这个问题。Carter和Laporte这样定义：“课程表问题是一个多元分配问题，它研究的就是如何把学生和老师分配给课程，课程单元或者班级，如何把事件（上课事件）分配给教室和时间” 。 简单一些的说大学课程表问题研究的就是如何把一系列的课程分给有限的教室和一周内有限的上课时间单元，如何把学生和老师分配给课程。当然实际研究的时候并没有理论上说得这么简单
