高校试题库组卷算法的研究与实践

刘 锋 郭维威 田铁刚

(鸡西大学，黑龙江 鸡西 158100)

试题组卷算法有很多种，到目前为止还没有一个令人满意的解决方案，组卷算法一直是我们需要探讨的问题。试题库系统中对试题的质量要求很高，自动组卷的速度与组卷的质量取决于组卷算法的优劣。如何才能设计一个合理、高效的算法以便从试题库中组合成最符合要求的试卷，对此，我们根据遗传算法原理进行了研究。

1 遗传算法原理

1.1 编码

在遗传算法中参数不能直接处理，它只能处理个体，因此必须把参数形式的问题解转化成为遗传空间的染色体或者是个体，这个转化过程叫做编码。近年来所使用的编码过程形式是多种多样的，有进制编码(最常用的编码方式)、多字符及实数编码、树编码和自适应编码。其中自适应编码方法的思想就是利用遗传算法在解决问题时，让它同时也能够调整编码，以便让遗传算法更好地利用它。

1.2 适应度函数

适应度函数将直接影响遗传算法的收敛速度及能否找到最优解。在遗传算法中，它的搜索过程不是利用外部信息，而仅把适应度函数作为依据，然后再利用个体的适应度进行搜索。遗传算法基本的要求是用户针对输入可以计算出能够用以比较的非负数结果，就是这个特点使得遗传算法具有了广泛的适用性。

1.3 遗传操作

我们通过编码过程组成初始群体之后，遗传操作能够对初始群体中的个体按照它对环境的适应程度来加以运行，从而实现优胜劣汰的进化过程。通过这个过程，遗传操作可以把问题解进一步地优化，进而接近最优解。遗传操作包括三个基本算子。

2 组卷算法设计与实现

2.1 编码初始化

初始染色体群体中染色体的长度为n，大小为m。如果m很小，很难求得最优解，过大反而会增长收敛时间。群体大小一般按经验或试验给出m=30～160的范围。例如在“Visual Basic程序设计”这门课程中，要求试卷总分值为100分，程序阅读(30%)、选择题(30%)、编程题(40%)。在试题库中，程序阅读的分值有两种6分、10分、20分，选择题的分值有10分和20分的，编程题有10分和20分的，那么可以看出程序阅读题占10个基因(5个6分，3个10分，1个10分与1个20分)，选择题占6个基因，编程题占13个基因，那么染色体总长度为29。

2.2 适应度函数

一般情况下，适应度函数由目标函数转换而成，其适应值越大个体就越好，适应值越小则个体越差。本文采用的方法将目标函数f转换为适应度函数F′，当f<100时，F′=100-f，当f为其他值时，F′=0。指数的比例可以提高个体之间的相互竞争，所以对F′采取指数比例变换的这种方法可以转换为适应度函数，则f=exp(-βF′)，β的值为-0.03。

2.3 遗传算子设计

在选择算子的设计中，为了保留遗传操作中较优的个体，保持群体的大小不变，可以删除适应度队列后面的2个个体，再随机抽取队列最前面的m-2个个体p(p≤m-2)进行交叉与变异操作。在交叉算子设计中，遗传操作利用了分段思想，交叉时按照题型段进行交叉，因此不存在试题重复的问题。每种题型的题量也不会发生变化，交叉概率pc按照经验值应该在0.4～0.6之间。变异算子设计过程中，变异在题型段内进行，变异概率pm一般按照经验值控制在0.01～0.2之间。

3 组卷结果测试与分析

为了验证算法的可行性与有效性，我们以“Visual Basic程序设计”这门课程为例，以鸡西大学计算机软件技术专业学生Visual Basic程序设计建立试卷模板。在这次试验中，试题库中共有600道题，分别为判断、单选、简答、填空和应用共5种类型题，这5种试题的数分别为100,150,150,100，100；各种题型的分数比例为2∶3∶6∶8∶20。系统组卷要求为100满分,难度系数0.75(即期望平均得分为75分)。利用遗传算法设计的系统在抽题时，变异概率pm和交叉概率pc的确定非常重要。pc过小会使抽取的试题过程缓慢，过大将会破坏高适应值的试题模型，按照经验值控制在0.4左右。pm过小不会产生新的试题模型，过大则产生的试题模型过多，最好控制在0.1左右。试验表明，参数的选择是非常重要的，即交叉概率在0.6～1.0之间，变异概率应该在0.001～0.01之间，群体规模控制在50～80时，利用试题库系统可以有效地解决组卷问题，很快地组合成用户满意的试卷。

目前，试题库建立与试卷生成系统已应用在黑龙江技师学院的考务管理中，在鸡西大学的“Visual Basic程序设计”和“操作系统”等课程中也得到了具体的应用。经过一年的应用，结果表明：该系统是合理有效的，具有较高的研究价值和市场应用价值。

参考文献：

[1]刘锋.试题组卷算法的研究与应用[J].鸡西大学学报，2008，(12).

[2]殷霖.遗传算法在自动组卷中的应用[J].廊坊师范学院学报，2011，(3).

[3]赵永虹.组卷算法研究与实现[J].现代电子技术，2011，(4).