摘  要： 针对遗传算法组卷易陷入早熟、难以收敛的问题进行研究，结合进化环境对进化过程的影响和引导，对动态进化环境进行建模，提出了一种基于动态变异池的策略。该策略的种群不共享变异池，在每次变异前，根据每个个体的弱点动态生成该个体的变异基因库，以此改善当前变异环境，实施引导性变异，提高解质量。该策略能加速收敛，并在很大程度上提高收敛精度。实验数据表明，采用了该策略的组卷算法能快速生成各项指标都与约束条件十分贴近的试卷，具有很好的实用价值。

　　关键词： 组卷；进化环境；遗传算法；动态变异池；收敛精度；题库系统

0 引言

　　随着信息技术的不断发展应用，考试模式将面临着巨大的变化。在线学习、考试系统层出不穷，如何自动实时地从题库中随机抽取合适的试题是这类系统要解决的首要问题，同时这也是一个多约束的NP难题。目前常用的组卷方法主要有随机抽取法、回溯试探法、最大权法和遗传算法[1-6]。其中，遗传算法[7-8]因其内在并行性和全局寻优能力被广泛应用于传统搜索方法难于解决的非线性、多约束等复杂问题。

　　然而，实际应用中发现，遗传算法生成试卷经常会出现早熟、收敛慢等问题，特别是当试卷约束较复杂时，算法会更加难以收敛，其结果往往是生成试卷的时间长、与客户要求的偏差大等。为解决这些问题，本文对动态进化环境进行设计和建模，提出了一种称为动态变异池的策略，该策略一方面监测试卷性能指标；另一方面根据试卷性能指标监测结果，结合客户偏好，为每个个体生成不同的变异池实施引导性变异。实验表明，动态变异池策略能加速收敛，提高收敛精度，生成满意度比较高的试卷。

1 遗传算法解组卷问题

　　1.1 编码设计

　　采用分题型段编码。取题号为染色体基因，一张试卷的题目数量决定了试卷个体的染色体长度。同时对染色体进行分段，一个题型对应一段，段的长度即根据题型约束计算而来的每种题型的题目数量。

　　分题型段编码有以下两点好处：

　　（1）编码长度适中，进化过程快。

　　（2）个体初始即满足题型题量和卷面分约束，这使得试卷个体具有“合法性”，并且这种“合法性”不会被进化操作所打乱，无论如何交叉和变异，个体均能满足题型题量的约束。

　　1.2 适应度函数设计

　　设组卷的题量要求为n，卷面分约束为G。采用分题型段编码后对应的题号分别为m1、m2、m3、…、mn。根据组卷的各项约束参数为每张试卷建立n×6的目标状态矩阵A=[A1 A2 A3 A4 A5 A6]，如式（1）所示，该目标状态矩阵决定着试卷个体的优劣。

　　其中，A1为题目分数指标，A2为课程指标，A3为难度指标，A4为章节指标，A5为知识点指标，A6为已抽过的频度指标。

　　可用式（2）计算第j门课程实际所占比例与理想百分比的误差：

　　其中，IPcj为第j门课程所占试卷总分的理想百分比，ai1为第i道题的分值。如果ai2为第j门课程，则δij为1，否则为0。式（2）还可以用来计算难度约束误差和章节约束误差。可用式（3）来计算试卷是否命中第j号知识点的误差：

　　其中，Nk为总共需要命中的知识点个数；IPkj为j号知识点的理想比例，一般为1/NK。如果ai5为j号知识点，则δij=1，否则δij=0。另外，组卷时，为保障随机性和多样化，尽可能每次能够优先抽取被抽中次数较少的“新鲜”题，可以用式（4）来计算整张试卷的新鲜程度：

　　其中，ai6为mi已被抽中的次数，min和max为题库中的题被抽中最少和最多的次数。设所有误差之和为E，适应度函数可表示为1/（E+1）。如有其他的约束，也可计算之后加入总计误差E中。误差越小，适应值越大，表明试卷个体与理想试卷偏差越小，竞争能力越强。

　　1.3 遗传算子设计

　　采用标准遗传算法的赌轮选择、两点交叉、单点变异和精英保留策略[7]。单点变异时选取与变异位置同题型的题目进行变异替换。值得一提的是，交叉和变异操作可能导致个体出现重题。如下所示，父代个体P1、P2在位置3~7处进行交叉，产生子代个体S1、S2。

　　P1=3 5 |1 6 9 10 12| 15 18 19

　　P2=2 4 |3 7 9 11 10| 13 19 20

　　S1=3 5 |3 7 9 11 10| 15 18 19

　　S2=2 4 |1 6 9 10 12| 13 19 20

　　交叉以后，S1个体出现了重题3，若继续对S2在位置8进行变异，取与13题同题型的12题进行替换，变异后的S2也将出现重题。

　　对于重题现象，一般有两种处理方法：进化操作后检查子代个体是否有重题并进行简单替换[9]；或者放弃本次进化，重新进化[10]。这两种处理方式都将耗费大量时间。本文的处理是在整个进化迭代结束后只对最优解进行重题优化。所谓重题优化是指找到与重题同题型并且各项约束指标最接近的题去替换重题，将去重题操作对个体适应度的影响减到最小。重题优化策略比前两种处理方式更节省进化时间，并且在题库规模越大时优势更明显[11]。

2 动态进化环境建模

　　“孟母三迁”的故事告诉人们环境因素不容忽视，同样，源于生物进化的遗传算法也不能忽视进化环境的影响。组卷问题是一个典型的组合优化问题，其约束很多，若忽略进化环境的引导性作用，进化过程会显得异常缓慢，其结果是出现早熟现象并且最优解的质量无法达标。表现在具体应用上，生成的试卷可能会与用户要求存在严重的偏差，比如某次生成试卷要求某重点章节占总题量的30%，然而实际抽出的题却只占5%，这样一些非重点章节（如选学章节）却抽出了严重过剩的题，这样的偏差是用户无法接受的，考生也无法适应。当组卷约束比较苛刻时，这种偏差会更明显。

　　进化环境对进化过程的影响主要体现在“优胜劣汰”和“基因突变”上，可归结为偏好一词。归根结底，这会指引进化个体产生和保留更好的基因。伴随进化过程的进行，这种偏好也在动态变化着，该如何对动态的偏好信息进行建模，引导进化过程更快地找到缺失基因呢？

　　改进变异算子的研究源于变异算子在进化计算中起主导作用的认识[12]。遗传算法进行组卷具有全局收敛性，但也有一定概率的不稳定性，特别是当组卷约束参数比较复杂和苛刻时，这种不稳定的概率就会增加。造成不稳定性的主要原因之一是有效基因的缺失，变异可有效解决这一问题。

　　目前应用的遗传算法的变异池是通用的，一般直接选取可用题库作为变异池。在组卷约束参数较为复杂时，这种通用变异池就会放慢有效基因恢复的步伐。为此，对变异算子做出改进，在每次变异前先改善当前的变异环境，设计了动态变异池策略，使每次变异都会产生比父辈更优秀的个体。

　　动态变异池的具体建模过程如下：

　　（1）取通用变异池（可用题集）作为旧变异池。

　　（2）根据组卷约束参数计算并记录当前个体严重缺失的基因。具体为：依次取约束参数（如章节约束），计算当前试卷与该类约束各项指标的实际误差，即计算该试卷各章节比例相对于约束参数要求的各章节比例的实际误差，并记录实际误差最大的指标项（章节编号）。

　　（3）重复步骤（2），直至各类约束都计算完毕。

　　（4）生成空的新变异池。

　　（5）根据步骤（2）、（3）中记录的指标项集合，对当前变异池进行优化。依次从旧变异池中挑出属于该指标项的题集加入到新的变异池中。每次挑选不改变旧变异池的内容。

　　（6）重复步骤（5），直至所有指标项都处理完毕，当前试卷“急缺基因库”形成，即当前个体此次变异的新变异池生成。

　　这种每个个体每次变异前都根据个体的缺点重新生成变异池的策略称为动态变异池策略。这样一来，算法的变异池很大程度上引导着变异朝着好的方向进行，从而改进个体质量，加速收敛。

　　需重点说明的是，动态变异池的生成过程中，对旧变异池的每次筛选都不能改变旧变异池的内容，这使得同时具有多个有效基因的题有可能重复进入变异池，增加被选中的概率，即增加了缺失的有效基因进入下一代的概率。实验表明，这能有效强化缺失基因，加大搜索力度和精度。

3 实验

　　对采用通用变异池的遗传算法（算法1）和采用动态变异池的遗传算法（算法2）进行实验对比，两个算法均采用了重题优化策略[11]。数据库总题量为10 977，题型15种，难度级别5个。根据多次实验，算法进化代数设置为2倍题量约束，下限为100，种群规模设置为2倍题量约束，下限为200。表1~表4为两种遗传算法按4组方案运行10次所得的平均性能详细对比。4组方案涉及3门课程，其中课程1（方案1）的题量为  1 773，课程2（方案2）的题量为1 424，课程3（方案3和方案4）的题量为1 811。

　　表中数据表明，算法2对不同的组卷方案都能比算法1更快更好地收敛。特别对较复杂的约束参数，算法2的优势能得到更好的体现。如方案2中出现的知识点包含要求，算法2能比算法1更多地命中，如表2所示。再如方案4中的章节分布约束，由于课程3各章节题目在数据库中存在比例较为均衡，面对组卷过程中常常出现的各章节要求比例偏颇的情况，一般算法很难得到与要求比例很贴近的解，但如表4所示，算法2找到的最优解满意程度很高，不仅章节比例，其他各项指标都与试卷约束参数很贴近，并且效率比算法1好。

　　目前该策略已经集成于主要用于期考出卷的教务助手系统，运行稳定，经统计，50道题最差10 s能完成组卷，100道最差30 s能完成组卷，且抽取试卷质量好，满意度高。

4 结论

　　试卷自动生成问题是一个多约束优化问题，同时也是一个NP难问题，它的约束参数很难用数学形式表达，所以传统算法无法对其求解，遗传算法因其优秀的搜索能力广泛应用于求解这类问题。为克服遗传算法易陷入早熟、难以收敛的问题，本文提出了基于动态变异池的遗传算法，该算法已经集成于教务系统运行，实验数据表明，加入了进化环境和偏好设计的遗传算法具有更好的鲁棒性和收敛性，能更早更好地找到满足条件的最优解，并在很大程度上提高求解精度，加速算法收敛，具有很好的实用价值。

　　基于动态变异池的研究只是基于环境的进化算法的一个小的着眼点，研究更复杂的进化环境从而避免算法陷入局部最优，跳出进化停滞是日后工作一个重要的开展方向。另外，如何一次产生n套高质量的不重复的试卷也是一个重要的后续实验课题。

参考文献

　　[1] 龚完全.基于最小回溯代价的智能组卷算法[D].长沙：湖南大学，2005.

　　[2] 李大辉.基于广度优先回溯算法的试题搜索算法[J].大庆石油学院学报，2006，30（3）：100-102.

　　[3] 金汉均，郑世珏，吴明武.分段随机抽选法在智能组卷中的研究与应用[J].计算机应用研究，2003，20（9）：102-126.

　　[4] Yan Song， Yang Guoxing. Item bank system and the test paper generation algorithm[C]. 2012 7th International Conference on Computer Science & Education（ICCSE）， IEEE， 2012：491-495.

　　[5] 尹常治，杨皓，赵立族.最大权法试卷组卷算法[J].工程图学学报，2004，25（3）：106-110.

　　[6] Huang Wei， Wang Zhaohui. Design of examination paper generating system from item bank by using genetic algorithm[C]. International Conference on Computer Science and Software Engineering（CSSE）， Wuhan， 2008：1323-1325.

　　[7] 陈国良，王煦法，庄镇泉，等.遗传算法及其应用[M].北京：人民邮电出版社，1996.

　　[8] 郑金华.多目标进化算法及其应用[M].北京：科学出版社，2007.

　　[9] 黄宝玲.自适应遗传算法在智能组卷中的应用[J].计算机工程，2011，14（37）：161-163.

　　[10] 周艳聪，刘艳柳，顾军华.小生境自适应遗传模拟退火智能组卷策略研究[J].小型微型计算机系统，2011，32（2）：323-327.

　　[11] 肖桂霞，赵武初，朱伟，等.基于遗传算法智能组卷的去重题方法[J].计算机工程，2012，11（38）：150-152.

　　[12] 霍红卫，许进，保铮.选择和变异算子的作用分析[J].电子学报，2000，28（2）：31-34.