QPSO和GA相融合的智能组卷模型研究

邱靖,郭睿南,浦涛文,于学媛,张海涛

（云南农业大学 教务处，云南 昆明 650201）

QPSO和GA相融合的智能组卷模型研究

邱靖,郭睿南,浦涛文,于学媛,张海涛

（云南农业大学 教务处，云南 昆明 650201）

为简化模型结构，改善算法全局搜索性能和组卷模型成功率，本研究提出利用QPSO中的全局和局部最优位置优化遗传算法中交叉、变异算子，粒子群编码采用实数编码，交叉、变异操作均在功能块内部进行，目标函数增加了权重系数判定是否更新粒子群，以此建立了智能组卷模型，并进行了相关实验分析。实验结果表明：改进的模型与其他三种组卷模型相比，该模型运行效率、全局搜寻性能、组卷成功率都有较大的提高，说明该组卷模型更稳定有效。

QPSO；遗传算法；权重系数；智能组卷；模型研究

随着信息技术、网络技术、计算机辅助教学和人工智能的发展，网络考试越来越受到广泛地应用，因此建立一个好的自动组卷系统尤为重要，而组卷模型的好坏直接关系到对学生所学知识的评估以及能否达到预期效果的关键因素。由此可见，组卷算法的研究成为智能组卷系统的核心。

组卷实际上是在一定约束条件下的多目标优化求最优解问题，保证自动生成的试卷能满足用户的组卷指标，具有随机性、客观性、合理性及科学性等特点。目前，组卷方法包括：随机选取法、回溯法、遗传算法、PSO算法、QPSO算法及蚁群算法等［1-7］。这些组卷算法在一定时期内对网络组卷起到了积极作用，但随机选取法结构简单，组卷的成功率低，很难满足用户的需求；回溯法其程序结构较复杂，但缺乏随机性，组卷速度较低；遗传算法虽具有全局寻优性、算法简单、并行性及通用性等特点，但因其算法本身有许多参数需要调整，搜索不够精确；粒子群算法简单易实现，参数不需大量调整，但因其算法本身易陷入局部极值，致使组卷结果不是全局最优。针对这些不足，本研究提出将量子粒子群算法（QPSO）和遗传算法相融合运用到智能组卷模型，并分析其组卷效率。

1　组卷数学模型

智能组卷即在试题库系统中，自动生成满足用户需求的试卷。题库中每道试题包括许多属性（分数、题型、难度系数、知识点、测试层次等），当用户抽取一份试卷时，设定总分值、题型数量、知识点、难度系数及题型分值。用户抽取n道题时，就决定了一n×m的参数矩阵A。

矩阵A每一列代表试题的一个属性，m为试题属性个数，每一行代表一道试题的属性值，n为所生成试卷的总题数。组卷的约束条件为：

分数 ai1表示试题的分值，M为用户给定的试卷总分ai1=M。

题型ai2表示试题的题型（判断题、单选题、多选题、填空题、问答题），用户可指定各类题型的分数。，其中当试题i为第j种题型时，cj=1，否则为cj=0，Sj为第j种题型的总分。

难度系数ai3表示难度系数（0-1），用户规定试题难度系数范围。，其中当试题i的难度系数属于用户规定的难度系数cj=1，否则cj=0，Mj为用户规定的难度系数总分。

知识点ai4表示试题对应的知识点，用户可根据考察需要来确定各章节的分值。，其中当试题i为第j个知识点时，cj=1，否则cj=0，zj为第j个知识点对应的总分。

测试层次ai5表示测试层次，测试层次分为初级、中级及高级。用户可以指定各类层次所占分数。，其中当试题i为第j种层次时，cj=1，否则为cj=0，Nj为第j个测试层次级别对应的总分。

时间ai6表示整套试卷完成的预计时间，

2　QPSO算法与遗传算法融合在智能组卷系统的应用

2.1量子粒子群算法

Sun［8］等人于2004年提出了量子粒子群算法（QPSO）。该算法可以在整个解空间进行搜索，具有较强的全局搜索性能。QPSO算法主要由以下3个进化方程［9-10］完成粒子群的更新迭代：

其中α1，α2，w为 （0,1）间的随机数，β为收缩扩张系数，β的选择和控制决定整个算法的收敛效率，N为粒子群数目，pi为第i次迭代的局部最优位置，pg为粒子群最优位置,mbest为粒子群的全局最优解平均位置。

2.2遗传算法

遗传算法（GA）［11］是通过选择、交叉、变异等操作，利用生物进化论思想，采用优胜劣汰理论，使种群进化逐步接近目标函数。本研究交叉及变异操作都采用在功能块内部进行。即在同题型内部进行交叉及变异操作，保证了组卷时各目标参数的正确匹配，简化了优化目标，同时能更好地满足用户的需求。

遗传算法的优劣，主要是粒子编码方式及适应度函数如何确定。本研究采用整型编码，而不是二进制编码（1和0），粒子长度由试卷题目数决定，粒子编码由所选取试题在试题库中的题号决定。这种编码方式大大缩短了粒子长度，也不存在频繁编码和解码变化而导致优化搜索空间急剧增大，从而降低算法搜索性能。适应度函数引入了组卷约束条件对应的权重系数，如公式（5）。

Wi为第i个约束条件的权重系数，满足。适应度函数值越小，说明实际组卷与用户需求的试卷指标相异度最小，因此目标函数表示为：

在算法中设定一个标志f来判定种群中是否有粒子仍在迭代，是否能搜寻到更优解。如f=1，则种群仍在进化，否则，种群已经找到最优解，程序结束。

2.3算法描述

1）初始化粒子群，按组卷目标中各种题型的题量、知识点、难度系数、测试层次、分值等要求，提取N套试题（种群为N），并初始化所有粒子的局部最优位置pi和全局最优位置pg；

2）根据迭代次数动态调整收缩扩张系数，使组卷寻优空间由全局调整到局部；

3）选择，计算粒子群所有粒子的适应度值，从当前种群中选取适应度函数值最小两个个体的直接进入下一代，而最大的两个个体淘汰，其余的个体进行交叉变异操作，并判断pi和pg是否更新；

4）交叉，根据交叉概率pc的值判定粒子是否进行交叉操作，交叉时采用功能块内部（同类题型）交叉，从种群中随机选取两个粒子，将该两个粒子中第i个功能块的所有试题进行交叉操作；

5）计算粒子群全局最优解平均位置mbest。

6）变异 根据变异概率pm的值判定是否对mbest进行变异操作，变异操作同样采用在功能块内部进行变异；

7）按种群的进化方程生成新的粒子；

8）判断是否满足算法的终止条件，若满足则转到下一步，否则转到步骤2）；

9）输出全局最优解（最佳组卷），算法结束。

3　实验结果与分析

本文针对《WEB技术》课程试题库进行了实验分析，题库中有判断题300道，选择题400道，填空题200道题，编程题100道，试题共分为5个章节，测试等级分为初、中、高3个等级。组卷约束条件设置为总分：100分；测试等级分数比例为初：20分，中：60分，高：20分；难度系数分布比例：0.0-0.3占20分，0.3-0.7占60分，0.7-1占20分；章节分数所占分值从第一章到第五章分别为：20分、20分、20分、20分、20分；题型数量为判断题15题、选择题20题、填空题10题、编程题5题。

分别用GA、PSO、QPSO以及GA和QPSO融合的算法等4种算法来解组卷问题，从而比较这些算法在求解组卷问题时的性能。结合算法和组卷的效率综合考虑，并经多次测试，交叉概率为0.8，变异概率为0.2；QPSO算法的学习率为C1= C2=0.2，惯性权重从0.9到0.5线性减少，最大迭代次数为600，每种组卷模型进行100次组卷实验，对这100次实验结果求平均，实验的结果如表1所示。

表1　4种算法实验结果对比

实验中，通过计算4种算法的平均进化次数、最大完成时间、最小完成时间、平均完成时间及组卷成功率来验证GA和QPSO融合算法的有效性，组卷成功率为算法进行100次实验得到的平均值。由表1可知，本文研究的算法无论从运行次数，还是最大、最小、平均完成时间均比其他3种算法小，但组卷成功率却比其他3种算法高。说明采用QPSA算法优化BP算法中的粒子群，使搜寻最优解空间的范围更大，提高了组卷算法的收敛速度，简化了智能组卷模型，克服了搜索空间易陷入局部极值，且搜索精度得到了提高。

4　结论

本研究针对目前组卷算法的不足，提出了将遗传算法和量子粒子群算法融合运用到智能组卷中，研究表明该方法相比遗传算法、粒子群算法等计算简单，收敛速度快，相比于量子粒子群算法有利于更快地收敛到全局最优解，且组卷的成功率也远高于其他算法。从组卷的结果来看，该算法组卷的稳定性好，可信度高，证明了该算法的有效性。

［1］刘贝贝,肖明,马晓敏.基于推理的组卷数学建模及其应用［J］.计算机工程，2010,36（4）：195-197.

［2］周伟.随机抽题任意组卷智能阅卷的无纸化考试方法研究［J］.软件,2014,35（3）:11-16,19.

［3］冶剑锋,张学良.基于Stirling数的多条件约束组卷算法的研究与实现［J］.数理医药学杂志，2013,26（3）：264-266.

［4］张敏辉.基于改进遗传算法智能组卷的研究［J］.计算机与数字工程，2012,40（3）：18-20.

［5］李俊,张建国.多目标粒子群算法在智能组卷中的应用研究［J］.河南大学学报：自然科学版，2013,43（6）：697-702.

［6］李欣然,樊永生.改进量子行为粒子群算法智能组卷策略研究［J］.计算机科学,2013,40（4）:236-239.

［7］武仁杰.蚁群算法在自动组卷建模中的应用研究［J］.计算机仿真,2011,28（8）:380-384.

［8］SUN J，XU W，FENG B．A global search strategy of quantum-behaved particle swarm optimization［C］//Cybernetics and Intelligent Systems，2004 IEEE Conference on．IEEE，2004：111-116．

［9］邱靖，吴瑞武，黄雁鸿，等.混沌理论与BP网络融合的稻瘟病预测模型［J］.农业工程学报，2010，26（2）：88－93.

［10］邱靖,杨毅,秦西云,等.QPSO优化BP网络预测烟蚜发生量［J］.云南农业大学学报（自然科学）,2013,28（4）:561-564.

［11］许永达．基于改进遗传算法的智能组卷研究［J］．计算机与数字工程，2013,41（2）：176-178，207.

Design of intelligent test paper constructing model based on QPSO and GA

QIU Jing,GUO Rui-nan,PU Tao-wen,YU Xue-yuan,ZHANG Hai-tao
（Teaching Affairs Office，Yunnan Agriculture University，Kunming 650201,China）

In order to simplify the model structure,improve the algorithm global search performance and the success rate of test paper model,this study proposes to use the global QPSO and local optimal location optimization GA crossover,mutation operator,the real number coding using particle swarm coding,crossover,mutation operation is performed in the inner functional block,the objective function increases the weight coefficient of determination whether to update the particle swarm,establishes the intelligent test paper model,and relevant experimental analysis.The experimental results show that:compared with other three kinds of test paper model,the model efficiency,the global search performance,and the success rate was higher,indicating that the test paper model is more stable and effective.

Quantum-behaved Particle Swarm Optimization（QPSO）；Genetic Algorithm（GA）；weight coefficient；intelligentpaper constructing；model research

TN01

A

1674－6236（2016）13-023-03

2015-07-24稿件编号：201507164

2010年云南省高等学校教学改革研究项目（201010）；云南农业大学2013年校级教学改革立项项目（ZNJG201306）

邱 靖（1979—），女，四川达州人，硕士，讲师。研究方向：人工智能。