基于遗传算法的开放教育在线考试系统组卷实现

[摘 要]文章利用遗传算法，实现开放教育在线考试系统组卷，教师只需设置部分常规的试卷题型、题量、总分等约束条件，其它如试卷难易度、章节覆盖率、试题曝光度等约束条件由系统自动生成，实现自动化、智能化组卷。

[关键词]开放教育;在线考试;遗传算法;组卷

[中图分类号]G434 [文献标识码]A [文章编号]1008-7656（2019）02-0024-03

由于开放教育在职成人学生存在分布分散、工学矛盾等特点，全部课程都集中在期末统一时间进行纸质考试，容易造成考试安排时间长、学生参考成本高、缺考率高、考务管理难度大等问题。为此，国家开放大学及各省级电大都在探索开展在线考试改革工作，通过采用网络在线考试，让基层考点能灵活组织课程考试，使学生随时随地考试，把考试融入到平时学习中，充分调动学生参与学习的积极性。对于开放教育在线考试而言，如何设计组卷策略是关键之一，要考虑开放教育多层级管理模式及基层考点数量多、技术力量相对薄弱的特点，尽量减少人工设置组卷参数，使组卷方式自动化、智能化，组卷生成的试卷具有随机性、科学性和合理性。

一、遗传算法

遗传算法（Genetic Algorithm）是一种模拟自然界生物进化规律的优胜劣汰规则演化而来的随机搜索算法，它模拟生物界从一个随机初始种群开始，通过对种群中个体不断进行选择、交叉、变异等操作，使种群中的优秀个体经过进化后保留下来，淘汰劣质的个体，通过不断的进化得到越来越优秀的种群，其在解决多种约束条件下的最优解这类问题上具有优秀的表现，算法主要步骤如下。

（一）初始化：设置问题编码方式，生成初始种群。

（二）计算个体适应度：对种群中的每个个体进行评价，计算个体的优劣程度。

（三）选择：根据个体适应度从种群中选择个体生成新种群。

（四）交叉：对种群中的个体进行叉交配对生成新种群。

（五）变异：对种群中个体的染色体进行变异生成新的种群。

（六）结束：通过不断进行选择、交叉、变异操作达到截止条件后，从种群中选择最优个体即作为问题最优解。

二、组卷原理

组卷是根据用户给定的约束条件（试卷总分、难度系数、考试时长、考试章节、题型、题量、曝光度等），从试题库中依据一定的策略（算法）选取与约束条件相匹配的试题组成试卷的过程。试题库中的约束条件试题通常包括：题号、题型、所属知识点、难度、区分度、题干、操作说明、作答时间、分数、曝光次数、上次使用时间等特征参数。

利用遗传算法组卷，首先将组卷过程中涉及的试卷库、试卷、试题、试题特征参数等相关概念映射为遗传算法中的种群、个体、染色体、基因等相关概念，其对应关系为：种群—试卷库，个体—试卷，染色体—试题，基因—试题特征参数。然后根据组卷约束条件建立遗传算法组卷数学模型，对组卷问题“解”（试卷）的染色体（试题）进行编码，确定数学模型的数据结构。最后通过对试卷库（种群）中的试卷（个体）不断执行选择、交叉、变异等遗传操作，当遗传操作达到设定的条件后，选择试卷库（种群）中最优的试卷（个体）完成遗传算法组卷操作。

三、遗传算法组卷实现

（一）适应度函数设计

虽然组卷涉及的约束条件较多，有总分、总时长、题型、题量、题目分值、难度系数、知识点覆盖率、曝光度等，但在本系统的开发中，为保证每科目试卷规格的统一，试卷的题型、题目分值、总分数、总时长等常规约束条件由教师在组卷时统一设置，因此算法需处理的约束条件仅包括试卷难度、知识点覆盖率和曝光度。

其中N表示试卷预期难度与实际难度的偏差值，NP表示试卷预期难度，取值范围为[0，1]，取值越大，试卷预期难度越大，k表示试卷题量，ni表示第i题的难度，ni取值范围为[0，1]，ti表示第i题的分数，Z表示试卷总分，可推算出N的取值范围为[0，1]，取值越小，试卷难度越接近预期难度，试卷質量越好。

其中P表示试卷曝光度，即试卷中出现已曝光的试题分数占试卷总分的比例，且该值与试题曝光次数相关，k表示试卷题量，pi表示第i题是否曝光，取值为0或1，0表示该题还未被使用过，1表示该题已被其它试卷使用过，ti表示第i题的分数，Z表示试卷总分，spi表示第i题的曝光次数，m表示题库总题量，当题库中无试题曝光时，P=0，可推算出P的取值范围为[0，1]， 取值越小，试卷曝光度越低，试卷质量越好。

其中F表示题库中各章节题量在题库所占比例与所生成的试卷中对应章节题量在试卷中所占比例的偏差之和，k表示题库章节数，tki表示题库中第i章题量，TK表示题库总题量，sji表示试卷中第i章题量，SJ表示试卷总题量，可推算出F的取值范围为[0，2]，取值越小，试卷章节题量与题库章节题量越对应，试卷质量越好。

4.对于遗传算法适应度函数来说，取值必须为非负，且取值越大越好，综合考虑式1、2、3取值范围，本系统试卷适应度函数设计为：

当N、P、F值越小时，S值越大，表示该试卷质量越好，其繁殖能力越强，有更大的几率参与下一代遗传。

（二）数据结构设计

遗传算法通过不断迭代计算求解最优解，虽然它具有良好的全局寻优和收敛速度快等特点，但也应结合实际应用及程序语言，做好编码方案和数据结构设计，以便提高算法执行速度。本系统采用vbscript作为程序语言，试题存储在数据库中，为了避免算法迭代过程中频繁读取数据库影响速度，对染色体采用字符串编码方式，将需要参与遗传计算的试题特征参数全部以基因形式存储在染色体编码中，即每道试题编码如下：试题编号-分数-难度-曝光次数-章节号，并利用二维数组存储种群，如式（5）所示。

二维数组S中每一行即表示一套试卷，dij表示第i套试卷第j道试题的编码（0≤i

（三）算法结构

1.种群初始化

设置初始种群规模大小为m，本系统m取值为50。设试卷共有k种题型，每种题型题目数量为Tk，每种题型每题分数为Sk，则试卷总题量为∑ki =1Tk，试卷总分为∑ki =1Sk，定义二维数组S[m，n+1]。从数据库中根据试卷题型及题型题量随机选取m套试卷的试题信息（试题编号-分数-难度-曝光次数-章节号）存入二维数组S中，利用公式（4），计算每套试卷适应度值，存入二维数组S最后一列。

2.选择

采用轮盘赌选择法，将种群中质量较好的试卷以较大的概率选择出来遗传至下一代，其原理为：利用种群中试卷的适应度值来划分轮盘区域，适应度越大，所占轮盘的区域就越大，被选取的概率就越大。设第i套试卷被选取的概率为Pi，则

每次从种群中选取试卷时，先随机生成一个在区间[0，1]之间的数R，若∑ki=0 Pi≥R（k<m），则第k套试卷被选取，重复该方法选取m套试卷存放在新数组St[m，n+1]中。

3.交叉

因试卷由多种题型组成，本系统采用按题型分段单点交叉法，即对试卷每种题型都进行交叉操作，每次采用随机法从数组St [m，n+1]随机选取两套试卷进行交叉，生成的下一代试卷存放回原数组S[m，n+1]中。同时为使部分试卷保留原始基因遗传到下一代，本系统设置交叉概率Pc=0.75，交换前先随机生成一个在区间[0，1]之间的数R，如R≤Pc，则对选取的试卷进行交叉，否则不交叉，选取的两套试卷原样遗传至下一代，对于执行了交叉的试卷，需重新计算试卷适应度值。交叉后，如试卷中存在重复的题目，则应将其替换为未重复的题目。

4.变异

变异属于小概率事件，本系统取变异概率Pm=0.08，依次选取数组S[m，n+1]的每套试卷，先随机生成一个在区间[0，1]之间的数R，如R≤Pm，则对该套试卷进行变异操作，随机生成一个小于试卷总题量的正整数作为需变异题目序号，将该题目替换成其它题型相同且不与当前试卷题目重复的题目。

5.結束

遗传算法通过不断迭代运行公式，使其解尽可能接近最优解，同时也要考虑算法运行时间，并不是迭代次数越多越好，本系统设置为300，同时设置最优试卷期望适应度值为3.8，在迭代过程中，满足任一条件即中止迭代，种群中适应度值最高的试卷即作为成功组卷的试卷。

四、总结

文章结合广西远程开放教育在线考试系统开发工作，重点研究针对开放教育特点，采用遗传算法实现系统组卷功能的原理及算法过程。系统测试结果表明，通过使用遗传算法对开放教育在线考试进行组卷，能够便捷、快速、随机且较为科学地实现考点考试组卷。

[参考文献]

[1]实例讲解遗传算法——基于遗传算法的自动组卷系统[EB/OL]. https：//www.Cnblogs.com/artwl/archive/2011/05/19/2051556.html，2011.

[2]余胜泉，姚顾波，何克抗.通用试题库组卷策略算法[M/CD].1999.

[3]胡木林. 基于遗传算法的在线考试系统组卷设计[J].中国教育技术装备，2018（12）.

[4]韩蕾. 基于遗传算法的自动组卷系统的研究与实现[D].青岛：中国海洋大学，2010.

[5]王军伟.基于遗传算法的组卷系统的研究与应用[D].南昌：南昌大学，2010.

[6]黄国政.基于遗传算法的组卷系统的设计与实现[D].南京：南京理工大学，2008.

[7]靳国兴，文汉云.试题库中自动组卷算法的设计[J].长江大学学报（自然科学版），2008（4）.

[作者简介]邓明学（1981-），男，江西宜春人，广西大学计算机与电子信息学院在读工程硕士，广西广播电视大学教务处副处长，工程师，研究方向：计算机网络与并行分布计算技术、远程教育管理。

[责任编辑 韦书令]