论文摘要：自动组卷系统是计算机辅助教学的重要组成部分，而遗传算法以其全局寻优和智能搜索的特性，得到了广泛的运用。根据自动组卷系统的特点，将遗传算法合理应用于自动组卷中，在遗传算法中，设计了双种群机制，并以试卷难度、试卷区分度、试卷的估计用时、知识点分布为基础构造适应度函数，通过轮盘赌选择方法、多点交叉和变异，较好地解决了自动组卷的多重目标寻优问题。

关键词：自动组卷；遗传算法；适应度函数
　　中图分类号：TP312文献标识码：A文章编号：16727800（2013）004005203

0引言
　　考试是教学过程中的一个重要环节，我们用它来检测教学效果，以期提高教学质量。传统的手工方式，都是以教师的经验与知识的积累为依据出题，带有一定的主观性，考试命题质量和科学性不能保证。另外，对于有些课程，我们希望平时能够在计算机机房通过上机完成测验。所以，伴随人工智能的广泛应用，自动组卷技术成为我们必须深入探讨的一个课题。现有不少自动组卷系统，但其算法存在时间复杂度和空间复杂度偏大、程序结构复杂、试题缺乏随机性等缺陷。将遗传算法应用于自动组卷系统中，并将试卷难度、试卷区分度、试卷的估计用时、知识点分布作为综合优化目标，对上述缺陷作出了改进。

1基于遗传算法的自动组卷算法设计
　　遗传算法的操作步骤为编码、随机产生初始种群、构建适应度函数、对初始种群迭代执行选择、交叉、变异等遗传操作产生下一代种群，获取最优解、解码。本自动组卷算法设计如下。
　　1.1编码设计
　　整数编码直接采用解空间的形式进行编码，意义明确，易于引入特定领域的信息，而且能大大缩短串长，遗传操作无须频繁地编码、解码，改善了遗传算法的计算复杂性，提高了算法效率。本算法采用整数编码将现实问题映射到染色体即个体形式。
　　实现时，按试卷的题型对个体进行分段编码。比如试卷由L种题型的试题组成，则染色体编码划分成L个子段，每个子段对应一种题型。每个子段中基因个数为该题型要求的题目个数。
　　试题库中每道题目，都有一个编号与其对应。比如现在生成了两张试卷个体ExaPaper1、ExaPaper2。分别由选择、填空、判断、问答、综合5道题组成。该试卷个体形式如表1、表2所示。
　　1.2产生两个初始种群
　　在初始种群产生时，应采用某种算法，使优秀、中等的、劣质的个体基本同概率存在。以保证初始种群产生的多样性和分布均匀性。并且采用产生2个初始种群的方法，同时对解空间内多个区域进行搜索，并互相交流信息。这种设置方法，虽然每次需执行与种群规模n成2倍的计算量，但实质上可进行大约O（n＼+3）个解的有效搜索。因此，这种2种群的设置方法，成本虽提高一倍，效率则以指数形式上升。
　　实现时，本算法采用随机的方法产生320个个体，将他们分为40个子空间，则每个子空间中有8个个体。然后从每个子空间中随机获取5个个体，这样就形成了200个个体，对这200个个体再随机划分到两个初始种群中。
　　1.3构造适应度函数
　　一份卷子设计是否合理，通常从3个方面考察：第一，题型比例配置是否适当；第二，题目难、中、易比例是否合理；第三，干扰项是否有效，能不能反映考生的典型错误。本算法将试卷难度、试卷区分度、试卷的估计用时、知识点分布4个目标作为综合优化目标，因此也将其作为构造适应度函数的主要依据。适应度函数的构造过程为，首先以各目标为基础分别构造各自的目标函数，然后使用加权的方法对各目标函数进行组合获得适应度函数。
　　1.3.1各目标函数构造
　　（1）试卷难度目标函数。
　　针对不同的考生，试卷难度要求也不同，因此将试卷难度作为构造适应度函数的一个依据。试卷难度目标函数构造如式（1）所示。
　　Fc（X）=1-1[]total_score∑N[]i=1fc（i）*p（i）-Exp_Difficulty（1）
　　其中，X为种群中个体，N为X的长度，i表示X中第i个位置。对应到自动组卷中，N为题目的个数，total_score为试卷的总分，i表示X这份试卷中第几道题目。f＼-c（i）为i这道题目对应的难易度，p（i）为这道题目对应的分值。Exp_Difficulty为对试卷的难度期望值。由此可知，F＼-c（X）值越大，说明试卷难度符合要求的可能性越大。
　　（2）试卷区分度目标函数、试卷估计用时目标函数。
　　区分度是指试题对被试者情况的分辨能力的大小。区分度适当的试卷能把优秀、一般、差三个层次的学生真正区分开。试卷区分度目标函数、试卷估计用时目标函数构造方法与试卷难度目标函数构造方法类似。试卷区分度目标函数构造如式（2）所示。
　　Fd（X）=1-1[]total_score∑N[]i=1fd（i）*p（i）-Exp_Difficulty（2）
　　其中，X为种群中个体，N为X的长度，i表示X中第i个位置。对应到自动组卷中，N为题目的个数，f＼-d（i）为i这道题目对应的区分度，p（i）为这道题目对应的分值。total_score为试卷总分值。Exp_Different为对试卷的区分度的望值。由此可知，F＼-d（X）值越大，说明试卷难度符合要求的可能性越大。
　　试卷估计用时目标函数构造如式（3）、式（4）所示。
　　Ft（X）=T（X）T（X）<11[]T（X）T（X）>1（3）
　　T（X）=∑N[]i=1ft（i）[]Exp_Time（4）
　　其中，X为种群中个体，N为X的长度i表示X中第i个位置。对应到自动组卷中，N为题目的个数，f＼-t（i）为完成i这道题目的期望时间。Exp_Time为完成本试卷估计用时的期望值。由此可知，F＼-t（X）值越大，说明试卷难度符合要求的可能性越大。
　　（3）知识点分布目标函数。
　　教学大纲中，对不同章节知识点的掌握程度要求也不同。因此，设计知识点分布目标函数，用来把握考察的知识点是否全面合理。
　　知识点分布目标函数构造如式（5）、式（6）所示。
　　Fn（X）=（∑M[]j=1fw（j）*∑N[]i=1Fs（i））/total_score（5）
　　Fs（i）=fs（i）第i题目属于第j章内容0第i题目不属于第j章内容（6）
　　其中，X为种群中个体，N为X的长度，i表示X中第i个位置。对应到自动组卷中，M为本试卷要考察到的章节总数。fw（j）为课本第j章在试卷中占用的权重。N为题目的个数，fs（j）为第i题目的分值。若第i题目是第j章节的内容，F＼-s（i）才存储f＼-s（i）的值，以便参与实际试卷中第j章节权重的计算。total_score为试卷总分值。由此可知，F＼-n（X）值越大，说明试卷难度符合要求的可能性越大。
　　1.3.2适应度函数构造
　　使用加权的方法对各目标函数进行组合，形成适应度函数。适应度函数如式（7）所示：
　　F（X）=1Fc（X）+2Fd（X）+3Ft（X）+4Fn（X）（7）
　　其中，F＼-c（X）、F＼-d（X）、F＼-t（X）、F＼-n（X）分别为试卷难度、试卷区分度、试卷的估计用时、知识点分布的目标函数。1、2、3、4分别为试卷难度、试卷区分度、试卷的估计用时、知识点分布目标函数的权值。并且1+2+3+4=1。权值1、2、3、4的取值应依据具体试卷考核目标而定。
　　1.4遗传操作
　　1.4.1选择操作设计
　　在本算法中，应用轮盘赌选择方法进行选择操作，决定将哪些个体复制到新种群中。并进一步根据适应度值对t+1代和t代种群最优个体进行比较及选取，确保在t+1种群中，最优个体的适应度并不低于t种群的最优个体适应度。
　　1.4.2交叉操作设计
　　本文使用多点交叉操作。针对两个个体即两份试卷中的选择、填空、判断、问答、综合5类题型，分别进行20%的基因点交叉。比如假设生成了表3、表4所示两份试题。黑边框处为交叉点。交叉操作后，试卷1、卷2转换为表5、表6所示内容。
　　1.4.3变异操作设计
　　变异操作为对群体中某些个体的基因进行小概率扰动。本变异的操作如下：以题型为基础，将个体分段，每段随机选择一个变异位置，并从同题型题库中随机选择一个题目替换该变异位置题目，条件是新选的题目不能与当前试卷中同题型其它题目重复。比如试卷一变异操作前如表7、表8所示，变异操作后结果如表9、表10所示。
　　1.4.4种群竞争设计
　　本算法采用产生2个初始种群的方法，同时对解空间内多个区域进行搜索，并互相交流信息。种群竞争的具体设计思想为：对两个初始种群K11、K21分别进行遗传操作产生新的种群，各经过T代（不同问题T的设定不同）后，获取到新种群K1T、K2T。将K1T、K2T两个种群中个体合并，按适应度排序。前一半个体形成新的K1T种群，后一半个体形成新的K2T种群。将新K1T、K2T再反复执行上述过程，直到满足终止条件时进化结束。本算法的终止条件是当达到规定的最大迭代次数HMAX或者最好个体的适应度函数值HMAX/5次达到了要求。
　　1.5选择最优解及解码
　　通过遗传算法最终可获得一组个体，对这组个体分别计算适应度值，获取适应度最优的个体，作为最终解。因为是整数编码，个体中基因值即为题库中被选中题的题号。因此，从最优个体可直接得到最终生成的试卷。

2结语
　　本文围绕自动组卷存在的问题，重点研究了遗传算法的改进及其在自动组卷算法中的应用。通过运行基于该遗传算法的组卷程序，证明了该设计的可行性、有效性。

参考文献：
　　[1]黎军.基于遗传算法的自动组卷设计[J].发表于  电脑学习，2009（3）.
　　[2]陈国良，王煦法，庄镇.遗传算法及其应用[M].北京：人民邮电出版社，1996.
　　[3]张超群，郑建国，钱洁.遗传算法编码方式比较[J].发表于  计算机应用，2011（3）.
　　[4]丁承层，强传生，张辉.遗传算法纵横谈[J].发表于  信息与控制，1997（1）.