基于遗传算法的试题库自动组卷问题的研究

文章编号 :1671 - 3559(2004) 03 - 0228 - 04收稿日期 :2004 - 03 - 22基金项目 :国家 863 计划资助项目 (863 - 306 - 01 - 4) ;山东省自然科学基金资助项目 (者简介 :杨青 (1972 - ) ,女 ,山东济南人 ,山东公安专科学校基础部讲师 ,硕士。基于遗传算法的试题库自动组卷问题的研究杨 青(山东公安专科学校 基础部 ,山东 济南 250014)摘 要 :给出了利用遗传算法求解试题库自动组卷问题的新方法 ,讨论了运用遗传算法求解在一定约束条件下的多目标参数优化问题 ,提出了功能块的概念 ,并采用了新的编码方式、交叉算子和变异算子。实验结果表明 ,改进的遗传算法相对于其他算法更能有效的解决自动组卷问题 ,具有较好的使用性能和实用性。关键词 :遗传算法 ;自动组卷 ;功能块 ;试题库中图分类号 :6 文献标识码 :由计算机自动从试题库中选择试题 ,组成一份符合要求的试卷。它是计算机辅助教学系统 (的重要组成部分。常用的自动组卷方法大致可分为两类 : (1) 随机抽取法 1 ,即根据组卷状态空间的控制指标 ,由计算机随机抽取一道符合控制指标的试题放入组卷题库 ,此过程不断重复 ,直到组卷完毕或已无法从题库中抽取满足控制指标的试题为止。该方法结构简单 ,具有很大的随意性和不确定性 ,无法从整体上把握题库不断变化的要求 ,不具有智能性。 (2)回溯试探法 ,即将随机抽取法产生的每一状态类型记录下来 ,当搜索失败时释放上次记录的状态类型。然后再按照一定的规律变换一种新的状态类型进行试探 ,通过不断的回溯试探直到试卷生成完毕或退回到出发点为止 ,文献 2 就是使用回溯方法实现自动组卷。实践证明 ,该方法适用于类型和出题量都比较小的题库系统 ,实际应用时程序结构相对复杂 ,而且选取试题随机性差 ,组卷时间长。对于现在越来越流行的考生随机即时调题的考试过程来说 ,它已不符合要求。本文中给出了利用遗传算法求解自动组卷问题的新思路 ,讨论了运用遗传算法求解在一定约束条件下的多目标参数优化问题 ,提出了功能块的概念 ,并采用了新的编码方式、交叉算子和变异算子。最后采用国际上目前评价遗传算法性能的惯用方法 ,对几个实例给出了计算机模拟实验结果。该结果表明新算法求解组卷问题具有简单、通用、收敛速度快、适于并行处理等特点 ,这些都适于试题库自动组卷问题。1 组卷问题在智能教学系统中 ,一个非常重要的课题是怎样在已生成的题库中自动生成满足教学和教师需求的试卷。一套试卷的构成需要涉及很多因素 ,在试卷中的每一道试题又包含多个属性 ,其中与组卷有关的属性有如下六项 : (1)题型 ; (2)章节 ; (3) 难度系数 ; (4)区分度 ; (5)时间 ; (6)分数。组卷中决定一道题 ,就是决定它的上述六个属性 ,组成一份 n 道题的试卷就是从试题库中抽取 n 道题 ,组成一个 n 6的矩阵 ,矩阵中的每一列代表一个属性 ,每一行代表一道题。即S = (1) 题型 :试题的题型。按照现代教育理论对于考试的客观性的要求 ,试卷应包含足够的客观性试题 (选择题、填空题 ) 。而为了考察学生的思维水平与能力 ,分析运算能力和科学表达能力 ,试卷又要有一定数量非客观性试题。考虑到上述两方面的要求 ,试题库内试题应包含判断题、填空题、选择题、问答题、改错题、证明题、和计算题 7 种题型 。(2) 章节 :试题内容所属的篇章。为保证试题有第 18 卷第 3 期2004 年 9 月济南大学学报 (自然科学版 )F J & 18 32004 1995o., 每个章节都要有相应的试题 ,且各章内容所占分数应与教学时数成正比。(3) 难度 :在试卷命题过程中 ,针对不同考试对象、不同阶段的考试 ,命题难度也不同。试题难度系数定义为 d = 1 - (平均分 / 该项满分 ) 。根据难度系数不同 ,将试题分为容易、中等、较难、难四个难度等级 :容易 :0. 05 0. 20中等 :0. 25 0. 40较难 :0. 45 0. 70难 :0. 75 0. 95在组卷中 ,对于各种难度级的试题在试卷中的分布也做出一个参考性规定 ,即 : (容易 ) : (中等 ) :(较难 + 难 ) 25 :60 :15(4) 区分度 :试题对考生的水平鉴别和区分程度的指标。为了估计区分度 ,我们将考生分成高分组和低分组两个组 ,分别统计高分组和低分组的得分率 ,我们把区分度定义为 :区分度 = 高分组的得分率- 低分组的得分率 3 。(5) 分数 :每份试卷的分数为 100 分 ,或由用户指定。(6) 时间 :考试时间为 120 分钟或由用户指定 。除了上面六个约束外 ,有时试卷还要满足教学要求层次 (掌握、理解、了解 ) 、能力要求 (知识、运用、灵活运用 ) 、试题内容的相关性以及出题频率等约束。但根据经验 ,指标过多会增加组卷问题的难度并降低其效率。2 传统遗传算法的问题求解遗传算法是基于生物学进化原理的一种全局搜索算法 ,它模拟了自然界适者生存、优胜劣汰这一基本的生物进化过程。遗传算法的框架是由 4 于 20 世纪 60 年代提出 ,可描述为 :(1)随机产生初始种群 ;(2)利用评价函数 (适应度函数 ) 对个体计算函数值 ;(3)按一定的概率对个体进行选择、交叉、变异等操作产生新种群 ;(4)重复 (2) 、 (3)两步 ,直到收敛 (找到最佳解或迭代次数足够多 ) 。上述框架中的参数往往与待解决的具体问题密切相关。针对自动组卷问题 ,我们给出相应的算法步骤如下 :步骤 1 :染色体的编码假设试题库中有 m 道题 ,可用一个 m 位的二进制串来表示 ,形式为 : x1 x2 其中若 1 ,则表示该题被选中 ,若 0 则表示该题未被选中 ,即 1 ,当第 i 道题被选中 ;0 ,当第 i 道题未被选中若一份试卷中有 n 道试题 ,则 x1 x2 中应有 n 个 1。步骤 2 :初始化群体通过随机的方法生成初始化的串群体。在串群体中 ,串的长度是相同的 ,群体的大小根据需要按经验或实验给出。步骤 3 :计算当前种群每个个体的适应度本问题的适应度函数可定义为f = 6i =1f i 表示第 i 个属性指标与用户要求的误差的绝对值 , 示第 i 个指标对组卷重要程度的权值 , 骤 4 :选择按照一定的选择概率对种群进行复制 ,选择较好的串生成下一代 (个体的适应度函数值越小 ,该串的性能越好 ,选择概率越大 ) ,去掉较差的串。步骤 5 :交叉交叉是两个串按照一定的概率 (交叉概率 ,从某一位开始逐位互换。首先 ,对每个二进制串产生一个在 0 1 的随机数 ,若该数小于 则选择该串进行交叉 ,否则不选择。随机地对被选择的二进制串进行配对 ,并根据二进制串的长度 n ,随机产生交叉位置 i , i 为 1 , n - 1 上的一个整数 ,然后按下面的方式交叉 :交叉前 交叉后a1 a2 1 a1 a2 1 b2 1 b1 b2 1 :变异变异是二进制串的某一位按照一定的概率 (突变概率 发生反转 , 1 变为 0 , 0 变为 1。这里 小于 0. 001。但在实践中发现 ,在有些遗传算子中 , 0. 1 时更好 5 。步骤 7 :终止记录进化的代数 ,并判断是否满足终止条件。若满足 ,则输出结果 ,否则转向步骤 3 继续执行 。终止条件如下 :(a)出现种群满足 f = 0 ;922第 3 期杨青 :基于遗传算法的试题库自动组卷问题的研究 1995o., b)某个个体适应度值达到指定要求 ;(c)达到指定的进化代数 ;(d)当前种群中最大适应度值与以前各代中最大适应度值相差不大 ,进化效果不显著。3 改进的遗传算法在传统的遗传算法中 ,初始种群的每个字符串中“ 1”的数目等于试题的数目 n ,可进行遗传操作(交叉、变异 ) 后 ,字符串中“ 1”的数目可能大于或小于 n ,从而变为非法解。此时必须对解进行修正 ,即进行相应的运算使字符串中“ 1”的数目为 n。一般说来 ,这个过程比较复杂 ,大大增加了运算量。另外 ,对于生成试卷的 6 个属性指标 ,我们的要求也不一样。对于考试分数 ,我们希望没有误差 ,而对于其他属性 ,如题型、章节、难度、区分度、时间等只要满足一定的要求就可以了。因此对传统的遗传算法做如下改进 :(1) 编码的改进在实际组卷中 ,假设在试卷中每种题型的数目是固定的 ,且相同的题型的分数和答题时间是相同的。这样 ,可以将整个二进制串按照题目的类型划分为不同的功能块。每个功能块采用独立的二进制编码。也就是说 ,每个功能块对应一种特定的题型 ,而该功能块中 ,“ 1”代表该题被选中 ,“ 0”代表该题未被选中 ,“ 1”的数目即该种题型的试题数目。显然 ,按这种规则产生的初始种群已经满足了试题对题型、分数和答题时间的要求。(2) 交叉运算的改进由于种群中每一个功能块对应着一个题型 ,所以 ,为了保证每个题型的数目不变 ,交叉点的选择不能破坏功能块的完整性。假设交叉点位于第 i 个功能块内 ,则前 i 个功能块保持不变 ,从第 i + 1 个功能块开始逐位交换 。(3) 变异运算的改进由于在每个功能块中 ,“ 1”的数目即是该题型试题的数目 ,因此在变异过程中应保证整个种群所有功能块中“ 1”的数目不变。可执行如下过程 ,首先 ,由变异概率决定某位取反 ;然后 ,检查、修正字符串中“ 1”的数目 ,保证不发生变化。(4) 用全局最优解替换本次迭代的最差解为保证好的字符串不至于流失 ,每次遗传操作前记录本次迭代的最优解 ,若该解优于全局最优解则替换全局最优解 ,否则全局最优解保持不变。此次遗传操作后 ,用全局最优解替换本代的最差解。4 实验411 实验设计与实验数据在实验中将 600 道试题按要求存放于所使用的试题库中 ,并给出个体评价函数 :f = w1 w2 w3 w4 w5 w6 1 ( i = 1 , 2 , 6) 。 示各试题分数之和与用户指定的总分之差的绝对值 ; 示各试题估时之和与用户指定的考试时间之差的绝对值 ; 示各种题型题量与用户指定的相应值的误差绝对值之和 ; 每一篇章试题分数与用户指定的相应值的误差绝对值之和 ; 每一难度的试题分数与用户指定的相应值的误差绝对值之和 ; 每一区分度试题分数与用户指定的相应值的误差绝对值之和。以下各表列出一部分实验结果。表 1 是运用传统的遗传算法在不同种群及不同迭代次数中得到的最小适应度的值 。其中 ,交叉概率 0. 6 ,变异概率 0. 1。表 1 传统遗传算法在不同种群及不同迭代次数中得到的最小适应度的值迭代数目 (代 ) 最小适应度的值(种群数目 = 10) 最小适应度的值(种群数目 = 15) 最小适应度的值(种群数目 = 20)10 109 91 8850 109 88 83100 93 86 74150 86 86 70200 86 83 65250 86 83 65表 2 是运用改进的遗传算法在不同种群及不同迭代次数中得到的最小适应度的值 。其中 ,交叉概率 0. 8 ,变异概率 0. 005。表 2 改进遗传算法在不同种群及不同迭代次数中得到的最小适应度的值迭代数目 (代 ) 最小适应度的值(种群数目 = 10) 最小适应度的值(种群数目 = 15) 最小适应度的值(种群数目 = 20)10 48 34 4450 38 22 30100 24 18 14150 20 14 10200 18 8 10250 16 6 4表 3 是应用改进的遗传算法在不同种群不同终032济 南 大 学 学 报 (自然科学版 ) 第 18 卷 1995o., 终止条件 1 适应度值 f 达到 16 ,终止条件 2适 应度值 f 达到 10) 下的运行时间。其中 ,交叉概率 0. 8 ,变异概率 0. 005。表 3 改进遗传算法在不同种群及不同终止条件中得到的运行时间种群数目 终止时间 / s(f 10)终止时间 / s( f 16)10 67 2815 21 1220 31 11表 4 是传统的遗传算法的求解时间情况 6 。其中 ,交叉概率 0. 6 ,变异概率 0. 05。表 4 传统的遗传算法及随机算法求解组卷问题所用时间实验次数 传统的遗传算法所用时间/ 4 2542 52 1643 58 301412 实验分析对比表 1、表 2 的实验结果可知 ,在不同种群下 ,采用功能块的改进的遗传算法性能优于传统的遗传算法 ,而且指标有很大的提高 ,这说明改进的遗传算法降低了问题的求解难度 ,提高了问题的求解效率。组卷是组成一份误差在可接受范围内的试卷 ,并非要求此试卷的整体指标一定是全局最优 ,尤其是在改进的遗传算法中 ,整个试卷的题目类型、题目数量、题目分数不会产生误差 ,而在篇章、难度、区分度上的一定范围内的误差是可以接受的。由表 3可知适当地放大误差 ,可较大幅度缩短求解时间。对比表 3、表 4 可知遗传算法效率好于普通的随机算法 ,改进的遗传算法在时间上也优于传统的遗传算法。5 结束语组卷问题是一个在一定约束条件下的多目标参数优化问题 ,而它的约束条件难以用数学形式描述 ,所以采用