《一种基于ＣＨＣ算法的自动组卷方法.doc》由会员分享，可在线阅读，更多相关《一种基于ＣＨＣ算法的自动组卷方法.doc（10页珍藏版）》请在三一文库上搜索。
1、一种基于算法的自动组卷方法?丶?词：自动组卷； 跨世代异物种重组大变异算法； 遗传算法 Approach of auto generating examination paper based on CHC algorithm DING Zhenguoa， GUO Haiyanb (a.School of Network Education, b.School of Computer Science & Technology, Xidian University, Xian 710071, China) Abstract:An approach of auto generating examin
2、ation paper based on the improved genetic algorithm CHC algorithm was proposedThe initial population was produced by the searching algorithms containing heuristic information The fitness function was the weighted sum of the absolute error of the paper entire index andactual indexThe select operating
3、 population was summation of current and previous one，for the operating population was big，the genetic diversity could be kept betterThe single node crossover was used in cross operatingThe mutate operating process was that some individuals of bad fitness were chosenfrom last generation first，then l
4、ocas in proportion with these individuals were picked up,these place values were determined randomlyDue to the restrict of the capability，the algorithm can avoid blindness and can speed up the constringency Simulation results show that the planning algorithm is faster than the basal genetic algorith
5、ms and meet the optimal requirements Key words：auto generating examination paper； cross generation heterogeneous recombination cataclysmic mutation(CHC)algorithms； genetic algorithm ? 0 引言 自动组卷就是根据用户输入的组卷要求，计算机自动从试题库中选择试题组成一份符合用户要求的试卷。自动组卷的效率与质量完全取决于组卷算法的设计。如何设计一个算法从题库中既快又好地抽出一组最佳解或是抽出一组非常接近最佳解的实体，涉
6、及到一个全局寻优和收敛速度快慢的问题。目前比较流行的自动组卷的方法是根据用户输入的试卷总体要求，分别匹配试卷的知识分布、题型分布、认知分类分布、难度分布、区分度分布、时间分布、分数分布，形成组卷参数表，然后根据该参数表从试题库中选题。这类方法在形成最终的组卷参数表时，没有考虑知识分布、题型分布、难度分布等各种参数之间的相互制约关系，因此在组卷时题库中经常会出现找不到满足所有属性的试题，只好用具有近似属性的试题替代，最终会降低组卷的指标。针对这个问题，选题时可以采取一些策略，如优先权策略、补偿策略、回溯策略等，但这样会使算法很复杂，效果也有限。 基于此，本文提出一种利用跨世代异物种重组大变异(C
7、HC)算法来进行自动组卷的方法。CHC算法是遗传算法的一种改进，它是由Eshelman于1991年提出的。该算法与基本遗传算法（SGA）的不同点在于：SGA的遗传操作比较单纯，简单地实现并行处理；CHC算法牺牲这种单纯性，换取遗传操作的较好效果，并强调优良个体的保留。 1 CHC算法概述 遗传算法是从代表问题可能潜在解集的一个种群开始的，一个种群则由经过基因编码的一定数目的个体组成，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一
8、样的后代种群比前代更加适应环境，末代种群的最优个体经过解码，可以作为问题的近似最优解。CHC算法是简单遗传算法的改进，它强调优良个体的保留，其改进之处首先表现在选择上。通常，遗传算法是依据个体的适应度复制个体完成选择操作的；而在CHC算法中，上世代种群与通过新的交叉方法产生的个体种群混合起来，从中按一定的概率选择较优的个体。这一策略称为跨世代精英选择。其明显特征表现在： a)健壮性。这一选择策略，即使当交叉操作产生较劣个体偏多时，由于原种群大多数个体残留，不会引起个体的评价值降低。 b)遗传多样性保持。由于大个体群操作，可以更好地保持进化过程中的遗传多样性。 c)排序方法。克服了比例适应度计算
9、的尺度问题。 d)在交叉操作上很灵活，根据不同的应用领域采取不同的交叉方法。自动组卷由于通常采用符号编码方案，可以利用单点交叉、双点交叉及均匀交叉等。变异操作上CHC算法在进化前期不采取变异操作，当种群进化到一定的收敛时期，从优秀的个体中选择一部分个体进行初始化。初始化的方法是选择一定比例的基因座，随机地决定它们的位值。这个比例值称为扩散率，一般取0.35。 2 组卷问题的数学模型 组卷问题实际上是一个多条件的约束优化问题，这个问题通常被定义为一个目标函数和多个约束条件的组合。 为了考核学生对所学内容的掌握情况，每道试题一般需具备如下九个属性:试题编号、题目类型、试题所属知识点、难度、区分度、
10、认知分类、估计答题时间、分值、曝光度。所以在组卷中生成一份试卷，就是得到一个m9的矩阵。其中：m是该试卷中试题量总数；每道试题的九个属性决定矩阵S一行元素的值。S可表示为如下形式: S= a11a12a18a19 a21a22a28a29 ?螃? ?螃螵? am1am2am8am9 这是一个问题求解中的目标状态矩阵，它应尽量满足如下多个约束条件: a)总答题时间f1(由用户给出) = mi=1ai,7。 b)试卷总分f2(由用户给出)=mi=1ai,8。 c)试卷难度系数f3(由用户给出)= mi=1ai,4/m。 d)区分度f4(由用户给出)=mi=1ai,5/m。 e)试卷题型分布及各题型
11、试题量分布f5(由用户给出)=ki=1bi=m。其中：k为试卷题型数；bi为各题型试题量。 f)试卷认知分类分布f6(由用户给出)=pi=1ci=f2。其中：p为认知分类类型数；ci为各认知分类的题目所占的分值。 g)曝光度f7=mi=1ai,9尽可能地小。 在实际应用中设定整卷指标来综合反映这个指标与用户要求的误差。由于它们的重要程度不同，整卷的指标就是几个指标的加权和；同时为了不至于各个误差相互抵消，这几个指标与用户要求的误差都取绝对值。可以用下式表示:f=fiwi。其中：fi表示第i个指标与用户要求的误差的绝对值；wi表示第i个指标的权值。组卷的目标就是使整卷指标f最小，或者尽可能小。
12、3 自动组卷的算法实现 3.1 编码方法 问题解的编码表示采用基因分段式编码，在编码时可以解决组卷中题型及各题型题量分布这些约束条件，简化求解问题。具体编码方式如下:首先根据各题型独立编码成基因段，基因段的数量由题型的数量决定，用k来表示；每一基因段内基因数由试题库内该题型的题量决定。因此，试题库有n道试题时编码为b1,b2,bn。 bi=1 当第i道题被选中时0 当第i道题被选中时；i=1,2,n 且满足条件ni=1bi=m, m是实际组卷中试卷所需题量 r1i=1bi=m1,r2i=r1+1bi=m2,rki=r(k-1)+1bi=mk,ki=1mi=m,rk=n rk-r(k-1)为试题
13、库中各题型的题量;m1,mk分别为实际组卷中各题型所需题量。 3.2 初始化群体的产生 初始试卷集是整个遗传算法迭代的起点，本文采取如下策略产生初始试卷集：对每一基因段随机选择m个位置，将它们的位值置1，其他位值置0。这样就生成一个初始试卷个体，如此反复生成包含n个个体的初始试卷集。在初始试卷集中，串长度都是相同的，群体大小根据需要，按经验或实验给出。在实际组卷中，设群体规模为N，每一个体的基因段都是通过random()这个函数在该类题型的最小题号与该类题型的最大题号之间随机选择mi道题。其中mi表示第i种题型所需题量。 在生成初始群体的个体时，每产生一个满足条件的随机数时，都要把题库中对应试
14、题选题标记置1。同时把题库中具有相同知识点的试题的选题标记置1，这样就可以避免相同知识点试题在同一试卷生成时重复出现，从而优化了初始群体。 3.3 适应度函数 首先通过解码得到个体的组卷参数矩阵S。具体过程如下：根据串b1,b2,bn的值，可知试卷中包含的试题题号；然后把这些试题的属性写到组卷参数矩阵S中(由此可以看到：组卷参数矩阵S的值是由题库中的试题属性组成的，这就保证了按照矩阵S来选题时不会出现找不到题的情况)；最后调用评估函数得到每个个体的适应度。在实际应用中，通过计算个体的整卷指标f来反映个体的适应度，整卷指标f越小，个体的适应度越高。所以可取适应度函数为整卷指标f的倒数，即F=1/
15、f。适应度函数反映了个体与成卷要求之间的差别，算法在优化搜索中以适应度函数为寻优依据。 3.4 遗传算子的设计 1）选择算子 根据适应度的大小按照比例选择方法来求取个体遗传到下一代的概率，方法如下：a)首先计算出当前群体P(k)和通过交叉方法产生的个体群体C(k)中每个个体的适应度Fi；b)计算每个个体的相对适应度的大小，即Fi/nj=1Fj,它就是被遗传到下一代的概率；c)利用轮盘赌选择方法来确定每个个体被选中的次数；d)对当前群体P(k)和通过交叉产生的群体C(k)中的个体按照适应度进行大小排序，选取前面N个适应度大的个体作为遗传到下一代的个体，这样群体规模又恢复为原来的规模。 2)交叉算
16、子 对当前群体P(k)与上世代群体P(k-1)混合后产生混合种群C(k)中的个体进行配对，即分成N对个体对，然后计算配对个体间的海明距离。当该距离大于海明距离阈值时，对该配对个体实行交叉策略；否则将该配对个体从种群C(k)中消除。这里采用单点交叉方法，即首先找出每对的两个个体中在同一基因段内距离最近的两个点，这就是需要交叉的点，交换这两个点的编码即产生了两个新个体。交叉后的种群记为C(k)。 3)变异算子 在进化前期不进行变异操作，当进化到一定收敛时期时才采取变异操作。变异的方法是从P(k)中选择适应度较差的N1个个体进行初始化。初始化的方法是选择一定比例的基因座，随机地决定它们的位值。 采用
17、没有重串的稳态繁殖技术，即在形成新一代种群时，使其中的种群均不重复。在将child1、child2加入到新的一代种群之前，先检查它们是否与种群中现有的个体重复；若重复，则舍弃，重新进行变异，甚至重新进行交叉。 4 实验结果与结论 利用J2EE平台进行实验分析，将500道试题按要求分别赋予各项特征值存于试题库中， 给出要生成的试卷要求，为了比较CHC算法与基本遗传算法，仿真时分别采用了这两种算法进行对比分析。这里，群体规模选为20。表1为两种算法的仿真结果。利用基本遗传算法时的平均迭代次数为354.4次，利用CHC算法时的平均迭代次数为24次。可见利用CHC算法得到的结果比基本遗传算法有较优的性能指标。 表1 两种算法的性能比较 迭代次数 实验次数 遗传算法CHC算法迭代次数 实验次数遗传算法CHC算法 121126446118 233317540931 335828平均354.424 5 结束语 智能组卷是一个典型的多条件约束优化问题，本文针对该问题，采用CHC算法进行求解，提高了遗传算法的搜索速度、简化了杂交运算，具有很好的性能和实用性。