基于量子遗传算法的知识分布优化研究

摘要:研究了智能考试系统的知识分布问题,基于量子计算理论,提出采用量子遗传算法,对知识分布优化策略进行改进,提高了试卷知识分布的覆盖率和效率。

关键词:量子计算;遗传算法;智能优化;考试系统

中图分类号:TP18文献标识码:A文章编号:1009-3044(2009)24-7068-03

Optimal Knowledge Distribution Based on the Quantum Genetic Algorithm

ZHANG Wei, HE Rong

(Yunnan Medical College, Kunming 650051, China)

Abstract: Researched the question about knowledge distribution of intelligent examination system, based on the theory of quantum computing, applied quantum genetic algorithm, to improve the strategy of knowledge distribution optimization for better coverage and efficiency.

Key words: quantum algorithm; genetic algorithm; intelligent optimization; test system

智能组卷是一种新型的计算机考试系统。试卷由撒布在测试区域内的考题按一定出题规则自组织而成, 这些考题具有一定的代表性,能检测出学生对考察科目知识的学习掌握情况。考试系统中,考题的分布以及组织对于提高系统的测试水平具有重要的意义。传统的考试系统知识分布有两种策略,一种是人工规划(Planning模式),另一种是大规模的随机分散(Scattering模式)。前者缺乏灵活性与多样性,且效率低下,不适宜计算机组卷等大规模考试。而后者若要取得较好的分布,就必须设置远多于实际需要的考题才能较完整地覆盖考察科目的测试区域,这与试卷中题目数量的有限性是相互矛盾的,试卷中可能存在考题不合理分布造成的测试阴影和盲区。因此考题的合理分布对智能考试系统的测试效果有重要的作用。尽管针对考试系统国内外进行大量的组卷算法研究,但对于知识点的分布优化问题研究工作还很少,很多研究运用传统遗传算法组卷[1],优化效果不尽理想。针对此问题,本文应用量子遗传算法优化知识点的分布,克服测试阴影和盲区,使考试系统更大范围地测试到更有效的学生学习信息。

1 知识覆盖问题

通过对考试科目的学习,学生学习掌握的知识储存在头脑中。由于学生个体之间的学习差异,导致每个学生大脑中储存和掌握的情况具有不确定性。考试的目的在于,通过试卷测试对学生学习情况做出相对确定的评价。科目知识是相对固定的,我们总是将科目知识当作图谱,按图索骥地构造出试卷去测试学生大脑中相关区域中知识的学习掌握情况,即是否掌握,掌握水平如何等。但在目标试卷生成以前,题库中的考题相对与目标试卷而言表现为存在或不存在两种可能形态。基于此,本文引入量子态对考题进行描述、编码和处理。

1.1 试卷分布构成

试卷覆盖是指由计算机考试系统生成一组考题集合(试卷)对测试区域各个知识点的涵盖。试卷的目的是系统地测试和评价试卷覆盖知识区域内学生的学习情况,并对这些数据进行处理,获得详尽而准确的信息,传送到需要这些信息的教师和教学管理部门。

考题是由考点以问题的形式构成的。其中考点与考试科目的相关知识点对应。因此考题的分布是考试系统获取学生学习信息的关键因素之一,其覆盖范围以及分布优化也随之成为研究领域中的重点。

1.2 试卷覆盖问题

试卷由数量有限的考题组成,每道考题包含若干有针对性的知识点所设置的考点。这些考点形成了考题的测试范围。如何组织试卷完成对目标区域的检测,就是考试系统覆盖性的问题。考题分布优化的任务就是在保持试卷结构完整的前提下,动态调整考题组成,以获得尽可能大的覆盖率,也就是使试卷能获得更广泛的信息。在保持考点充分覆盖的前提下,引入以下定义。

假设考察科目所涵盖的知识范围用集合S表示,组成每套试卷的考题用集合Q={qi,i=1,2,...,n}表示,每道考题测试的知识范围为ci,试卷的测试目标知识区域为A,(A?哿S),则理想的探测效果为。设为试卷有效覆盖知识区域的度量(考点数),d2=A为目标科目知识区域的度量(知识点数),则称ρ=d1/d2为试卷覆盖度。

覆盖性问题不仅反映了试卷所能测试的范围,而且通过合理的覆盖控制还可以使试卷中的考题组合得到优化,提高试卷的命题质量。

1.3 约束条件

我们采用以下公理化方式对知识覆盖问题进行描述(目标):在考题集合Q={q1,q2,...,qn}中求一个子集T作为试卷,使得满足以下约束条件。

① 各考题满足试卷总体约束条件;

② 试卷覆盖度ρ最大;

③ 考题数目T为最少。

3 量子遗传算法的考题分布优化

试卷的考题分布优化是一个多目标优化问题 ,需要在考题数与知识覆盖率之间达到平衡。即在保持试卷中考题数目与题型符合命题要求的情况下,尽可能增加试卷的知识覆盖度,使考题获取最广泛的测试信息。

3.1 量子遗传算法

量子遗传算法是量子计算与遗传算法相结合的产物。它以量子计算的一些概念和理论为基础,用量子比特编码来表示染色体,用量子门作用和量子门更新来完成进化搜索[2]。

我们根据考题在科目知识中的分布和权重(主要是指命题价值)按字典序编号,形成知识地图的坐标。由于题库中的考题在目标试卷生成以前具有不确定性,即在目标试卷中既可能存在,也可能不存在。这符合量子力学中的测不准原则。我们对这些编号进行量子编码,并用量子遗传算法在命题规则的约束下进行知识分布优化。

3.1.1 量子编码

1) 量子态引入

我们用Dirac算符|>和|>分别表示考题在目标试卷中表现为存在或不存在的两种可能形态。若用“1”表示存在,用“0”表示不存在。考题以叠加态的形式存在。即将一个量子比特可能处于|0>和|1>之间的中间态。可表示为:

|Ψ>=α|0>+β|1> (2)

其中α和β分别是|0>和|1>的概率幅,且满足下列归一化条件:

|α|2+|β|2=1(3)

式(3)中,|α|2表示量子比特的观测值在|0>状态的概率投影,|β|2表示量子比特的观测值在|1>状态的概率投影。

定义2.1满足式(2)和式(3)的一对实数α、β称为一个量子比特的概率幅,记为[α,β]T。

定义2.2角度ζ(ζ∈[-π/2,π/2])定义为一个量子比特的相位,即ζ=arctan(β/α)。

2) 染色体量子编码

我们从题型、章节、考题三个方面对试卷的染色体及种群进行量子编码。

其中,m为染色体的基因个体表示知识分布数量(章节数);k为每个基因的量子比特数表示每道题的属性数量。n个这样的个体构成的种群Q(t)={q1t,q2t,...,qnt}表示试卷,其中n为题型数量。

3.1.2 量子旋转门

量子旋转门是实现演化操作的执行机构。[3-5]图1为量子旋转门示意图。

其操作规律如下:

θi=k*f(αi,βi) (6)

其中k是一个与算法收敛速度有关的系数,k的取值必须合理选取,如果k的取值过大,算法搜索的网格就很大,容易出现早熟现象,算法易于收敛于局部极值点,反之,如果 k 的取值过小,则搜索速度太慢甚至会处于停滞状态。因此,本文将k视为一个变量,将k定义为一个与进化代数有关的变量,如,其中t为进化代数,max t是根据待求解的具体问题而设定的一个常数,因此k可以根据进化代数合理地调整网格大小。

函数f(αi,βi)的作用是使算法朝着最优解得方向搜索。本文采用表1的搜索策略。其原理是使当前解逐渐逼近搜索到的最佳解,从而确定量子旋转门的旋转方向。其中符号e表示α和β的乘积,即e=α*β,e的正负值代表此量子比特的相位ζ在平面坐标中所处的象限。 如果 e的值为正,则表示ζ处于第一、三象限,否则处于第二或第四象限。

在表1中,α1和β1是搜索到的最佳节的概率幅,α2和β2是当前解的概率幅,当e1,e2同时大于0时,意味着当前解和搜索到的最佳解均处于第一或第三象限。当|ζ1|>|ζ2|时,表明当前解应朝着逆时针方向旋转,其值为 +1,反之为 -1。同理可推出其他三种情况。

这样,量子门的更新过程可以描述为qjt+1=G(t)*qjt其中,上标t为进化代数,G(t)为第t代量子门,为第t代某个个体的概率幅,qjt+1为第t+1代相应个体的概率幅。

3.1.3 量子遗传算法流程(见图2)

①初始化种群,种群Q={q1,q2,...,qn},其中qj为种群中的第 j 个个体。 令种群中全部的染色体基因(αi,βi) (i=1,2,...,m)都被初始化为,这意味着一个染色体所表达的是其所有可能状态的等概率叠加。同时初始化进化代数t=0。

②量子坍塌法测量:对处于叠加态的量子位进行观测时,叠加态将因此受到干扰,并发生变化,称为坍塌。扰动使为叠加态坍缩为基本态。确定种群大小n和量子位的数目m,包含n个个体的种群通过量子坍塌,得到P(t),其中为第t代种群的第j个解(即第j个个体的测量值),表现形式为长度m为的二进制串,其中每一位为0或1。(量子坍塌即对Q进行测量,测量的步骤是生成一个[0,1] 之间的随机数,若其大于概率幅的平方,则测量结果值取1,否则取0。

③群体的适应度评价,保存最优解作为下一步演化的目标值。

④算法进入循环。首先判断是否满足算法终止条件,如果满足,则程序运行结束;否则对种群中个体实施一次测量,获得一组解及其相应的适应度。

⑤根据当前的演化目标,运用量子旋转门进行调整更新,获得子代种群。调整过程为根据式(6)计算量子旋转门的旋转角,并应用式(5)作用于种群中的所有个体的概率幅,即更新Q。

⑥群体灾变:当接连数代的最优个体为局部极值,这时就实行群体灾变操作,即对进化过程中的种群施加一个较大扰动,使其脱离局部最优点,开始新的搜索。具体操作为:只保留最优值,重新生成其余个体。

⑦迭代与终止进化代数t'=t+1,算法转至式(2)继续执行,直到算法结束。

4 仿真试验

为了验证算法的有效性,我们对传统遗传算法(CGA)与量子遗传算法(QGA)所获得的考题知识覆盖度进行仿真对比。我们将考题对考查科目所含知识的覆盖问题简化为:用12个半径为200的圆所代表的考题去覆盖一块1200×1000的二维平面内用矩形代表的知识区域;种群个体数 P = 45,量子位数目 m = 30,运行 600 代。算法运行结果对照如下。

从图3所示考题知识分布优化中覆盖度的变化特性可以看出在不同阶段的变化中,量子遗传算法优化性能高于传统遗传算法而且稳定性也更强。

5 结论

在试卷中存在考题不合理分布造成的测试阴影和盲区。通过量子遗传算法优化考题分布,使其在保证命题要求的情况下,用最少的考题取得最大的覆盖率,可以有效地消除探测区域内的阴影和盲点。仿真结果也表明,算法能够较好地完成试卷考题的分布优化,从而有效提高试卷的测试能力,对于实际的试卷命制提供了可靠的解决方案和调整依据。本文提出了创新性的考题分布的优化方法,即确立了试卷的覆盖模型,并以此为目标函数,运用量子遗传算法对考题分布进行优化。

参考文献:

[1] 张维,何蓉. 基于参数估计的遗传算法组卷研究[J]. 云南民族大学学报,2009,18(3):276-278.

[2] Donald A.Prospective Algorithms for Quantum Evolutionary Computation[C].Proc of the 2nd Quantum Interaction Symposium (QI-2008), College Publications, UK, 2008.

[3] 黄友锐. 智能优化算法及其应用[M]. 北京:国防工业出版社,2008:38-40.

[4] 唐欢容,蒋浩,郑金华. 量子多目标进化算法研究[J]. 计算机工程与应用,2007,43(13):48.

[5] Han K H,Kim J H.Genetic quantum algorithm and its application to combinatorial optimization problems[C].Proc of IEEE Conference on Evolutionary Computation.Piscataway:IEEE Press,2000:1354-1360.