基于遗传和模拟退火算法的自动组卷系统设计与实现.doc

CN4321258/ TPISSN 10072130X计算机工程与科学COMPUTER ENGINEERING & SCIENCE2004年第 26卷第 11期Vol126 ,No111 ,2004文章编号 :10072130X(2004) 1120065204XDesign and Implementation of an Automatic Test PaperGeneration System Based on the Genetic Algorithmand the Simulated Annealing Algorithm张辰 ,张艳群ZHANG Chen , ZHANG Yan2qun(中国矿业大学计算机学院 ,江苏徐州 221008)( School of Computer Science and Technology , China University of Mining andTechnology , Xuzhou 221008 , China)摘要 :本文介绍了组卷算法的数学模型和主体思想。我们从算法的合理性、用性和可操作性上加以分析和设计 ,用遗传算法和模拟退火算法创建模型 ,用于解决自动组卷的问题 ,并且在 Delphi平台下实现了自动组卷系统。Abstract :This paper introduces the mathematical model and the main ideas of the test paper generation algo2rithm. Based on analysing the reasonability , utility and manipulation of the algorithm , we create a model with thegenetic algorithm and the simulated annealing algorithm to solve the problem of automatic test paper generation.关键词 :试题库 ;遗传算法 ;模拟退火算法 ;多目标规划Key words :question library ;genetic algorithm ;simulated annealing algorithm ; multi2target planning中图分类号 : TP311文献标识码 :A法 ,能够用随机搜索技术从概率意义上找出目标1引言计算机考试系统自动组卷的效率与质量完全取决于抽题算法的设计。如何设计一个算法从题库中既快又好地抽出一组最佳解或是抽出一组非常接近最佳解的实体 ,涉及到一个全局寻优和收敛速度快慢的问题 ,具有很高的研究价值。遗传算法 1 ,2 以其自适应寻优及良好的智能搜索技术 ,受到了广泛的运用。模拟退火算法 3 是一种基于金属退火机理而建立的一种全局最优化方函数的全局最小点。本文提出了一种基于遗传和模拟退火算法的数学模型 ,并且在 Delphi平台下实现了自动组卷系统。2模型的提出一般情况下 ,一门课程由多个章节组成 ,其中包括重点性的、理解性的、必考的、不考的章节等内容。以电工电子学为例 ,它涉及到数理统计、法设计、二进制结构化存储、计算机密码学、运筹X收稿日期 :2003207202 ;修订日期 :2003210212作者简介 :张辰 (1979 - ) ,女 ,江苏徐州人 ,硕士生 ,研究方向为集群和网格计算 ;张艳群 ,硕士生 ,研究方向为网格安全和 Web Ser2vice安全。通讯地址 :221008江苏省徐州市中国矿业大学计算机学院 ; E2mail :zhch97 sina. comAddress :School of Computer Science and Technology ,China University of Mining and Technology , Xuzhou ,Jiangsu 221008 ,P. R. China65 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.基于遗传和模拟退火算法的自动组卷系统设计与实现实算学等多方面的知识。同时 ,根据试题答案的唯一性 ,试题又可分为客观题与主观题两大类。通过调研 ,该组卷算法应完成的目标如下 :(1)试卷的总分值需达到规定的分值 ;(2)客观题与主观题的分值比例应达到规定的比例 ;(3)严格按照重点章节、考章节、考章节的要求筛选试题 ;(4)同一试题在连续几次的组卷中被抽取的频次应尽可能低 ;(5)试卷的难度、分度适当 ,应当满足规定的试卷平均分与不及格率。2. 1基本假设(1)对于每道试题而言 , n位学生的测试结果近似服从正态分布 ;(2)对于 k道试题组成的试卷而言 , n位学生的测试结果仍然服从正态分布。本文中涉及到的参数符号及其含义均在附录中予以说明。2. 2分析问题一个好的组卷算法 ,要综合考虑总分值、项比例、章节、频次、难度、不及格率等各方面的要求。但是 ,有些目标难以同时满足 ,针对每个目标应用的方法不尽相同 ,有的应严格达到 ,有的可以人工调整 ,有的可以通过算法的预处理过程直接保证 ,而有些目标之间甚至是相互冲突的 ,因此必须对每个目标逐个设计解决方案后加以协调。对于目标 (1) ,显然所选试题组成的试卷必须要达到规定的分值 ,但由于生成的试卷是由 Word文档形成提交的 ,完全可以人工在其上进行较小的调整。因而只要生成的试卷的总分值在规定值间的分值差处于一个可接受的范围内即可 ,即三类 : (1)重点章节的试题 ; (2)必考但非重点章节的试题 ; (3)非必考且非不考章节的试题。这样 ,该目标就包含以下两方面 :第一 ,本张试卷必须覆盖必考章节的内容 ,每个必考章节中的试题至少要出现一题 ,故 V/ V 0 = 1也是约束条件之一。第二 ,为了做到试卷的重点突出 ,必须使 (1)及 (2)类试题的量尽量多 ,这就需要一种标准来衡量试卷重点是否突出。在此引入一种量化的“权重参数”,其值可在以后的算法调试中设定。对于一张试卷而言 ,其综合权重参数是必须规划的量 ,作为目标加入模型中 ,即 :maxW = S hwh + S mwm + S lwl对于目标 ( 4) ,根据经济学中经典的“20比80”或“黄金分割”原则 ,在算法的预处理中就可以将频次的问题解决。具体做法是将试题库中的试题按照试题被抽取的频次排序 ,去掉频次较大的 80 %或 61. 8 %不参加组卷 ,可保证试题的频次尽可能小。具体用“20比 80”原则还是“黄金分割”原则要根据试题库的规模而定。如果试题库的规模较大 ,则宜用“20比 80”原则 ,反之则宜用“黄金分割”原则。该问题的解决可通过预处理过程控制 ,不应体现在数学模型中。应该注意到 ,去掉频次较大的试题后有可能所剩余的必考章节的试题不够或者覆盖面不广。所以 ,在以频次为第一次序排列的同时 ,应采用“惯例重要度”的第二次序 ,以保证其随机性。所谓的“惯例重要度”是指对于惯例而言 ,该题的重要程度。例如 ,对于某一个章节来说分为四级“重要度”,即“重点出题章节”“一般必考章节”“一般章节”和“一般不出题章节”分别对应的重要度为 13、4、6、8之间的某随机数 ,而每道试题的“惯例重要度”就是指该试题包含的所有章节的“章节重要|Kni = 1i- N 0 |。可以将其作为数学模型的度”的均值后加某一微小随机数调整。对于目标 (5) ,试卷和试题的难度、区分度是约束条件。对于目标 ( 2 ) ,与 ( 1 )类似 ,同样可以将衡量试卷和试题质量的最重要的两个标准 ,在整个指标体系中占有突出地位 ,直接决定系统的质|K0ni/ni = 1 i = K +10i- P0 | ,以及 | Nw/ Nt - Q0 |量。难度是指试题或试卷的难易程度 ,本文以国际惯例为准 ,难度系数大 ,试题容易。标准化考试作为约束条件。对于目标 (3) ,不考章节的题目不能出现在试卷中 ,同时试卷必须有必考章节 ,而重点章节包含于必考章节中 ,是需要重点出题的。首先根据不考章节 ,将试题库中所有不考章节的试题全部去掉不参加组卷 ,然后将试题库中剩下的试题分为要求多数试题的难度系数在 0. 30. 7 ,如果考试能对全体考生最大程度地区分 ,则整个试卷的难度系数在 0. 5左右 ,学业考试以 60分为及格线 ,因而所规划的试题库系统应将难度系数控制在0. 60. 8之间为好 ,即平均分在 60分80分之间。难度可操作的计算公式为 p =平均分/满分。66 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.必不区各、, 2 4 6K如果试题或试卷的考察情况服从正态分布 ,显然p =。如果已知每一道试题的难度系数 ,则通过min0 -Ki = 1niiiKn / (i = 1Kni) 2i = 1计算可得全卷的难度系数为 :至此 ,将问题抽象为一个多目标规划的数学 =K Kn /ni = 1 i = 1i模型。区分度是最大限度区分被试者的特性和能力的指标 ,区分度好的试卷 ,不仅对学生的特性、能力和学业水平有较高的鉴别能力 ,而且可以说明试题难易搭配合理 ,能区分学生的等级 ;区分度低 ,说明整套试卷偏难或偏易 ,试题难易搭配不合3模型的建立通过对组卷过程及各种影响它的重要因子的分析 ,提出了一个新的数学模型 :maxW = S hwh + S mwm + S lwl理。国际标准化考试的优秀试卷的区分度 0. 4。若 0. 2 区分度 0. 29 ,试题尚可 ,下次出同类的min0 -Kn/i = 1Kni = 1i试卷需要修正 ;若区分度 0. 19 ,本次考试作废 ,需重新考试。试题或试卷区分度的可操作计算公min0 -Ki = 1niiiKn / (i = 1Kni) 2i = 1式有如下三种 :区分度 = (高分平均分 2低分平均分) /平均分|Kni = 1i- N 0 |(1)“高分平均分”和“低分平均分”分别是平均分以上和以下分数的平均值。s. t. |K0ni/i = 1Kni = K +10i- P0 |区分度 = (高分组平均分 2低分组平均分) /满分(2)“高分组”和“低分组”的取法是将样本分数由高到低排列 ,高分向下低分向上分别取 27 %为高分组和低分组。区分度 = 1. 6满分 /平均分 (3)其中 ,是试题或试卷的标准差除以其满分后所得的标准 1分制的试题或试卷的标准差。同时 ,V/ V 0 = 1| Nw/ Nt - Q0 |4模型的求解与算法设计首先 ,模型中的、0仍然不够明确 ,由基本假设 ( 2) ,显然 = N/ N 0。而得分少于 N 0的60 %被认为是不及格的 ,则不及格率为 :由上面的分析可知 ,试题或试卷的难度系数为=平均分/满分 ,故区分度 = 1. 6/。另外 ,如果已知试卷中每一道试题的区分度 Di ,其全卷的P x 0. 6 N = Px N ( N , N 2020)x - NN 0 0. 6 N 0 - NN 00 =区分度估算表达式为 :K KD =niDi /nii = 1 i = 1如采用公式联系区分度和的话 ,则可将全卷的表达为 :x - NN 0 0( ) =u(其中 u可查标准正态分布表)K1. 6 = 1. 6i = 1niiiK/ni i = 1本模型采取遗传模拟退火算法来解决并应用于实践。其基本思想如下 :K K Ki ii = 1 i = 1 i = 1在规划组卷算法时生成的试卷应该与规定值尽可能相近 ,但无法给出一个可以接受的差值上限。事实上给出的差值上限并无实际意义。因此 ,该目标是数学模型中应当规划的目标4 ,即 :K Kmin -n /nii = 1 i = 1( 1)通过预处理 ,将模型中的各项参数一一明确 ,同时限定算法所搜索的全体目标试题。(2)染色体编码方案 :采取 0/ 1编码 ,某基因座上的 0表示对应的试题不选取 ,1则表示选取。同时染色体分为两段 ,第一段为客观题选取情况( x 1 x 2xm) ,第二段为主观题选取情况 ( y 1 y 2y n)。(3)算法开始 ,随机产生 M个染色体。(4)对每一个染色体 ,以所取客观题试题的总分与标志客观题总分和所取主观题总分与标志主观题总分之差的绝对值为能量函数。即对两段染色体进行校正 ,使得总分和比例达到要求。具体来说 ,对于染色体( x 1 x 2xmy 1 y 2y n)来说 ,设其客观题总分为 X ,主观题总分为 Y ,则两个能量函数为 :E1( X) = | N 0P0/ ( 1 + P0) - X |E2( Y) = | N 0(1 + P0) - 1 - Y |67 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.i ii iiii i000 N (0 ,1)0. 6 -000 =0. 6 -0/nii =n / (n ) 2.i0 ii当然 ,容易计算 ,只要满足如下条件 :E1( X)P0/ ( 1 + P0)E2( Y) =(1 + P0) - 1即可退出该此步校正 ,这样调整出来的染色体已满足总分和比例的要求。(5)选择算子作用。本算法针对多目标规划的模型 ,采取并列选择的方法作遗传操作 ,即将染色体按子目标函数的个数平均分组 ,各分组按各自的子目标适应度在分组中独立地进行按比例遗传的操作。为了进行适应度的计算 ,将三个目标转换成如下等价形式 :maxW 1 = S hw h + S mwm + S lw lK KmaxW2 = 1 - |0 - (i = 1K K Kii = 1 i = 1 i = 1这样 ,适应度函数就满足了“最大”和“非负”两个条件 ,可以进行正比例选择。同时 ,考虑到约束条件 V/ V 0 = 1的作用 ,这里采用惩罚函数的做法。由于此条件与目标 W1的逻辑联系比较紧密 ,因此将其体现在第一个子目标中 ,即将第一个子目标调整为 :max W1 = S hw h + S mwm + S lwl -| 1 - V/ V 0 |当然 ,这样的做法是否有效以及惩罚因子的定量 ,还有待调试。对染色体的综合评价采取 W =1W1 +2W2 +3W3 (其中、1、1为权重系数 ,可调) ,在并列选择之后对每一个染色体计算该值 ,保存当前最优解不参加交叉和变异操作。(6)交叉算子。交叉算子仍采取普通的单点交叉算法 ,但改变对于配对的交换染色体来说 ,代表客观题和主观题的染色体分别进行单点交叉。(7)变异算子。变异算子使用基本位变异算子。(8)对于产生的新一代群体 ,重复 ( 4)、( 5)、( 6)、( 7)的过程 ,选出适应度最优的个体。算法结束。5结束语本文提出的遗传模拟退火算法在本校教改项目“软件工程自动组卷系统”中已经实现 ,限于篇幅 ,代码在此不予详细介绍。本文利用遗传算法的概率搜索和收敛速度快的特点 ,结合模拟退火算法的全局寻优 ,设计了一种用于自动组卷的智能算法 ,提高了组卷的效率和成功率 ,为智能组卷的实现提供了一种新途径。要使自动出题的误差精度和收敛速度进一步得到改进 ,还需要进行更深的研究。参考文献 :1 王小平 ,曹立明.遗传算法 :理论、用与软件实现 M .西安 :西安交通大学出版社 ,2002.2 李敏强 ,寇纪淞 ,林丹.遗传算法的基本理论与应用 M .北京 :科学出版社 ,2002.3 康立山 ,谢云 ,尤矢勇 ,等.非数值并行算法 :模拟退火算法M .北京 :科学出版社 1994. 4 冯尚友.多目标决策理论方法与应用 M .华中理工大学出版社 ,1990.5 美 Zbigniew Michalewicz.周家驹 ,何险峰译.演化程序 :遗传算法和数据编码的结合M .北京 :科学出版社 ,2000.附录 :(1) K:试卷的总题量; ( 2) Ko :试卷中客观题的总题量; ( 3)Ks :试卷中主观题的总题量; ( 4)、 :将试题或试卷折合为标准 1分制后大量取测试样本后测出的正态分布的参数; ( 5)、0 :该试卷的测试结果应当符合的正态分布的参数; ( 6) ni :第 i题的分值; (7) N 0 :试卷规定的总分值; (8):决策者认为可接受的试卷总分与 N 0的差值的上限; ( 9):决策者认为可接受的试卷客观题与主观题总分比例与 P0的差值的上限; (10) S h :试卷中包含重点章节的试题的总题量; ( 11) P0 :规定的客观题与主观题总分比例(12) S m :试卷中包含必考但非重点章节的试题的总题量; ( 13) S l :试卷中包含非必考且非不考章节的试题的总题量; ( 14) w h :一道包含重点章节的试题的权重参数; ( 15) wm :一道包含必考但非重点章节的试题的权重参数; ( 16) wl :一道包含非必考且非不考章节重点章节的试题的权重参数; ( 17) V 0 :试卷应当涉及的必考章节的数目; ( 18) V :试卷涉及的必考章节数; ( 19) Nw :试卷中电工学的试题的总分值; ( 20) N t :试卷中电子学的试题的总分值; ( 21)Q0 :规定的电工电子学总分值的比例; (22):决策者认为可接受的试卷电工电子学总分值的比例与 Q0的差值的上限; ( 23) Di :第i道试题的区分度; ( 24):规定的试卷的不及格率; ( 25) N :规定的试卷的平均分。(上接第 50页)5结束语为了减少资源浪费 ,提高系统的资源利用率 ,人们从不同角度提出了多种有效的节目调度方案 14 ,它们在不同程度上提高了系统的资源利用率 ,增加了系统的可扩展性。本文根据节目的流行度将其分成热门和冷门两类 ,提出了基于流行度的视频流控制方法 ,分析了系统的瞬间转移概率 ,给出了不同流行度视频流的带宽预测公式。仿真结果表明 ,这种方法也可以有效节省服务器的资源 ,提高视频的服务水平。参考文献 : 1 Mundur A , Simon R. Threshold2Based Admission Control for Mul2ti2Class Vedio2on2Demand SystemsJ . Proc of the IEEE IPCCC ,1998 ,6 (2) :154 - 160.2 Jiang X , Mohapatra P. Efficient Admission Control Algorithms forMultimedia Servers J . Multimedia Systems , 1999 , 7 ( 4) : 294 -304.3 Aggarwal C C , Wolf J L , Yu P S. The Maximum Factor QueueBatching Scheme for Video2on2Demand Systems J . IEEE TransComputers