遗传算法组卷【基于遗传算法的智能组卷的研究】

　　摘要： 智能组卷是计算机辅助教学(CAI)中一个重要的研究课题，本文针对试卷生成的目标要求，建立了智能组卷的数学模型，并给出了用改进的遗传算法解决此问题的新方法。实验结果表明该改进的遗传算法能很好的解决试题库中智能组卷问题，具有较好的性能和实用性。
　　关键词：遗传算法；智能组卷；试题库
　　中图分类号：TP311文献标识码：A 文章编号：1009-3044(2007)18-31694-03
　　Research of the Intelligent Test Paper Composition Based of the Genetic Algoritnm
　　QU Xiao-tang
　　(Nantong Universitycollege of computer science & technology, Nantong 226007,China)
　　Abstract:The intelligent test paper composition is an important research subject in CAI. In the paper ,for the requirements of the test paper, the mathematical model of intelligent test paper composition is set up,And the author gives new method to resolve this problem with improved genetic algorithm.The experiment results show that algorithmcan solve the intelligent test paper composition problem in examination database effectively and it has the more capability and utility.
　　Key words:genetic algorithm; intelligent test paper composition; examination database
　　
　　1 引言
　　
　　为了了解学生的学习情况，分析教学的效果，需要对学生进行考核、评价，而一份高质量的试卷是准确评价学生的基础。在我们的日常教学中，为了组好一份试卷，教师往往要花费很多时间。因此，计算机自动组卷一直是CAI研究的热点问题。自动组卷就是根据用户输入的组卷要求，计算机自动从试题库中选择试题组成一份符合要求的试卷。
　　
　　2 组卷模型的建立
　　
　　2.1 问题的提出
　　从动态题库中每选一道题，都要根据某些约束条件对其进行筛选，这些条件包括对题型、内容、难度、知识点等约束，从这个意义上讲，可以把计算机智能组卷描述成一个约束满足问题，智能组卷就是在局部约束与全局约束协调一致的前提下对每个试题是否可以选择进行判断。这个问题可以表示成一个五元组，其中:
　　V={v1,v2……vn}，是一个有限变量集，对应着每道试题的属性变量(科目、内容、难度、知识点……)。
　　L={ll,l2,……ln}，是一个有限数字集，对应着每种属性变量的取值范围。
　　S={S1 S2……sn}，是一个有限规则集，对应着各试题属性变量的取值之间的约束关系。
　　R={r1,r2,……rn}，是一个有限规则集，对应着用户需求的约束关系。
　　C={cl,c2,……cn}，是一个试题序列，对应着从动态试题库中选择出来的满足约束的试题。
　　组卷系统要做的是从试题库中随机选出一组试题C，使得它们所有的属性变量V在L的取值范围内都满足S与R的约束，是一个多重约束目标的问题求解，且目标状态不是惟一的。根据经验，指标过多会增加组卷问题难度，降低效率。
　　2.2 试题难度和区分度分析
　　根据经典测试理论，题目的难度是指题目的难易程度，是被试总体在该题平均得分率，即：
　　得分率(d)=(平均分/该题满分)；
　　难度P=失分率=1-得分率=1-(平均分/该题满分)。
　　试卷的难度作为试卷的特征指标，它反映的是组成试卷的题目的总体平均难度水平。试卷的难度值可以通过对组成它的所有题目的难度进行加权平均的计算方法获得。试卷的平均难度
　　其中m是试卷所含的题目数，Pi, di没分别是第i道题的难度和分数。组卷时用户可以指定所抽取试卷的平均难度（为某一确定值）。
　　试题区分度的计算采用两端分析法:D= (Rk-Rl)/n，其中Rk为高分组(前27%的被试者)合格人数，Rl为低分组(后27%的被试者)合格人数。
　　教育测量学家认为:如果考试的目的是要在全体考生间进行最充分的比较，要求分数能够最大程度地区分考生，则此时考试的平均难度应控制在0.5左右较为适宜。若要达到这一难度要求，试卷中的试题难度最好分布在[0.3,0.7]范围之间。一般认为区分度在[0.3,1]为较好的题。
　　2.3 试卷难度控制量的数学模型
　　在各种组卷方案中，各类题型的试题量和各章的试题量都可以很容易地设定，而试卷平均难度与各试题的难度以及每级难度的试题量之间存在一定的关系。由于随机抽取的试题出现的概率都不依赖于其他抽题的结果，对于每道试题而言只有两种可能，即被抽出或不被抽出，并具有随机性。因此，随机抽题事件符合离散型随机变量的二项分布函数B（n, p),
　　其中k=0,1, 2，……,n, n为正整数，p>O,q>O,p+q=1
　　上式可写成：
　　在此模型中，k表示难度级别，P(k)表示难度级别为k的概率(即难度级别为k的题目在总题数中所占的比例)，q表示试卷的平均难度级别。对于n, p固定的二项分布B(n,p)，当n单调增加时，概率P{x=k}先是单调增加至最大值，然后单调减少，两头的概率很小可以忽略。这种特性正好符合我们对试卷难度分布的大致期望，即:“中间大，两头小”。
　　
　　3 遗传算法介绍
　　
　　遗传算法是一种模拟生物界自然选择和遗传变异的机制来求解复杂问题的随机搜索和优化方法。它模拟自然界生物体的演化过程，采用优胜劣汰，适者生存的自然法则选择个体，通过交配、变异来产生下一代种群，逐代演化直到满足条件为止。在演化计算中，我们不必非常明确地描述问题的全部特征，只根据自然法则来产生新的优化解，它采用简单的编码技术来表示各种复杂的数据结构，通过对相应的编码进行简单的遗传操作和自然选择机制来确定搜索的方向。
　　遗传算法的群体搜索策略为多目标优化提供了非常合适的解决方案。一般来说，多目标优化问题并不存在一个最优解，所有可能的解都称为非劣解，也称为Pareto解。传统优化技术一般每次能得到Pareto解集中的一个，而用遗传算法来求解，可以得到更多的Pareto解，甚至是整个的解都成为Pareto解。
　　
　　4 基于遗传算法的组卷问题的设计
　　
　　4.1 染色体编码
　　编码就是用一种数字排列方案来表示问题的解的方法，利用编码将问题的解空间映射到GA算法的编码空间。如何将问题的解转换为编码表达的染色体是遗传算法的关键问题，即先要将问题的解空间映射成一组代码串。
　　常见的编码方案有二进制编码、十进制编码、实数编码等。在组卷问题上常见的采用二进制编码，用1表示该题被选中，0表示该题未被选中，这种编码简单明了，但是进行交换等遗传操作时，各题型的题目数难以精确控制，而且，当题库中题量很大时，编码很长。在本文中，我们将一份试卷映射为一个染色体，组成试卷的各个试题映射为基因，基因的值直接用试题的题号表示，这样染色体的编码可表示为(G1, G2,G3……Gn)，其中Gi(i=1, 2，……,n, n为试卷的总题目数)为试题编号，比如要组成一份选择题5道、填空题5道、简答题2道的一份试卷，则染色体编码可以是：
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　并且编码将同一题型的题目放在一起，同时为保证一份试卷中考查点不重复，每条染色体中，各基因的考查点编码必须各不相同。由于不同的题型是从不同的题型表中取出，有可能在同一个基因串中会出现相同的试题编号，它们属于不同题型，考察的知识点也未必相同，这属于正常情况，不影响我们进行组卷。
　　在实际组卷过程中，假设在试卷中每种题型的数目是固定的，且相同题型的分数和答题时间是相同的。这样我们将整个编码串按照题目类型划分为不同的功能块，每个功能块可以认为是独立的编码。也就是说每个功能块对应一种特定的题型。显然按这种规则产生的初始群体己经满足了试卷对题型、分数和答题时间的要求。
　　4.2 群体的初始化
　　根据用户选定的考试内容及各种题型的题目数，按同一试卷中考查点不重复的原则，从相应题型表中随机抽取试题，生成初始群体，群体的大小按经验或实验给出。
　　由于遗传算法和其它启发式算法一样，不对全部解空间进行穷举搜索，因此初始的候选解群体的选择会对得到最终解的速度和质量有影响。初始的候选解群体在解空间内分布得越均匀，它们拥有的遗传基因就越有代表性。
　　4.3 适应度函数
　　在遗传算法中，以适应度大小来区分群体中个体的优劣。
　　设di(i=1, 2,……,m, m为试卷的总题目数)表示基因串中所选试题的考查点，用集合。表示用户要求试卷中应包含考查点的集合。生成的试卷满足用户关于各考查点要求的程度可以用f1的大小来评价:
　　可见，f1的取值范围为:O≤fll≤1, fl的值越小，生成的试卷越接近于用户关于各考查点的要求。
　　关于所生成的试卷的难度系数(设为DC)须为用户指定的系数(设为NDXS)，这一要求的满足程度可用f2的大小来衡量:
　　f2=|DC-NDXS|
　　f2的取值范围:0≤f2≤1, f2的值越小，生成的试卷越接近用户关于试卷难度的要求。
　　因而试卷的总体评价函数可写为:
　　f3= fl + f2 (8)
　　由于f3的取值范围为:0≤f3≤2，为了提高相近个体间的竞争，且通常情况下我们说适应度越大的个体越好，我们对上述函数采取如下变化，得到最终求解组卷问题的目标函数: (-200≤F≤0)
　　max F=-100 *f3=-100(f1+f2) (9)
　　4.4 遗传概率
　　1)选择概率
　　基因选择是个体位串根据其适应度函数拷贝自己的过程，是遗传算法中比较关键的一步，有时直接关系到收敛速度问题。基因选择有很多种方法，比如确定方法、轮盘赌法、贝努利实验法等。
　　直观地讲，可以把适应度函数F看作是我们期望的最大效益或好处的某种量度。显然，个体适应度愈高，被选中的概率愈大。不过，若直接按照适应度函数确定选择概率会使有些基因模式基本失去竞争的机会，故我们用F(i)/∑F (i)作为个体i生存下去的极率。但是，适应度小的个体也有可能被选中，这样有助于增加下一代群体的多样性。
　　2)交叉概率和变异概率
　　遗传算法的交叉概率Pc和变异概率pm的选择是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性。
　　交叉操作是遗传算法产生新个体的主要方法，交叉操作通常有单点交叉、双点交叉、多点交叉等等，交叉可以提高群体多样性。由于我们选择的初始群体接近我们的组卷要求，对其进行单点交叉运算即可。故将以上选出的个体进行两两随机配对，对每一对相互配对的个体采用有条件的“均匀交叉”，即2个配对个体的每一个基因座上的基因都按设定的交叉概率PC和一定的条件(即交换后各基因的考查点不重复)进行交换，产生2个新个体, Pc一般应取较大值，但若取值过大，易于破坏群体中的优良模式;若取值过小，产生新个体的速度又太慢。
　　变异操作是产生新个体的必不可少的辅助方法，也有三种方式:一点变异，多点变异，模板变异。若pm取值较大，有可能破坏掉很多较好的模式，使得算法的性能近似于随机搜索的性能;若pm取值太小，则变异操作产生新个体的能力和抑制早熟现象的能力较差。
　　由上可知，Pc和pm越大，算法产生新个体的能力就越强，个体之间的适应度波动比较大，产生新的超平面的能力比较强; Pc和pm越小，算法使个体趋于收敛的能力越强，个体的平均适应度比较平稳，有可能产生早熟现象。所以我们采用自适应的思想，在算法的运行过程中对Pc和pm进行调整，让它们随着个体适应度值的增加而变小，随着个体适应度值的减小而增加。其计算公式为:
　　交叉概率:
　　(10)
　　变异概率:
　　 (11)
　　(10) （11)两式中fmax为当前群体中个体适应度的最大值，favg为当前群体的平均适应度，f,为参与交叉操作的两个个体的适应度中较大的一个，f为参与变异的个体适应值，本算法中，取Pc1=0.9, Pc2=0.6, Pm1=0.1, Pm2=0. 001.由于种群中每一个功能块对应着一个题型，所以，为了保证每个题型的数目不变，交叉点的选择不能破坏功能块的完整性。假设交叉点位于第1个功能块内，则前1个功能块不变，从第i+l个功能块开始逐位交换。(交叉如果在功能块内也发生的话，可能会出现同一模块中有重复试题的情况)。
　　普通的变异操作可能会使用户指定范围外的题目出现在染色体中，也会使各题型的题目数难以保证，采用有条件的变异算子，即每个个体的每一个基因座上的基因都按设定的变异概率Pm在一定范围内(与该基因题型相同且考查点与本个体其他题的考查点不重复)变异。通过变异算子可以达到局部搜索的目的。
　　4.5 最优保存策略
　　进行了选择、交叉、变异操作后，比较新一代的最好个体与上一代的最好个体的适应度，如下降，则以上一代最好个体替换新一代的最差个体。此策略可以保证迄今为止的最优个体不会被交叉、变异等遗传运算所破坏，它是遗传算法收敛性的一个重要保证条件。
　　遗传算法中，用于寻优的目标函数的自变量为试题ID组，经过交叉、变异操作后，染色体(G1,G2……;Gm)中有一个基因Gi发生改变，将对整个基因都要进行检查，若有知识点重复的试题存在，需做出调整，从试题库中抽取试题，调换重复试题。这个约束在个体初始化，交叉/基因重组，变异中都要考虑。
　　
　　5 结束语
　　
　　由于遗传算法实行了全局并行搜索，搜索空间大，并且在搜索过程中不断向可能包含最优解的方向调整搜索空间，从而易于找到最优解。从实验结果看出，本文设计的动态调整遗传算子的遗传算法能有效地解决试题库智能组卷问题，与传统的随机算法相比，能较快地找到满足组卷多重约束目标条件的解。具有较好的适用性和效率。
　　
　　参考文献：
　　[1]LIU You,KAMG Li-Shan.Nonnumerical parallel Algorithms-Genetic Algorithms[m].Beijin:publishing House of Electronics Industry,1997(Ch)
　　[2]陈国良等.遗传算法及其应用[M].北京：人民邮电出版社，1996.
　　[3]全惠云等基于遗传算法的试题库智能组卷系统研究[J].武汉大学学报:自然科学版，1999,45(5):758-760.
　　[4]王学友等.模拟电子技术试题库智能组卷算法研究与系统实现[J].电子电气教学学报，2004，26(1)：85-89.
　　[5]微平，熊伟清.用遗传算法解组卷问题的设计与实现[J].微电子学与计算机，2002(4)：48-50.
　　[6]钟求喜，解涛，陈火旺，任务分配与调度中的遗传算法[J].知识表示与遗传算子研究 ,计算机科学，2000 27(6),46-49.
　　注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文