遗传算法在试题组卷的作用综述

1、遗传算法在试题组卷的作用综述摘要：本文运用遗传算法的全局寻优对考试中的自动化 组卷进行了研究，并得到了一个解决适合考方要求的试题模 型的好的算法。关键词：遗传算法全局寻优自动化组卷1引言计算机辅助考试系统的自动组卷的效率与质量完全取 决于抽题算法的设计。如何设计一个算法从题库中既快又好 的抽出一组最佳解或是抽出一组非常接近最佳解的实体，涉 及到一个全局寻优和收敛速度快慢的的问题，很多学者对其 进行了研究。遗传算法以其自适应寻优及良好的智能搜索技 术，受到了广泛的运用。PottsJC等人基于变异和人工选择的遗传算法对最优群 体规模进行了论述；HamiltonMA等结合遗传算法把其运用 到神经网络

2、中，并取得了良好的效果4;也有众多的学者对保留最佳状态的遗传算法的收敛速度做了讨论。通过理论推 导和事实运用，发现遗传算法在寻优和收敛性方面都是非常 有效的。本文结合遗传算法的原理和思想，对考试自动出题组卷 的问题进行了研究，找到了一种获得与考试试题控制指标符 合的试题模型的解决方法。2问题描述自动组卷是考试系统自动化或半自动化操作的核心目 标之一，而如何保证生成的试卷能最大程度的满足用户的不 同需要，并具有随机性、科学性、合理性 ，这是实现中的一个 难点。尤其在交互式环境下用户对于组卷速度要求较高，而 一个理论上较完美的算法可能会以牺牲时间作为代价，往往 不能达到预期的效果。因此，选择一个高

3、效、科学、合理的 算法是自动组卷的关键。以往的具有自动组卷功能的考试系统大多采用随机选 取法和回溯试探法。随机选取法根据状态空间的控制指标， 由计算机随机的抽取一道试题放入试题库，此过程不断重 复，直到组卷完毕，或已无法从题库中抽取满足控制指标的 试题为止。该方法结构简单，对于单道题的抽取运行速度较 快，但是对于整个组卷过程来说组卷成功率低，即使组卷成 功，花费时间也令人难以忍受。尤其是当题库中各状态类型 平均出题量较低时，组卷往往以失败而告终。回溯试探法这是将随机选取法产生的每一状态类型纪 录下来，当搜索失败时释放上次纪录的状态类型，然后再依 据一定的规律变换一种新的状态类型进行试探，通过不

4、断的 回溯试探直到试卷生成完毕或退回出发点为止，这种有条件 的深度优先算法，对于状态类型和出题量都较少的题库系统 而言，组卷成功率较好，但是在实际到一个应用时发现这种 算法对内存的占用量很大，程序结构相对比较复杂，而且选 取试题缺乏随机性，组卷时间长，后两点是用户无法接受的， 因此它也不是一种很好的用来自动组卷的算法。分析上述两种算法的优缺点，不难发现，在限制条件状 态空间的控制下，随机选取法有时能够抽取出一组令用户满 意的试题。只不过由于它随机选取试题的范围太大，无法确 定目前条件下哪些区域能够抽取合适的试题，反而可能在那 些已经证明是无法抽取合适试题的区域内反复选题，进行大 量的无效操作进

5、入死循环，最终导致组卷失败。回溯试探法 组卷成功率高，但它是以牺牲大量的时间为代价的，对于现 今越来越流行的考生网上随机即时调题的考试过程来说，它 已不符合要求。因此，必须结合以上两种方法寻找一种新的改 进算法，这种算法要具有全局寻优和收敛速度快的特点。遗 传算法以其具有自适应全局寻优和智能搜索技术，并且收敛 性好的特性能很好的满足自动考试组卷的要求。3遗传算法描述遗传算法是一种并行的、能够有效优化的算法，以Morgan的基因理论及 Eldridge与Gould间断平衡理论为依 据，同时融合了 Mayr的边缘物种形成理论和Bertalanffv -般系统理论的一些思想，模拟达尔文的自然界遗传学

6、：继承、进化优胜劣汰。其实质就是一种把自然界有机体的优胜劣汰 的自然选择、适者生存的进化机制与同一群体中个体与个体 间的随机信息交换机制相结合的搜索算法。运用遗传算法求 解问题首先需将所要求解的问题表示成二进制编码，然后根据环境进行基本的操作： selection，crossover， mutation 这样进行不断的所谓生存选择”，最后收敛到一个最适应环 境条件的个体上，得到问题的最优解。6,74遗传算法应用一般来说，用户在自动组卷时会对试卷的质量提出多方 面的要求，如总题量、平均难度、题型比例、章节比例、重 点章节比例、知识点的交叉与综合等，自动组卷就应最大程 度的满足用户的要求。因此，在

7、组卷之前，我们首先为自动 组卷过程建立控制指标相应状态空间D ,D=D的每一行由某一试题的控制指标组成，如题号、题型、章节、难度等，并且这些属性指标都进行编码表示成二进制 形式，而每一列是题库中的某一指标的全部取值。在具体出 题时，考方可能不会用到所有的指标，所以D包含的个体d_target 可以表示为 d_request和 d_void , d_request 表示考方 要求的控制指标，d_void表示考方不要求的控制指标。即d_target:=:=0 , 1m:=0 , 1n试题库STK中的每一道试题在建库时都输入了相应的属性指标。试题模型的产生形式是:ifthen:=0 , 1 , #m

8、#表示0和1之间的任意一位。考试自动出题的遗传算法如下：根据考方的出题要求，规划状态空间库D中的数据，保留d_request部分，而不要d_void部分，对其剩余部分进行编码D1 , D2,Di。初始化试题库STK。随机从题库中抽出一组试题，并进行编号 STK1,STK2STKj,确定合适的交换概率Pc和变异概率 Pm；并定义其适应值flexibilityk(k=1,2j)flexibilityk(3)从试题库STK中取出STKm(0 m与状态空间库D中的指标 Dn(0 n进行匹配。如果STKm与Dn完全匹配，则flexibilityk如果不匹配，则有flexibilityk进行淘汰选择，保留

9、具有高适应度的试题。即把flexibilityk为0的STKm去掉，这样就生成了一个新的试题模型 STKh。(5) 重复过程2生成新的试题模型STKp。按一定的交换概率Pc从STK中随机选取模型 STKh和STKp，交换彼此位串中对应的值，产生新的试题模型STKh、STKp,交换前 STKh=1101011STKp=0011110交换前 STKh=1111011STKp=1111110(6) 按一定的变异概率从题库 STK中随机选出一试题模 型STKh进行基因突变，产生一个新的试题模型。(7) 在完成以上选择、交叉、变异步骤后，产生一个考试试题模型，按照事先确定的误差精度对其进行收敛性的判别，

10、当其适应度高时，试题组卷成功，转向步骤8，如果其适应度低，则转向步骤 3继续执行。(8) 输出相应的考试试题，组卷结束。以上用遗传算法抽题时，交换概率Pc和变异概率Pm的 确定很重要。Pc太小使选题工作进展缓慢，太大则会破坏适应值高的试 题模型。通常规定其为。同样，Pm太小就不能产生新的试题模型，太大又会产生过多的试题模型。它宜规定为。在自动选题时，选题的方式可米用父辈挑选和生存选择 两种。父辈挑选就是采用不返回随机抽样，它使每个题目都 有被选中的可能；生存选择采用允许父辈和子代进行竞争， 并让其中的优良者进入下一轮竞争环境的二分之一择优选择。两种选择方式共同作用于选题保证了选题的顺利完成。 在选题的过程中，哪一道题目被选中是一个非均匀随机事 件，其概率依赖于上一次选题的过程。5结束语本文利用遗传算法的全局寻优和收敛速度快的特点，结 合随机选取法和回溯试探法的优点，设计了一种用于自动组 卷的好的算法，使自动组卷的成功率和速度都得到了明显的 提高。要使自动出题的误差精度和收敛速度进一步得到改 进，还需要做出更深的研究。参考文献1 J. H . Holland ,Adaptationinnaturalandartificialsystem