智能组卷策略的研究

王 颖，刘志丹

（1.商丘职业技术学院，河南 商丘 476000；2.河南大学 软件学院，河南 郑州 475001）

在线考试系统研发过程中［1］39，实现系统自动化的关键问题就是智能组卷.智能组卷是计算机自动随机地从试题库中抽取出与约束条件相对应数量和质量的试题，从而组成一份满足组卷要求的试卷，同时满足用户的组卷约束条件.通常为了方便组卷，需要给每道试题设置一系列参数，这些参数要反映试题情况，例如，出题日期、试题题型、所属章节、知识点、分值、题目内容、使用次数等等.智能组卷就是依据上述试题的属性去匹配相关的用户要求，通过组卷算法抽题并组卷的.

1 组卷的约束条件

计算机组卷的约束条件是由用户对试卷的细节要求所构成的.计算机根据这些用户需求循环抽取每一道试题，最终生成整张试卷.因此，组卷问题的求解过程可以看成是寻找满足条件的最优组合，而这些约束条件则影响着试卷的质量.

一般来说，这些条件可以包括对试题题型、所属章节、知识点、难度、分值、估时、抽取次数等试题的属性.如果把对所有题目的每一项条件都看成是局部的约束，那么所有条件就组成了整个试卷的全局性的约束条件.为了让整个试卷满足各项指标之间的平衡，就需要协调局部与全局约束，从而，判断哪些试题可以被选用.这就是智能组卷.

而根据考试学理论［2］131，通常评价试卷的质量要遵循以下规律：1）试卷中设计的考点内容是否合理、科学；2）试卷中设计的考点广度是否符合大纲要求；3）整个试卷的难度分配、考查的深度是否合理；4）试卷中的试题类型是否丰富，各类题型所占试卷比例是否合适；5）试卷是否具备良好的优劣区分度.

依据以上目标，在线考试系统采取下列步骤进行组卷.首先，在建设试题库系统时，细化试题的属性包括难度、区分度、效率度、信用度，对组卷的约束条件进行预先设计，一般先确定章节和考点的覆盖面、试题的类型、用时、试卷难度；然后，采用合理的组卷算法［3］214自动也更高效地从试题库中抽取一定的试题，确定并合理调整各试题所占分值，最后合理完成排版.

2 组卷算法

在线考试系统所采用的组卷算法一直是近年来研究的热点，国内外有很多学术机构都在研究.相对成熟的算法有随机法、回溯法、粒子群算法和遗传算法，笔者在此介绍一下上述4种组卷算法，并简单分析它们各自的优缺点以及适用性.

2.1 随机法

随机法在组卷中很常见，即根据试题库中的试题属性和数量，计算机调用随机函数从试题库中抽取每一道符合要求的试题，然后加入试卷，循环进行直到组卷完成作为结束.这是最常用的一种组卷算法.由于要考虑的组卷约束条件较多，算法还需要使用到大量的附加函数，用来区分试题的难度、知识点等属性.

显然，该算法结构简单易行，对于单次试题的抽取，算法运行速度较快.这正是随机抽题法的优点.但是，基于随机函数的算法抽题的特点是随意和不确定，试卷的质量把握不具有整体性.随着题库规模变大，随机法的效率就会降低，组卷过程就会变长.随机抽题法还需要协调局部和全局的约束条件，但这些相互制约的约束条件有时会造成组卷失败.

2.2 回溯法

回溯法（探索与回溯法）是对随机法的改进，属于深度优先算法，也是一种选优搜索法.按选优条件向前搜索以达到目标.回溯法的算法原理为：先使用随机法进行深度优先搜索，记录下沿路产生的状态，一旦某次搜索失败，就出栈返回到上次记录的状态，以此为起点重新探索试探.通过这样循环反复的回溯以及试探，直到成功组成一份完整的试卷.

2.3 粒子群算法（PSO）

粒子群优化算法［4］86（Particle Swarm optimization，PSO）又称为微粒群优化算法、微粒群算法或粒子群算法，是由Kennedy博士和Eberhart博士发明.该算法的应用领域很广，通常用于组合优化问题的解决，也可以解决连续优化的问题.该算法模拟鸟群的捕食行为.

一群鸟在某个区域随机搜寻一块食物，而食物在哪里对于所有的鸟都是未知的.已知的是每只鸟的位置和食物之间的距离.那么怎么样更快地通过鸟儿们寻找到食物呢？最快的办法就是先找到所有鸟中谁距离食物是最近的，然后搜寻这只鸟的周围即可.粒子群算法先抽象每个优化问题的解，即粒子.每个粒子都有决定其运动方向和距离的速度值，以及由优化函数决定的适应值，最优粒子将成为粒子们所追随搜索的目标.

该算法简洁易实现，它的优点是参数少，收敛速度特别快，特别是在运行的初期.而粒子群算法的缺点是容易发散且精度低，在某些条件下造成算法不收敛，使得算法结果无法获取最优解；而在某些条件下，粒子趋向同一化，精度较低.

2.4 遗传算法（GA）

遗传算法［5］61于1975年由美国密西根大学JoHolland教授首先提出，通过对生物进化论中的自然选择和遗传学机理的模拟，建立计算模型，搜索最优解的方法.遗传算法利用"优胜劣汰"的原理，从群体中选择出更优的个体为主要目标，借助选择、交叉以及变异操作将个体靠近最优解，最终逐步搜索到问题的最优解.遗传算法广泛应用于很多学科，为了反映各种复杂的结构，算法采用简单编码的技术.当遗传算法应用于智能化组卷时，算法中的基因问题由每一题试题代入并进行编码.为了简化基因编码的复杂度，遗传算法常用的简单的编码方式比如二进制编码、实数编码和自然数编码.例如二进制编码，依据算法产生初始种群之后，按照"优胜劣汰"的原理，将初始种群逐代演化，得到越来越好的近似解，然后从每一代选择适应度大小合适的个体，再采用遗传算子进行交叉、变异，得出的种群代表了新的解集，这个结果作为问题近似最优解.

3 结论

通过讨论组卷约束条件和常见的组卷策略，综合比较各种算法的优缺点，根据不同用户的需求合理地选取组卷算法.可以看出，随机搜索法和回溯法都简单易于实现，但不太适合计算量较大的情况.粒子群算法和遗传算法两者都是对初始化的种群随机化，都通过使用适应值来对系统进行评价，并依据适应值进行随机的搜索.在求解方面，两个系统都不保证一定能找到最优化的解.可以说，粒子群算法和遗传算法其实有很多共同之处.

［1］刘志丹，王 颖.基于ASP的网络试题库系统的研究［J］.商丘职业技术学院学报，2013（2）.

［2］刘新平，刘存侠.教育统计与测评导论［M］.北京：科学出版社，2003.

［3］雷英杰.MATLAB遗传算法工具箱及应用［M］.西安：西安电子科技大学出版社，2005.

［4］冯 雪，裴志松.粒子群优化算法的研究与应用［J］.吉林建筑工程学院学报，2011（03）.

［5］关凇元，刘大有，金 弟，王新华，苏 奎.基于局部搜索的遗传算法求解自动组卷问题［J］.吉林大学学报（理学版），2009（05）.