在线考试系统的自动组卷算法研究

佟婷婷 长沙理工大学 湖南交通职业技术学院

随着计算机相关技术的发展以及教育教学水平的不断提高，考试类型和考试标准也随之发生改变，采用传统的考试已经不能满足当前教育教学的需要，因此在线考试系统在很多领域逐渐取代了纸质考试，成为水平测试和技能考核的基本工具。科学有效的组卷算法是在线考试系统的核心，目前主要有人工组卷和自动组卷两类方法。显然，人工组卷与传统纸质制卷并无本质的区别，要充分发挥在线考试系统的功效，还需要依赖自动组卷算法。根据自动组卷算法的特点，分为传统组卷方法和智能组卷算法两种。

1 传统组卷方法

传统的自动组卷方法主要包括随机算法和回溯算法两种。

1.1 随机组卷算法

随机组卷算法是根据预设参数，随机从题库中抽取符合要求的试题，并不断重复这一过程达到组卷的目的。因为随机组卷算法的稳定性不高，因此为了防止组卷失败，一般都会设置尽可能少的条件，所以，这种算法只适用于一般的简单组卷系统。

1.2 回溯组卷算法

回溯算法可以认为是随机算法的一种改进，与随机算法不同的是，回溯算法设置一个条件，当随机选择的题目不满足条件时，进行“回溯”返回并尝试选择别的题目。相比随机组卷方法，回溯算法在一定程度上提高了组卷稳定性，但因为在极端的情况下也有可能历遍所有题目，所以其效率不如随机算法，基于回溯算法的组卷过程一般适用于题量和题型都较少的情况。

2 智能组卷方法

智能组卷是利用智能算法进行组卷的方法，应用于组卷的智能算法主要有遗传算法、粒子群算法、蚁群算法和人工鱼群算法等几种。由于智能算法的求解过程不依赖于梯度信息，因此智能算法适用于于传统组卷算法不能解决的大规模题库的组卷问题。

2.1 遗传算法

遗传算法是计算数学中应用最广泛的方法，该方法通过模拟生物进化过程中的“优胜劣汰，适者生存”法则，经过多个种群的不断迭代，即复制、交叉和变异等行为，最终得到最优解。作为一个多目标优化问题，自动组卷问题适合采用遗传算法来进行。相对来说，遗传算法计算较为简单、鲁棒性也较强，但容易陷入“早熟”现象，其参数的确定也不容易，通过改进算法可以一定程度上解决这些问题。

2.2 蚁群算法

蚁群算法是一种针对离散优化问题的元启发式算法，其本质是一种全局优化算法。蚁群算法通过模拟蚂蚁群体的觅食行为来寻找最优解，这种算法具有分布计算、信息正反馈和启发式搜索的特征。蚁群算法一般都是为了得到一个最优解，但因为组卷问题是一个多目标优化问题，所以在实际应用中，需要对蚁群算法进行改进。

2.3 粒子群算法

粒子群算法是模拟鸟群觅食行为，通过鸟群的集体协作和竞争，而完成最优目标的一种智能算法。与其它智能算法一样，粒子群算法首先随机生成初始种群作为可行解，在每次迭代中，每个粒子根据自身所寻找的最优解和整个种群的最优解两个极值来更新自己，通过不断迭代达到最优解。粒子群算法容易实现、收敛速度快，而且不需要过多的参数调整。在应用于自动组卷中，粒子群算法往往比遗传算法更快完成组卷，但需要解决精度低的问题。

2.4 人工鱼群算法

人工鱼群算法是一种利用鱼群的觅食行为、群聚行为、追尾行为和随机行为等特点，通过构造人工人工鱼来实现寻优的过程。作为一种新型的仿生学算法，人工鱼群算法具有收敛速度快、稳定性好等特点。自提出以来，人工鱼群算法广泛用于电力系统规划和多级阶梯物流中转运输系统优化等领域。将人工鱼群算法引入自动组卷问题中，能有效解决编码太长、适应度函数计算复杂等问题。此外，人工鱼群算法与其它方法，例如遗传算法相结合，能进一步提高组卷效率。

3 总结

除了以上算法，专家系统法和项目反应理论等方法也被应用于自动组卷中。专家系统法可以利用用户参与试卷指标设定增强组卷的可控性和灵活性，项目反应理论与其它的算法不同，它主要侧重于对应试者实际能力水平的衡量。各种组卷算法均有其优缺点，在实际的应用中，应根据需要采取适应的自动组卷方法。为了提高组卷效率，往往要结合多种方法来完成组卷过程，例如粒子群和遗传算法相结合，人工鱼群与遗传算法相结合等等。

[1]戴亚非，李晓明.计算机自动组卷算法分析[J].小型微型计算机系统2012,16(9):50-55

[2]魏平，熊伟洁.用遗传算法解组卷问题的设计与实现[J].微电子学与计算机,2012(4):48-50

[3]肖豆.智能组卷系统的设计与实现[D].电子科技大学，2017

[4]乔东平，裴杰，肖艳秋，周坤.蚁群算法及其应用综述[J].软件导刊，2017,12(16)

[5]陈新.基于人工鱼群算法的柔性作业车间调度研究[D].大连理工大学，2015

[6]李跃松，樊金生，张巧迪.用改进的人工鱼群算法求解TSP问题[J]. 石家庄铁道大学学报自然科学版，2011,24(2)

[7]单美静，刘琴.基于项目反应理论的组卷算法研究[J].软件工程,2017(12)