现阶段的数据库技术专业课程的考试中, 有学校用机试, 也有用笔试, 其操作过程为个人出卷、发卷, 考生考完后, 需回收试卷, 再交到改卷老师手里, 工作量巨大且效率低下, 耗费了大量人力、物力和财力. 因此, 开发数据库技术专业课程考试资源库与在线考试系统刻不容缓, 以期推行无纸化组卷及考试, 提高工作效率同时降低人财物力. 要推行无纸化在线考核, 关键技术为自动化组卷问题, 其组卷结果及效率是众多学者关心和研究热点^[1–3]. 在学者们研究的基础上, 对多种组卷技术及方法进行对比和研究, 主要有随机变量法、回溯试探法及人工智能法. 最早所使用的随机变量算法, 顾名思义为随机选择题目实施试卷组合, 后与目标期望值来比对, 达到要求即形成考试试卷, 该方法易于操作, 但因为仅仅是排列组合, 故试卷组装的质量不佳, 费时费力, 失败率极高. 回溯试探算法进一步优化了组卷效率, 无效试卷得到控制, 但缺点是题库数目大时, 回溯的数量大大增加, 使用时间更长, 耗费大量的系统内存. 为了更好组成高质量的试卷, 满足在线考试的要求, 本文更多的是讨论和研究人工智能算法, 主要是遗传算法及蚁群算法. 通过对比, 使用更加高效的算法应用于自动组卷, 从而更好的促进在线考试和远程教育的发展.

1 遗传算法与蚁群算法组卷简介

求解遗传算法的关键是在多目标求解时引入了竞争机制及变异机制, 关键问题是优化遗传算子、交叉算子和变异算子. 而求解蚁群算法的关键是在蚁群爬过的路段上释放信息素, 其浓度可以反映出路段的优劣, 得出最佳解^[4,5]. 与遗传算法和蚁群算法相类似, 自动化组卷的过程即为求得多目标最优解的过程^[6].

2 构建组卷质量指标体系

数据库技术专业课程组卷关键是按试卷的要求及期望来形成试卷, 指标体系主要有平均难度指标、区分度指标、信度指标等.

2.1 平均难度指标

数据库技术课程组卷平均难度指标指参加考试的全部学生在题目上的失分率, 以符号A描述. 平均难度指标见公式(1).

$A = \frac{{\displaystyle\sum\limits_{i = 1}^t {{X_i} \times {Y_i}} }}{M}$

(1)

上述等式的 X i 描述的是题目 i 的分值, Y i 描述的是题目 i 的难题, t 描述的是数据库技术试卷的题量.

2.2 区分度指标

该指标描述的是全部考生的水平等级区分度, 以字母 B 表达, 见公式(2).

$B = {B_{high}} - {B_{low}}$

(2)

公式(2)的 B h i g h 指全部考生中高得分的比例, B l o w 指的是低得分的比例, B的值越大, 则区分度越大, 成正相关关系.

2.3 信度指标

该指标描述的是可信度, 为考试结果是否可靠的量化指标, 如公式(3)所示.

$l = \displaystyle\frac{t}{{t - 1}}(1 - \frac{{\displaystyle\sum\limits_{i = 1}^t {{C_i}(1 - {C_i})} }}{{{S^2}}})$

(3)

公式(3)中, t 指总试题量, S 2 指题目总分的方差, C i 指试卷 i 通过的比例, 而信度以 l 表示.

3 人工智能自动组卷 3.1 自动化组卷数学模型

通过预先设定数据库技术专业课程的组卷约束和质量目标, 包括组卷题型、知识点、难度等指标和要求, 并以此为属性按要求展开组卷. 组卷期望值及约束一般有试卷题型、试卷难度水平、试卷知识点要求及排列等. 本文的数据库技术试题库的一份试卷的题目数量为m, 每一试题为n个指标或属性, 由此构建或组成的试卷T为m×n矩阵, 如公式(4)所示.

${\rm T} = \left[ {\begin{array}{*{20}{c}}{{a_{11}}}&{{a_{12}}}& \cdots &{{a_{1n}}}\\{{a_{21}}}&{{a_{22}}}& \cdots &{{a_{2n}}}\\ \vdots & \vdots & \vdots & \vdots \\{{a_{m1}}}&{{a_{m2}}}& \cdots &{{a_{mn}}}\end{array}} \right]$

(4)

其中, 根据组卷要求, T矩阵必须满足的约束条件主要有:

(1)分数约束, 见公式(5)所示.

$E = \displaystyle\sum\limits_{i = 1}^t a $

(5)

该约束一般由使用者确定.

(2)题型约束, 见公式(6)所示.

${F_i} = \displaystyle\sum\limits_{i = 1}^t {{P_{ij}} \times {a_{ij}}} $

(6)

式中， ${P_{ij}} = \left\{ {\begin{array}{*{20}{c}}{0\;\;({a_{ij}} = t)}\\{1\;\;({a_{ij}} \ne t)}\end{array}} \right. $ .

F_i为第i题型分数, t为题型号, P为选择、填空、判断、操作题, 该约束的题目类型及各题分数比例由使用者确定.

(3)总时间约束, 见公式(7)所示.

${T_0}(A) = (1 + \alpha )T(A) = (1 + \alpha )\displaystyle\sum\limits_{i = 1}^m {{T_i}(A)} $

(7)

公式中, 考生做试题 A 耗时为 T ( A ) , 复查试卷耗时为 α T ( A ) , 试卷总用时即为 T 0 .

(4)题目难度分布约束, 见公式(8)所示.

${D_i} = \displaystyle\sum\limits_{i = 1}^n {{A_{li}} \times {\alpha _{i1}}} $

(8)

式中, D_i为难度约束. 假设α_i1在第i个难度等级范围内, 则A_1i即为1, 其他情况即为0.

(5)知识点分数约束, 见公式(9)所示.

$\left\{ {\begin{array}{*{20}{c}}{{M_1} \le \displaystyle\sum\limits_{i = 1}^x {{A_{1i}} \times {\alpha _{i1}} \le {N_1}} }\\{{M_2} \le \displaystyle\sum\limits_{i = 1}^x {{A_{2i}} \times {\alpha _{i2}} \le {N_2}} }\end{array}} \right.$

(9)

M₁和M₂为掌握题型和理解题型等的集合, 相对的分数范围分别为[M₁, N₁]和[M₂, N₂], 其公式为式(9)所示.

(6)知识点覆盖约束, 见公式(10)所示.

$G = \displaystyle\frac{L}{U} \ge g$

(10)

公式中, 试卷对数据库课程大纲的知识覆盖比例用 G 表示, L 描述了试卷中已覆盖的知识点, U 描述的是考试大纲总知识点数, 正常情形下, 通常的试题知识点覆盖率应大于80%或以上.

通过对上述的组卷数学模型研究与分析, 可知自动组卷核心和关键是多目标的求解和优化. 要求出最优解, 必须满足多个目标的情形, 并且需满足给定的约束条件, 使得目标函数越小, 所求的解就越好. 不过, 不同的目标之间求解往往会有互斥性, 所以在多个目标情形下, 有可能得不到最优. 为求得解, 往往将多变量变换为单目标变量函数. 本文通过目标加权法, 对自动组卷实施数学建模. 根据各个目标的实际需求, 分别计算权值, 各目标与权值相乘, 再相加即归一化的目标数学模型. 如公式(11)所示.

$\min \displaystyle\sum\limits_{i = 1}^i {{\omega _i}({D_{1i}} + {D_{ni}})} $

(11)

$\left\{ {\begin{array}{*{20}{c}}{\displaystyle\sum\limits_{i = 1}^T {{A_i} = t} }\\{\displaystyle\sum\limits_{i = 1}^T {{\alpha _{ij}}{A_i} + {D_{1i}} - {\varepsilon _{1i}} = {M_i},i = 1,2,3, \cdots, j} }\\{\displaystyle\sum\limits_{i = 1}^T {{\alpha _{ij}}{A_i} + {D_{ni}} - {\varepsilon _{ni}} = {N_i},i = 1,2,3, \cdots, j} }\end{array}} \right.$

(66)

其中,

${A_i} = \left\{ {\begin{array}{*{20}{c}}\!\!\!\!1, \text{当被选中的第}i\text{题时}\\\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!0, \text{其他情况时}\end{array}} \right.\text{，}i = 1,2,3, \cdots, T$

(65)

通过加权与乘积, 求和后获得组卷的目标函数, 如公式(12)所示.

$F(A) = {\omega _1} \times {D_1} + {\omega _1} \times ({D_{M1}} + {D_{N1}} + {D_{M2}} + {D_{N2}}) + {\omega _3} \times {D_3}$

(12)

公式(12)中, ϖ 描述的是各目标所占的权重, 其实现了多目标的合并化处理, 只需求出线性函数 F ( A ) 的值即可.

3.2 改进遗传算法自动组卷

以遗传算法和相关技术为依据, 按照上述的组卷归一化函数为目标, 重新设计及改进遗传算法的编码形式、适应度函数、遗传算子及组卷策略.

3.2.1 改进编码形式

传统的遗传算法的编码形式使用的是二进制, 但编码形式为二进制对线性函数的优化有某些误差. 因此, 本文进行了修正, 编码方式采取了段式设计, 其中, 试卷和染色体对应和映射, 题目即和基因对应和映射, 同类型的题目, 其所处的分段区间相同.

图1显示的是数据库技术专业课程按分段实数编码进行求解的人工智能方法, 这样的好处是缩减解码程序, 提升算法效率.

3.2.2 适应度函数设计

当试卷的差值达到最小值, 甚至为零时即为最优解, 这时, 与组卷预期完全一致. 组卷的预期要求函数定义成 F = F 1 + F 2 + F 3 . F 1 为组卷难度分布预期, 它的值小, 则更接近难度分布预期, F 1 定义如公式(13)所示.

${F_1} = \displaystyle\sum\limits_{i = 1}^T {{D_i}} $

(13)

式中, $\left\{ {\begin{array}{*{20}{c}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{{D_i} = 0,\text{当}\left| {{{{Y}}_i} - {X_i}} \right| \le {Z_i}}\\[6pt]{{D_i} = \left| {{Y_i} - {X_i}} \right| - {Z_i},\text{当}\left| {{Y_i} - {X_i}} \right| > {Z_i}}\end{array}} \right. $ .

T描述的是难度值, D_i描述的是难度i相差的值, X_i描述难度i占的分值, Y_i描述难度i实占的分值, Z_i描述难度i允许分值误差. 同理, F₂求认知分值分布的组卷预期, F₃求单元分值分布的组卷预期. 传统的遗传算法的收敛性有所缺陷, 原因是传统遗传算法对适应度函数的取值问题, 其范围一般没有太多限定, 通常是正数即可. 上述的改进遗传算法引用指数比来构造出适应度函数, 如公式(14)所示.

$F = {e^{\alpha (100 - f)}}$

(14)

f描述的是目标函数, α通常设定为−0.03, f值增大, 则F值减少, F>0; 对组卷函数优化后, 其分值分布与期望值差距缩小,f值随之缩小, F值相应增大; 一旦组卷与期望值一致, f值等于0, F值为最大值, F_max=e³, 求得其值约为20. 因为指数比转换法的适应度函数满足目标期望, 体现组卷质量好坏, 因此能很好的应用在遗传算法组卷中.

3.2.3 改进遗传算子

对于遗传算法来说, 选择算子是遗传基因决定因素, 适应度高的组卷元素将优先被选择, 相反, 较低的元素将逐渐被淘汰. 传统遗传算法的选择算子通常是轮盘选择, 其特点是取决于概率, 统计学上有误差, 不一定都能收敛.

本文的改进锦标赛选择算子操作方法是每次均选取适应度函数大的因子进化, 使得形成种群的适应度值为最大, 重复n次后, 最终得到最优的种群. 改进均匀交叉算子在新种群里选择2个配对的题目, 以题目一为起始, 依据交叉概率对每个题目进行交换与比较, 若比较值为大, 即放弃交换, 否则, 先判断是否为重复题目, 若发现重复, 即取消, 否即交叉交换. 改进均匀变异算子以初始化概率起始变异, 将值来比对, 若比较值为大, 即放弃, 若为否, 检查有没有重复, 若有, 重复步骤再比对. 终止条件为无重复, 为真即进行变异操作.

3.3 蚁群算法自动组卷 3.3.1 试卷编码方式

数据库技术课程试题库的题目一般由事先确定, 同一题型其属性相同, 可以使用分块式二进制表示, 每一题型均表示一块. 假如数据库技术课程的试题库有m种题型, 每一题型有n个题目, 这样每个蚂蚁K的编码长度就是m×n, 数据库技术课程组卷编码方式与遗传算法编码大体相同, 具体见图1数据库技术专业课程题目分段编码方法.

3.3.2 适应度函数设计

评价组卷群体的个体是否合适用的是适应度函数, 关于本文, 指的就是组卷的质量. 数据库技术课程的组卷是对试卷要求和期望的实现, 即多目标期望值的优化和求解. 若求得的多目标解为最小值, 即为最佳值, 如公式(15).

$Y(a) = \min (f(a))$

(15)

3.3.3 信息素更新规则与状态转移概率

按照数据库技术课程组卷的要求和期望, 在组卷题库里抽取题目, 初始化信息素浓度及挥发值, 求得蚂蚁爬行角度. 将蚂蚁选好的个体(题目)将先存到内存, 直到求解出所有的解, 后与约束条件进行比较. 假如与约束条件不符, 即需对解执行修正动作, 至符合约束条件为止. 在实际操作中, 往往先对区域最优解进行搜索, 从而得到区域最优解为此轮目标值. 如果这一轮最优解(最优试卷)比全局的解更优, 即取代全局最优, 同时更新信息素, 直到全局最优或结束条件到达. 在开始时, 设定的初始化浓度相同, 搜索过程中, 按照信息素浓度及挥发值作为移动方向, 其值大, 按该题目移动, 同样, 移动方向的机会多, 浓度增高.

设数据库技术数据库中, i 题目的信息素挥发值为 η i , 如公式(16)所示.

${\eta _i} = \displaystyle\frac{{\left[ {\displaystyle\sum\limits_{j = 1}^t {{T_i}({\theta _j})} } \right]}}{t}$

(16)

蚂蚁在移动时, 转移概率见公式(17).

${P^k}_{ij}(x) = \left\{ {\begin{aligned}& {\displaystyle\frac{{{\tau ^\alpha }_{ij}{\eta ^\beta }_{ij}}}{{k{\tau ^\alpha }_{it}{\eta ^\beta }_{it}(x)}},\text{当}t \in allowed,j \in allowe{d_k}}\\& {0, \text{其他情况}}\end{aligned}} \right.$

(17)

公式(17)中, P i j k ( x ) 描述的是蚂蚁 k 在 t 时内从题 i 移转到题 j 的转移概率, η i j 描述的是 i 题转移到 j 题信息素挥发值, a l l o w e d k 描述的是下一目标值, α 与 β 均为权重信息因子, α 描述了残留信息的相对重要程度, β 描述了预见值的相对重要程度, 根据上述, 存储蚂蚁选择过的题目, 不断搜索最优解并更新,

3.3.4 蚁群算法的自动组卷过程

蚁群算法自动组卷方法是先设定并检查自动组卷的约束条件和期望. 初始化蚁群算法及蚁群路径, 设定题目路径的初始值(信息素)为0, 开始时间t为0, 从数据库技术试题库中搜索题目并放进相应的禁忌列表, 设定该蚂蚁在表中Index等于1, 执行i++操作(循环数的递增), 按照转态转移概率公式, 决定蚂蚁下一爬行的路径, 则搜索下一题目的编号, 蚂蚁决定了路径, 即选择了新题目后, 需将该题目编码排进禁忌表, 并对该表的索引号进行修正. 蚁群算法自动组卷步骤示意图见图2.

3.4 人工智能算法组卷非法个体的修正

人工智能算法自动组卷过程中, 可能会有不符合期望值的试卷, 这就要求对算法产生的不符合个体做必要的修正. 即在蚁群对数据库技术试题库求解完毕及路径上信息素执行更新前, 需把与约束条件相勃的个体(试题)优化及修正, 具体做法见以图3给出的步骤.

以上步骤的修正完成判断依据为: 一是达到了最大迭代次数, 二是已得到最优解, 符合原来要求和预期值. 这两个条件的达成则自动组卷完成, 生出最终试卷.

4 人工智能组卷实验结果分析 4.1 遗传算法实验结果

与遗传算法为基础的人工智能组卷方法, 关键指标主要有种群规模、交叉概率及变异概率, 这些指标决定了组卷质量, 应依据组卷实验来设置符合要求的组卷指标. 因此, 本文通过大量的实验数据, 分析和选择符合本数据库技术试题库组卷参数及指标.

4.1.1 实验数据说明

本文以数据库技术课程的自动化组卷为案例, 根据前述的组卷模型、指标及期望值展开试验验证. 设定总分为一百, 组卷要求及约束如表1所列.

在总分100分不变情况下, 已知各种题型的分值、分值分布, 可得到各个题目的数量.

4.1.2 实验结果分析

以文献为参考, 对组卷使用的各项参数进行设定, 种群规模、交叉概率和变异概率分别设定为40、0.6和0.01.

以种群规模为例来试验, 分别设置40、80、160、280和400, 并以此对照组装试卷, 每组数例分别实施3次试卷组装, 对各数例的组装时间及适应度函数均值实施研究, 见图4的折线分析图.

根据图4结果, 分析发现当种群规模为400时, 组卷适应度函数值最高, 而组卷时间相差不显著.

以交叉概率为例来试验, 分别设置0.2、0.4、0.6和0.8, 以此来对照组装试卷, 每组数例分别实施3次试卷组装, 对各数例的组装时间及适应度函数均值实施研究, 见图5折线分析图.

根据图5结果, 分析发现交叉概率值为0.6时, 组卷适应度函数值最高, 而组卷时间相差不显著.

关于变异概率的设定, 其值分别设定为0.004、0.016、0.1、0.16、0.32和0.64, 并进行对照组卷试验, 实施3次组卷对各参数的组卷时间和最大适应度值进行研究, 见图6折线分析图.

根据图6结果, 分析发现变异概率值为0.1时, 组卷适应度函数值最高, 而组卷时间相差不显著. 按照图4至图6的实验结论, 可以得到最佳参数设置的种群规模、交叉概率和变异概率的值为别为400、0.6和0.1. 该参数比例, 本文的数据库技术组卷达到最优组合, 组卷的平均时间可以低至10 s完成一份合符期望的卷子.

4.2 蚁群算法实验结果 4.2.1 实验数据说明

同样是对数据库技术课程实施组卷, 数据库技术试题库的题型同样有选择题、填空题、判断题及操作题5类题目. 组卷题型等约束条件的设定与遗传算法的设定一致, 可以参考表1数据库技术课程组卷约束条件表所示.

4.2.2 实验结果分析

参照相关文献和经验, 初始化蚁群算法的组卷参数, 设置蚂蚁数为10, α =1, β =2, 迭代最大值为100. 为了更好对比各种算法的优劣, 将蚂蚁算法分别与随机变量算法、回溯试探法、遗传算法进行对比研究.

4.3 组卷效率比较

在实际应用中, 组卷方法有很多, 本文将遗传算法、蚁群算法与随机变量法、回溯试探法的组卷效率进行对比研究, 如图7所示.

通过分析和对比, 发现随机变量法的组卷效率要远远低于其它3种算法, 耗费的时间也远远高于其它算法. 其次较低的是回溯试探法, 耗费的时间相对也比较长. 究其原因, 可能是由于该2种算法均是随机搜索算法, 没有人工智能加入, 一旦题目数量很大时, 存储的内存占用较大, 计算起来相当复杂. 从图中分析可知, 遗传算法组装试卷所耗费的时间比随机变量法和回溯试探法要短, 算法效率等到了提升. 而蚁群算法在所有算法里面, 效率最高, 组卷时间也最短, 其为最智能的搜索算法, 全局搜索能力更强, 并且可以并行, 从而缩短搜寻时间, 在一定程度上解决了遗传算法的收敛慢问题, 并可以避免局部最优——即“早熟”问题, 因此, 组卷效率最高.

4.4 组卷成功率比较

四种算法组卷成功率对比如图8所示.

分析图8可以发现, 人工智能算法的成功率最高, 平均达到98%以上(含蚁群算法100%, 遗传算法96%), 而非人工智能的算法成功率较低, 随机变量法62%, 回溯试探法84%. 通过对比研究, 结论是蚁群算法成功率及效率均为最高, 收敛速度快, 质量高, 满足组卷要求和期望值.

5 结束语

数据库技术试题库组卷的本质是对多约束、多目标的问题求最优解. 以数据库技术课程的自动组卷为例, 文中使用了随机变量法、回溯试探法组装试卷, 也用了遗传算法、蚁群算法等人工智能算法用于自动组装试卷. 遗传算法和蚁群算法由于引入了人工智能, 应用了更好的系统框架, 高效的实现了求解功能. 本文对数据库技术课程的试卷组装重新编码、修正各种函数及应用, 并且通过建立求解目标约束矩阵来构建组卷的数学模型, 达到线性化求解组卷的约束条件及期望值. 对遗传算法, 修正遗传算子及组装试卷方法; 对蚁群算法, 完善信息素设计、状态转移概率、非法个体修正等. 本文通过对数据库技术课程试卷组装试验, 大量数据表明, 选择合适试卷组装参数, 多种人工智能的试卷组装时间花费及可靠性均比随机变量法、回溯试探法有很大的改善, 缩短了组卷时间, 提高了成功率, 很好的适应组卷需求和期望, 具备适应性及实用性, 在计算机辅助考试和远程网络学习中应用广泛.