基因遗传算法在智能排课系统中的应用研究

陈莉莉 胡宁

摘要：本文主要针对当前智慧校园环境下高校在多种类型实验室、多用途的智慧教室、多校区、多学科类型教师授课等复杂环境下，对教学管理过程排课的约束条件、流程处理进行研究，利用基因遗传算法在处理排课系统中的优势，以此来解决高校教务部门部分排课问题，生成最优化的教学课表。

关键词：遗传算法；智能排课；教学管理；智慧校园

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2019）06-0159-03

On Design of Intelligent Classroom Scheduling System Based on Genetic Algorithm

CHEN Li-li， HU Ning

（Jinling Institute of Technology， Nanjing 211169， China）

Abstract： The study explores the approaches to classroom scheduling in the multi-dimensional context of College Smart Campus concerning labs， classrooms， and teaching staff. It is concluded that genetic algorithms can be employed to achieve optimum course schedules because of their advantages in coping with multi-objective optimization and large-scale classroom scheduling under various mission constraints.

Key words： Genetic algorithm； Intelligent classroom scheduling； Teaching Management； Smart Campus

随着智慧校园和一站式网上服务大厅在高校数字化校园中的广泛应用，高校的教学和管理随之发生了巨大的变革，微课、互动教学和翻转课堂等新型的教学模式被不断的应用到教学体系中，其课堂教学质量和效果也得到了很大的提高。近些年来，为了不断满足社会对高技术人才的需求，高校规模随之不断扩大，对高校教学管理提出了更高的要求，特别是在多种教学模式和环境的约束下，教师、课程、各类型实验室、多用途的智慧教室、多校区等环境下的教学排课已经逐渐成为高校教学管理工作中一个难点，每学期如何设计出一套即符合师生上课的实际需求又能够充分统筹利用好学校的各类资源的教学课表，以达到最优的教学目标，已经是各高校教学管理人员研究的重点课题。

1 高校智能排课系统发展现状及存在问题

我国高校排课方面的工作研究始于 1980 年左右，初期主要研究的是各类型课程的规划、班级与教师的匹配模型两大类的问题。排课问题是一个多目标、多约束条件的组合优化问题，是一个NP完全问题[1]，在实际排课过程中需要综合考虑教师、教室、校區、课程设置等多种约束条件，例如高校的体育、数学、英语等基础课程基本采用的都是合班教学，学科专业课程都是小班教学，如数据结构、软件工程等，而且还需要考虑各学科的不同教学计划等诸多条件，因此，通过排课系统很难自动生成满意的课表。

对于高校排课问题，很多学者对此进行了广泛的研究，提出了很多不同的解决方法。有些是基于传统和标准模式下的算法进行排课系统的设计，再根据教务管理部门和工作人员的经验进行观察调整课表，最终形成教学计划和课表；也有基于改进的流程实现排课系统，主要采用不同的排课算法，如模拟退火算法、回溯算法、贪心算法等，在实现的过程中均需要大量的人工干预，且在实际使用过程中也存在较多问题，主要体现在以下几个方面：

（1）基础信息录入不方便、不准确。目前，大多数高校智慧校园还处于建设阶段，其教务排课系统相对独立，与校内主数据平台信息交互和共享接口均不完善，师生和教学场所等信息都需要教学管理人员不断的更新，对教务排课系统的实时性和准确性无法保障。

（2）对于约束条件定义不完整。目前高校基本都采购了不同类型的智能排课系统，大多数为标准化的配置。实际上，高校排课中除了需要考虑基本的约束条件外，每所高校都有各自的个性化需求，其标准化的排课系统难以适应高校个性化的约束功能和条件，这些约束条件的缺失和不完整，对排课计划和方案实施的可行性都会产生影响。

（3）难以实现智能化排课系统。教务排课系统在高校使用的过程中已经在不断的优化流程和算法，实现了根据排课过程不同阶段，不断地对教学方案和计划进行调整，从而达到自主收敛，生成适合高校师生和教学条件的排课方案。但是如何根据每所高校的不同情况制定个性化教学需求，找到最优化的智能处理算法，达到较好的收敛效果，更加适合师生教学的排课方案，是每个高校教学管理部门需要不断处理的难点问题之一。

2 智能排课系统算法的问题描和述约束分析

2.1排课问题概述

在高校教学管理工作中，排课是学校各类教学管理工作的必须和前提保障。在每学期开学前，高校教务管理部门都会重新收集和统计下学期的额教学计划、教师和学生基本信息、各校区的基本资源、各院部的特殊要求等，然后根据实际情况针对全校不同校区不同院系进行排课。排课工作会涉及到上课时间、上课地点、任课教师、教学计划等众多因素，任何因素的调整或变更都会影响到整个排课系统，而且在大多数情况下都会因为教师资源、教学场地和不同听课人员等多种因素的影响，在编排课表的过程中出现各种矛盾和冲突。因此排课工作就是要综合考虑学校各方面的因素，安排出能够最大化提高教学资源和利用率，且尽可能符合师生意愿和最佳教学效果的全校课表。

2.2排课系统的约束条件

合理的教务排课课表必须遵循如下的基本约束条件：

（1）同一时间同一地点只能安排一门课程；

（2）同一时间同一教师只能安排一门课程；

（3）同一时间同一学生只能安排一门课程；

（4）同一专业不同课程不能安排在同一时间；

（5）班级上课人数不能超过上课教室实际可容纳人数；

（6）教学计划、教学课时、教学任务不能随意变更。

除上述的基本约束条件之外，还有存在一些非必要约束条件，主要体现在如何提高实际课表编排的真实性和合理性，使得教学管理服务工作更加智能和人性化。结合笔者本校的实际情况，主要存在如下非必要约束条件：

（1）所有课程尽可能合理均匀分布，课程不能连天安排；

（2）每位教师和学生每天的课程不能跨校区安排；

（3）学生同一天连续节次的两门课程安排地点时考虑就近原则；

（4）理论性较强课程尽量每天间隔时间段内合理分布，将理论学习、实践教学、体育课程等相继排课；

（5）专业核心课程尽量安排在上午1至2节、选修课程尽量安排在下午或晚间教学；

（6）对特殊学院特殊要求的课程先行排课，尽量满足。

另外，根据每所高校的不同情况，对实际存在的师生情况、教学场所情况等具体问题具体分析。

2.3排课系统算法的数学描述

高校排课系统想要找到最优化的智能处理算法，达到较好的收敛效果，必须依靠智能化的软件来实现，实现智能化的软件就需要对现有的约束条件进行详细的描述来，且将智能排课问题描述以数学建模的模型为基础结构，建立排课系统的数学描述和数学模型，更有利于实现智能化的自动排课功能。

3 基因遗传算法在智能排课系统中的应用

基于排课系统复杂性，近几年来，随着高校智慧校园的不断发展，以基因遗传算法为代表的各类智能算法被广泛的应用到智能排课系统中，在很大程度上适应了各高校的个性化需求，取得了良好的效果。

3.1基因遗传算法的基本原理

基因遗传算法是一种高度模仿生物进化的理论模型，遵循自然界中优胜劣汰、适者生存的规则，模拟生物进化进程的启发式智能算法。借鉴这种基本原理，可以引入到计算数学中来处理各类型应用程序，从而得到最优化搜索问题的有效方法。为了更好的理解其流程算法，必须先了解其最基本的一些概念和术语。比如个体指染色体上的基因表现特征的实体，在一般问题中用于代表染色体；种群指在某一时间段内占据一定空间的同一物种的所有个体；适应度指用来衡量种群中某个体针对个性化环境的适应程度，适应度是描述个体性能的主要指标，将直接影响到遗传算法的收敛速度和排课系统能否最终找到最优解。

3.2基因遗传算法迭代的基本步骤和流程设计

基因遗传算法的整个过程就是不断寻找问题最优解的过程，在每次迭代过程中都会给出新解，每个解都会利用适应度函数进行评价，保留适应度高的染色体再进行迭代，其算法的主要流程描述如下。

首先利用人工对基因进行编码，给定起始种群规模，其中每一个染色体由多个基因组成，多个染色体组成一个种群；其次構建适应度函数，对种群中的每一个染色体计算其针对问题的适应度，然后利用算法进行交叉操作和变异操作，根据“优胜劣汰、适者生存”的原则来判断是否有满足最优性能的染色体；最后，对遗传算法的进化结束条件进行判断，主要包含两种状态，即达到了迭代过程的最大值或达到了最优化的要求。否则继续进行迭代处理。笔者为了能够清晰的表示遗传算法的主要步骤和流程，结合基因遗传算法给出的流程图如图1所示。

3.3基因遗传算法在智能排课系统的需求和设计

利用基因遗传算法对排课系统进行设计时，需要针对不同高校的排课业务流程、学校资源和个性化需求统筹分析，制定出符合高校排课规则的智能排课系统，由此来自动生成满足教学管理需求的排课方案，以达到高校对智能排课系统的性能需求，其性能需求主要指标主要有算法在执行效率，系统的稳定性、可扩展性和可维护性等。其需求目标是能够构建一套充分利用现有资源、有较高智能化自动处理能力，用户使用时具有较强的灵活性、扩展性和多角色应用的高效智能排课系统，最终能够最优化的满足高校教学管理部门和师生的需求。笔者结合基因遗传算法和实际工作给出的高校智能排课系统功能架构设计图如图2所示。

4 总结

本文对基因遗传算法在高校智能排课系统中的设计和应用进行了研究，并针对当前高校建设规模和排课约束条件不断增加的情况下，如何提高排课的效率和效果进行了分析。从目前实施的效果来看，遗传算法作为一种寻求最优解的算法，利用其作为排课处理的核心算法，研究各类约束条件，优化问题求解模式，构建适应度函数，实现智能领域的排课方案，解决了高校教务部门部分排课问题，但是，如何能够更好的提高多约束条件下的排课效率，获得全局最优解，还需要进一步研究和探讨。

参考文献：

[1] 张赫男，张绍文. 采用改进的混合遗传算法求解高校排课问题[J].计算机工程与应用，2015，51（5）：240-246.

[2] 李新良. 基于移动互联网的智慧校园体系架构研究[J]. 职教与经济研究， 2016（3）： 54-58.

[3] 吴松慧. 基于遗传算法的智能排课系统设计与实现[D]. 苏州大学， 2016.

[4] 吴卫东. 高等院校智慧校园信息系统建设研究[J]. 数字技术与应用， 2016（1）： 85-86.

[5] 张越然. 改进型遗传算法在高校排课系统中的应用[J]. 中国新通信， 2017（19）：100-104.

[6] 马小姝，李海芸. 遗传算法在高校排课系统中的应用研究[J].信息与电脑， 2018（8）：76-80.

【通联编辑：王力】