数学建模社区-数学中国

标题: [推荐]遗传算法在试题组卷中的应用 [打印本页]
作者: sxqiang    时间: 2005-5-22 00:43
标题: [推荐]遗传算法在试题组卷中的应用
本文运用遗传算法的全局寻优对考试中的自动化组卷进行了研究，并得到了一个解决适合考方要求的试题模型的好的算法。
　
关键词：遗传算法 全局寻优 自动化组卷

5 ^6 E9 B+ `4 n

1 引言

/ i- d& p+ g3 h0 m% q

计算机辅助考试系统的自动组卷的效率与质量完全取决于抽题算法的设计。如何设计一个算法从题库中既快又好的抽出一组最佳解或是抽出一组非常接近最佳解的实体，涉及到一个全局寻优和收敛速度快慢的的问题，很多学者对其进行了研究。遗传算法以其自适应寻优及良好的智能搜索技术，受到了广泛的运用。Potts J C等人基于变异和人工选择的遗传算法对最优群体规模进行了论述；Hamilton M A等结合遗传算法把其运用到神经网络中，并取得了良好的效果[4]；也有众多的学者对保留最佳状态的遗传算法的收敛速度做了讨论。通过理论推导和事实运用，发现遗传算法在寻优和收敛性方面都是非常有效的。

# I# Y2 W- C4 z: V! A3 }- m

本文结合遗传算法的原理和思想，对考试自动出题组卷的问题进行了研究，找到了一种获得与考试试题控制指标符合的试题模型的解决方法。

7 S/ Y1 i p) q) U

2 问题描述

5 E% S2 k" ]2 _" W d

自动组卷是考试系统自动化或半自动化操作的核心目标之一,而如何保证生成的试卷能最大程度的满足用户的不同需要,并具有随机性、科学性、合理性,这是实现中的一个难点。尤其在交互式环境下用户对于组卷速度要求较高，而一个理论上较完美的算法可能会以牺牲时间作为代价，往往不能达到预期的效果。因此，选择一个高效、科学、合理的算法是自动组卷的关键。

/ |- Y9 c! j% w. d+ {

以往的具有自动组卷功能的考试系统大多采用随机选取法和回溯试探法。随机选取法根据状态空间的控制指标，由计算机随机的抽取一道试题放入试题库，此过程不断重复，直到组卷完毕，或已无法从题库中抽取满足控制指标的试题为止。该方法结构简单，对于单道题的抽取运行速度较快，但是对于整个组卷过程来说组卷成功率低，即使组卷成功，花费时间也令人难以忍受。尤其是当题库中各状态类型平均出题量较低时，组卷往往以失败而告终。

N: D; s, h1 N/ I4 m% f

回溯试探法这是将随机选取法产生的每一状态类型纪录下来，当搜索失败时释放上次纪录的状态类型，然后再依据一定的规律（正是这种规律破坏了选取试题的随机性）变换一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成完毕或退回出发点为止，这种有条件的深度优先算法，对于状态类型和出题量都较少的题库系统而言，组卷成功率较好，但是在实际到一个应用时发现这种算法对内存的占用量很大，程序结构相对比较复杂，而且选取试题缺乏随机性，组卷时间长，后两点是用户无法接受的，因此它也不是一种很好的用来自动组卷的算法。

, t- ~3 U. S [, } b9 e1 @( L/ G

分析上述两种算法的优缺点，不难发现，在限制条件状态空间的控制下，随机选取法有时能够抽取出一组令用户满意的试题。只不过由于它随机选取试题的范围太大，无法确定目前条件下哪些区域能够抽取合适的试题，反而可能在那些已经证明是无法抽取合适试题的区域内反复选题，进行大量的无效操作进入死循环，最终导致组卷失败。回溯试探法组卷成功率高，但它是以牺牲大量的时间为代价的，对于现今越来越流行的考生网上随机即时调题的考试过程来说，它已不符合要求。因此,必须结合以上两种方法寻找一种新的改进算法，这种算法要具有全局寻优和收敛速度快的特点。遗传算法（Genetic Algorithms）以其具有自适应全局寻优和智能搜索技术，并且收敛性好的特性能很好的满足自动考试组卷的要求。

; S# P7 Y$ a0 I) L8 E% y, K( K( c* }4 m

3 遗传算法描述

# ]+ L T1 Y$ ^) K+ f' @7 v" P

遗传算法是一种并行的、能够有效优化的算法，以Morgan的基因理论及Eldridge 与Gould间断平衡理论为依据，同时融合了Mayr的边缘物种形成理论和Bertalanffv一般系统理论的一些思想，模拟达尔文的自然界遗传学：继承（基因遗传）、进化（基因突变）优胜劣汰（优的基因大量被遗传复制，劣的基因较少被遗传复制）。其实质就是一种把自然界有机体的优胜劣汰的自然选择、适者生存的进化机制与同一群体中个体与个体间的随机信息交换机制相结合的搜索算法。运用遗传算法求解问题首先需将所要求解的问题表示成二进制编码，然后根据环境进行基本的操作：selection，crossover，mutation……这样进行不断的所谓“生存选择”，最后收敛到一个最适应环境条件的个体上，得到问题的最优解。[6,7]

3 V* X; Y; E, K; K+ n

4 遗传算法应用

8 a- B/ m( T( G0 F; n

一般来说，用户在自动组卷时会对试卷的质量提出多方面的要求，如总题量、平均难度、题型比例、章节比例、重点章节比例、知识点的交叉与综合等，自动组卷就应最大程度的满足用户的要求。因此，在组卷之前，我们首先为自动组卷过程建立控制指标相应状态空间D，

+ K% M- C3 \+ v8 I! w

D=[]

6 ?+ X1 s2 j* t% ^% r+ W

D的每一行由某一试题的控制指标组成，如题号、题型、章节、难度等，并且这些属性指标都进行编码表示成二进制形式，而每一列是题库中的某一指标的全部取值。在具体出题时，考方可能不会用到所有的指标，所以D包含的个体d_target可以表示为d_request和d_void，d_request表示考方要求的控制指标，d_void表示考方不要求的控制指标。即

% S2 Q: L/ m& ]5 J7 O

d_target：：=<d_request>：<d_void>
<d_request>：：={0，1}m
<d_void>：：={0，1}n

7 w5 L1 b9 I* M5 q! B9 a( w

试题库[STK]中的每一道试题在建库时都输入了相应的属性指标。试题模型的产生形式是：

, Y' T8 X8 |9 X7 H s# A, R, v

if <data> then
<model>
<data>：：={0，1，#}m

' g8 _2 g6 k6 M6 z$ |: {

#表示0和1之间的任意一位。

7 ^8 e$ T8 ~3 V+ S. H

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

M8 r* i' H [% z$ h

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

& |4 n2 l% B. @" D2 s

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

6 w: g) }; V3 B8 p' X" m

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

' D0 w" M2 f: A- C9 X* b

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

, O# d& y5 G0 h! ~* e3 E4 b) J3 }

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

0 c b9 O# k' k* }2 z

如果不匹配，则有

- g# r+ X9 _4 y/ W! z% D2 N

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

x9 x; S3 P' O$ \" A/ g

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

l5 C+ i( H/ I( E; Y) O& m/ z: E ?3 H

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

: u. A( E, U. Y b, V3 O

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

5 M v0 g- p3 Q/ O

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

; Z/ @! R1 s/ s& r+ a$ P6 _

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

) e' B% Y/ d% Y1 f3 t' b% Y# Q) V" t

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

; o9 J2 u, W: {# X) A b

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

1 [- B3 z' f/ K8 y

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

) N+ z1 }0 b! M( ], ^

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

8 v9 A$ U1 \5 |( j

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

( H: l7 c9 w7 K# B/ @5 s0 s! p& \

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

N( ]# H- c1 x1 b( U: ]% @

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

# u# X& F2 o5 ]% ?3 c( G. N

5结束语

' t3 @3 z: t4 y- _& z2 J# Q

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

2 I% } t9 R" o+ j1 k1 O/ U2 r

参考文献

1 I% G$ t6 S& c& c9 F; p

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

6 A4 p7 R1 q/ w4 Y3 n" n

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

' D: Q1 c% i" ]2 C

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

7 w" h) o: S; d# \2 E K( E

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

8 |# b2 U: ~# s5 B, s0 ?

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

作者: hyip    时间: 2009-6-21 11:39
感谢，我要好好学习学习
作者: yinfeiyangfang    时间: 2010-1-8 10:05
回复 1# sxqiang
$ I# [* v  ~+ ~, v$ A& J* H" q% q+ @' V/ \/ \% F$ s1 B  }

1 z1 q! q+ Z1 |  A+ P    神经网络
作者: wendoog    时间: 2010-2-1 09:54
看看再顶一下~才能下多一个，嘻嘻
作者: liunengwu    时间: 2010-4-17 10:31
看看再顶一下~才能下多一个，嘻嘻



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5