商俊燕（常州轻工职业技术学院）
摘要：试题组卷是考试系统的重要组成部分。通过在编码策略、适应度函数、遗传算子、控制参数等方面的研究提出一种适应于试题智能组卷的改进遗传算法。对适应度函数的适当定标和建立自适应的交叉概率和变异概率，有利于克服未成熟收敛现象，同时能在维持群体多样性的情况下，防止群体进入局部最优。
关键词：改进遗传算法智能组卷适应度函数
中图分类号：TP311
文献标识码：A
0引言
随着计算机技术的飞速发展，传统的考试方式正逐步向利用计算机的在线考试的方式过渡。在线考试系统中，组卷的方法是其中的关键技术。当前计算机考试中常用的组卷算法有随机组卷法和回溯试探法。随机选取法是利用计算机提供的随机函数或随机量，根据组卷状态空间的控制指标，不断抽取符合控制指标的试题放入试卷中，直到组卷成功，或再也无法从题库中抽取满足控制指标的试题为止。这种算法对于单个实体的抽取速度快，但对于整个组卷过程来说组卷成功率较低，花费时间长。回溯试探法是将随机选取法产生的每一状态都记录下来，当搜索失败时释放上次记录的类型，然后再依据一定的规律(正是这种规律破坏了选取试题的随机性)变换一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成完毕或退回出发点为止，这种有条件的深度优先法，对于状态类型和出题量都较小的题库系统而言，组卷成功率较好。但是在实际到一个应用时发现这种算法对内存的占用量大，程序结构相对比较复杂，而且选取试题缺乏随机性，组卷时间长，因此它不是一种很好的用来自动组卷的算法。这两种算法都存在很大缺陷，有些用户是无法接受的，因此不是很好的组卷算法
1组卷问题的数学模型
智能组卷就是要在题库中根据约束条件生成满足教学和教师要求的试卷，因此，除了题目内容本身以外，试题还需要其他的属性，比如：试题的编号、题型、知识点、教学要求、难度、区分度、使用频度、最近试题使用时间和答题时间等。根据这些属性，组卷系统的数学模型如下：其中n表示一份试卷中试题的数量
A的第i行元素的意思表示为第i个题的题号ai1，题分ai2，题型ai3，知识点ai4，教学要求ai5，难度ai6，区分度ai7，使用频度ai8，答题时间ai9
2智能组卷问题的算法设计
2.1算法描述改进遗传算法是基于标准遗传算法的，它是将一种自然选择和遗传理论为基础，将生物进化过程中适者生存规则和种群内部染色体的随机信息交换机制结合的优化搜索算法。与标准遗传算法相比，改进遗传算法中采用实数编码和自适应的交叉概率和变异概率，可以改善遗传算法的局部搜索效率较差、可能出现早熟等缺点。
改进遗传算法的一般过程为：①染色体编码；②初始化群体；③个体评价；④终止；⑤遗传操作；⑥跳转到步骤③
2.2改进遗传算法设计
针对智能组卷问题，给出相应的算法步骤如下：
步骤1染色体编码
染色体编码采用分组实数编码，即将染色体映射为一个染色体，组成试卷的基因就是各个试题，而基因的值直接用试题的题号表示。同一种题型放在一起，如要组成一份由选择题、填空题、名词解释题、简答题和案例分析题组成的《电子商务实务》试卷，采用染色体分组编码
步骤2初始化群体
为了加快遗传算法的收敛并减少迭代次数，初始化种群不采用完全随机算法生成，而是根据题型比例、总分等要求随机产生，使得初始种群已经满足了题型和总分的要求。
步骤3个体评价
计算每个个体的适应度值f（x），f（x）越高表示个体适应度值越高，对环境的适应能力就越强，则被选择繁殖后代的可能性就越高。在本文中使用的适应度函数采用
标与用户要求的误差绝对值，wi表示第个指标对组卷重要程度的权值，n表示参数指标的个数，f是所有参数指标与用户要求的误差绝对值之和。
步骤4终止判断
终止条件有3个：第一，当搜索到最优解时；第二，当运行次数达到设定的对答代数时；第三，当最新最大适应度值与上代的最大适应度值相差不大时。
步骤5遗传操作
①选择操作为了保证搜索达到的最佳个体不会被各种遗传操作破坏，能保留上代群体中的优良个体，多采用的算法把上代群体全部复制并保留到临时池中。这是一种允许父代参加竞争的方式。这种操作有利于保持群体的多样性，避免“早熟”现象。具体做法：对临时池中除最优解以外的其他个体进行两两竞争。从池中随机选择两个个体，比较它们的适应之，把适应值较大的个体保留到子代，直到产生完整的子代群体为止。
②自适应交叉操作交叉操作在两个个体的各个相同题型段内进行。交叉概率采用自适应方式产生，采用这种方式不但在进化后期表现良好，而且在进化初期提高群体中表现优良个体的交叉率，使得他们不会出于一种停滞不前的状态，降低进化走向局部最优解的可能性。
其中，fmax为群体中最大的适应值，favg为每代群体的平均适应度值，f'为待交叉的两个个体中的较大的适应值，Pc1=0.9，Pc2=0.6
③自适应变异操作变异采用段内单位置替换方式变异，即在个体的各个不同题型段内随机选择一位进行替换，且规定该位被替换后的题号不能与该个体的其他位题号重复。变异概率采用自适应变异概率，使变异在进化初期和后期都有很好的表现。
其中，fmax为群体中最大的适应值，favg为每代群体的平均适应度值，f'为待交叉的两个个体中的较大的适应值，f为待变异个体的适应度值，fm1=0.1，fm2=0.001
3实验结果与分析
为验证该算法的可行性和有效性，对《电子商务实务》题库，利用ASP环境编制了程序，进行组卷实验。本实验题库中共700道试题。遗传算法参数为：种群规模N=50，最大代数=500。给定的组卷要求：总分为100分，考试时间为120分钟。
在试题库较大，且分布合理，组卷约束条件较多的情况下，改进遗传算法和回溯试探法都有较高的组卷成功率，而随机法常常由于约束条件的局部满足而导致组卷失败，所以组卷成功率较低。
4结束语
智能组卷问题是典型的约束组合优化问题，本文针对该问题，研究了一个基于整数编码的改进遗传算法，该算法搜索速度快，能避免了标准遗传算法中经常出现的“早熟现象”，具有很好的性能和实用性。
本文作者创新点：提出了一种基于改进遗传算法的组卷方法，采用分段实数编码方法和自适应遗传算子，从而使得组卷效率更高。
参考文献：
[1]王小平，曹立明.遗传算法-理论、应用于软件实现[M].西安：西安交通大学出版社.2002.
[2]高玮.改进的快速遗传算法及其性能研究[J].系统工程与电子技术，2003.25（11）：1428-1430.
[3]李敏强，寇记淞，林丹等.遗传算法的基本理论与应用[M].北京：科学出版社.2003.
[4]姚文俊.遗传算法及其研究进展[J].计算机与数学工程，2004，32（4）：41-43.