1、基于遗传算法的试题库组卷研究摘要：组卷问题是一个多重优化约束目标求解问题，使用传统方法解决此种问题较困难，考试题库以及组卷算法的设计决定了组卷的效率和质量。文中提出一种基于遗传算法的组卷方法，给出了初始种群方法，分段编码及交叉算子、变异算子，优化了搜索过程，实验证明求解组卷问题采用该方法行之有效，有利于实现考试的规范化、科学化、教考分离。 关键词：组卷 遗传算法 试题库 计算机辅助测验 中图分类号：TP39 文献标识码：A 文章编号：1007-9416（2014）12-0128-02 Abstract：Test paper construction is a multi-object opti
2、mization restrict problem，it is quite difficultly to solve using traditional mathematics method.The efficiency and the quality completely are decided to tries the question bank design as well as pulls out the topic algorithm the design.This paper puts forward an intelligent algorithm，which optimizes
3、 the search course and adopts the segment code.The experiment proves that the algorithm has practicability.It is a key way to separate the examination from teaching and make the exam more standard. Key Words： test paper construction， Genetic algorithm， item bank， computer assisted testing 计算机辅助测验1（c
4、omputer assisted testing，简称CAT）是现代管理教学中的重要组成部分之一，它综合利用信息和网络技术协助对考生的研习效果进行测验和学习能力评估，并对测验的结果做出相应解析。通常情况下，完善的 CAT 系统是以试题库为基础，包括试题库模块、试卷组合模块、联机测试、考卷批阅、测试分析、成绩管理与总结等。组卷是 CAT 非常重要的一部分，考卷可以全面地反应考生的真实水平，它的质量直接决定了本次考试的有效性。因此，组卷模块是影响 CAT 系统性能指标的重要参考依据。 文中基于遗传算法的基本原理和思想方法，设计了一个组卷算法，能够在较短的时间内生成较高质量的试卷。 1 遗传算法的基
5、本原理 遗传算法2，3的本质可以理解为一种求解问题的高效并行全局搜索方法，它模仿整个群体的学习过程，每个个体都表示既定问题中搜索空间的一个待解点。 首先，需要对问题数据进行抽象，实现从问题到位串的编码映射，初始种群也会从解中随机产生出来。将初始化群体置于遗传算法的执行过程中，依据适者生存的原则，由个体适应度函数值的大小决定出适应环境的个体进行复制，再通过随机选择、交叉和变异等遗传操作过程产生出更适应的下一代种群，使群体逐代地进化到搜索空间中越来越适应环境的区域，直到解趋于收敛，得到最优解为止。2 组卷问题的基本原则 组卷过程中应遵循一些准则，以使产生的试卷能够满足高可信度的测验要求： （1）按
6、设定指标适当配比题目分数以保证组成试卷的效度。 （2）试卷内试题知识点涵盖面较全，数目适当，为确保试卷的可信度，应尽量避免临近知识点试题多次抽取在同一份试卷中。 （3）适当设定试卷的难度，同时使试卷具有较好的区分度，适当地调整试卷的难易程度。 （4）设定卷面的满分值和考试用时，一般的，卷面满分为 100 分，考试用时 2 小时。 （5）适当降低考题抽中率。 3 数学描述 根据文中问题的基本原则和特点，通过分析试卷指标，采用矩阵理论方法，建立问题空间的数学模型。如果各考卷包含 m 道考题，且各题包含 5 个属性，如表 1 所示，可以映射为建构一个 m5 阶的目标矩阵 X，如下所示。其中，m 表示
7、每份试卷题目数，行代表某一道考题，列表示考题的某种属性。 4 组卷算法 4.1 编码方案 文中应用分段自然数编码方法，在此方法中，首先将编码按题型分为三组，每组编码代表一个题型，每个题型的编码方法同样应用自然数编码，也就是在试题库中各题型的题目单独建立试题表，题目均使用自然数编号。按照组卷的需求，在试题库中每个题型都要筛选题目（编号）组成染色体，染色体采用变长编码策略，一个考题就代表染色体中的某一位基因，考卷所含考题的数目就是染色体包含基因的数目，不同题型间的编码都是相对独立的。 试卷包含选择、判断、简答等 3 种题型，每个题型的数目分别为 m1、m2、m3 ，总共 100 道考题，如下所示。
8、 4.2 初始种群 针对组卷问题，初始种群是指从试题库中按照设定的参数随机抽取的考题组成的考卷。设定的初始种群的大小对组卷算法的收敛速度和性能有很大影响，故初始种群的设置一定要合理。文中使用初始试卷的套数作为初始种群，且参与算法的试卷数目设置要合理，因数目过多将减缓算法的收敛速度，过少则对生成最优试卷造成消极影响。设初始群体大小为 100，从题库中分别随机抽取考题，构成100 套初始试卷，并计算它们的适应度值。 4.3 适应度函数 本文适应度函数设计如下： 其中， ， 。 U（0U1）代表每个约束条件分属权重，|sMi| 代表考卷中难度为 i 的考题分值总和同第 i 种设定难度的分值Mi 的偏
9、差值的绝对值；|sNj|表示考卷中第 j 个知识点的考题的分值总和同第 j 种设定知识点的数值 Ni 的偏差的绝对值；|sQh|表示考卷中第 h 种考题要求度的分数总和与第 h种设定要求度的数值 Qh 的偏差的绝对值。 4.4 选择算子 选择操作的作用是确定下一步要进行交叉和变异操作的个体，通常情况下，由适应度函数值的高低来决定要使用哪些优良个体。文中使用轮盘赌选择方法4，算子描述：（1）分别计算当前考卷群体中各个考卷的适应度函数值，分别得到累计值 Ki，以及最末一个累计值 Kn； （2）在区间0，Kn产生一个随机数 X； （3）分别将 Ki 与 X 做对比，当产生第一个 KiX 的考卷 i
10、时，即作为复制对象； （4）重复操作上述两步，直到满足所需个体数目为止。4.5 交叉算子 文中应用分段单点交叉策略：不同题型在各自的编码段内随机设定交叉点，实现交叉时，对其附近的某些基因进行交换。依据基本遗传算法的应用经验，交叉概率 Qc 常在 0.5-0.8 间选取，按此 Qc 值，在群体中抽出 M（M=Qc群体规模 N）个适应度值较高的个体组成一个群体。随机选出试卷 S1 和 P1 配对，并在各段中均随机生成一个交叉点，各段逐一交换对应基因位上的基因，产生一对新的个体 S2 和 P2。新考卷个体 S2 和 P2 在段内可能出现相同考题，但并不调整每个题型数目，此时需将重复的试题编号替换成此
11、段中未出现过的编号。操作方法是：产生一个范围为 1-K 的随机数 i，判断其是否与考卷中同类型题号相同，如果相同则继续随机抽取，不相同则替换掉重复出现的题号。如图 1 所示。 4.6 变异算子 针对编码特点，文中将变异算子 Hm 的操作转换为对新试题的搜索和替换，以确保变异后的编号未超出指定范围。具体的变异操作如下： （l）设 nMax 作为考卷考题数目，变异操作前将当前查找新考题的次数 N=0。 （2）在区间0，1内随机生成实数 J，若 J 不小于Hm，该位基因不变；否则，产生一个随机数用来标记变异基因的位置，由此位置判断归属题型。开始在题库中搜索新试题，如搜索成功，则将新题号替换掉该基因的
12、值，如失败则继续。 （3）搜索次数 N 增 1，如 NnMax，则停止搜索，该基因位保持不变。 （4）判断新搜索试题所在章节是否在本次考试范围内，如不是，重复第三步；判断新题号与已有题号是否一致，如是，重复第三步。 （5）将原染色体基因替换为新试题编号。 变异操作如图 2 所示。 如上所示，随机生成一个实数 J，因大于 Hm，随机数指出变异的基因位在箭头所指处，此位置位于判断题型内，在判断题范围内随机生成一个整数 88 当做新考题编号，在父个体判断题段编码串中没有 88，将原基因位上的编号 35用 88 代替，变异操作完成。 5 结果分析 为证实文中方法的有效性和可操作性，在.NET 环境下采
13、用 C#语言实现了该程序，完成组卷试验。本次实验有选择、判断、简答等题型，共 1000 道试题，各题 2 分，分属7 章。题库中难度分布如下，容易试题 100 道，难度系数0.85-1.0，较易试题 240 道，难度系数 0.76-0.85，中等试题330 道，难度系数 0.66-0.75，较难试题 250 道，难度系数0.56-0.65，难试题 110 道，难度系数 0.0-0.55。程序运行前需设置参数包括群体规模、变异概率、难度系数、最大迭代次数、交叉概率。试卷满分为 100，期望平均得分为85。 实验证实，当设置的参数适当，群体规模 M 取 100，变异概率 Hm 在 0.01-0.0
14、2 之间，交叉概率 Pc 在 0.5-0.6 之间，平均迭代次数 70 次，此时组卷效果较好。 6 结语 本文采用分段编码方法在组卷问题中实现了遗传算法，能够更好的反映实际组卷情况，相应的采用段交叉算子和段内变异算子，恰当的适应度函数比较好的解决了组卷问题，不仅提高了搜索效率，也可以使种群较快地收敛于全局最优解。应用分段编码方式不需在进化过程中控制题型和题目数量，问题求解难度得到了显著降低。实践说明，采用遗传算法解决组卷问题可以得到良好的组卷效果。 参考文献 1马宗梅.遗传算法在考试系统组卷中的应用与研究D.郑州：郑州大学，2009. 2孙凤喜.基于遗传算法的智能组卷系统的设计与实现D.石家庄：河北科技大学，2013. 3李会民，张仁津，马桂英.基于遗传算法的交规考试自动组卷方法研究J.计算机工程与设计，2009：4333-4335. 4韩蕾.基于遗传算法的自动组卷系统的研究与实现D.青岛：中国海洋大学，2010.
