遗传算法在试题组卷中的应用

。

考试自动出题的遗传算法如下：

(1) 根据考方的出题要求，规划状态空间库D中的数据，保留d_request部分，而不要d_void部分，对其剩余部分进行编码D [1]，D[2]，……D[i]。

(2) 初始化试题库[STK]。随机从题库中抽出一组试题，并进行编号STK[1],STK[2]……STK[j],确定合适的交换概率Pc和变异概率Pm；并定义其适应值flexibility[k](k=1,2……j)

flexibility[k]<-0 (k=1,2……j)

(3) 从试题库[STK]中取出STK[m](0≤m≤j)与状态空间库[D]中的指标D[n] (0≤n≤i)进行匹配。如果STK[m]与D[n]完全匹配，则

flexibility[k]<-flexibility[k]+1

如果不匹配，则有

flexibility[k]<-flexibility[k]+0

(4) 进行淘汰选择，保留具有高适应度的试题。即把flexibility[k]为0的STK[m]去掉，这样就生成了一

个新的试题模型STK[h]。

(5) 重复过程2生成新的试题模型STK[p]。按一定的交换概率Pc从[STK]中随机选取模型STK[h]和STK[p]，交换彼此位串中对应的值，产生新的试题模型STK[h]、STK[p]，如

交换前STK[h]=1 1 0 1 0 1 1

STK[p]=0 0 1 1 1 1 0

交换前STK[h]=1 1 1 1 0 1 1

STK[p]=1 1 1 1 1 1 0

(6) 按一定的变异概率从题库[STK]中随机选出一试题模型STK[h]进行基因突变，产生一个新的试题模型。

(7) 在完成以上选择、交叉、变异步骤后，产生一个考试试题模型，按照事先确定的误差精度对其进行收敛性的判别，当其适应度高时，试题组卷成功，转向步骤8，如果其适应度低，则转向步骤3继续执行。

(8) 输出相应的考试试题，组卷结束。

以上用遗传算法抽题时，交换概率Pc和变异概率Pm的确定很重要。Pc

太小使选题工作进展缓慢，太大则会破坏适应值高的试题模型。通常规定其为0.4。同样，Pm太小就不能产生新的试题模型，太大又会产生过多的试题模型。它宜规定为0.1。

在自动选题时，选题的方式可采用父辈挑选和生存选择两种。父辈挑选就是采用不返回随机抽样，它使每个题目都有被选中的可能；生存选择采用允许父辈和子代进行竞争，并让其中的优良者进入下一轮竞争环境的二分之一择优选择。两种选择方式共同作用于选题保证了选题的顺利完成。在选题的过程中，哪一道题目被选中是一个非均匀随机事件，其概率依赖于上一次选题的过程。

5结束语

本文利用遗传算法的全局寻优和收敛速度快的特点，结合随机选取法和回溯试探法的优点，设计了一种用于自动组卷的好的算法，使自动组卷的成功率和速度都得到了明显的提高。要使自动出题的误差精度和收敛速度进一步得到改进，还需要做出更深的研究。

参考文献

[1] J．H．Holland ，Adaptation in natural and artificial systems[M]，Ann arbor: University of Michigen press,1975.

[2] Hamilton M A. Java and the Shift to Net-centric Computing. IEEE Computer, 29(8),1996.

[3] 袁富宇等，多目标相关分类的算法，浙江大学学报，33(3),1999

[4] 张师超 蒋运承 ，模糊数据库中近似相等的研究，计算机科学，25(6),1998.

[5] 余建桥，预测模型获取的遗传算法研究，计算机科学，25(2),1998.

《遗传算法在试题组卷中的应用(第2页)》