论文部分内容阅读
【摘要】智能组卷是一个多约束条件的组合优化问题，算法的效率是决定智能组卷算法是否能获得高质量试卷的核心。Memetic算法组卷策略采用整数编码的形式、单点交叉策略、随机变异策略和爬山算法，以难度、知识点分布和认识层次设计适应度函数，以期达到快速生成高质量试卷的目的。文章的最后用随机组卷算法（Random）和标准遗传算法（GA_random）作为对照算法，以详细的实验结果证明了Memetic算法的有效性。综上所述，Memetic算法是一种有效实用的组卷策略。
【关键词】智能组卷;算法;适应度函数;数学模型
1.引言
随着计算机辅助教学的不断发展，智能组卷系统已成为教育学和计算机科学领域研究的热点。如何根据教学的需要自动生成考卷是计算机考试系统中的关键。智能组卷实质上是一个基于对试卷约束条件求解的多目标参数优化问题。目前常见的解决办法有：随机抽取、回溯试探、遗传算法、粒子群算法等[1]，但都存在一定的局限性。Memetic算法结合了遗传算法和局部搜索算法的优点，既具有全局寻优能力，又能通过局部搜索优化种群分布，保证了较高收敛性能[2]，是求解多目标优化问题的最有效方法之一。本文尝试用Memetic算法来解决智能组卷的问题，以期达到高可靠性和实用性的组卷目的。
2.组卷约束模型
2.1 指导思想
组卷的主要依据是教学大纲，系统生成的试卷必须全面反映大纲的广度和深度[3];系统生成的试卷要利于考核考生的知识水平和促进考生智力发展;试题要有总分和时间限制。
2.2 试卷的属性指标
试卷的属性指标指试卷必须达到的用户需求，由试题本身的属性来体现，是建立组卷系统的核心。试卷的属性越贴近用户的需求，试卷的质量越高。一般来说，试卷的属性指标由以下部分组成：分数（Score）、难度（Degree of Difficulty）、认知层次（Cognitive Level）、知识点（Knowledge Point）、题型（Item Topic）及时间（Answer Time ） [4] [5]。假设一张试卷由m道试题组成，每道题有n个属性，则一张试卷可以由m×n的矩阵R来表示。
矩阵的每行表示一道试题，列表示该题的属性。每道试题的属性amn所代表的含义如下：am1表示题目的分数、am2表示难度系数、am3表示对应的认知层次、am4表示所属的知识点章节、am5表示题型及am6表示估计答题时间。
2.3 组卷约束模型
（1）试卷总分，即计算试卷矩阵所有题目的分数（第一列所有元素）之和。
（2）试卷难度系数，即计算试卷矩阵中每一道试题的分数与其对应的难度系数乘积之和，再除以试卷总分，则得出该试卷的难度系数。
（3）认知层次为x的题目分数，其中，即计算试卷矩阵中认知层次为x的试题的分数之和。
（4）知识点为y的题目分数，其中，即计算试卷矩阵中知识点为y的试题的分数之和。
（5）题型为z的题目分数，其中，即计算试卷矩阵中题型为z的试题的分数之和。
（6）估计总答题时间，即计算试卷矩阵所有题目的答题时间（第六列所有元素）之和。
组卷约束模型可以分为简单目标约束（即：试卷总分和估计总答题时间）和曲线分布约束（即：由试题相应属性所占的分数总和来体现）组成。为了简化试卷的约束模型，我们可以根据实际情况通过指定总分、时间、试卷总难度系数和各知识点所占的分数等措施降低算法的搜索空间。
3.Memetic算法描述
3.1 算法流程
Memetic算法就是在遗传算法中通过局部搜索使个体达到局部最优，算法流程如图1所示。
图1 Memetic算法流程
3.2 算法模型
3.2.1 染色体编码
为便于理解和计算适应度函数，本文采用整数编码的方式。试卷可以表示成染色体的形式，染色体的长度代表了试卷的题量，染色体每位基因的数值代表组成该试卷的题号。
3.2.2 试卷初始化
本文将随机产生n份试卷作为初始种群，其中每份试卷将按题型从试题库中随机选取m道题，保证同一试卷不存在同号试题，且尽量满足总分和总的时间要求。
3.2.3 选择算子
采用轮盘赌策略来完成选择操作。
3.2.4 交叉算子
采用单点交叉策略作为交叉操作的方式，即： 依据交叉概率，首先各自在两条进行交叉操作的染色体中随机选择交叉点;将第一条染色体的交叉点以前的代码加在第二条染色体之前，将第二条染色体的交叉点以前的代码加在第一条染色体之前;然后对新产生的两条染色体依次删除相同的基因，得到最终的两条新染色体。
3.2.5 变异算子
采用随机变异策略作为变异操作的方式，即： 根据变异概率，在需进行变异操作的染色体中随机选择交叉点;然后在相应的题型库中选择不与当前染色体基因重复的一道满足要求的试题基因来替代当前交叉点所存在的基因，从而形成新的染色体。
3.2.6 局部搜索策略
本文采用爬山算法对遗传算子产生的新个体进行爬山操作，从而获得最优解。
3.2.7 适应度函数
为了降低算法的搜索空间，提高算法的效率，本文在初始化试卷矩阵时就已经满足了试卷估计答题时间、题型分布和试卷总分的要求，因此适应度函数只考虑难度分布、认知层次分布和知识点分布的要求，具体构建如下：
设生成的试卷各难度级别占的分数用sds表示，预期各难度级别占的分数用yds表示，各难度级别允许的误差用es表示，则难度分布的误差函数可用下式表示：
（7）其中，f1越小，说明试卷越接近难度分布的要求。 同理可得到认知层次分布的误差函数f2和知识点分布的误差函数f3：
设生成的试卷各认知层次占的分数用scs表示，预期各难度级别占的分数用ycs表示，各难度级别允许的误差用ec表示，则认知层次分布的误差函数可用下式表示：
（8）其中，f2越小，说明试卷越接近认知层次分布的要求。
设生成的试卷各知识点所占的分数用sks表示，预期各难度级别占的分数用yks表示，各难度级别允许的误差用ek表示，则知识点分布的误差函数可用下式表示：
（9）试卷的误差函数是f1 、f2 和f3的加权和。试卷的误差函数越小，则试卷的质量越高。为了便于计算，让试卷的质量与适应度函数成正比，本文用试卷误差函数的倒数来设计适应度函数，同时为了防止出现分母为0的现象，本文用试卷误差函数加1作为分母，即：
（10），其中wi指的是各评价函数所占的权重，所有权重之和（w1+ w2+w3）为1。因此，本文中的组卷目标就是使适应度函数尽可能大。
4.仿真实验与分析
计算机的实验平台是：处理器Intel（R）Core（TM）Duo T5750 2.0GHz 2.0GHz，内存3.0GB，操作系统Windows xp。
表1 组卷的约束条件
总分 100 答题时间 90 期望得分率 0.7
题型分布 题数，题分 认知层次 卷面分值 知识点分布 卷面分值
填空题 10，2 了解 10 第一章 10
选择题 10，2 识记 30 第三章 30
判断题 10，2 理解 30 第四章 30
简答题 2，5 应用 30 第五章 30
操作题 2，15 允许误差 2 允许误差 2
测试数据是340道《计算机文化基础》试题组成的试题库，共有5种题型、5个难度级别、4种认知层次、知识点分布4个章节，权重系数分别为0.7、0.2、0.1，允许的误差均为2，总分100分，耗时约为90分种。组卷的具体约束条件见表1。
初始种群为20，迭代次数为100，交叉概率为0.68，变异概率为0.006。
在本文中，我们选取随机组卷算法（Random）和标准遗传算法（GA_random）作为对照算法，各算法组成试卷的适应度函数值、难度分布、知识点分布和认知层次的对比如图2、图3、图4和图5所示。其中，Random算法的种群数为20，GA_random算法的种群数为20，迭代次数为100，交叉概率为0.68，变异概率为0.006。由于各算法本身的参数具有不确定性，因此本文展示的是部分实验结果。
图2 各算法在适应度函数值对比
图3 各算法在难度分布上的对比
图4 各算法组成在知识点分布上的对比
图5 各算法在认知层次分布上的对比
在适应度函数值的对比上，由图2可知，Memetic算法在迭代26次后适应度函数值达到了1，从而能得出满意的试卷，GA_random算法和Random算法的适应度函数值均不高。
在难度分布的对比上，Memetic算法的难度分布值为{10，29，34，21，6}，根据期望得分率0.7得出难度标准分布值为{12，30，32，19，7}，在允许误差为2的情况下，Memetic算法的难度误差均在允许范围内。由图3可见，Memetic算法的性能最优，GA_random算法次之，Random算法最差。
在知识点分布的对比上，Memetic算法的知识点分布值为{8，32，31，29}，知识点标准分布值为{10，30，30，30}，在允许误差为2的情况下，Memetic算法的难度误差均在允许范围内。由图4可见，Memetic算法的性能最优，GA_random算法次之，Random算法最差。
在认知层次分布的对比上，Memetic算法的认知层次分布值为{8，32，31，29}，知识点标准分布值为{10，30，30，30}，在允许误差为2的情况下，Memetic算法的难度误差均在允许范围内。由图5可见，Memetic算法的性能最优，GA_random算法次之，Random算法最差。
综上所述，在相同条件下，Memetic算法在智能组卷过程中要优于GA_random算法和Random算法。在本次实验中，Memetic算法策略生成了一套题号为（52，73，30，75，2，57，6，86，48，9，194，149，145，136，175，144，177，105，107，176，284，292，238，240，283，265，216，269，203，290，306，320，329，325），适应度函数值为1的最优试卷。
5.结语
本文介绍了如何设计编码方案，适应度函数、遗传算子和局部搜索策略来应用Memetic算法进行智能组卷工作。本文将Memetic算法应用到《计算机文化基础》组卷过程中，实验证明该算法方案可行，组卷效率高，试卷质量好。
参考文献
[1]王琦.智能组卷算法研究比较[J].科技信息，2008（27）： 403-404.
[2]彭建伟.基于memetic 算法的个性化学习路径推荐的研究与实现[D].长沙：湖南大学，2009：37-40.
[3]吴树锦.基于遗传算法智能组卷系统的研究与实现[J].天津职业院校联合学报，2010（05）：34-37.
[4]周艳聪，刘艳柳.遗传模拟退火智能组卷策略研究[J].计算机工程与设计，2011（03）：1066-1069.
[5]周艳聪，刘艳柳，顾军华.小生境自适应遗传模拟退火智能组卷策略研究[J].小型微型计算机系统，2011（02）：323-327.
基金项目：湖南省科技厅一般项目（2013PJ3066）。
作者简介：
谭慧琳（1982—），湖南邵阳人，硕士研究生，邵阳医学高等专科学校讲师，研究方向：信息技术教育。
肖擎纲（1956—），男，湖南邵阳人，教授，湖南省邵阳市高等医学专科学校副校长，主要研究方向：计算机教育。
【关键词】智能组卷;算法;适应度函数;数学模型
1.引言
随着计算机辅助教学的不断发展，智能组卷系统已成为教育学和计算机科学领域研究的热点。如何根据教学的需要自动生成考卷是计算机考试系统中的关键。智能组卷实质上是一个基于对试卷约束条件求解的多目标参数优化问题。目前常见的解决办法有：随机抽取、回溯试探、遗传算法、粒子群算法等[1]，但都存在一定的局限性。Memetic算法结合了遗传算法和局部搜索算法的优点，既具有全局寻优能力，又能通过局部搜索优化种群分布，保证了较高收敛性能[2]，是求解多目标优化问题的最有效方法之一。本文尝试用Memetic算法来解决智能组卷的问题，以期达到高可靠性和实用性的组卷目的。
2.组卷约束模型
2.1 指导思想
组卷的主要依据是教学大纲，系统生成的试卷必须全面反映大纲的广度和深度[3];系统生成的试卷要利于考核考生的知识水平和促进考生智力发展;试题要有总分和时间限制。
2.2 试卷的属性指标
试卷的属性指标指试卷必须达到的用户需求，由试题本身的属性来体现，是建立组卷系统的核心。试卷的属性越贴近用户的需求，试卷的质量越高。一般来说，试卷的属性指标由以下部分组成：分数（Score）、难度（Degree of Difficulty）、认知层次（Cognitive Level）、知识点（Knowledge Point）、题型（Item Topic）及时间（Answer Time ） [4] [5]。假设一张试卷由m道试题组成，每道题有n个属性，则一张试卷可以由m×n的矩阵R来表示。
矩阵的每行表示一道试题，列表示该题的属性。每道试题的属性amn所代表的含义如下：am1表示题目的分数、am2表示难度系数、am3表示对应的认知层次、am4表示所属的知识点章节、am5表示题型及am6表示估计答题时间。
2.3 组卷约束模型
（1）试卷总分，即计算试卷矩阵所有题目的分数（第一列所有元素）之和。
（2）试卷难度系数，即计算试卷矩阵中每一道试题的分数与其对应的难度系数乘积之和，再除以试卷总分，则得出该试卷的难度系数。
（3）认知层次为x的题目分数，其中，即计算试卷矩阵中认知层次为x的试题的分数之和。
（4）知识点为y的题目分数，其中，即计算试卷矩阵中知识点为y的试题的分数之和。
（5）题型为z的题目分数，其中，即计算试卷矩阵中题型为z的试题的分数之和。
（6）估计总答题时间，即计算试卷矩阵所有题目的答题时间（第六列所有元素）之和。
组卷约束模型可以分为简单目标约束（即：试卷总分和估计总答题时间）和曲线分布约束（即：由试题相应属性所占的分数总和来体现）组成。为了简化试卷的约束模型，我们可以根据实际情况通过指定总分、时间、试卷总难度系数和各知识点所占的分数等措施降低算法的搜索空间。
3.Memetic算法描述
3.1 算法流程
Memetic算法就是在遗传算法中通过局部搜索使个体达到局部最优，算法流程如图1所示。
图1 Memetic算法流程
3.2 算法模型
3.2.1 染色体编码
为便于理解和计算适应度函数，本文采用整数编码的方式。试卷可以表示成染色体的形式，染色体的长度代表了试卷的题量，染色体每位基因的数值代表组成该试卷的题号。
3.2.2 试卷初始化
本文将随机产生n份试卷作为初始种群，其中每份试卷将按题型从试题库中随机选取m道题，保证同一试卷不存在同号试题，且尽量满足总分和总的时间要求。
3.2.3 选择算子
采用轮盘赌策略来完成选择操作。
3.2.4 交叉算子
采用单点交叉策略作为交叉操作的方式，即： 依据交叉概率，首先各自在两条进行交叉操作的染色体中随机选择交叉点;将第一条染色体的交叉点以前的代码加在第二条染色体之前，将第二条染色体的交叉点以前的代码加在第一条染色体之前;然后对新产生的两条染色体依次删除相同的基因，得到最终的两条新染色体。
3.2.5 变异算子
采用随机变异策略作为变异操作的方式，即： 根据变异概率，在需进行变异操作的染色体中随机选择交叉点;然后在相应的题型库中选择不与当前染色体基因重复的一道满足要求的试题基因来替代当前交叉点所存在的基因，从而形成新的染色体。
3.2.6 局部搜索策略
本文采用爬山算法对遗传算子产生的新个体进行爬山操作，从而获得最优解。
3.2.7 适应度函数
为了降低算法的搜索空间，提高算法的效率，本文在初始化试卷矩阵时就已经满足了试卷估计答题时间、题型分布和试卷总分的要求，因此适应度函数只考虑难度分布、认知层次分布和知识点分布的要求，具体构建如下：
设生成的试卷各难度级别占的分数用sds表示，预期各难度级别占的分数用yds表示，各难度级别允许的误差用es表示，则难度分布的误差函数可用下式表示：
（7）其中，f1越小，说明试卷越接近难度分布的要求。 同理可得到认知层次分布的误差函数f2和知识点分布的误差函数f3：
设生成的试卷各认知层次占的分数用scs表示，预期各难度级别占的分数用ycs表示，各难度级别允许的误差用ec表示，则认知层次分布的误差函数可用下式表示：
（8）其中，f2越小，说明试卷越接近认知层次分布的要求。
设生成的试卷各知识点所占的分数用sks表示，预期各难度级别占的分数用yks表示，各难度级别允许的误差用ek表示，则知识点分布的误差函数可用下式表示：
（9）试卷的误差函数是f1 、f2 和f3的加权和。试卷的误差函数越小，则试卷的质量越高。为了便于计算，让试卷的质量与适应度函数成正比，本文用试卷误差函数的倒数来设计适应度函数，同时为了防止出现分母为0的现象，本文用试卷误差函数加1作为分母，即：
（10），其中wi指的是各评价函数所占的权重，所有权重之和（w1+ w2+w3）为1。因此，本文中的组卷目标就是使适应度函数尽可能大。
4.仿真实验与分析
计算机的实验平台是：处理器Intel（R）Core（TM）Duo T5750 2.0GHz 2.0GHz，内存3.0GB，操作系统Windows xp。
表1 组卷的约束条件
总分 100 答题时间 90 期望得分率 0.7
题型分布 题数，题分 认知层次 卷面分值 知识点分布 卷面分值
填空题 10，2 了解 10 第一章 10
选择题 10，2 识记 30 第三章 30
判断题 10，2 理解 30 第四章 30
简答题 2，5 应用 30 第五章 30
操作题 2，15 允许误差 2 允许误差 2
测试数据是340道《计算机文化基础》试题组成的试题库，共有5种题型、5个难度级别、4种认知层次、知识点分布4个章节，权重系数分别为0.7、0.2、0.1，允许的误差均为2，总分100分，耗时约为90分种。组卷的具体约束条件见表1。
初始种群为20，迭代次数为100，交叉概率为0.68，变异概率为0.006。
在本文中，我们选取随机组卷算法（Random）和标准遗传算法（GA_random）作为对照算法，各算法组成试卷的适应度函数值、难度分布、知识点分布和认知层次的对比如图2、图3、图4和图5所示。其中，Random算法的种群数为20，GA_random算法的种群数为20，迭代次数为100，交叉概率为0.68，变异概率为0.006。由于各算法本身的参数具有不确定性，因此本文展示的是部分实验结果。
图2 各算法在适应度函数值对比
图3 各算法在难度分布上的对比
图4 各算法组成在知识点分布上的对比
图5 各算法在认知层次分布上的对比
在适应度函数值的对比上，由图2可知，Memetic算法在迭代26次后适应度函数值达到了1，从而能得出满意的试卷，GA_random算法和Random算法的适应度函数值均不高。
在难度分布的对比上，Memetic算法的难度分布值为{10，29，34，21，6}，根据期望得分率0.7得出难度标准分布值为{12，30，32，19，7}，在允许误差为2的情况下，Memetic算法的难度误差均在允许范围内。由图3可见，Memetic算法的性能最优，GA_random算法次之，Random算法最差。
在知识点分布的对比上，Memetic算法的知识点分布值为{8，32，31，29}，知识点标准分布值为{10，30，30，30}，在允许误差为2的情况下，Memetic算法的难度误差均在允许范围内。由图4可见，Memetic算法的性能最优，GA_random算法次之，Random算法最差。
在认知层次分布的对比上，Memetic算法的认知层次分布值为{8，32，31，29}，知识点标准分布值为{10，30，30，30}，在允许误差为2的情况下，Memetic算法的难度误差均在允许范围内。由图5可见，Memetic算法的性能最优，GA_random算法次之，Random算法最差。
综上所述，在相同条件下，Memetic算法在智能组卷过程中要优于GA_random算法和Random算法。在本次实验中，Memetic算法策略生成了一套题号为（52，73，30，75，2，57，6，86，48，9，194，149，145，136，175，144，177，105，107，176，284，292，238，240，283，265，216，269，203，290，306，320，329，325），适应度函数值为1的最优试卷。
5.结语
本文介绍了如何设计编码方案，适应度函数、遗传算子和局部搜索策略来应用Memetic算法进行智能组卷工作。本文将Memetic算法应用到《计算机文化基础》组卷过程中，实验证明该算法方案可行，组卷效率高，试卷质量好。
参考文献
[1]王琦.智能组卷算法研究比较[J].科技信息，2008（27）： 403-404.
[2]彭建伟.基于memetic 算法的个性化学习路径推荐的研究与实现[D].长沙：湖南大学，2009：37-40.
[3]吴树锦.基于遗传算法智能组卷系统的研究与实现[J].天津职业院校联合学报，2010（05）：34-37.
[4]周艳聪，刘艳柳.遗传模拟退火智能组卷策略研究[J].计算机工程与设计，2011（03）：1066-1069.
[5]周艳聪，刘艳柳，顾军华.小生境自适应遗传模拟退火智能组卷策略研究[J].小型微型计算机系统，2011（02）：323-327.
基金项目：湖南省科技厅一般项目（2013PJ3066）。
作者简介：
谭慧琳（1982—），湖南邵阳人，硕士研究生，邵阳医学高等专科学校讲师，研究方向：信息技术教育。
肖擎纲（1956—），男，湖南邵阳人，教授，湖南省邵阳市高等医学专科学校副校长，主要研究方向：计算机教育。