基于遗传算法的考试监考安排最优化分配模型的研究外文翻译资料

英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料

基于遗传算法的考试监考安排最优化分配模型的研究

1 Wang Yunwu, 2 Yu Xueyong, 3 Xu Weiqiang

*1, Corresponding Author Zhejiang University City College, E-mail: wywchinazj_2013@126.com

2, Zhejiang University City College, E-mail:yuxy@126.com

3, Huzhou Public Security Bureau, E-mail:xuweiqing001@163.com

摘要：考试监考安排基于教室资源、教师资源和考试课程，在怎样合理安排问题的前提下，其实质是包含多目标数学编程问题的约束条件。然而，在实际的问题中，因为变化涉及的很多因素，在时间复杂度的信息是NP难的问题，所以用传统的多目标数学规划算法很难给出答案。同时基于经典多目标数学规划算法的结合，采用现代遗传算法，它可以简化处理困难问题的难度，对于解决同样的问题给予了总体规划。

关键字：遗传算法 多目标规划 惩罚因子 试用函数

1 介绍

近年来，随着大学生数量的增加，学校对于期末考试总是遭遇着各种各样的难题，例如没有根据年级将各班学生的考试时间错开，教师分配不充足或者学生参与考试的时间过于集中等。当考试是显而易见的时候，这些问题存在于大领域的进程中，例如高等数学和线性代数的测试，和一些全校性选修课宽考试等等。

2 问题描述和设计思路

考试合理安排和管理的问题是一个带有复杂约束条件的排列优化和规划问题，在这些安排中涉及专业，教师，教室，时间，课程等等相互牵制的不同因素，它的解决方案是在任何考试过程中需要有两个监考老师和适当容量的相关教室，并在这些安排上不能有冲突，例如：

1. 一个监考老师负责一个或多个课程；
2. 同一年级的专业需要参加一个或多个专业必修考试；
3. 同一个教室安排一个或多个考试；
4. 考试人数比课堂容量大。

这些类型的冲突，属于硬性冲突，一定要避免，否则不能安排测试，同时，在尽可能的情况下，考虑一些教师的利益和学生们的需求，例如：

1. 同一专业的考试要尽可能地分散，不要太集中;
2. 当安排老师需要不断监考的时候，尽可能将该老师安排在相同的教室里；
3. 专业类的考试应该避免在全校性的大范围内测试时间；
4. 重要的考试课程尽量安排在一个合适的时间段，比如一个学校选修课程类的考试可以被布置在傍晚时分；
5. 安排教室应尽可能要考试人数匹配课堂容量，合理充分利用教室资源。

这种冲突显然不是绝对的，但是会影响到学生、教师和学校满意度。

因此，主要矛盾与安排的困难是得到资源的最大利用率，与此同时，尽量满足学生和教师的利益，尽量分散考试的监考压力，如图1所示：

图一 考试和考试时间的关系

A，B，C，D代表四项考试，1,2,3,4代表四个考试时间段，我们的目标是每个考试时间段不发生冲突，并且每一时间段包含的考试尽量平均。与此同时，另一个困难在于如何安排学校课程选修性与学校课程大面积性，而后者可以认为是每个必修课的主要要求，如英语，积分，线性代数等。这将会使得某个专业学生的课程作为这三种，无法得到解集。这里的问题是一些大面积的课程和学校选修课以及必修专业课在考试时间上的冲突，这样增加了安排的难度。在为了解决这个问题，根据实际情况，我们首先假设全校性选修课考试部分有测验形式结束（包括论文），并在考试过程中，我们假设考试时间每天有间四个时间段，最后的时间用于其余部分的全校性公共课程的考试。所以我们思考如何去安排学校课程，兼顾每个主要大型强制考试和监考安排。我们将按照上面的思路和约束条件，采用数学规划的经典目标方法，建立目标函数，然后所有约束条件作为评价函数产生的方式，代入目标函数，当安排的某一点不能满足优化的目标会产生其相应的惩罚值。我们再次利用遗传算法的目标函数确定适应度函数。遗传算法是在持续指导下的和适度，计算机迭代给定随机的初始解，并在同一时间，创建新的一组解，每个答案通过一个适合度552s函数得到评价，除非它达到某种形式的收敛，否则重复此过程。一组新的解决方案经由旧解决方案选择性的、高价值的功能，不仅可以保留一些客观函数，并且可以包括与其他的一些组合解决方案，并得到答案。

3 符号和功能的说明

1. 专业的数量是N；
2. 每个专业的学生数量是；
3. 学校内大面积都有的一个课程其数量是A；
4. 必修课的数量i在每个专业是；
5. 学校的集合是；
6. 考试时间是m天，这是根据不同的实际情况可以是认为是可变或固定的值；
7. 教室总数是Ｒ，每个教室的总容量是Ｑ；
8. 设，它们分别以量化教师，学生和学校的满意度，目标函数和适应度函数的作用是很重要的因素。三大功能被定义的，所以我们首先定义三组，｛各专业课程考试科目｝，｛大面积考试科目｝，｛考试时间段｝，，考试进行由ｍ天代表。所给标志，它的意思是测试的Ｊ时间段，例如代表第一天的第一时间段。
9. ，代表ｉ专业的ｊ必修课，设可以表示为，设可以表示为。

定义：

是笛卡尔乘积，其含义是如果中该第i专业的j专业考试被布置在所述p天里q部分的第一天，否则结果为0。

的意思是i专业和j专业的考试被安排在一天里，否则结果为0。

定义：

在中，意思是第一场考试在第一天的大区域p门举行。

1. 两个函数定义为和

定义：

意思是老师在p天的q时间段有监考任务，否则值为0。

定义：

意思是专业老师需要监考的总数。

1. 引入数学标志，Card意味着一组或者潜在的此类基数，例如

4 建立和模型的求解

4.1 建立模型

从需要解决的问题和假设的问题，我们分别对学生，教师和办学效益量化。首先，我们考虑到学生群体，学生总是希望他们的专业考试分布尽可能地均匀不是过于集中，并与大区考试日程不发生冲突，所以我们定义：

考试的分散度意味着中某个较大值越高，学生的满意程度越高，是每个实际问题的权重系数，根据实际情况可以考虑设定一个某个值。类似的我们定义：

其中beta;是一个常值的权重系数，的值受两个因素影响，监考安排越分散，监考的值越高。最后给一个特定的表达，我们使用资源利用率给出资源利用这个定义，那就是：

这是一个资源配置分配的优化措施，是一个水平的重要标准，定义如下：

其中表示在考试期间，只将一般的老师用作考试监考，另一半作为自习教室的使用或者其他，并且表示i天参加考试的学生总数，作为权重系数，让我们考虑涉及到的约束条件：

1. 硬性冲突

在同一天的同一时间段不能超过考试学科的数目，其可以有多个考场考相同的学科，那就是：

其中。例如，对一个特定的时间段，一门考试科目所需要的监考老师不能超过教师的总数，即：

1. 不仅考虑避免软性冲突，一个专业的两个专业考试不在同一天

其中是权重系数，在权重中用来平衡，是惩罚因子，即：

最后，适用函数如下：

冲突越明显，满意度越不高，适用性小，用自然净化的规则其被选中的遗传概率就小。我们给特定的遗传算法，所示图2。

图二 遗传算法流程

4.2 遗传算法与优化

所给的条件通过适用性函数，解决这个问题，在进化的定算法设计过程来确定第一编码方案，在经典遗传算法，它是经常使用十进制或二进制编码方法。考虑到本体论的实际情况，我们

采用矩阵码。首先定义矩阵A表示可能的考试教师安排计划，矩阵X为A可能的监考安排。首先，我们将整个学校m天的考试时间根据顺序分为3m的时间区间，其中定义A行的课程编码的值，学校所有专业必修课和A的大面积A课程，A列值为整个学校所有r教师3m的时间标准数字，具体定义为：

其特定的意义是如果，即第i专业第j个教室被安排在第p个专业考试的第q个时间段，否则。类似的即对i个大范围内，在p个教室和q个时间段。所以我们将考试教室安排和矩阵建立在相关关系中。矩阵B的定义，对于所以老师的ID号的行列值同上，即：

它的含义是，即第一个老师在P教室的Q时间监考，否则。

5 结果

我们采取以下课程为例;在C编程语言有以下课程教室和教师监考的时间表，如表1所示。

表2 考试时间和地点

因为在这种情况下，模型算法结果受许多因素的影响，我们转向在旁边的总教室和教师数的总数，在灵敏度分析算法的基础上，求总数。

为了比较，我们重新定义,上述两个因素影响在图3中所示的模型，其中，纵坐标是量化的S值，代表整体示满意，1,2,3,4代表其满意的逐渐增加，横轴表示的变化因素值。

图3 在模型结果影响的教室和教室因素

教师的总数是影响模型结果在一个非常重要的方面，教师的数目将直接影响到监考安排难度大小，从结果可以看出，减少教师的数量影响比的增加的老师数量的影响更大，在教师数量的减少的情况下，满意度急剧下降，整体水平减少的比例可近似为线性。

约束的总数也是模型效应的结果，从图中不难发现，当改变数目，整个装置的结果产生重大的改变，总体满意度也有相应的增加或减少。

据老师们对事件和监考时间的满意度的反应，我们选择一些属性，一般认为以下五个属性对教师监考满意度有较大的影响：

1. 监考老师人数(NoET);
2. 候选人(NoC);
3. 考试课程的数量(NoEC)；
4. 考场的数量(NoER)；
5. 教室容纳量(ERC)。

遗传算法引入这个过程，被用于调整每个属性的权重。

1. 代码：因为在这种情况下有五个属性，所以在这里将取决于设定在0~1的每个属性的重要性，有效值给定到小数点后两位。根据问题将为染色体二进制方式，为了在0至100的范围内设置，因此，我们将给出第二个数字为个位数，第一个数字是10位数，每个基因包含7字节，由5个基因的染色体代表一个属性的权重，并且表示可能解。
2. 选择：本研究的的轮盘，选择高概率适应较大值。
3. 匹配：取双点交配模式，在0.6和1.0，这之间的一般速度设定研究设定为0.7。
4. 突变：采取单点反向操作：0变为1，1变为0的不太大的突变率，所以设置为0.015。

图4是该系统的遗传算法的框架进行模拟的图像，在该画面的左侧是遗传算法的收敛过程。在图的中间是遗传算法设置参数区域。在图中的右侧，有遗传的存在算法是最好的建议染色体的解决方案。可以从曲线图中，在考试课程栅极可见数是影响模型的结果是最重要的因素，但在考试过程中栅数目并不变化，所以因素将不会被考虑。

6 讨论

用来实现最优解测试装置的遗传算法是是一种相对简单和实用的方案，收敛速度快时，时间分布合理。但在实际应用中可能不会停止这种状态;其目的是提供一种不同的解决方案供用户选择，直到所有解决方案完成或用户终止。值得一提的是，可行解决方案的一些实际问题是唯一可能的，如教师或资源短缺的教室。如果约束条件是过于苛求，可能没有可行的解决方案。

该解决方案是一个纯粹的数学规划问题，考场要求

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[31239]，资料为PDF文档或Word文档，PDF文档可免费转换为Word