分段组卷伪并行遗传算法的研究与实现

方俊

摘 要： 遗传算法组卷存在收敛速度慢和未成熟收敛问题，难以满足考核要求。已有较多算法采用了分段编码、分段进化的策略，以降低算法的复杂度，提高算法的性能，但均未实现分段组卷，没能从根本上提高算法的性能。为此提出分段伪并行组卷的方法，即：分段组成符合要求的试卷段，再组合成一份完整的符合用户需求的试卷。实验证明，该方法能够大大加快收敛速度，提高组卷质量。

关键词： 遗传算法； 适应度； 组卷； 种群多样性； 伪并行

中图分类号：TP181 文献标志码：A 文章编号：1006-8228（2014）07-37-03

Abstract： There exist problems of slow convergence speed and premature convergence in genetic algorithm， making it hard to meet the inspection requirements. Hence the block coding， and segmented evolution strategy are adopted in many algorithms in order to reduce the complexity of the algorithm， and improve the performance of the algorithm. However， none of them can realize composing test paper piecewise. The performance of the algorithm is failed to fundamentally be improved. To solve the above problems， a method of pseudo-parallel group volume is proposed. Test paper is composed individually， and assembled into a complete test paper. It meets the demand of the users. Experiments show that this method can greatly speed up the convergence and improve the quality of composing test paper.

Key words： genetic algorithm； fitness value； composing test paper； diversity of population； pseudo-parallel

0 引言

随着人工智能技术的发展，出现了基于智能的计算机辅助教学系统。智能组卷是智能计算机辅助教学系统的重要组成部分，它的研究目的是使计算机代替人工出卷。能否快速地组成科学的、合理的和具有随机性的高质量试卷取决于组卷算法的设计。20世纪80年代中后期，国内外研究者根据组卷问题的特点进行了组卷算法的研究，相继产生了多种组卷方法。其中具有代表性的有随机抽题法、回溯试探法和遗传算法等[1]。①随机抽题法是根据组卷时定义的控制指标，不断从试题库中随机选取试题加入试卷中，直到组卷完成。该方法简单，单次运行速度快，但成功率低。②回溯试探法的基本思想：判断随机抽取的试题是否满足指定的约束条件，当满足约束条件时继续向前搜索，并保存待生成试卷的状态空间。当组卷失败时，则返回上次记录，再按照预定策略进行新的搜索试探，直到生成试卷或回到出发点为止。该方法组卷耗时长，且内存空间占用量也较大。③遗传算法作为一种优秀的算法，已在很多领域得到应用，与传统的搜索算法不同，它是模仿自然选择和遗传进化过程来搜索最优解，特别适于处理传统的搜索方法无法解决的复杂问题和非线性问题。智能组卷是一种多目标约束问题[2]，受多种因素的影响，如总分、题型，每种题型的题量，每种题型所占的分值、时间、难度、区分度等，但遗传算法利用适应度值来指导搜索方向，使得采用遗传算法解决多目标约束的组卷问题具有明显的应用优势。它具有所组试卷随机性强，质量高的特点，但由于约束条件多，易出现未成熟收敛和收敛慢，多个目标方向在收敛速度上存在不一致的现象，容易向一个方向上侧重。在采用遗传算法进行组卷时，较多算法采用了分段编码、分段进化的策略[3-4]，以降低算法的复杂度，提高算法的性能，但并未实现分段组卷，没能从根本上提高算法的性能。本文提出分段伪并行组卷的方法，即按题型分段成子群体，各子群体独立进行遗传进化。按题型组成符合要求的试卷段，再将其组合成一份完整的符合用户需求的试卷。由于各子群体的进化计算是在同一台计算机上串行进行的，所以称为伪并行遗传算法。该算法由于简化了关系，使得进化速度明显提高，只需经过几代进化即可取得符合用户要求的试卷，而且精度也有较大的提高。

1 试题的属性与试卷的约束条件

1.1 试题的属性

1.2 试卷的约束条件

一份试卷往往要求同时满足多个约束条件，但过多的约束条件增加了组卷的难度。本文采用分段伪并行组卷的方法，要求按题型分段组卷，按段组成满足要求的试卷段，再组合成一份符合用户要求的试卷。试卷及各段必须满足下面的约束条件。

⑴ 试卷总分要求：试卷的各试题的分值之和与用户设定的试卷总分相等。

⑵ 试卷难度要求：试卷的各段、整份试卷的难度值与用户设定的试卷难度值相等。

⑶ 试卷区分度要求：试卷的各段、整份试卷的区分度值与用户设定的试卷区分度值相等。

⑷ 考试时间：整份试卷的各试题的答题用时之和与用户设定的试卷时长相等。

⑸ 各题型题量：各题型中的题目数量与用户设定的每种题型的题目数量相等。

⑹ 各题型所占的分值：各题型所占的分值与用户设定的每种题型占试卷总分值的百分比相等。

⑺ 各题型答题用时：各题型答题用时与用户设定的每种题型答题用时相等。

2 分段组卷伪并行遗传算法

对于分段组卷伪并行遗传算法，给出相应的算法步骤。

步骤1 染色体编码及种群初始化

编码是应用遗传算法时首先需要解决的问题，对于组卷来说常用编码的有两种，基于二进制的编码[5]和基于实数的编码[6]。与实数编码相比， 二进制编码的搜索效率更高，且二进制编码具有操作简单易行，交叉、变异便于实现的特点，故本文采用二进制编码的方式。编码按题型分段进行，假设题库中某一题型共有m道试题，则可用一个m位的二进制串来表示，如果其中的题目被选中，则用“1”表示，未被选中，则用“0”表示。

初始化群体采用随机方式产生。通常，种群规模将影响算法的性能，种群设置越大可以提供处理的模式越多，群体中个体多样性越高，可以防止早熟收敛，但会增加计算量；种群设置过小则使遗传算法的搜索空间受到限制，不能提供足够的采样点，一般可通过实验确定。

步骤4 选择运算

选择是采用某一选择策略挑选父代中的优良个体进行复制，以繁殖后代。选择的方法有轮盘赌选择、最优保存策略、确定式采样选择、无回放随机选择、无回放余数随机选择、排序选择、随机联赛选择[9]。本文算法采用基于目标函数值的排序选择方法和最优保存策略。选择运算在各题型段内独自进行，将目标函数值按照从小到大的顺序排列，目标函数值越小，所对应的个体越优良。本文选取前面20%的优良个体直接复制进入下一代。

分段选择运算相对于整条染色体的选择运算具有更高的性能。比如，一条染色体由于某一染色体段的目标函数值偏大就可能被丢弃，不会被复制进入下一代。而分段选择只是将目标函数值大的染色体段淘汰，其他目标函数值小的染色体段将被复制进入下一代，从而减少了无效迭代，能够提高选择运算的效率。

步骤5 交叉运算

交叉操作是遗传算法中最主要的操作，是产生新的优良个体的主要方法。交叉操作要求既不破坏染色体中基因的优良性状，又能有效地产生出一些好的新个体。常用的交叉方式有单点交叉、多点交叉、均匀交叉和算术交叉[9]。本文采用单点交叉，在各自的题型段内，随机选取两个相互配对的染色体段，随机确定交叉点，在交叉点位置后面部分字符串相互交换而形成二个新的染色体段。具体的交叉方式如下。

由于交叉操作后生成的新染色体段中所包含的“1”的个数可能发生改变，为了确保题型段内所包含的题目数与用户设定的一致，因此需要检查字符串中所包含的“1”的个数。这里只检查交叉点后“1”的数目是否改变，如果增加了就随机选择其中的“1”将其反转为“0”，如果减少了就随机选择其中的“0”将其反转为“1”，以保证在题型段内所包含的题目数与用户设定一致。本文采用杂交产生子代60%的新个体。

步骤6 变异运算

遗传算法中的变异算子是生物体进化过程中染色体上的基因位发生突变的现象，它使染色体的结构和性状发生改变。它能改善遗传算法的局部搜索能力和维持群体的多样性，防止出现早熟现象。在遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子，对于二进制编码而言，变异操作就是把某些基因位的值取反[9]。具体是在各题型段内随机确定变异点的位置，将其值取反。如果是“0”变为“1”，则该题型段的题目数量增加了1题，因此需要随机选取其他位置的“1”将其变为“0”以保持该题型的题目数量与用户设定的数量一致。如果是“1”变为“0”，则该题型段的题目数量减少了1题，因此需要随机选取该段其他位置的“0”值将其变为“1”以保持该题型的题目数量与用户设定的数量一致。实际编程可以随机选取一个“1”和一个“0”，再分别变为“0”和“1”，本文采用变异产生子代20%的新个体。

在执行完以上步骤后，返回到第2步骤，对个体进行评价。如果满足终止条件，即可输出结果；如果不满足终止条件，则继续向下执行，循环往复，使各染色体段向最优解方向移动，从而使整条染色体逐渐接近最优解。

3 实验条件和结果

表2数据为本文方法与排序方法的比较，此处的排序算法与本文算法惟一的不同是未采用伪并行的计算策略，其他条件相同。从表2可以看出，组卷50次，采用分段组卷伪并行遗传算法时，在组卷约束条件较多的情况下，本文算法迭代次数明显减少，算法的效率有了较大的提高。

4 结束语

组卷是一个多目标约束问题，由于约束条件多、题量大，用原始遗传算法进行组卷易出现未成熟收敛和收敛速度慢问题。本文给出分段组卷伪并行遗传算法，对于约束条件多的组卷问题，采用分段组成符合要求的试卷段，再组合成一份完整的符合用户需求的试卷，该方法有明显的优势。在进化过程中，利用目标函数值排序的选择方法和最优保存策略，保证了优质个体能够被复制进入下一代。利用较大的杂交、变异概率补充新个体，保持了种群多样性。对在杂交、变异运算过程中所引起的题目数量的变化进行检查，并进行处理，使其与用户设定的数量相等。实验证明，分段伪并行遗传算法能够大大加快收敛速度，提高组卷质量，并可同时生成多份满足要求的试卷。

参考文献：

[1] 彭雪莲.基于多策略改进遗传算法的智能组卷研究[D].广西大学，2010.

[2] 张琨，杨会菊，宋继红，赵学龙.基于遗传算法的自动组卷系统的设计与实现[J].计算机工程与科学，2012.5（34）：178-183

[3] 魏平熊，伟清.用遗传算法解组卷问题的设计与实现[J].微电子学与计算机，2002.4：48-50

[4] 孟朝霞.基于自适应免疫遗传算法的智能组卷[J].计算机工程，2008.34（18）：203-205

[5] 于淼，王日宏.改进遗传算法在智能组卷中的应用[J].计算机工程与应用，2008.44（25）：236-238

[6] 黄宝玲.自适应遗传算法在智能组卷中的应用[J].计算机工程，2011.37（14）.

[7] 饶乐三，王晓柳.教育统计学[M].南京大学出版社，1990.

[8] 鲁萍，王玉英.多约束分级寻优结合预测计算的智能组卷策略[J].计算机应用，2013.33（2）.

[9] 陈国良，王煦法，庄镇泉，王东生.遗传算法及其应用[M].人民邮电出版社，2001.