遗传算法在组卷系统中的应用

来源:用户上传      作者:

　　摘 要： 随着理论与技术的发展，人们的要求逐渐增加，目前没有一个软件或者是一种技术能够解决组卷面临的一系列问题，也就是说，关于组卷仍然有一些问题有待解决，比如组卷的速度、试卷的质量以及与考生的匹配情况等问题仍待解决。因此，本文针对这些问题展开研究，以期找到一个理想的解决方法。
　　关键词：遗传算法 组卷 考试系统
　　中图分类号：O14 文献标识码：A 文章编号：1003-9082（2015）08-0209-02
　　一、引言
　　在传统的考试模式中，主要是采用纸笔的形式完成考试，教师为了完成考试工作，往往要花大量的时间和精力来收集试题、编制、整理才能生成试卷，这种考试不但给教师带来很重的工作负担，而且效率很低。与此同时，计算机技术和网络的迅速发展使得计算机已经成为学习和教学过程中的重要组成部分，计算机测试应运而生。根据用户的具体要求，计算机测试的试卷可以由系统自动生成，这一方面增加了考试的规范性、客观性，另一方面节省了大量的人力物力资源和时间。
　　组卷作为考试系统的核心就是依据考试目的、性质和特点，按照教育测试理论编制质量良好的试题、组成符合要求的试卷并给出科学的参考答案与评分标准[1]。智能组卷可描述为利用计算机从一定题量的试题库中抽取满足目标要求的一组试题组合[1]。
　　二、遗传算法简介
　　1.遗传算法的基本思想
　　根据生物进化原则，遗传算法将问题的求解过程模拟成一个生物进化的过程，它首先将要求解的目标对象化为一个生物种群（population），每个种群都有能够描述自身特点的基因（gene），这个基因是经过一定的编码方式而获得，而每个中群里又包括很多有这种基因编码特点的个体（individual），每一个体的具体表征形式即为个体的染色体（chromosome），染色体是个体所有信息的载体。[4]
　　2.遗传算法的特点
　　而遗传算法作为搜索算法的一种，同时具备搜索算法所有特点，并将这些特点以其特有的方式进行组合，构成遗传算法所特有的优点，这些组合方式包括：并行搜索方式，以及选择、交叉和变异操作。现将遗传算法的的优点总结如下：
　　2.1遗传算法的求解过程抛弃了传统的从问题的某个单一解开始进行搜索，而是以问题解的集合即种群为起点进行搜索，这样从整体角度出发，是搜索的结果为全局最优而非局部最优。
　　2.2遗传算法以种群为单位进行全局寻优不仅避免了陷入局部最优解的可能性，更重要的是实现寻优过程的并行计算，大大提高了算法的效率。
　　2.3遗传算法的搜索过程不依赖于其他信息的标记与计算，只靠适应度函数进行评估，简单易行，同时适应度函数的设计由用户根据具体问题自行设计，具有很高的灵活性。
　　2.4遗传算法的运算过程不依赖于任何条件，是完全随机的，只和交叉、变异的概率有关。
　　2.5具有自组织、自适应和自学习性。算法的求解过程是完全的自发性的搜索过程，根据优胜劣汰的原则，好的个体总因为有较好的适应性和生存概率而被保存下来。
　　3.遗传算法的基本操作及运算流程
　　3.1遗传算法的基本操作
　　遗传算法包括三个基本遗传算子操作：选择（Selection）、交叉（Crossover）和变异（Mutation）[4]。
　　（1）选择。选择操作对应达尔文进化论中的自然选择过程，根据优胜劣汰的原则将种群中的优良个体保留下来，成为新的种群，并进行下一代的遗传操作，即繁衍子孙。而这种优胜劣汰的原则在遗传算法中对应的就是适应度值，我们将按照具体的规则制定适应度函数，进而计算出每个个体的适应度值，根据适应度值决定那些个体能够被保留下来，并遗传到下一代种群中。因此适应性越强的个体被保留并将优秀基因遗传给下一代的概率就越大，符合优胜劣汰原则。实际应用中最常见的选择方法就是轮盘赌方法，也称适应度比例法。即适应度越高的个体在整个的轮盘中占得比例越大，被选中的概率越高。[7]
　　（2）交叉。交叉操作即为两个个体通过交换部分染色体编码，生成两个新的个体的过程。这一操作同变异共同控制着遗传过程中的基因重组，而交叉所得的新个体保留了其父辈个体的所有特征，因此是遗传算法的主要操作。在具体的操作中，交叉操作是通过随机函数为种群中的个体进行随机配对，然后为每一对个体随机生成一个交叉点，控制个体交叉的具体位置。常用交叉算子有：单点交叉、双点交叉和多点交叉以及均匀交叉和算术交叉等等。
　　（3）变异。变异操作即遗传过程中的基因突变。其具体操作过程为为每一个个体随机生成一个变异点，这个点就是基因突变的位置，然后为这个位置选择新的基因来替换原有基因，这一过程即为变异操作。具体的变异方式包括单点、两点、多点、有效基因、均匀等，除此之外还包括变异算子的自适应变化。
　　3.2遗传算法计算流程
　　遗传算法的第一步就是种群的初始化，即根据编码方式利用随机函数生成种群规模为N的初始种群，即随机组成N个个体。第二步是根据适应度函数为种群中的每个个体计算适应度值。第三步即为交叉过程，即为种群中的个体进行两两配对，使其杂交产生新的个体。然后是变异，为产生的新个体进行变异操作，首先生成随机数判断此个体是否需要变，若需要，则继续生成变异位置和变异基因，完成变异操作，如不需要，则继续对下一个体进行判断，直至所有个体都判断完为止。至此新一代个体已经生成，因此我们要为其重新计算适应度值，然后从中选择优秀个体进入下一代的遗传操作，如此循环往复，直到满足终止条件为止。[6]
　　三、基于遗传算法的组卷系统设计
　　1.编码设计
　　对组卷问题采用二进制编码时，题库中每一道题的状态都要在这一编码中显示出来，此时编码的长度即为题库中的题目数量，而每一个位置上的二进制数则表示该题目是否被选中，1表示选中，0表示未被选中。[2-3]若题库中有10个选择，10个判断题，分别选取两道选择，两道判断题，假设选择题第2，6被选中，填空题第1，7被选中，其染色体编码如下： 　　0100010000|1000001000
　　选择题 | 填空题
　　但是题库是试题的存储仓库，其中包含大量的试题，这样的编码方式会导致个体的染色体会很长，当种群规模很大的时候会占用大量的运算空间，而且在进行交叉和变异操作时，题目的数量和位置均不容易被控制，因此不是一种理想的编码方式。故本文中系统采用十进制编码方式，以试卷的题目数量作为染色体长度，每个位置上的十进制数即表示此位置上选择的试题编号，编码将所有的题型放在一起，并按题型分段，在整个的算法操作中均按段进行[5]。
　　2.种群的初始化
　　种群的数目即每一代中个体的数量。在遗传算法中，种群数目的确定对算法的效率有直接的影响。一方面，种群的规模越大，表示算法搜索的范围越大，得到全局最优解的机会也越大；另一方面，种群的规模越大，运算量也会随之增大，计算时间过长，收敛速度慢等问题也会随之出现。[8]经过多次尝试，本文最终确定种群的初始规模为60，即每一代都有60个个体参加遗传操作， 。
　　3.适应度函数的设计
　　适应度函数是评判种群中个体优差程度的标尺，掌握着优胜劣汰，适者生存的选择机制和种群的进化方向，因此，适应度函数的设计至关重要。本文的系统中，试卷题目的知识点范围、题型等约束条件已经在初始化种群时进行了限制，因此，这里只需考虑试题的难度系数和区分度对试卷的影响即可，所以暂定个体的初始适应度函数F1由试卷难度系数与项目区分度两个约束条件组成，假设他们对试卷的影响权重是相同的，则F1可以用公式3-1表示。
　　（3-1）
　　4.选择操作
　　所谓的选择操作其实就是优胜劣汰的过程，算法根据个体的适应度值，选择优良的个体保留下来，进行下一代遗传。而在这一过程中，算法对选择算子的要求是要适中，因为如果算法选择的强度过大，即直接遗传到下一代个体很多，导致两代种群之间的相识度很大，而多样性差，使得算法很容易陷入局部最优。[9]相反，若选择的强度过小，种群的进化过程就会变得缓慢，影响算法的效率。在选择的过程中，适应性越强的个体被保留并将优秀基因遗传给下一代的概率就越大，符合优胜劣汰原则。目前常用的选择算子有轮盘赌选择、适应度比例选择、锦标赛选择、排序选择等等。轮盘赌方法，也称适应度比例法，即适应度越高的个体在整个的轮盘中占得比例越大，被选中的概率越高它是目前遗传算法中最常用，也是最经典的选择方法。
　　5.交叉操作
　　所谓交叉操作是指父代的两个个体经过交换基因片段产生新个体的过程。这个过程中最重要的两个操作就是交叉概率和交叉位置的选择。传统的遗传算法采用恒定的交叉概率，但是这种方法导致算法的效率非常低，失去了遗传算法的优点。并且容易在遗传的过程中发生“早熟”的现象。所谓“早熟”现象，是指在种群中出现了一些超级个体，而这些个体中的基因片段将会随着演化过程的进行在种群中占据统治地位，使算法容易陷入局部最优。因此，交叉概率对算法的收敛速度有直接的影响。[10]
　　本文中的遗传算法汲取了上述经验，采用了随个体适应度变化的交叉概率。当群体的个体适应度值趋于一致或趋于局部最优时，增大交叉概率；当群体适应度值比较分散时，减小交叉概率。同时对适应度低的个体使用较低的交叉概率，而对适应度高的个体给予高的交叉概率，这样有助于优秀的个体（低适应度）下来，而不优秀的个体（高适应度）被淘汰。这种方法既保持了群体的多样性，又保证了遗传算法的收敛能力，能够有效地避免“早熟”现象的发生，同时提高算法全局寻优的效率。[11]
　　6.变异操作
　　在遗传算法中，变异概率一般较小。本文中的变异操作是针对某个基因点进行变异，而非上述过程的基因段。其具体操作过程分为两个步骤，第一步决定染色体是否变异，第二步决定变异的位置。[12]
　　7.算法终止条件
　　遗传算法的终止条件一般包含以下几种：
　　7.1当某一代产生的最优个体完全满足组卷的约束条件或满足用户设定的组卷条件时，算法终止；
　　7.2当前连续几代的最优个体适应度值不再发生变化或者变化不大（相差很小）时，说明当前个体已经非常接近最优，进化出现停滞，终止算法；
　　7.3达到指定的进化代数，算法终止。
　　四、小结
　　本文对智能组卷基本问题和一些常用组卷算法进行了介绍，然后介绍了遗传算法的基本思想和运算流程，并对遗传算法在组卷问题中的应用进行了详细的叙述。并根据这个思想针对智能组卷问题进行了详细的算法设计和实现。对教师的教学和学生的学习均有很大的帮助作用。但仍存在一些问题，如考试的评分标准的同一性与权威性等问题仍需改进，希望日后能设计出符合类似考试的统一的评价体系。
　　参考文献
　　[1]吴泽晖.基于 ASP 开发的网上组卷考试系统[J].微型机与应用，2000，19（9）： 51-53.
　　[2]金汉均，郑世迁，吴明武.分段随机抽选法在智能组卷中的研究与应用[J].计算机应用研究，2003，20（9）：102-103.
　　[3]张国才，徐效美.基于分割策略的快速抽题组卷算法.微计算机应用[J]，2003，24（4）：197-199.
　　[4]赵加江.基于改进遗传算法的自动组卷研究：[D].辽宁：辽宁工程技术大学.2010.
　　[5]葛宪强 基于十进制编码遗传算法的试卷生成系统设计：[D].上海：华东师范大学 2009.
　　[6]闭应洲，苏德富，陈宁江.基于矩阵编码的遗传算法及其在智能组卷中的应用[J].计算机工程，2003，29（6）：73-75.
　　[7]吴树锦.基于遗传算法智能组卷系统的研究与实现[D].上海：华东师范大学，2008.
　　[8]袁鑫攀.基于自适应遗传算法的智能考试系统研究[D].湖南：中南大学，2008.
　　[9]朱剑冰，李战怀，赵娜.基于混合遗传算法的自动组卷问题的研究[J].计算机仿真，2009（5）：328-331.
　　[10]于淼，王日宏.改进遗传算法在自动组卷中的应用研究[J].计算机工程与应用，2008.25：236-238.
　　[11]魏平，熊伟洁.用遗传算法解组卷问题的设计与实现[J].微电子学与计算机，2002（4）：48-50.
　　[12] 吉根林.遗传算法研究综述.计算机应用与软件.2004，18（2）：20-30
　　作者简介：刘培艳（1987-），女，汉族，河北省沧州市，理学硕士，助教，研究方向为计算机辅助教育，远程教育。
转载注明来源:https://www.xzbu.com/4/view-11718112.htm