论文部分内容阅读
摘 要：教育信息化背景下，众多行业已经或准备实施网络化考试，对网络化考试系统功能也提出了更高要求，文章对网络化考试系统中的一项核心功能——组卷进行研究，提出了一种智能化的组卷方法。该方法首先对题库建立一个目标状态矩阵；然后按照量子进化算法求解多目标约束组合优化问题的方法从矩阵中选取最优化的行组合，从而生成一份最接近用户各项需求的试卷；最后使用《面向对象程序设计》课程试题库进行了实验验证。实验结果表明，该方法能够根据用户需求自动完成组卷过程，而且组卷效率和成功率都比较高。
关键词：网络化考试；智能组卷；组卷目标；试题库
中图分类号：G434 文献标识码：A 文章编号：1673-8454（2015）16-0079-03
一、引言
随着教育信息化的发展，对标准化考试提出了新的要求，建立网络化考试系统是教育信息化背景下实行标准化考试的一项重要内容[1]，而智能组卷作为网络化考试系统的核心功能之一，引起了许多专家的重视，成为网络化考试系统研究的一个重要方向。在早期的计算机自动组卷方法中，常用的有随机选取法和回溯试探法[2]，两种方法虽然算法结构简单，但是组卷时间长，成功率低，智能性差，得到的试卷质量不高，不能满足随机性、科学性、合理性的组卷需求。
智能组卷是指根据用户提出的多项组卷要求，自动地从试题库中选择满足各项需求的试题构成试卷的过程，智能组卷实质上是一类多目标约束组合优化问题。据此，近年来一些研究者提出了使用遗传算法来求解智能组卷问题[3，4]，但是由于此类问题具有NP难度，限制了遗传算法的优化性能，难以获得满意的组卷性能。
量子进化算法（ Quantum Evolutionary Algorithm，QEA） 是量子计算理论与进化计算原理相结合的产物，是一种新发展起来的智能优化算法[5]。QEA使用量子比特编码来表示染色体，增加了种群的多样性，从而避免了早熟收敛；通过量子门更新染色体，保证了进化方向，提高了寻优能力和寻优速度。QEA这种独特的编码和进化机制，使得算法在求解组合优化问题时具有明显的优势，寻优能力和寻优速度都要优于遗传算法。本文使用QEA来求解智能组卷问题，使用QEA的寻优机制快速高质地完成智能组卷过程。
二、组卷问题的模型构建
1.组卷指标选择
智能组卷的操作对象是题库中的试题，组卷时要求能根据各项指标自动地从题库中抽取试题。组卷指标由试题属性来确定，试题的属性有很多，通常有题型、内容、层次、题分、知识点、难度、区分度、题时、曝光度、信度、效度等，这些属性构成了组卷的约束条件。我们的实验表明：约束条件过多会增加组卷难度，降低组卷效率，并且容易导致组卷失败，因此本文根据试题属性对组卷的重要性以及属性之间的内在联系，选取题型、题分、难度、区分度、题时5个试题属性作为组卷的约束条件，对它们的定义如下：
题型：题库中试题的类型，每类题型赋给一个整数值。我们在前期研究中已经开发了《面向对象程序设计》课程的题库（以下简称本文题库），包含判断题、选择题、填空题、编程题、综合应用题，给它们的赋值分别是1、2、3、4、5。
题分：题库中试题的分值，每一题试题都有相应分值。本文题库中试题的分值为1-20的整数。
难度：题库中试题的难易程度，每一题试题都赋给相应的难度系数值。我们通过抽样测试，将本文题库中的试题难度分为难、较难、中、较易、易5个等级，并赋给难度系数为0.9、0.7、0.5、0.3、0.1。
区分度：题库中试题对被测试对象的区分程度，每一题试题都赋给相应的区分度系数值。我们通过抽样测试，将本文题库中的试题区分度分为高、中、低3个等级，并赋给区分度系数为0.8、0.5、0.3。
题时：题库中某试题完成所需的估计时间，每一题试题都赋给一个估计完成时间。我们通过抽样测试，获得了本文题库中每一试题的估计完成时间。
2.组卷模型设计
确定组卷指标后，可以根据组卷指标对题库建立一个由指标所对应的试题属性值构成的目标状态矩阵，由上面选取的5个指标可以获得一个nX5的目标状态矩阵T：
T=t
t
t
t
t
t
t
t
t
t
… … … … …
t
t
t
t
t
其中，n代表题库中试题的总数，矩阵T中每行表示一题试题、每列表示题库中全部试题的某个属性，此时组卷问题的求解转换为： 根据用户确定的组卷目标要求，在矩阵T 中寻找满足组卷目标要求的行组合。它的解可以用一个二进制串来表示：（S1，S2……Sn）Si∈{0，1}，i=1，2……，n，Si=1表示第i题试题被选择，反之表示第i题试题不被选择。
组卷目标要求根据组卷指标设置，对应着组卷约束条件，矩阵T 中的试题属性构成的组卷约束条件如下：
试卷总分：paperScore=S·t （1）
试卷完成时间：paperTime=S·ti5 （2）
试卷难度： paperHard=S·（·t） （3）试卷区分度： paperDis=S·（·t） （4）
三、基于量子进化算法的智能组卷算法设计
分析组卷模型设计的结论可知，组卷问题属于多目标约束组合优化问题，大量的研究已经证明QEA在求解多目标约束组合优化问题时效果明显，据此我们将QEA应用到智能组卷问题中，设计一种能够自动获得满足用户各项需求的试卷的智能组卷算法。算法设计的基本思想是对题库中的试题编码形成初始种群，根据适应度值对其逐代优化，生成一份满足组卷要求的最优试卷。 1.量子染色体构造
使用QEA求解具体问题时，首先应对问题的解进行编码构成QEA中的量子染色体，本文对量子染色体的构造过程如下：将状态矩阵T映射为QEA中的个体（即量子染色体），并按照题型属性将染色体的量子位进行分段。对于本文题库，共有5类题型，假设各类题型的试题数分别为n1、n2、……、n5，则量子染色体结构如下：
（5）
2.种群初始化
随机产生若干个（5）式结构的量子染色体构成QEA的初始种群Q（t），Q（t）={qt1，qt2……qtm}（m为种群大小），然后将量子染色体的各量子位初始化为等概率状态，即将量子位概率幅[αi，βi]初始化为（，）。
3.种群观测
种群观测是对初始化后的量子态种群中个体的各量子位实施测量操作，目的是使各个体量子位从不确定的概率态坍塌到确定的基态，获得观测态个体。测量操作的过程是：对于量子染色体的每一个量子位，随机产生[0，1]之间的一个常数r，若r≥|αi|2（αi为染色体第i个量子位的概率幅），则该量子位（xi）取1，否则取0。种群观测后，量子态种群Q（t）就转化为了观测态种群P（t），P（t）={pt1，pt2……ptm}，其中，观测态个体ptj（j=1，2，……，m）是长度为n的二进制串（x1，x2……xn），xi∈{0，1}。
4.适应度函数设计
QEA中使用适应度来衡量种群中个体的优劣，个体的适应度值通过适应度函数来计算，适应度函数通常由问题的目标函数转化而得到。分析组卷约束条件可知，试卷总分是刚性约束，在每一次组卷过程都必须完全满足，而试卷完成时间、试卷难度、试卷区分度是柔性约束，在组卷时应尽量接近用户指定的期望值，因此组卷的目标函数只需考虑柔性约束。适应度函数的设计过程如下：
step1，根据（2）、（3）、（4）式的约束条件，采用与用户期望值的误差百分比作为单个指标的目标函数：
fpaperTime=（6）
fpaperHard= （7）
fpaperDis=（8）
其中，time、hard、dis分别为对应指标的期望值。
step2，为每个指标分配权重并将其组合为组卷目标函数：
minf=w1fpaperTime w2fpaperHard w3fpaperDis （9）
其中，w1、w2、w3分别为对应指标的权重。
Step3，采用指数比例变换方法将目标函数转换成适应度函数：
F=exp（-ρf） （10）
其中，ρ为放大系数。
5.染色体更新
染色体更新的作用是实现种群的进化，通常使用（11）式所示的量子旋转门来更新量子态种群中的个体，通过（12）式所示的将量子旋转门作用于染色体的量子位，使量子位朝着目标方向偏转。
U（θ）=cos（θ） -sin（θ）
sin（θ） cos（θ）（11）
其中，θ为旋转角度。
αit 1
βit 1=U（θi）αti
βti=cos（θi） -sin（θi）
sin（θi） cos（θi）αti
βti（12）
其中，[αti，βti]T为更新染色体第i个量子位的概率幅，[αit 1，βit 1]T为更新后染色体第i个量子位的概率幅。θi=s（αiβi）·Δθi，Δθi、s（αiβi）分别表示旋转角的大小和方向，可以通过查表获得。
6.染色体交叉
染色体交叉的作用是增加种群的多样性，防止算法陷入早熟收敛。染色体交叉的方法很多，本文根据所设计的染色体结构特点，以各题型分界处为断点，进行全干扰交叉。
7.搜索停止设定
算法在解空间搜索到一定程度后，应该能够停止搜索，输出最优个体。本文以到达最大进化代数或获得最优个体为搜索停止条件。最大进化代数可事先设定，最优个体的判定方法为：连续5代进化中最优个体适应度值的变化小于给定的极小阀值δ。
四、实验验证
1.实验对象与环境
我们以前期研究所开发的《面向对象程序设计》课程试题库为操作对象，对本文提出的智能组卷算法进行验证，并与文[4]算法进行比较。实验在一台Intel（R） Pentium（R） 4 CPU 2.60GHZ、1.00GB内存、Microsoft Windows XP Professional SP2操作系统的单机上进行，在Eclipse Standard环境中使用Java语言完成算法代码。
2.实验参数
实验中，试卷参数设置为：试卷总分设定值为100，试卷完成时间期望值为120，试卷难度期望值为0.6，试卷区分度期望值为0.5；本文算法参数设置为：种群大小为50，搜索停止阀值δ为0.01， 最大进化代数T为300，组卷指标权重系数w1、w2、w3分别为0.4、0.3、0.3，适应度函数的指数比例放大系数ρ为10；文[4]算法参数设置为：种群大小为80，交叉概率、变异概率按文[4]中自适应设置，最大进化代数T为300。
3.实验结果与分析
分别运行本文算法和文[4]算法进行组卷测试，以运行时间、进化代数、组卷成功率为指标来比较算法的性能，实验进行组卷50次，运行结果如表1所示。
由于量子进化算法和遗传算法都能对解空间进行全局搜索，并且在搜索过程中逐步向包含最优解的方向调整搜索空间，从而易于找到最优解，因此在实验结果中可以看出两种算法的组卷成功率都比较高。通过表1数据对两种算法进行比较，可以得出：本文算法的组卷效率明显高于文[4]算法，组卷成功率也略好，表明本文算法的寻优性能优于文[4]算法。
五、结束语
自动、高效的组卷过程和满足用户需求的组卷结果是教育信息化背景下对网络化考试系统组卷功能的要求，本文研究了网络化考试系统中的组卷问题，将组卷转化为多目标约束组合优化问题进行求解，提出了一种智能化的组卷方法，并使用《面向对象程序设计》课程试题库对方法的有效性进行了实验验证。
参考文献：
[1]雍丹，赵丹维.开放教育网络化考试的影响因素及对策探讨[J].中国教育信息化，2012（15）：33-35.
[2]代保新.基于智能组卷的在线考试系统设计与实现[D].长春：吉林大学，2014.
[3]肖理庆，徐晓菊.改进遗传算法智能组卷研究[J].计算机工程与设计，2012，33（10）：3970-3974.
[4]许永达.基于改进遗传算法的智能组卷研究[J].计算机与数字工程，2013，41（2）：176-178.
[5]Han K H， Kim J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization [J]. IEEE Trans on Evolutionary Computation，2002（6）：580-593.
（编辑：鲁利瑞）
关键词：网络化考试；智能组卷；组卷目标；试题库
中图分类号：G434 文献标识码：A 文章编号：1673-8454（2015）16-0079-03
一、引言
随着教育信息化的发展，对标准化考试提出了新的要求，建立网络化考试系统是教育信息化背景下实行标准化考试的一项重要内容[1]，而智能组卷作为网络化考试系统的核心功能之一，引起了许多专家的重视，成为网络化考试系统研究的一个重要方向。在早期的计算机自动组卷方法中，常用的有随机选取法和回溯试探法[2]，两种方法虽然算法结构简单，但是组卷时间长，成功率低，智能性差，得到的试卷质量不高，不能满足随机性、科学性、合理性的组卷需求。
智能组卷是指根据用户提出的多项组卷要求，自动地从试题库中选择满足各项需求的试题构成试卷的过程，智能组卷实质上是一类多目标约束组合优化问题。据此，近年来一些研究者提出了使用遗传算法来求解智能组卷问题[3，4]，但是由于此类问题具有NP难度，限制了遗传算法的优化性能，难以获得满意的组卷性能。
量子进化算法（ Quantum Evolutionary Algorithm，QEA） 是量子计算理论与进化计算原理相结合的产物，是一种新发展起来的智能优化算法[5]。QEA使用量子比特编码来表示染色体，增加了种群的多样性，从而避免了早熟收敛；通过量子门更新染色体，保证了进化方向，提高了寻优能力和寻优速度。QEA这种独特的编码和进化机制，使得算法在求解组合优化问题时具有明显的优势，寻优能力和寻优速度都要优于遗传算法。本文使用QEA来求解智能组卷问题，使用QEA的寻优机制快速高质地完成智能组卷过程。
二、组卷问题的模型构建
1.组卷指标选择
智能组卷的操作对象是题库中的试题，组卷时要求能根据各项指标自动地从题库中抽取试题。组卷指标由试题属性来确定，试题的属性有很多，通常有题型、内容、层次、题分、知识点、难度、区分度、题时、曝光度、信度、效度等，这些属性构成了组卷的约束条件。我们的实验表明：约束条件过多会增加组卷难度，降低组卷效率，并且容易导致组卷失败，因此本文根据试题属性对组卷的重要性以及属性之间的内在联系，选取题型、题分、难度、区分度、题时5个试题属性作为组卷的约束条件，对它们的定义如下：
题型：题库中试题的类型，每类题型赋给一个整数值。我们在前期研究中已经开发了《面向对象程序设计》课程的题库（以下简称本文题库），包含判断题、选择题、填空题、编程题、综合应用题，给它们的赋值分别是1、2、3、4、5。
题分：题库中试题的分值，每一题试题都有相应分值。本文题库中试题的分值为1-20的整数。
难度：题库中试题的难易程度，每一题试题都赋给相应的难度系数值。我们通过抽样测试，将本文题库中的试题难度分为难、较难、中、较易、易5个等级，并赋给难度系数为0.9、0.7、0.5、0.3、0.1。
区分度：题库中试题对被测试对象的区分程度，每一题试题都赋给相应的区分度系数值。我们通过抽样测试，将本文题库中的试题区分度分为高、中、低3个等级，并赋给区分度系数为0.8、0.5、0.3。
题时：题库中某试题完成所需的估计时间，每一题试题都赋给一个估计完成时间。我们通过抽样测试，获得了本文题库中每一试题的估计完成时间。
2.组卷模型设计
确定组卷指标后，可以根据组卷指标对题库建立一个由指标所对应的试题属性值构成的目标状态矩阵，由上面选取的5个指标可以获得一个nX5的目标状态矩阵T：
T=t
t
t
t
t
t
t
t
t
t
… … … … …
t
t
t
t
t
其中，n代表题库中试题的总数，矩阵T中每行表示一题试题、每列表示题库中全部试题的某个属性，此时组卷问题的求解转换为： 根据用户确定的组卷目标要求，在矩阵T 中寻找满足组卷目标要求的行组合。它的解可以用一个二进制串来表示：（S1，S2……Sn）Si∈{0，1}，i=1，2……，n，Si=1表示第i题试题被选择，反之表示第i题试题不被选择。
组卷目标要求根据组卷指标设置，对应着组卷约束条件，矩阵T 中的试题属性构成的组卷约束条件如下：
试卷总分：paperScore=S·t （1）
试卷完成时间：paperTime=S·ti5 （2）
试卷难度： paperHard=S·（·t） （3）试卷区分度： paperDis=S·（·t） （4）
三、基于量子进化算法的智能组卷算法设计
分析组卷模型设计的结论可知，组卷问题属于多目标约束组合优化问题，大量的研究已经证明QEA在求解多目标约束组合优化问题时效果明显，据此我们将QEA应用到智能组卷问题中，设计一种能够自动获得满足用户各项需求的试卷的智能组卷算法。算法设计的基本思想是对题库中的试题编码形成初始种群，根据适应度值对其逐代优化，生成一份满足组卷要求的最优试卷。 1.量子染色体构造
使用QEA求解具体问题时，首先应对问题的解进行编码构成QEA中的量子染色体，本文对量子染色体的构造过程如下：将状态矩阵T映射为QEA中的个体（即量子染色体），并按照题型属性将染色体的量子位进行分段。对于本文题库，共有5类题型，假设各类题型的试题数分别为n1、n2、……、n5，则量子染色体结构如下：
（5）
2.种群初始化
随机产生若干个（5）式结构的量子染色体构成QEA的初始种群Q（t），Q（t）={qt1，qt2……qtm}（m为种群大小），然后将量子染色体的各量子位初始化为等概率状态，即将量子位概率幅[αi，βi]初始化为（，）。
3.种群观测
种群观测是对初始化后的量子态种群中个体的各量子位实施测量操作，目的是使各个体量子位从不确定的概率态坍塌到确定的基态，获得观测态个体。测量操作的过程是：对于量子染色体的每一个量子位，随机产生[0，1]之间的一个常数r，若r≥|αi|2（αi为染色体第i个量子位的概率幅），则该量子位（xi）取1，否则取0。种群观测后，量子态种群Q（t）就转化为了观测态种群P（t），P（t）={pt1，pt2……ptm}，其中，观测态个体ptj（j=1，2，……，m）是长度为n的二进制串（x1，x2……xn），xi∈{0，1}。
4.适应度函数设计
QEA中使用适应度来衡量种群中个体的优劣，个体的适应度值通过适应度函数来计算，适应度函数通常由问题的目标函数转化而得到。分析组卷约束条件可知，试卷总分是刚性约束，在每一次组卷过程都必须完全满足，而试卷完成时间、试卷难度、试卷区分度是柔性约束，在组卷时应尽量接近用户指定的期望值，因此组卷的目标函数只需考虑柔性约束。适应度函数的设计过程如下：
step1，根据（2）、（3）、（4）式的约束条件，采用与用户期望值的误差百分比作为单个指标的目标函数：
fpaperTime=（6）
fpaperHard= （7）
fpaperDis=（8）
其中，time、hard、dis分别为对应指标的期望值。
step2，为每个指标分配权重并将其组合为组卷目标函数：
minf=w1fpaperTime w2fpaperHard w3fpaperDis （9）
其中，w1、w2、w3分别为对应指标的权重。
Step3，采用指数比例变换方法将目标函数转换成适应度函数：
F=exp（-ρf） （10）
其中，ρ为放大系数。
5.染色体更新
染色体更新的作用是实现种群的进化，通常使用（11）式所示的量子旋转门来更新量子态种群中的个体，通过（12）式所示的将量子旋转门作用于染色体的量子位，使量子位朝着目标方向偏转。
U（θ）=cos（θ） -sin（θ）
sin（θ） cos（θ）（11）
其中，θ为旋转角度。
αit 1
βit 1=U（θi）αti
βti=cos（θi） -sin（θi）
sin（θi） cos（θi）αti
βti（12）
其中，[αti，βti]T为更新染色体第i个量子位的概率幅，[αit 1，βit 1]T为更新后染色体第i个量子位的概率幅。θi=s（αiβi）·Δθi，Δθi、s（αiβi）分别表示旋转角的大小和方向，可以通过查表获得。
6.染色体交叉
染色体交叉的作用是增加种群的多样性，防止算法陷入早熟收敛。染色体交叉的方法很多，本文根据所设计的染色体结构特点，以各题型分界处为断点，进行全干扰交叉。
7.搜索停止设定
算法在解空间搜索到一定程度后，应该能够停止搜索，输出最优个体。本文以到达最大进化代数或获得最优个体为搜索停止条件。最大进化代数可事先设定，最优个体的判定方法为：连续5代进化中最优个体适应度值的变化小于给定的极小阀值δ。
四、实验验证
1.实验对象与环境
我们以前期研究所开发的《面向对象程序设计》课程试题库为操作对象，对本文提出的智能组卷算法进行验证，并与文[4]算法进行比较。实验在一台Intel（R） Pentium（R） 4 CPU 2.60GHZ、1.00GB内存、Microsoft Windows XP Professional SP2操作系统的单机上进行，在Eclipse Standard环境中使用Java语言完成算法代码。
2.实验参数
实验中，试卷参数设置为：试卷总分设定值为100，试卷完成时间期望值为120，试卷难度期望值为0.6，试卷区分度期望值为0.5；本文算法参数设置为：种群大小为50，搜索停止阀值δ为0.01， 最大进化代数T为300，组卷指标权重系数w1、w2、w3分别为0.4、0.3、0.3，适应度函数的指数比例放大系数ρ为10；文[4]算法参数设置为：种群大小为80，交叉概率、变异概率按文[4]中自适应设置，最大进化代数T为300。
3.实验结果与分析
分别运行本文算法和文[4]算法进行组卷测试，以运行时间、进化代数、组卷成功率为指标来比较算法的性能，实验进行组卷50次，运行结果如表1所示。
由于量子进化算法和遗传算法都能对解空间进行全局搜索，并且在搜索过程中逐步向包含最优解的方向调整搜索空间，从而易于找到最优解，因此在实验结果中可以看出两种算法的组卷成功率都比较高。通过表1数据对两种算法进行比较，可以得出：本文算法的组卷效率明显高于文[4]算法，组卷成功率也略好，表明本文算法的寻优性能优于文[4]算法。
五、结束语
自动、高效的组卷过程和满足用户需求的组卷结果是教育信息化背景下对网络化考试系统组卷功能的要求，本文研究了网络化考试系统中的组卷问题，将组卷转化为多目标约束组合优化问题进行求解，提出了一种智能化的组卷方法，并使用《面向对象程序设计》课程试题库对方法的有效性进行了实验验证。
参考文献：
[1]雍丹，赵丹维.开放教育网络化考试的影响因素及对策探讨[J].中国教育信息化，2012（15）：33-35.
[2]代保新.基于智能组卷的在线考试系统设计与实现[D].长春：吉林大学，2014.
[3]肖理庆，徐晓菊.改进遗传算法智能组卷研究[J].计算机工程与设计，2012，33（10）：3970-3974.
[4]许永达.基于改进遗传算法的智能组卷研究[J].计算机与数字工程，2013，41（2）：176-178.
[5]Han K H， Kim J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization [J]. IEEE Trans on Evolutionary Computation，2002（6）：580-593.
（编辑：鲁利瑞）