基于遗传算法的自动排课系统毕业设计

基于遗传算法的排课系统研究基于遗传算法的排课系统的研究谷冰（沈阳建筑大学信息学院）摘要：排课问题是一个有约束的、多目标的组合优化问题，并且已经被证明为一个NP完全问题。

本文主要基于遗传算法，结合排课系统的一些具体需求，研究并实现一个排课系统。

【关键词】排课问题；遗传算法；组合优化一、背景近年来随着大学扩招，大学生人数的增加，每学期的排课问题一直是学校一项巨大的工作任务，使用人工手动排课对于这样一个庞大的课程体系来说简直是天方夜谭。

其中，最突出的问题就是班级多、课程多、教师少、教室少，从而导致传统的手工排课方法，由于工作量巨大、效率低下，容易出错已经不能满足需求；因此，研究计算机排课系统有重大的现实意义。

二、遗传算法遗传算法（Genetic Algorithms，GA）是根据自然界的选择和进化原来发展起来的高度并行、随机、自适应的随机搜索算法。

其模拟达尔文的适者生存原理，每个种群所面临的问题是寻找一种对复杂和变化着的环境最有利的适应方式。

遗传算法维持一个潜在的群体（染色体、变量），定义一个函数为：ttP(t)={ x1??,xn}染色体通常形成是一串的数组，近年来基于实数编码的遗传算法也得到广泛的应用。

每个解用其“适应值”进行评价其优劣程度。

然后通过选择更新（t+1次迭代）个新的群体。

新群体的成员通过杂交和变异进行变换，以形成新的解。

杂交组合了两个亲体染色体的特征，并通过交换父代相应的片段形成了两个相似的后代。

例如，如果父代用五维向量来表示，如下：(a1 ,b1 ,c1 ,d1 ,e1)，(a2 ,b2 ,c2 ,d2 ,e2) 在第二个基因后杂交，染色将产生后代 (a1 ,b1 ,c2 ,d2 ,e2)杂交算子的意图是在不同潜在解之间进行信息交换。

变异是通过用一个等于变异率的概率随机地改变染色体上的一个或多个基因。

变异算子的意图是向群体加入一些额外的变化性。

我们可以把遗传算法简化以下步骤：1) 产生初始遗传群体的方法。

基于遗传算法的智能排课系统设计与优化摘要基于遗传算法的智能排课系统设计与优化是一项具有挑战性和重要性的任务。

排课是学校管理中关键的一环，它需要平衡师生时间表安排，确保教室和教学资源的有效利用。

然而，传统的手动排课方式存在效率低、容易出错的问题。

因此，开发一种高效、准确的智能排课系统对于学校管理的提升至关重要。

本文将介绍基于遗传算法的智能排课系统设计与优化的方法和实现。

1. 引言智能排课系统是指利用计算机科学和人工智能技术，通过自动化和优化算法来实现对学校课程排列的自动分配和优化。

传统的手动排课方式一方面存在人力浪费的问题，另一方面也容易出现排课冲突和资源浪费的情况。

基于遗传算法的智能排课系统可以借助计算机的高效计算能力和优化算法，解决传统排课方式的一系列问题。

2. 系统设计基于遗传算法的智能排课系统的设计包含以下几个关键步骤：2.1 问题建模智能排课系统需要将问题建模为数学模型。

通常，问题的建模包括定义课程、教师、班级、时间和教室等相关参数，以及约束条件。

建模的目的是为了将复杂的排课问题转化为数学优化问题。

2.2 遗传算法设计基于遗传算法的智能排课系统主要采用进化算法中的遗传算法来进行优化。

遗传算法模拟了生物界的进化过程，通过选择、交叉和变异等操作来生成和改进解。

具体来说，遗传算法包括以下几个关键步骤：初始化种群、选择操作、交叉操作、变异操作和适应度评价。

通过不断迭代和优化，遗传算法能够逐渐找到最优解。

2.3 系统实现基于遗传算法的智能排课系统的实现需要开发相关的软件工具和算法。

通常，系统的实现包括以下几个方面的内容：数据管理模块、遗传算法优化模块、结果评价模块和用户界面模块。

数据管理模块负责对课程、教师、班级、时间和教室等数据进行管理和处理。

遗传算法优化模块是系统的核心部分，负责通过遗传算法来进行排课优化。

结果评价模块用于评估算法的性能和结果的质量。

用户界面模块则提供给用户一个友好的交互界面，方便用户使用和操作系统。

Network & Computer Security引言自动排课算法(TTP: Time Table Problem)，是一个N P完全问题，集成了时间、空间的双重约束。

从数学上讲，排课问题是一个在时间、教师、学生和教室四维空间，以教学计划和各种特殊要求为制约条件的组合规划问题。

其实质就是解决各因素之间的冲突。

无冲突是指不存在一个教师被同时安排给一个以上的班级上课，或一个以上教师被同时安排给同一个班级上课等。

在众多软件公司研究的排课系统中，较多地采用传统回溯算法，但真正投入应用的排课软件却很少。

原因在于，如果仅仅采用简单的回溯算法，通常情况下得到课表的适应度非常低，并且算法的复杂度比较高，通常为 m×O(n3)。

如某一门课程连续两天在同一时间上课，其他时间却没有安排此课程；或者不能满足教师连堂课的要求。

然而，如果想得到一张高质量的课表，就要设定一周多学时课程的上课时间间隔，也不合适，因为初始排课时总的搜索空间非常大（班级数×周学时数^总课程数），对一个有 2个班级，周学时为20(4×5)，共有20门课的学校，这样的搜索空间是 .25829× 027；即使大部分课程已安排完毕，其余课程在有限的搜索空间中搜索合适的上课时间，由于定义了不适当的搜索间隔，可能永远也搜索不到合适的上课时间。

显然，这样的效果是不能令人满意的。

为了解决这一问题，考虑把人工智能的知识引入这一领域，结果发现使用遗传算法，可以大大减少搜索空间，使用适应度函数评估个体能够找到最优解，使用自适应的交叉和变异能使最优解尽快收敛。

2 排课中的基本问题2. 名词解释（ ）时间片：任一上课时间段，2个小时为一个时间片，一天内共分配4个时间片。

（2）学时：40-60分钟的上课时间，即为一个学时。

（3）授课单元：根据教学计划得到的课程、教师和班级的对应关系。

如《C语言程序设计》由 066号教师为20050 002班讲授，这样一个对应关系就是一个授课单元。

摘要随着科学技术和社会信息技术的不断提高，计算机科学的日渐成熟，其强大的功能已为人们深刻认识，它在人类社会的各个领域发挥着越来越重要的作用，给人们的生活带来了极大的便利，成为推动社会发展的首要技术动力。

排课是学校教学管理中十分重要、又相当复杂的工作之一。

解决好教学工作中的排课问题对整个教学计划的进行，有着十分重要的意义。

首先对排课的已有算法作了相关的调查研究，决定采用遗传算法。

通过设计实现基于遗传算法的自动排课系统，研究了遗传算法在排课系统中的应用。

关键词：遗传算法、自动排课、Java。

AbstractAlong with science technical and community information technical increases continuously, calculator science is gradually mature, its mighty function has behaved deep cognition, and it has entered the human social each realm erupts to flick the more and more important function, bringing our life biggest of convenience. Curriculum arrangement is an important and complicated working in school, so solving the problem is of great importance for teaching programming. Investigated and studied the algorithm existed, determine that adopt genetic algorithm. Through Design Implementation the Auto Course Arrangement Management System Base on Genetic Algorithm, researched the application of genetic algorithm in the Course Arrangement Management System.Keywords: Genetic Algorithm Auto Course Arrangement Management Java.第一章绪论1.1排课系统研究背景排课是学校教学管理中十分重要、又相当复杂的管理工作之一，其实质就是为学校所设置的课程安排时间和地点，从而使整个教学能够有计划有秩序的进行。