计算机组卷算法研究

郝运来

随着教育改革的不断深入，设计一个相对科学的考试系统对促进人才质量具有重要意义。本文介绍了当前较为流行的几种组卷算法，对其进行了优缺点分析，并对未来组卷算法的发展进行了预测。

【关键词】考试系统 自动组卷 组卷算法

1 引言

當前教学改革正在如火如荼展开，而考试是教学过程中的重要环节，是对师生“教”与“学”成果的检验，将计算机及互联网等现代科技应用到考试中去，可以克服传统考试耗费人力物力、效率低下的缺点，使出卷、考试、评阅、成绩统计与分析更加科学、客观。而组卷算法是其最为关键的部分，研究组卷算法并将其应用到考试系统中具有重要意义。

基于试题库的考试系统中，组卷问题是一个多目标、多约束条件组合优化问题，传统组卷方法包括基于随机算法、回溯算法的组卷算法。作为NP问题，当前研究解决此问题的热门智能组卷算法主要基于遗传算法、粒子群算法和蚁群算法。本文针对这几种算法进行了详细的分析，为组卷算法的进一步研究做好铺垫。

2 基于随机算法的组卷方法

该组卷方法的核心思想是利用随机函数rand（n），产生服从均匀分布的从1到n的随机数，将其作为要抽取的试题在试题库中的编号，之后按照试题类型、试题难度、知识点、区分度等约束条件进行判断，选择符合要求的记录录入试卷，重复该过程直到题目数量满足要求或无法从试题库中抽取满足控制指标的试题，最后输出试卷。

该算法结构简单、易于理解、实现容易；但是随着试题数量的增加，选择试题过程中没有目标，导致组卷成功率低，组卷耗时，不确定性和用户满意度差。

3 基于回溯算法的组卷方法

回溯组卷算法是在随机组卷算法的基础上，利用深度优先搜索算法改进而来。组卷过程中，从试题库中随机抽取一道试题，如果试题满足组卷约束，则将其按照先后顺序放入栈中，并标记成功状态；否则，返回到上一个成功状态，并按照新的状态继续搜索。

该算法继承了随机组卷算法简单和易于实现等优点，避免了其方法重复搜索试题的缺点，理论上可以搜索所有试题组合，形成最优试卷集，当试题库较小时，成功率较高，试卷质量较好，但试题库较大时，时空复杂度较高，成功概率低。

4 基于遗传算法的组卷方法

遗传算法是基于自然界选择原理和自然遗传机制的搜索算法。其原理是模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化。该算法的组卷方法对试题库中的试题采用十进制或二进制编码，之后随机生成规模适当的初始种群；然后运用适应度函数对初始种群进行优劣评估，并进行选择。接着对群体进行交叉和变异等遗传操作，生成新一代的试题群体。重复上述过程，直到算法满足终止条件，输出试卷。

遗传算法采用并行处理，可以同时搜索试题库中的多个区域，不易陷入局部最优解当中而过早收敛，效率上优于搜索法，但容易产生早熟现象，因此需要对其进行改进，当前改进遗传算法的组卷算法较多。

5 基于粒子群优化算法

粒子群算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于Swarm Intelligence的优化方法。首先从试题库随机抽取适量的试题，构成初始粒子群，然后通过由组卷目标确定的适应度函数计算粒子本身最优值和全局最优值，粒子根据速度和位置更新公式改变速度信息和位置信息，经有限次迭代后找到最优解，输出试卷。

该算法采用并行搜索，搜索速度快、效率高，受初始种群和迭代次数影响有可能陷入局部最优，对于处理组卷这类多目标问题效果不理想，需要进行改进。

6 蚁群算法

蚁群算法是群智能理论研究领域的一种主要算法，通过模拟自然界蚂蚁搜索路径的行为搜索最优解，成功解决了旅行商、图着色等经典组合优化问题。首先初始化试题信息素浓度，之后设置适当数量的蚂蚁在试题库中随机分布，之后用根据组卷目标确定的转移概率函数使蚂蚁状态进行转移，并更新信息素浓度，然后再次用蚂蚁重复上述过程，直至满足终止条件或达到迭代次数。

蚁群算法本身在求解复杂优化问题特别是离散优化问题具有优势，可以与多种启发式算法结合来改善算法性能，缺点是计算量大，所需时间长；参数设置不当时，容易出现停滞现象，收敛速度变慢、陷于局部最优等缺陷。

随机组卷算法和回溯算法由于其简单实用的优点，这两类算在实际工程应用较多，尤其在一些要求较低的系统中较多使用。遗传算法提出时间较早，基于其进行改进的算法较多，是当前智能算法应用在组卷系统中研究最为深入的算法之一，且已经在较为复杂度组卷系统中使用。其他两种现代智能算法，由于提出时间较晚，对其研究还不够深入，仍有巨大发展潜力。

7 结语

本文从产生历史、算法流程、优缺点等方面介绍了组卷算法的应用，在人工智能产生巨大影响的背景下，考试系统正朝着规模化、智能化和并行化的方向发展，智能组卷算法也将对组卷产生巨大影响。综合比较上述各种算法优缺点，将多种算法组合，发挥不同算法的最大优势，互相取长补短，将会使组卷算法在一个较短的时间内对考试系统产生巨大影响，为更好的实现科学组卷打下很好基础。

参考文献

[1]高欢欢.分类分段回溯试探算法在计算机基础在线考试系统中的应用[J].软件导刊，2016，15（05）：157-159.

[2]胡泊，刘欣.基于改进随机选取法的自动组卷方法研究[J].海军工程大学学报（综合版），2013，10（03）：78-81.

[3]裴胜玉，周永权.用于约束多目标优化问题的混合粒子群算法[J].计算机工程与应用，2011，47（15）：49-52+111.

[4]唐世文.基于蚁群算法的智能组卷算法研究[J].计算机时代，2011（10）：37-39.

[5]http：//doc.mbalib.com/view/737a90590a3abc56bb1d9a281e44adeb.

作者单位

陕西省西安市空军工程大学信息与导航学院 陕西省西安市 710000