一种自适应混合算法的排课方法及系统

摘要

本发明涉及一种自适应混合算法的的排课系统，包括：利用数据存储模块存储系统中的原始数据；利用初始节点生成模块从数据存储模块中获取的原始数据生成多个结构化课程节点；利用子图生成模块生成子图；将所述初始节点生成模块与所述子图生成模块的信息输入至经训练的图神经网络，由图神经网络输出最优的一个或多个按推荐分值大小依次排列的排课表，应用图神经网络解决排课问题，可以自适应不同的需求变化，有极强的通用性，当排课变量发生变化时，仅需改变排课过程中的基础网络节点，而不用调整排课算法本身，能够以较低的时间复杂度得到最优的排课结果，避免了传统遗传算法不收敛或陷入局部最优解的问题。

说明书

技术领域

本发明涉及教务管理技术领域，主要是涉及一种自适应混合算法的排课方法及系统。

背景技术

排课问题早在70年代就证明是一个NP完全问题，即算法的计算时间是呈指数增长的，这一论断确立了排课问题的理论深度。对于NP完全问题，目前在数学上没有一个通用的算法能够很好地解决。解决NP完全问题只能依靠近似算法，包括动态规划、贪心算法、回溯法等。

在现有技术进行排课时，也有人采用遗传算法GA(Genetic Algorithm)。GA是一种抽象于生物进化过程的、基于自然选择和生物遗传机制的优化技术，按照“优胜劣汰，适者生存”的原则，通过快速随机搜索力求找到最优解或满意解。但GA容易产生早熟收敛的问题，导致得到的解为局部最优解而非全局最优解，存在因“基因突变”导致排课表不收敛的问题，同时GA算法实现复杂，当数据量大时，时间复杂度高。在现实生活中，排课问题所涉及的变量因素很多，现有的排课方法通用性较差，一旦有影响变量发生改变则需重新调整中间的排课算法。

深度学习是近几年，特别是进入2010年以来人工智能领域的热点技术，深度学习常用两种基础网络：一种是卷积神经网络，简称CNN，主要用于图像类数据的处理。另一种是循环神经网络，简称RNN，主要用于时序类数据的处理，例如语音类数据及文本类数据的处理。

2019年是图神经网络发展的元年，简称GNN，目前GNN被初步用于场景图生成、点云分类与分割、动作识别、交通预测、商品推荐、程序验证、程序推理、社会影响预测、对抗性攻击预防、电子健康记录建模、脑网络、事件检测和组合优化等领域。

现有的排课方法难以在实践中得到应用，亟需一种时间复杂度低、通用性强，具备自适应特定且可快速得到全局最优解的排课方法。

发明内容

为了解决上述问题，本发明提出了一种自适应混合算法的排课系统，所述系统包括：

数据存储模块，用于存储系统中的原始数据；

初始节点生成模块，用于从所述数据存储模块中获取的原始数据生成多个结构化课程节点；所述课程节点包含多个属性，包括课程编号、课程名称、授课教师、授课起始时间、授课终止时间、前置课程、后置课程等；所述前置课程指当前课程编号所依赖的上一课程，所述后置课程指当前课程编号结束后启动授课的下一课程；

子图生成模块，所述子图生成模块包括多个课程节点及各课程节点之间连接边，所述子图为来自同一课程的有向图；

将所述初始节点生成模块与所述子图生成模块的信息输入至经训练的图神经网络，由所述图神经网络输出最优的一个或多个按推荐分值大小依次排列的排课表。

进一步的，在一种实施方式中，所述数据存储模块还用于存储历史排课表，所述历史排课表为已经成熟使用过的可靠排课表，其本身必须满足多个刚性条件，所述多个刚性条件受客观自然条件的强制约束。

进一步的，在一种实施方式中，所述刚性条件包括但不限于：同一现实或虚拟课堂的时间段内只能安排一门课程；同一批学生在同一现实或虚拟课堂的时间段只能学习一门课程；同一教师在同一现实或虚拟时间段仅能教授一门课程。

进一步的，在一种实施方式中，所述训练包括：

构建训练样本集，利用所述数据存储模块存储的可靠排课表中的数据构建排课样本节点；所述排课样本节点为排课网络图中的目标节点，所述目标节点具有多个属性，包括课程编号、课程名称、授课教师、授课起始时间、授课终止时间、前置课程、后置课程等；所述前置课程指当前课程编号所依赖的上一课程，所述后置课程指当前课程编号结束后启动授课的下一课程；所述排课网络图中包括多个目标节点以及目标节点之间的连接边，各个连接边具有各自对应的权重、方向以及编号信息。

进一步的，在一种实施方式中，所述图神经网络包括编码层和译码层；所述编码层为带有编码参数的图神经网络算法及其组合，所述译码层为带有译码参数的学习算法以及组合；以训练样本子图中的任一节点及其邻接节点为基础，基于各节点的属性利用编码层生成图表示向量；对译码参数进行多次迭代训练，在每次迭代中，从训练样本提取指定数量的目标，基于所述图表示向量，利用译码层生成每个节点的预测位置值；所述图神经网络还设置有目标损失函数，用于优化图神经网络，不断重复优化过程，直到满足训练条件为止。

相应的，本申请还提出了一种自适应混合算法的排课方法，所述方法包括：

利用数据存储模块存储原始数据；

利用初始节点生成模块用于从所述数据存储模块中获取的原始数据生成多个结构化课程节点；所述课程节点包含多个属性，包括课程编号、课程名称、授课教师、授课起始时间、授课终止时间、前置课程、后置课程等；所述前置课程指当前课程编号所依赖的上一课程，所述后置课程指当前课程编号结束后启动授课的下一课程；

利用子图生成模块生成子图，所述子图包括多个课程节点及各课程节点之间连接边，所述子图为来自同一课程的有向图；

将所述初始节点生成模块与所述子图生成模块的信息输入至经训练的图神经网络，由所述图神经网络输出最优的一个或多个按推荐分值大小依次排列的排课表。

进一步的，在一种实施方式中，所述数据存储模块还用于存储历史排课表，所述历史排课表为已经成熟使用过的可靠排课表，其本身必须满足多个刚性条件，所述多个刚性条件受客观自然条件的强制约束。

进一步的，在一种实施方式中，所述刚性条件包括但不限于：同一现实或虚拟课堂的时间段内只能安排一门课程；同一批学生在同一现实或虚拟课堂的时间段只能学习一门课程；同一教师在同一现实或虚拟时间段仅能教授一门课程。

进一步的，在一种实施方式中，所述训练包括：

构建训练样本集，利用所述数据存储模块存储的可靠排课表中的数据构建排课样本节点；所述排课样本节点为排课网络图中的目标节点，所述目标节点具有多个属性，包括课程编号、课程名称、授课教师、授课起始时间、授课终止时间、前置课程、后置课程等；所述前置课程指当前课程编号所依赖的上一课程，所述后置课程指当前课程编号结束后启动授课的下一课程；所述排课网络图中包括多个目标节点以及目标节点之间的连接边，各个连接边具有各自对应的权重、方向以及编号信息。

进一步的，在一种实施方式中，所述图神经网络包括编码层和译码层；所述编码层为带有编码参数的图神经网络算法及其组合，所述译码层为带有译码参数的图神经网络算法以及组合；以训练样本子图中的任一节点及其邻接节点为基础，基于各节点的属性利用编码层生成图表示向量；对译码参数进行多次迭代训练，在每次迭代中，从训练样本提取指定数量的目标，基于所述图表示向量，利用译码层生成每个节点的预测位置值；所述图神经网络还设置有目标损失函数，用于优化图神经网络，不断重复优化过程，直到满足训练条件为止。

本发明还提出了一种终端设备，所述终端设备包括存储器、处理器，所述存储器存储有运行于所述处理器之上的计算机程序，所述程序执行上述步骤所述的方法或各步骤之间的组合，只要能解决所要解决的技术问题的各种组合都包含在此申请中。

本发明还提出了一种计算机可读介质，所述计算机可读介质存储有运行于所述处理器之上的计算机程序，所述程序执行上述步骤所述的方法或各步骤之间的组合，只要能解决所要解决的技术问题的各种组合都包含在此申请中。

本申请的创造性贡献及有益效果：本申请首次应用图神经网络解决排课问题，可以自适应不同的需求变化，有极强的通用性，当排课变量发生变化时，仅需改变排课过程中的基础网络节点，而不用调整排课算法本身，能够以较低的时间复杂度得到最优的排课结果，避免了传统遗传算法不收敛或陷入局部最优解的问题。

附图说明

图1展示了本发明的基本流程图

具体实施方式

如图1所示，展示了本发明的基本流程图，其与排课系统流程相对应。

本发明提出了一种自适应混合算法的排课系统，所述系统包括：

数据存储模块，用于存储系统中的原始数据；

初始节点生成模块，用于从所述数据存储模块中获取的原始数据生成多个结构化课程节点；所述课程节点包含多个属性，包括课程编号、课程名称、授课教师、授课起始时间、授课终止时间、前置课程、后置课程等；所述前置课程指当前课程编号所依赖的上一课程，所述后置课程指当前课程编号结束后启动授课的下一课程；

子图生成模块，所述子图生成模块包括多个课程节点及各课程节点之间连接边，所述子图为来自同一课程的有向图；

将所述初始节点生成模块与所述子图生成模块的信息输入至经训练的图神经网络，由所述图神经网络输出最优的一个或多个按推荐分值大小依次排列的排课表。

进一步的，在一种实施方式中，所述数据存储模块还用于存储历史排课表，所述历史排课表为已经成熟使用过的可靠排课表，其本身必须满足多个刚性条件，所述多个刚性条件受客观自然条件的强制约束。

进一步的，在一种实施方式中，所述刚性条件包括但不限于：同一现实或虚拟课堂的时间段内只能安排一门课程；同一批学生在同一现实或虚拟课堂的时间段只能学习一门课程；同一教师在同一现实或虚拟时间段仅能教授一门课程。

进一步的，在一种实施方式中，所述训练包括：

构建训练样本集，利用所述数据存储模块存储的可靠排课表中的数据构建排课样本节点；所述排课样本节点为排课网络图中的目标节点，所述目标节点具有多个属性，包括课程编号、课程名称、授课教师、授课起始时间、授课终止时间、前置课程、后置课程等；所述前置课程指当前课程编号所依赖的上一课程，所述后置课程指当前课程编号结束后启动授课的下一课程；所述排课网络图中包括多个目标节点以及目标节点之间的连接边，各个连接边具有各自对应的权重、方向以及编号信息。

进一步的，在一种实施方式中，所述图神经网络包括编码层和译码层；所述编码层为带有编码参数的图神经网络算法及其组合，所述译码层为带有译码参数的学习算法以及组合；以训练样本子图中的任一节点及其邻接节点为基础，基于各节点的属性利用编码层生成图表示向量；对译码参数进行多次迭代训练，在每次迭代中，从训练样本提取指定数量的目标，基于所述图表示向量，利用译码层生成每个节点的预测位置值；所述图神经网络还设置有目标损失函数，用于优化图神经网络，不断重复优化过程，直到满足训练条件为止。

可选的，所述图神经网络进一步包括：第一卷积单元、第一池化层、第二卷积单元、第二池化层、全连接层；所述第一卷积单元采用的卷积核大小为3*3，其第一激活函数记为RL

激活函数RL＝RL

所述损失函数φ如下：

N表示样本数据集的大小，i取值1～N，y

所述损失函数φ用于对图神经网络进行训练，收敛模型参数。

相应的，本申请还提出了一种自适应混合算法的排课方法，所述方法包括：

利用数据存储模块存储原始数据；

利用初始节点生成模块用于从所述数据存储模块中获取的原始数据生成多个结构化课程节点；所述课程节点包含多个属性，包括课程编号、课程名称、授课教师、授课起始时间、授课终止时间、前置课程、后置课程等；所述前置课程指当前课程编号所依赖的上一课程，所述后置课程指当前课程编号结束后启动授课的下一课程；

利用子图生成模块生成子图，所述子图包括多个课程节点及各课程节点之间连接边，所述子图为来自同一课程的有向图；

将所述初始节点生成模块与所述子图生成模块的信息输入至经训练的图神经网络，由所述图神经网络输出最优的一个或多个按推荐分值大小依次排列的排课表。

进一步的，在一种实施方式中，所述数据存储模块还用于存储历史排课表，所述历史排课表为已经成熟使用过的可靠排课表，其本身必须满足多个刚性条件，所述多个刚性条件受客观自然条件的强制约束。

进一步的，在一种实施方式中，所述刚性条件包括但不限于：同一现实或虚拟课堂的时间段内只能安排一门课程；同一批学生在同一现实或虚拟课堂的时间段只能学习一门课程；同一教师在同一现实或虚拟时间段仅能教授一门课程。

进一步的，在一种实施方式中，所述训练包括：

构建训练样本集，利用所述数据存储模块存储的可靠排课表中的数据构建排课样本节点；所述排课样本节点为排课网络图中的目标节点，所述目标节点具有多个属性，包括课程编号、课程名称、授课教师、授课起始时间、授课终止时间、前置课程、后置课程等；所述前置课程指当前课程编号所依赖的上一课程，所述后置课程指当前课程编号结束后启动授课的下一课程；所述排课网络图中包括多个目标节点以及目标节点之间的连接边，各个连接边具有各自对应的权重、方向以及编号信息。

进一步的，在一种实施方式中，所述图神经网络包括编码层和译码层；所述编码层为带有编码参数的图神经网络算法及其组合，所述译码层为带有译码参数的图神经网络算法以及组合；以训练样本子图中的任一节点及其邻接节点为基础，基于各节点的属性利用编码层生成图表示向量；对译码参数进行多次迭代训练，在每次迭代中，从训练样本提取指定数量的目标，基于所述图表示向量，利用译码层生成每个节点的预测位置值；所述图神经网络还设置有目标损失函数，用于优化图神经网络，不断重复优化过程，直到满足训练条件为止。

可选的，所述图神经网络进一步包括：第一卷积单元、第一池化层、第二卷积单元、第二池化层、全连接层；所述第一卷积单元采用的卷积核大小为3*3，其第一激活函数记为RL

激活函数RL＝RL

所述损失函数φ如下：

N表示样本数据集的大小，i取值1～N，y

所述损失函数φ用于对图神经网络进行训练，收敛模型参数。

本发明还提出了一种终端设备，所述终端设备包括存储器、处理器，所述存储器存储有运行于所述处理器之上的计算机程序，所述程序执行上述步骤所述的方法或各步骤之间的组合，只要能解决所要解决的技术问题的各种组合都包含在此申请中。

本发明还提出了一种计算机可读介质，所述计算机可读介质存储有运行于所述处理器之上的计算机程序，所述程序执行上述步骤所述的方法或各步骤之间的组合，只要能解决所要解决的技术问题的各种组合都包含在此申请中。

本公开实施例还提出一种电子供电设备，包括：处理器；用于存储处理器可执行指令的存储器；其中，所述处理器被配置为上述方法。电子供电设备可以被提供为终端、服务器或其它形态的供电设备。

本公开可以是系统、方法和/或计算机程序产品。计算机程序产品可以包括计算机可读存储介质，其上载有用于使处理器实现本公开的各个方面的计算机可读程序指令。

计算机可读存储介质可以是可以保持和存储由指令执行供电设备使用的指令的有形供电设备。计算机可读存储介质例如可以是――但不限于――电存储供电设备、磁存储供电设备、光存储供电设备、电磁存储供电设备、半导体存储供电设备或者上述的任意合适的组合。计算机可读存储介质的更具体的例子(非穷举的列表)包括：便携式计算机盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存储器(EPROM或闪存)、静态随机存取存储器(SRAM)、便携式压缩盘只读存储器(CD-ROM)、数字多功能盘(DVD)、记忆棒、软盘、机械编码供电设备、例如其上存储有指令的打孔卡或凹槽内凸起结构、以及上述的任意合适的组合。这里所使用的计算机可读存储介质不被解释为瞬时信号本身，诸如无线电波或者其他自由传播的电磁波、通过波导或其他传输媒介传播的电磁波(例如，通过光纤电缆的光脉冲)、或者通过电线传输的电信号。

这里所描述的计算机可读程序指令可以从计算机可读存储介质下载到各个计算/处理供电设备，或者通过网络、例如因特网、局域网、广域网和/或无线网下载到外部计算机或外部存储供电设备。网络可以包括铜传输电缆、光纤传输、无线传输、路由器、防火墙、交换机、网关计算机和/或边缘服务器。每个计算/处理供电设备中的网络适配卡或者网络接口从网络接收计算机可读程序指令，并转发该计算机可读程序指令，以供存储在各个计算/处理供电设备中的计算机可读存储介质中。

用于执行本公开操作的计算机程序指令可以是汇编指令、指令集架构(ISA)指令、机器指令、机器相关指令、微代码、固件指令、状态设置数据、或者以一种或多种编程语言的任意组合编写的源代码或目标代码，所述编程语言包括面向对象的编程语言—诸如Smalltalk、C++等，以及常规的过程式编程语言—诸如“C”语言或类似的编程语言。计算机可读程序指令可以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络—包括局域网(LAN)或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机(例如利用因特网服务提供商来通过因特网连接)。在一些实施例中，通过利用计算机可读程序指令的状态信息来个性化定制电子电路，例如可编程逻辑电路、现场可编程门阵列(FPGA)或可编程逻辑阵列(PLA)，该电子电路可以执行计算机可读程序指令，从而实现本公开的各个方面。

这里参照根据本公开实施例的方法、装置(系统)和计算机程序产品的流程图和/或框图描述了本公开的各个方面。应当理解，流程图和/或框图的每个方框以及流程图和/或框图中各方框的组合，都可以由计算机可读程序指令实现。

这些计算机可读程序指令可以提供给通用计算机、专用计算机或其它可编程数据处理装置的处理器，从而生产出一种机器，使得这些指令在通过计算机或其它可编程数据处理装置的处理器执行时，产生了实现流程图和/或框图中的一个或多个方框中规定的功能/动作的装置。也可以把这些计算机可读程序指令存储在计算机可读存储介质中，这些指令使得计算机、可编程数据处理装置和/或其他供电设备以特定方式工作，从而，存储有指令的计算机可读介质则包括一个制造品，其包括实现流程图和/或框图中的一个或多个方框中规定的功能/动作的各个方面的指令。

也可以把计算机可读程序指令加载到计算机、其它可编程数据处理装置、或其它供电设备上，使得在计算机、其它可编程数据处理装置或其它供电设备上执行一系列操作步骤，以产生计算机实现的过程，从而使得在计算机、其它可编程数据处理装置、或其它供电设备上执行的指令实现流程图和/或框图中的一个或多个方框中规定的功能/动作。

附图中的流程图和框图显示了根据本公开的多个实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或指令的一部分，所述模块、程序段或指令的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

以上已经描述了本公开的各实施例，上述说明是示例性的，并非穷尽性的，并且也不限于所披露的各实施例。在不偏离所说明的各实施例的范围和精神的情况下，对于本技术领域的普通技术人员来说许多修改和变更都是显而易见的。本文中所用术语的选择，旨在最好地解释各实施例的原理、实际应用或对市场中的技术的技术改进，或者使本技术领域的其它普通技术人员能理解本文披露的各实施例。