遗传算法组卷的研究与设计

倪雪飞 孙吉花

【摘要】在线考试系统中的自动组卷技术是系统的核心，是近年来的一门综合新兴学科，它是根据每次的考试要求通过系统来实现自动生成考试试卷，从而克服传统的一些弊端。本系统考试的要求包括：考试人员类被，考试方向，考试试题类别，试题数量，试卷分值，试题分值，考试时间等参数。通过考试了解当前阶段的任务完成情况和存在的不足。自动组卷能够避免考试中因为人为主观因素造成的影响，自动组卷技术已经被越来越多的在线考试系统采用。

【关键词】自动组卷  遗传算法  在线考试

当今社会工作节奏的加快，为了能够增强自己在社会中的竞争力，学习充电是必须的，但是繁琐的异地资格考试很是浪费时间和精力，在线考试系统就应运而生，在线考试系统需要做到能够真实有效的考察一个人的知識掌握情况，这就需要在组卷上算法上做到尽量智能化。特别是要避免人工组卷带来的不安全性和不客观性，所以在线考试系统采用的组卷技术一般都是自动组卷。其中常见的组卷技术有随机组卷、回溯组卷和遗传算法组卷等，下面我们详细讲解遗传算法组卷。

遗传算法

遗传算法概述

遗传算法[1]（Genetic？Algorithm，简称GA）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法，由美国的J.Holland教授1975年首先提出。遗传算法是一种模拟达尔文的生物进化理论物竞天择的计算模型，通过对自然界生物进化的模拟来解决多约束条件下的最优解。算法实施流程图如图1所示

遗传算法是对种群中的个体进行操作，问题空间的参数通过基因链的形式表示出来，编码的好坏对算法解决问题的能力有直接影响。目前，存在的编码方式包括二进制编码、动态编码、格雷码编码[2]、十进制编码和实数编码等多种方式。在本系统的组卷应用中，在组卷过程中对数据库的存取访问速度受到试题数据结构的影响较大，为了能够在组卷过程中减少数据访问的时间开销，直接以题号作为基因的值，每种题型的题号放在一起，这样就能快速的获得指定类型的试题。因此，本系统采用分段的实数编码方案，比如要组一份“后勤理论”的试卷6道单选，5道多选，3道判断，2道论述，其染色体的编码为：

（10，12，3，5，9，40）  （25，32，21，6）  （16，51，11）  （7，26）

单选题       多选题     判断题    论述题

在遗传算法的开始，一般采取的是随机生成初代种群，以达到遍历所有状态的目的。但是这样会一定程度上延长进化的时间，本文针对系统的使用对象和问题的实际情况，采用不完全的随机初始化种群的方法，初始化种群的时候就设定试卷的考试方向、各个题型的数量、分数以及考试时间，这样生成的种群就已经满足了试卷的一大部分要求，加快了算法的收敛和减少了迭代次数，同时取消了个体解码时间，提高了求解速度。

适应度函数设计

适应度函数是遗传算法寻求最优解的依据，一般来说是由目标函数直接转化而来，通过它来对群体中的个体的优劣程度进行评估，指导算法的搜索方向，因此适应度函数的好还是至关重要的，因此，一份试卷的适应度[3]越高，那么它就越接近算法的最优解，本文在初始化种群中就已经约束了试题方向、分数、考试时间等辅助信息，只需要考虑试卷的难度系数就行了，所以本文中所用的适应度函数是由试卷的难度系数公示转换而成的。试卷的难度系数为公式1：

（1）

其中Di 为第i道题的难度系数，Si为第i道题的分数 ，n为试卷中试题的总数目。用户的期望难度EP与试卷的难度P之间的差越小越好。如果一份试卷中期望含有N个知识点，而一个个体试卷中含有M个知识点，那么该份试卷中知识点覆盖率为 ，上面说到EP和P之间的差值越小越好，知识点覆盖率则越大越好，本文中遗传算法的适应度函数为公式2：

（2）

公式2中f1为知识点分布权重，f2为难度系数所占权重，其中f1为零时，那么只考虑难度系数;f2为零时，只考虑知识点覆盖率，由于本系统使用对象的特点，只考虑难度系数。

遗传算子

1.选择算子

选择算子[4]的主要作用是根据个体的适应度大小决定个体是被选中还是淘汰，这样适应度高的个体生存机会就要高一些，为了让遗传算法在组卷中发挥更好，本文采用的是轮盘赌方法，根据个体的适应度的不同，个体被选中的概率为公式5-1所示，通过公式可以看出，个体的适应度越高，被选中的概率就越大，这样优秀的个体就能够得到保留。

2.交叉算子

本文在对个体进行染色题编码的时候采用的是分段实数编

码，所以交叉就采用了分段单点交叉策略，具体实现过程为：随机选择个体使其两个为一组，通过交叉概率Pc和适当的条件进行交换，产生两个新的个体，其中Pc的选择会影响到算法的收敛性，如果Pc过大，产生新个体的速度就越快，但是容易使得优秀个体遭到破坏，而Pc过小，则会使的搜索过程缓慢。

3.变异算子

在对个体进行交叉后，对个体的基因进行基于概率Pm进行基因变异，这个概率一般较小，对Pm的设置不能过小，如果过小不易产生新个体，如果过大就变成了纯粹的随机搜索。本文在交叉的时候采用了分段单点交叉，这里就不进行分段变异了，而是对整个基因的某段上的某个基因进行变异。通过随机生成一个[1，n]的随机数r，r作为一个变异位置，然后从题库中选取一个变异基因，在选取的时候要保证新选择的基因要与原基因具有相同的题型，相同的分数，相同的考试方向。

遗传算法控制参数设置[5]

遗传算法的多个参数中交叉概率Pc和变异概率Pm对算法的影响较大，其中Pc的选择会影响到算法的收敛性，如果Pc过大，产生新个体的速度就越快，但是容易使得优秀个体遭到破坏，而Pc过小，则会使的搜索过程缓慢。而Pm的取值的大小同样影响算法的性能，在保持群体保持多样性的前提下Pm不能设置过大，如果Pm取值过大，会使算法变为随机搜索，Pm取值过小，个体的多样性就无法得到满足，从而使得算法陷入局部最优的状态，而过早收敛。为了避免因为交叉概率和变异概率取值造成算法性能受到影响，加快遗传算法收敛和有效的避免其陷入局部最优状态，同时保持较为优良的试卷个体，本文采取交叉概率 Pc 和变异概率 Pm 的自适应策略，即使得交叉概率 Pc 和变异概率 Pm能够随适应度自动改变，当种群的个体趋于一致或者陷于局部最优时，交叉概率Pc和变异概率 Pm就增加，当群体适应度比较分撒时，交叉概率 Pc 和变异概率 Pm就减小。

可以通过实验对Pc和Pm的值进行设定从而取最佳值，通过实验可以Pc取值范围在0.2～1.0之间时，组卷的成功次数多，而迭代次数少，在组卷方面呈现先增后减，在迭代次数上呈现先减后增。Pm取值过大时，组卷的成功率较低，迭代次数增加，这是由于变异造成的群体中优良的个体遭到了破坏，但是取值过小产生新个体的速率就会降低，导致种群不能实现多样性。当种群规模较小时，组卷成功率很低，因为种群的规模本身就小，这样就不具备多样性的特点，使得算法的搜索空间局限性很强，出现了未成熟收敛的情况。随着种群规模的提高，算法的搜索空间加大，这样组卷的成功率也提高，但是平均迭代次数也会随着种群的提高而提高，这样也会影响算法的效率。

【参考文献】

[1]陈国良、王熙发等，遗传算法及其应用，北京：人民邮电出版社，2001，1～400

[2]李华山;格雷码的代数结构和分形生成的递归算法[J];北方工业大学学报;1996年01期

[3]Holland J. Adaptation in Natural and Artifical Systems[M].AnnArbor：The University of Michigan Press，1975，1～50

[4]王小平，曹立明.遗传算法一理论、应用与软件实现[M].西安：西安交通大学出版社，2002

[5]劉学增，周敏. 改进的自适应遗传算法及其工程应用[J]. 同济大学学报（自然科学版）. 2009（03）