基于分步渐进策略的多目标优化排考方法及系统

摘要

本发明提供基于分步渐进策略的多目标优化排考方法，包括以下步骤：获取考试课程、考场、时间段、考试对象、任课教师和监考教师信息；对考试对象、考场进行分组优化；采用改进离散粒子群算法进行时间段优化安排；采用离散云进化算法进行监考教师优化安排；输出优化后的考试课程对应的时间段、考场、考试班级和监考教师安排。本发明还提供基于分步渐进策略的多目标优化排考系统。本发明提出一种课程分组、时间优化、教师安排的分步渐进求解策略，能够有效降低大规模排考问题的复杂度，提高求解效率、全局寻优能力和算法稳定性。

说明书

技术领域

本发明涉及教学管理技术领域，具体涉及基于分步渐进策略的多目标优化排考方法及系统。

背景技术

随着高校招生人生的不断增加以及选课制、学分制的逐步推进，各教学单位期末考试安排工作变得日益复杂。因此，目前常用的“人工+通用办公软件”的排考模式已无法适应规模巨大、复杂度超高的现实形势。这种模式受人为因素影响较大，常会出现约束冲突、时间安排不合理或资源利用不合理的情况。为了避免上述问题，提高大规模排考工作效率，优化资源配置，学者们开始研究计算机辅助优化排考算法。

目前常用的排考算法包括：图着色算法、遗传算法、蚁群算法、模拟退火算法等。在已有文献中，图着色算法应用相对较多，这种方法能够较好地解决时间和场地冲突问题。遗传算法、蚁群算法以及模拟退火算法等都属于启发式优化方法，具备一定的优化解搜索能力。

上述的排考算法存在具有以下问题：图着色算法不具备全局优化解搜索能力，因而应用这种方法得到的排考结果只能保证满足刚性约束条件但无法取得优化解；遗传算法存在编码过程较复杂、容易收敛于局部极值等问题；蚁群算法需要使用相邻状态间参数的变化构建适应度函数，不适合求解排考问题；模拟退火算法受初始状态和参数设置的影响较大，在求解效率和全局寻优方面存在不确定性。

发明内容

为了克服上述现有技术存在的问题，本发明提供基于分步渐进策略的多目标优化排考方法。

本发明提供的方案如下：

基于分步渐进策略的多目标优化排考方法，包括以下步骤：

获取考试课程、考场、时间段、考试对象、任课教师和监考教师信息；

对考试对象、考场进行分组优化；

采用改进离散粒子群算法进行时间段优化安排；

采用离散云进化算法进行监考教师优化安排；

输出优化后的考试课程对应的时间段、考场、考试班级和监考教师安排。

作为本发明的进一步技术方案为：所述对考试对象、考场进行分组优化；具体包括：

设定优化排考数学模型：

min h(P,C,S,L,R,T)；

min g(P,C,S,L,R,T)；

min y(P,C,S,L,R,T)；

min v(P,C,S,L,R,T)；

D

D

R

其中，P,C,S,L,R,T分别表示时间段，班级，学生，课程，考场和教师；D

上述模型中，目标函数h(P,C,S,L,R,T)为各时间段内所安排考试数量的均方差，取其最小值就是为保证各时间段的考试场次数一致；g(P,C,S,L,R,T)为每位学生相邻两次考试最小间隔时间总和的倒数，取其最小值就是为实现同一学生两门课程的考试间隔尽可能最大化，以保证学生有充足的复习时间；y(P,C,S,L,R,T)为每位监考教师相邻两次监考最小间隔时间总和的倒数；目标函数v(P,C,S,L,R,T)为各监考教师参加监考数量的均方差，取其最小值就是为保证各教师监考次数一致；式(1)保证不出现同一学生在同一时间段内参加两门课程考试的情况；式(2)保证同一时间段内一个考场只安排一门课程考试；式(3)保证修读一门课程的所有学生在同一时间段内考试；式(4)保证一个时间段内同时考试的场次数小于可供使用的考场总数；式(5)保证每个考场内参加考试的学生人数小于其容量；式(6)保证在不发生冲突的情况下各门课程的任课教师均参与该课程的监考；

对考试对象、考场进行分组优化；具体包括以下步骤：

S1：在给出所有课程{L

S2：对于所有N门课程，求出β

S3：按β

S4：在

S5：遍历未分组课程数组

S6：当约束条件(2)～(4)无法满足时，增加考场数量以完成分组；当优化目标minh无法满足时，放弃该目标以完成分组；

S7：判断

S8：分组结束，输出{G

完成优化分组后，可得到{G

在分组优化阶段，欲实现的目标函数为min h，约束条件为式(1)～(5)；为保证式(1)，可定义课程约束矩阵LS：

LS＝[l

矩阵LS具有对称性，即l

第r门课程与其它课程的关联系数β

设参加一门课程考试的学生总数为M，标准化考场的容量为U，则该门课程需要的最少考场数量X＝int(M/U+0.5)，int表示四舍五入取整；

根据课程门数、选课学生数以及标准化考场的容量可计算出总考试场次数为：

设考试时间段总数为J，如果ZE≥J，则Q＝J，否则Q＝ZE，Q为分组数量；每个时间段内的平均考试场次数

作为本发明的进一步技术方案为：所述采用改进离散粒子群算法进行时间段优化安排；具体包括：将每个分组视作一个粒子，以min g和min y为目标，对各分组进行排序，不同的位次对应不同的考试时间段；包括以下步骤：

S1：参数初始化：取λ

S2：变量初始化：初始化各粒子的排序X

S3：应用式(7)、(8)更新各粒子的排序X

S4：应用式(11)计算各粒子的新适应度newfit

S5：若t

S6：迭代结束，输出具有最优排序的课程分组{OG

离散问题的粒子群算法如下：设在J维空间有N

式中w是惯性系数，λ

进一步的，所述适应度的计算方法如下：

构建考试时间分布矩阵JT

J、M、F分别表示考试时间段数量、学生人数和监考教师人数；每位考生考试时间间隔最小值之和I

式中

每位教师监考时间间隔最小值之和I

式中

根据式(9)、(10)，可按计算适应度fit：

fit＝1/(α

式中α

作为本发明的进一步技术方案为：所述采用离散云进化算法进行监考教师优化安排；具体包括：

S1：参数初始化：设最大迭代次数为1000，连续平凡代数极值为500；

S2：对于F个教师，生成随机数列{f}(f＝1,2,...,F)；对于每一个f，若满足第j行(1≤j≤J)非零元素之和小于需要的监考教师总数NT

S3：根据式(10)，计算适应度值Fit

S4：根据云模型，在F个教师中随机抽取F

S5：判断是否达到最大迭代次数或连续平凡代数极值；若是，转S6；否则转S4；

S6：输出BestFit和BestIndiv；

其中，设共有监考教师F人，每个考场需要N

为了满足目标min v，每位教师的监考次数应不超过平均值

本发明还提供基于分步渐进策略的多目标优化排考系统，包括：

数据获取模块，用于获取考试课程、考场、时间段、考试对象、任课教师和监考教师信息；

分组优化模块，用于对考试对象、考场进行分组优化；

时间优化模块，利用改进离散粒子群算法对时间段进行优化安排；

监考教师优化模块，利用离散云进化算法对监考教师进行优化安排；

输出模块，用于输出优化后的考试课程对应的时间段、考场、考试班级和监考教师安排。

本发明的有益效果为：

本发明提出一种课程分组、时间优化、教师安排的分步渐进求解策略，能够有效降低大规模排考问题的复杂度，提高求解效率、全局寻优能力和算法稳定性；在优化分组阶段，通过基于约束矩阵和课程关联系数排序的分组算法，能够有效解决考生和考场冲突问题；在时间优化安排阶段，通过改进的粒子群算法，能够有效提高收敛速度和全局寻优能力；在监考教师优化安排阶段，通过离散云进化算法，能够实现各组监考教师的优化安排。

附图说明

图1为本发明提出的基于分步渐进策略的多目标优化排考方法流程图；

图2为本发明提出的基于分步渐进策略的多目标优化排考系统结构图；

图3为本发明提出具体实施例中时间安排最优适应度进化曲线图；

图4为本发明提出具体实施例中监考安排最优适应度进化曲线图。

具体实施方式

以下将结合一种实施例和附图对本发明的构思、具体结构及产生的技术效果进行清楚、完整地描述，以充分地理解本发明的目的、特征和效果。显然，所描述的实施例只是本发明的一部分实施例，而不是全部实施例，基于本发明的实施例，本领域的技术人员在不付出创造性劳动的前提下所获得的其他实施例，均属于发明保护的范围。

在学分制管理模式下，学生可以按照一定的规则自由选课，与按班级上课、按班级考试的传统模式相比，排考复杂度更高。为了方便描述优化排考的数学模型，做如下定义：

时间段：在期末考试阶段，一般都是课程教学结束后集中安排考试，因此可将一天划分为几个时间段，比如上午、下午、晚上三个时间段，将其记为D

班级：同时选择一门课程的学生构成一个教学班，一个教学班可分为若干考试班。班级C

课程：在期末考试阶段需要安排考试的所有课程记为集合{L

考场：可供期末考试使用的考场记为R

教师：任课教师记为T

对于优化排考问题，可用如下数学模型描述：

min h(P,C,S,L,R,T)；

min g(P,C,S,L,R,T)；

min y(P,C,S,L,R,T)；

min v(P,C,S,L,R,T)；

D

D

R

上述模型中，P,C,S,L,R,T分别表示时间段，班级，学生，课程，考场和教师；目标函数h(P,C,S,L,R,T)为各时间段内所安排考试数量的均方差，取其最小值就是为保证各时间段的考试场次数一致；g(P,C,S,L,R,T)为每位学生相邻两次考试最小间隔时间总和的倒数，取其最小值就是为实现同一学生两门课程的考试间隔尽可能最大化，以保证学生有充足的复习时间；y(P,C,S,L,R,T)为每位监考教师相邻两次监考最小间隔时间总和的倒数；目标函数v(P,C,S,L,R,T)为各监考教师参加监考数量的均方差，取其最小值就是为保证各教师监考次数一致；式(1)保证不出现同一学生在同一时间段内参加两门课程考试的情况；式(2)保证同一时间段内一个考场只安排一门课程考试；式(3)保证修读一门课程的所有学生在同一时间段内考试；式(4)保证一个时间段内同时考试的场次数小于可供使用的考场总数；式(5)保证每个考场内参加考试的学生人数小于其容量；式(6)保证在不发生冲突的情况下各门课程的任课教师均参与该课程的监考。

参见图1，为本发明提出的基于分步渐进策略的多目标优化排考方法流程图；

如图1所示，基于分步渐进策略的多目标优化排考方法，包括以下步骤：

步骤101，获取考试课程、考场、时间段、考试对象、任课教师和监考教师信息；

步骤102，对考试对象、考场进行分组优化；

步骤103，采用改进离散粒子群算法进行时间段优化安排；

步骤104，采用离散云进化算法进行监考教师优化安排；

步骤105，输出优化后的考试课程对应的时间段、考场、考试班级和监考教师安排。

本发明提出一种课程分组、时间优化、教师安排的分步渐进求解策略，能够有效降低大规模排考问题的复杂度，提高求解效率、全局寻优能力和算法稳定性；在优化分组阶段，通过基于约束矩阵和课程关联系数排序的分组算法，能够有效解决考生和考场冲突问题；在时间优化安排阶段，通过改进的粒子群算法，能够有效提高收敛速度和全局寻优能力；在监考教师优化安排阶段，通过离散云进化算法，能够实现各组监考教师的优化安排。

在步骤102中，所述对考试对象、考场进行分组优化；具体包括：

S1：在给出所有课程{L

S2：对于所有N门课程，求出β

S3：按β

S4：在

S5：遍历未分组课程数组

S6：当约束条件(2)～(4)无法满足时，增加考场数量以完成分组；当优化目标minh无法满足时，放弃该目标以完成分组；

S7：判断

S8：分组结束，输出{G

完成优化分组后，可得到{G

在分组优化阶段，欲实现的目标函数为min h，约束条件为式(1)～(5)；为保证式(1)，可定义课程约束矩阵LS：

LS＝[lrc]

矩阵LS具有对称性，即lrc＝lcr；主对角线元素全部设为0；

第r门课程与其它课程的关联系数β

设参加一门课程考试的学生总数为M，标准化考场的容量为U，则该门课程需要的最少考场数量X＝int(M/U+0.5)，int表示四舍五入取整；

根据课程门数、选课学生数以及标准化考场的容量可计算出总考试场次数为：

设考试时间段总数为J，如果ZE≥J，则Q＝J，否则Q＝ZE，Q为分组数量；每个时间段内的平均考试场次数

在步骤103中，所述采用改进离散粒子群算法进行时间段优化安排；具体包括：

S1：参数初始化：取λ

S2：变量初始化：初始化各粒子的排序(位置)X

S3：应用式(7)、(8)更新各粒子的排序(位置)X

S4：应用式(11)计算各粒子的新适应度newfit

S5：若t

S6：迭代结束，输出具有最优排序的课程分组{OG

将每个分组视作一个粒子，以min g和min y为目标，对各分组进行排序，不同的位次对应不同的考试时间段；求解离散问题的粒子群算法如下：设在J维空间有N

式中w是惯性系数，λ

在分组优化阶段，已使各时间段内的考试安排满足目标min h以及约束条件(1)～(5)，因此，针对各分组的时间优化安排只需满足目标min g、min y和约束(6)即可；对于约束(6)，此阶段只需考虑任课教师监考时间间隔优化问题，其余监考教师安排与考试顺序无关，故此步暂不考虑。

将每个分组视作一个粒子，以min g和min y为目标，对各分组进行排序，不同的位次对应不同的考试时间段。根据待求解问题的特点，本发明采用改进离散粒子群算法进行时间优化安排。

其中，求解离散问题的粒子群算法如下：设在J维空间有N

式中w是惯性系数，λ

将{G

构建考试时间分布矩阵JT

J、M、F分别表示考试时间段数量、学生人数和监考教师人数；每位考生考试时间间隔最小值之和I

式中

每位教师监考时间间隔最小值之和I

式中

根据式(9)、(10)，可按计算适应度fit：

fit＝1/(α

式中α

在步骤104中，所述采用离散云进化算法进行监考教师优化安排；具体包括：

S1：参数初始化：设最大迭代次数为1000，连续平凡代数极值为500；

S2：对于F个教师，生成随机数列{f}(f＝1,2,...,F)；对于每一个f，若满足第j行(1≤j≤J)非零元素之和小于需要的监考教师总数NT

S3：根据式(10)，计算适应度值Fit

S4：根据云模型，在F个教师中随机抽取F

S5：判断是否达到最大迭代次数或连续平凡代数极值；若是，转S6；否则转S4；

S6：输出BestFit和BestIndiv；

其中，设共有监考教师F人，每个考场需要N

为了满足目标min v，每位教师的监考次数应不超过平均值

参见图2，为本发明提出的基于分步渐进策略的多目标优化排考系统结构图；

如图2所示，本发明还提供基于分步渐进策略的多目标优化排考系统，包括：

数据获取模块201，用于获取考试课程、考场、时间段、考试对象、任课教师和监考教师信息；

分组优化模块202，用于对考试对象、考场进行分组优化；

时间优化模块203，利用改进离散粒子群算法对时间段进行优化安排；

监考教师优化模块204，利用离散云进化算法对监考教师进行优化安排；

输出模块205，用于输出优化后的考试课程对应的时间段、考场、考试班级和监考教师安排。

以下实施例对本发明进行具体说明。

设某学期末共有31门课程需要安排考试，各门课的选课人数分别为96，61，102，65，98，110，114，95，78，102，113，62，106，74，99，76，31，35，38，33，69，36，72，78，92，101，105，29，32，74，75，共有标准化考场8个，每个考场容量40人，监考教师38人，每个考场配置2位监考教师，考试时间为5天，每天上午、下午各一个时间段。

本文算法已通过matlab软件编程实现。应用分组优化算法，可得到如下结果：{1,[27,2,9]}，{2,[1,8,17]}，{3,[5,4,12]}，{4,[10,13,18]}，{5,[26,14,19,22]}，{6,[30,11,16]}，{7，[25,15,20]}，{8,[3,21,28]}，{9，[6,24,29]}，{10,[31,7,23]}。以第一个分组为例，说明各分组的含义：1表示组序号，[27,2,9]表示该组内包含的课程序号。

从以上结果可以看出，各组对应的考试场次数分别为：7，7，7，7，7，7，7，6，6，7。通过计算可知，在10个考试时间段内，共需进行考试68场，平均场次数为6.8，在无法达到完全均等的情况下，这一分组结果基本实现了各时间段内场次数基本一致的目标。

应用粒子群优化算法进行时间优化安排，得到的结果为5，3，8，4，10，1，7，9，6，2(数字表示分组序号)。种群最优适应度进化曲线如图3所示。

应用离散云进化算法，对监考教师安排进行优化，最优适应度进化曲线如图4所示。

经过以上步骤，最终所得排考结果见表1。

表1优化排考结果

表中D1～D5表示安排考试第1至5天。[26-1/1/0207]中26-1表示第26门课程的第1个考试班(共3个)，1表示编号为1的考场(共8个，实际一次最多使用7个)，0207表示编号为02和07的两位监考教师(共38位)，其他含义与此相同。

采用遗传算法对课程分组结果进行优化排序，与本文算法的对比情况见表2。遗传算法的相关参数设置为：种群数量1000，交叉概率0.8，变异概率0.1，最大迭代次数200，连续平凡代数极值20。

表2两种算法的对比情况

从表2的数据对比可以看出，本文提出的粒子群算法在收敛速度、计算效率上具有比较明显的优势。同时，适应度值也小于遗传算法的计算结果。因此，在优化排考计算过程中，使用本文提出的改进粒子群算法能够取得较好的优化效果，而且无需编码，操作简单，收敛速度快，计算效率高。

本发明提出的基于分步渐进策略的多目标优化排考方法及系统，针对多约束、多优化目标的大规模排考问题，提出一种“三步式”优化策略。采用“课程分组、时间优化、教师安排”的分步式求解策略，能够化繁为简，大大提高求解效率和优化效果。基于课程约束矩阵和相关系数排序的分组方法，能够在保证多个刚性约束条件的前提下，最大可能地实现柔性优化目标，能够得到相对合理、优化的分组结果。通过改进权重计算和交换序生成方法，提出改进的粒子群方法，并应用其求解各课程组的时间优化安排问题。与遗传算法相比，该方法具有收敛速度快和求解效率高的优点。

以上对本发明进行了详细介绍，但是本发明不限于上述实施方式，在本领域普通技术人员所具备的知识范围内，还可以在不脱离本发明宗旨的前提下做出各种变化。不脱离本发明的构思和范围可以做出许多其他改变和改型。应当理解，本发明不限于特定的实施方式，本发明的范围由所附权利要求限定。