基于遗传算法的在线考试系统的研究

苏小兵 李天平

山东师范大学传播学院 济南 250014

近年来，计算机技术和人工智能得到快速发展，随着教育测量理论研究的不断深入，基于遗传算法组卷系统的研究与开发得到越来越多的专家学者的关注。本文从教学要求出发，结合项目反应理论，以遗传算法为基础，提出基于项目反应理论的数学模型。用此组卷算法实现的在线考试系统的数据表明，算法能够有效解决自动组卷问题，有效提高组卷的质量和速度。

1 教育测量理论

试题库是按照一定的教育测量理论利用计算机技术构成的某学科试题的集合。目前常用的教育测量理论主要有两种，一种是经典测量理论（Classical Test Theory，CTT），另一种是项目反应理论（Item Response Theory，IRT）。

项目反应理论是克服经典测量理论的各种局限性而发展起来的一种全新的测量学理论[1]。项目测量理论在20世纪50年代初正式确立，它的基本思想是：确定考生的心理特质值和他们对于项目反映之间的关系，这种关系的数学形式就是“项目反映模型”。这种模型不是确定性模型，而是概率模型，其原因是考生对于测验项目的反映除了受到某种特定的“能力”的支配外，还受到许多随机因素的影响，如焦虑、动机、考试技能等。项目反映模型是表示考生能力和考生对考试项目正答概率之间关系的数学形式，主要有拉希模型、Logistic双参数模型，还有探索使用的等级积分模型、分布评分模型等。

2 遗传算法

遗传算法（Genetic Algorithm，GA）是一类借鉴生物界的进化规律（适者生存、优胜劣汰遗传机制）演化而来的随机化搜索方法。它由美国的J.Holland教授于1975年首次提出[2]，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定，具有内在的隐含并行性和更好的全局寻优能力。采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域，是现在有关智能计算的关键技术之一[3]。

以Holland1975年提出的称为传统的GA为例，简述它的主要步骤。

编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成不同的点。

初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体。N个个体构成一个群体。GA以这N个串结构数据作为初始点开始迭代。

选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。判断个体优良与否的标准是各自的适应度值的大小。

交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代的个体，新个体组合了其父辈的个体特性。交换体现了信息交换的思想。

变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.001～0.01。变异为新个体的产生提供了机会。

3 遗传算法在在线考试系统中的应用

基于IRT的组卷问题可以描述为一个最大化模型，此模型满足测试条件的同时，匹配公式（1）中对目标测验信息函数指定的形式，最大化测验信息函数[4]：

其中Xi表示试题是否被选进试卷中。若被选中，Xi＝1；否则，Xi＝0。Ii是能力θk点的项目信息函数值，而rk是测验目标信息量，系数qin是题目i具有属性n的参数值，Qn代表测验中包含属性n的题目数。cim是题目i的类别决策值，即如果题目i属于类别m则其值为l，否则为0。Cmn代表测验中允许包含的某一类别m的题目数范围。而Lip是题目间约束关系的系数，Lp是约束边界值。公式（1）用于表示题目之间的互斥或包含关系。

1）染色体编码及初始种群的生成。染色体编码就是对试题库的某道题目进行标示，当第i题被选中时，xi＝l；当第i题未被选中时，xi＝0。初始化串群体就是随机生成含有N个串的群体。在串群体中，串长度都是相同的，群体大小根据需要给出，一般取个体编码长度数的一个线性倍数。

2）适应度函数的确定。在遗传算法中，适应度函数的大小区分群体中个体的优劣。通常，适应度函数是通过目标函数转化而来，其值越大个体越好。通过对公式（1）的分析，适应度函数定义为：

其中对于函数t(x)，当x＞0时，函数值为x；当x≤0时，函数值为0。

3）遗传操作。选择：常用的选择算法为按比例的适应度分配，主要包括繁殖池选择、轮盘赌选择等方法。本文采用的选择算法是轮盘赌算法。交换：交换又叫基因重组，对于不同的编码方式，交换算子是不同的。本文采用的是二进制编码的单点式交换算子，即在两个父代个体上随即产生一个交换点，再间接交换两个父代个体的对应片段，从而得到两个子代个体。变异：变异是遗传算法中保持物种种群多样性的重要途径。在二进制编码中就是将随机选择出来的基因座上的基因值由1变0，由0变1。

4 结束语

本文以项目反应理论为理论基础，使试题本身的参数与考生样本无关，测试更加真实，评价更加合理。将遗传算法应用于在线考试系统，实现试题库的自动组卷，有效地提高组卷的质量和速度。

[1]余嘉元.教育和心理测量[M].南京:江苏教育出版社,1987

[2]Holland J. Adaptation in Natural and Artificial Systems[M].Ann Arbor: University of Michigan Press,1975

[3]张文修,梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社,2000

[4]董敏,霍剑青,王晓蒲.基于IRT智能组卷的模型管理系统[J].中国科学技术大学学报,2004,10(5):612-617