（计算机软件与理论专业论文）遗传算法在计算机辅助考试系统自动组卷中的应用.pdf

太原理工大学硕士研究生学位论文 遗传算法在计算机辅助考试系统自动组卷中的应用 摘要 为了了解学生的学习情况，分析教学的效果，都需要对学生进行考 核、评价，而一份高质量的试卷是准确评价学生的基础。在日常教学中， 为了组好一份试卷，教师往往要花费很多时间，是要利用计算机进行出题 考试就必然涉及到组卷抽题的问题，国外和国内的许多科研单位、学校 机构都对组卷系统进行了研究。虽然组卷系统是一个被探讨了很长时间 的问题，但至今也没有一个很好的解决其自动出题的算法方案。随着计 算机技术和人工智能的发展，组卷系统的研究被越来越多的专家所关注。 研究不仅涉及到组卷数学模型的建立问题，还包括对其应用的算法进行 研究。 在分析国内外大量文献的基础上，本文对智能自动组卷问题及常用 组卷算法进行了分析，运用遗传算法的全局寻优对智能自动组卷问题进 行研究。本文中首先根据用户要求、试题指标和试卷指标建立试卷数学 模型为一有约束的多目标优化数学模型：接着运用罚函数法及权重系数 法将建立好的有约束的多目标优化数学模型转化为无约束的单目标优化 数学模型，并对运用遗传算法对求解该数学模型进行了探讨。 本文主要工作为对自动组卷数学模型的建立及求解的研究。第一章 i 奎堕里三奎堂堡主塑塞生堂堡堡奎 为绪论，对所研究课题的主要内容及国内外研究现状进行了介绍：第二章 对考试系统自动组卷问题进行了分析并建立了数学模型：第三章对本文 所用到的知识及求解所建立数学模型所需要的知识及方法作简单介绍： 第四章重点介绍了所建立的数学模型的求解及遗传算法在求解该模型中 的应用，解集即为目标试卷中具有相同试题指标取值的试题。 关键字：组卷算法，遗传算法，多目标优化，数学模型 i i 太原理工大学硕士研究生学位论文 t h ea p p l i c a t i o no fg a i na u t o g e n e r a t i n ge x a mp a p e r o fc 0 u t e ra s s i s t a n tt e a c h i n gs y s t e m a b s t r a c t a h i g hq u a l i t ye x a m i n a t i o np a p e ri st h eb a s i st oe v a l u a t eh o w w e l lt h es t u d e n t sm a s t e r w h a tt h e yl e a r na n dc a l lb eu s e dt oa n a l y z et h ee f f e c to f t h et e a c h i n g i ne v e r yd a yt e a c h i n g ， t h et e a c h e r sw i l ls p e n dal o to ft i m ei nm a k i n gh i 曲q u a l i t ye x a m i n a t i o np a p e r s b u ti fw e w a n tt ou s et h ec o m p u t e r t oh e l pt h et e a c h e r st om a k eh i 曲q u a l i t yp a p e r , ad i f f i c u l t p r o b l e m ，h o wt oc h o o s et h ea p p r o p r i a t eq u e s t i o n sf r o mt h eq u e s t i o n sd a t a b a s eh a st ob e s o l v e d m a n ya c a d e m i ca n dr e s e a r c hi n s t i t u t e sm a k eal o to fr e s e a r c ho nt h i sp r o b l e m t h o u g ht h i sp r o b l e mh a sb e e nr e s e a r c h e df o ral o n gt i m e ，n o ww es t i l lc a nn o tf i n dt h e a p p r o p r i a t em e t h o d st os o l v et h i sp r o b l e me f f e c t i v e l y a st h ed e v e l o p m e n to fc o m p u t e r t e c h n o l o g i e sa n da r t i f i c i a l i n t e l l i g e n c e ，t h ee x a n lp a p e rg e n e r a t i n gs y s t e mh a sb e e np a i da l o to fa t t e n t i o nb ym a n ys c i e n t i s t s t h er e s e a r c hn o to n l yi n v o l v e sh o wt oe s t a b l i s ht h e m a t h e m a t i c a lm o d e lo fe x a u lp a p e rg e n e r a t i n gs y s t e m ，b u ta l s or e l a t e st ot h ea p p l i e d a l g o r i t h m s a f t e ra n a l y z i n gm a n yd o m e s t i ca n di n t e r n a t i o n a la c a d e m i cp a p e r s ，t h i sp a p e ra n a l y z e e x a mp a p e rg e n e r a t i n gp r o b l e ma n dt r yt ou s et h eg at oh e l ps o l v et h i sp r o b l e m f i r s t ， i i i 太原理i ：人学硕士研究生学位论文 a c c o r d i n gt ot h en e c e s s i t yo f t h eu s e r s ，am a t h e m a t i c a lm o d e li ss e tu pt od e s c r i b et h ee x a m p a p e rg e n e r a t i n gp r o b l e m ，t h e nu s i n gt h ef af u n c t i o n , w e i g h tc o e f f i c i e n ta n dg a t os o l v e t h i sm a t h e m a t i c a lm o d e l t h em a i nw o r ko ft h i sp a p e ri sm a k i n gt h er e s e a r c ho fh o wt os e tu pa i la p p r o p r i a t e m a t h e m a t i c a lm o d e lf o re x a mp a p e rg e n e r a t i n gp r o b l e ma n dh o wt ou s eg at os o l v et h i s m a t h e m a t i c a lm o d e l t h ef i r s t c h a p t e r i st h e e x o r d i u m ，i n t r o d u c i n gt h e a c a d e m i c b a c k g r o u n da b o u tt h i sp r o b l e m ；t h es e c o n dc h a p t e r a n a l y z e st h ec r i t i c a lp r o b l e ma n ds e tu p am a t h e m a t i cm o d e l ；i nt h et h i r dc h a p t e r , im a k ei n t r o d u c t i o nt os o m em e t h o d sa n d p r i n c i p l e siu s e di ns e tu pa n ds o l v et h em o d e l ；a n di nt h ef o r t hc h a p t e r , ip r o p o s eam e t h o d t ou s eg at os o l v et h i sm a t h e m a t i c a lm o d e la n dt h er e s u l t sa r et h ep a p e r st h eu s e r sw a n tt o u s e ；t h el a s tc h a p t e ri st h es u mu po f t h i sp a p e r k e yw o r d s ：e x a mp a p e rg e n e r a t i n g a l g o r i t h m ；g e n e t i ca l g o r i t h m ；m u l t i o b j e c t i v e o p t i m i z a t i o n ；m a t h e m a t i cm o d e l i n g i v 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体。均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：速杰日期： 关于学位论文使用权的说明 翌! ! ：互：! 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签名：銎煎日期：翌垒：兰：兰! 导师签名：盍鱼耋日期：! 堑：! ：! ! 太原理工大学硕士研究生学位论文 1 1 主要研究内容 第一章绪论 为了了解学生的学习情况，分析教学的效果，都需要对学生进行考核、评价，而 一份高质量的试卷是准确评价学生的基础。在日常教学中，为了组好一份试卷，教师 往往要花费很多时间。但是要利用用计算机进行出题考试就必然涉及到组卷抽题的问 题，国外和国内的许多科研单位、学校机构都对组卷系统进行了研究。虽然组卷系统 是一个被探讨了很长时间的问题，但至今也没有一个很好的解决其自动出题的算法方 案。 随着计算机技术和人工智能的发展，组卷系统的研究被越来越多的专家所关注。 它不仅涉及到组卷数学模型的建立问题，还包括对其应用的算法进行研究。如何设计 一个算法使得从题库中既快又好的抽出一组最佳解或是抽出一组非常接近最佳解的 实体，涉及到全局寻优和收敛速度快慢的的问题。本文在分析国内外大量文献的基础 上，对智能自动组卷问题及各种组卷算法进行了分析，运用遗传算法的全局寻优对智 能自动组卷问题进行研究，得到解决适合要求的试题模型的实用算法，并设计了一个 自动组卷系统及试题库对所研究的结果进行实现。实现结果表明遗传算法相对于其他 算法更能有效的解决自动组卷问题，具有较好的使用性能和实用性。 1 2 国内外研究现状 国外和国内的许多科研单位、学校机构都对组卷系统进行了研究。虽然组卷系统 是个被探讨了很长时的问题，但至今也没有一个很好的解决其自动出题的算法方案。 组卷问题是一个带约束的多目标优化问题，采用经典的数学方法很难解决这个难题， 太原理i 大学硕士研究生学位论文 自动组卷的效率和质量很大程度上取决于选题算法的设计。如何设计一个算法从试题 库即快又好的抽出一组最符合考生要求的试题，涉及到一个全局寻优和收敛速度快慢 的问题。以往的有自动组卷功能的考试系统大多采用随机选取法和回溯试探法，虽然 都能最终组出试卷，但都存在不足和缺点吲 随机选取法根据状态空日j 的控制指标，随机的抽取一道试题放入试题库，此过程 不断重复，直到组卷完毕，或已无法从题库中抽取满足条件的试题为止。该方法结构 简单，对于单道题的抽取运行速度较快，但是对于整个组卷过程来说组卷成功率低， 即使组卷成功，花费时间也很长。尤其是题库中各状态类型平均出题量时，组卷往往 以失败告终。埘 回溯试探法是将随机选取法产生的每一状态都记录下来，当搜索失败时释放上次 记录的状态类型，然后再依据一定的规律( 正式这种规律破坏了选取试题的随机性) 交换一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成完毕或退回出 发点为止，这种有条件的深度优先法，对于状态类型和出题量都较小的题库系统而 台，组卷成功率较好，但是在买际到一个应用时发现这种算法对内存的占用量大， 程序结构相对比较复杂，而且选取试题缺乏随机性，组卷时间长，后两点是用户无法 接受的，因此它不是一种很好的用来自动组卷的算法。 分析上述两种算法的优缺点，不难发现，在限制条件和状态空间的限制下，随机 选取法有时能够取出一组令用户满意的试题。只不过由于它随机选取试题的范围太 大，无法确定目前条件下那些区域能抽出合适的试题，反而可能在那些已经证明是无 法抽取合适的试题区域内反复选题，进行大量的无效操作进入死循环，最终导致组卷 失败。回溯法组卷成功率高，但它以牺牲大量的时间为代价，对于先进越来越流行的 考生网上随机即时调题的考试过程来既，它已不符合要求。 由上分析我们知道必须结合以上几种方法寻求一种新的改进算法。这种算法要具 有全局寻优和收敛速度快的特点。遗传算法( g e n e t i ca l g o r i t h m s ) 以其具有自适应全 局寻优和智能搜索技术，并且收敛性好的特性能很好满足自动组卷的需要。 2 太原理丁二大学硕士研究生学位论文 1 3 本文主要工作 本文研究的主要内容如下 自动组卷数学模型的研究 自动组卷算法实现的关键在于构建合理的自动组卷模型。组卷过程实质上二是一个 多重属性约束条件下复杂的多目标寻优过程。将用户对试题数量、试题内容、试题难 度等属性的要求进行量化，建立试卷模式，得到各个属性的分数分布列，这些分布列 联立起来就构成了自动组卷的数学模型。 自动组卷数学模型的求解 自动组卷模型是一个多目标优化的数学模型，模型结构复杂，能否正确、快速求 解成为关键内容，常规的求解多重约束条件下的高维方程组在理论和实践上都有一 定的难度。本文首先利用权重系数法将多目标优化转化成单目标优化的模型，然后利 用自适应罚函数法将有约束的组卷数学模型转化成无约束的模型，最后运用自适应遗 传算法对其进行求解。由于遗传算法有较好的全局寻优能力，相对传统的方法而言， 可以快速而准确的得到较优解。 3 太原理工大学硕+ 研究生学位论文 第二章考试系统自动组卷问题分析 2 1 自动组卷问题分析 自动组卷是考试系统自动化或半自动化操作的核心目标之一，而如何保证生成的 试卷能最大程度的满足用户的不同需要，并具有随机性、科学性、合理性，这是实现 中的一个难点。尤其在交互式环境下用户对于组卷速度要求较高，题目应具有多样性， 不宜作弊等，因此一个良好的组卷系统对于考生考试来说起着非常重要的作用。 组卷系统首先要了解考试的要求，然后应用组卷经验知识，确定考试的要求特性， 设计出相应的试卷模式，再按试卷模式选取试题组成试卷。对于组卷系统来说，它要 符合一定的约束和规范，对生成的试卷进行测试主要是使生成的试卷满足有效考试的 条件、考试的信度和效度、组卷系统的评价标准等。 组卷的目的是生成一份用于考试的试卷。组卷的初始阶段是用户输入对要生成的 试卷的具体要求，然后计算机就根据一定的算法去抽取试题，把这些抽取出来的试题 和评判条件相比较，如果评判不通过则重新选题，通过则编排试题、打印试卷供考生 考试。在进行出题之前，我们必须对问题的特征进行具体的、系统的分析，才能设计 出合理的组卷系统。 对组卷问题来说，它可规约为以下内容，也即组卷的特点。 数据的不精确性、模糊性 组卷系统是要从一些已有的试题中找出一部分满足用户要求的试题合成一份试 卷。所以系统中的数据首先就是试题正文以及相应的试题答案等。如果试题是无规则 的排列的话，则无法进行搜索或者搜索的难度很大，所以必须有一些描述这些试题的 指标数据。这些指标数据有一些是明确的，比如分数、题型等：但有些数据也是一个 比较模糊的概念，比如难度等级，还有些数据需要测试得到，比如解答该题说需要的 4 奎曼里王查堂堡圭堡塑尘堂堡垒奎 时问等。因此系统中的数据不是单一的精确数据，有的具有模糊性。 解的多样性 组卷是一个状态空间的问题的求解过程，初始节点为用户输入的试卷要求，叶节 点为一些满足要求的试题。由于题库中的试题有许多道，一般情况下能满足用户要求 的试题有许多，即问题的解空间是相当大的，这样就能在相同的条件下组出不同的、 内容丰富的试卷。 知识的特征 对于组卷系统来说，因为知识大都来源于成卷专家的经验，因此不可避免的会出 现一下的问题：不同的专家有不同的成卷经验，一个专家所认同的经验，可能另一个 专家不接受或者否定：有些专家经验也许对某部分内容是有效的，但对于其它部分 却无效：随着时间的推移、环境条件的变化，原来有效的经验变得无效。同时，软件 的研究过程本身就是在不断的总结专家经验，吸取错误的基础上进行的，所以以往的 组卷系统都存在着不完善性。所以在维护时就必须不断的更新知识、增减知识、完善 知识，使得系统能尽量产生高质量的试卷。 组卷系统最基本的目的是根据用户的要求，组出一份符合要求的、高质量的试卷。 对于一个组卷系统，它应该满足如下的功能要求： 用户可以组出几分试卷的指标相同，但题目的内容不同或者题目的顺序不同的 可比性试卷，以满足当今越来越流行的网上考试公正性的需要，杜绝作弊。 考试内容可以由用户决定，既可以按章节，也可以按题型。试卷的各章节所占 的分数比例一般应该与教学所用的时间成正比，但是用户也可根据需要改变分数的比 例。 试题值的难度值的问题。试卷中试题的难度比例、考查深度要符合考试大纲的 要求，试题的难度应适中，并且能根据不同的时间、不同的考试对象动态的改变。 试题的覆盖面要广。每个章节每个题类都出一道题，但当考试内容较窄时，也 允许一个题类不止出一道题。考察点分布合理，考查的内容对整个考试内容有足够好 的代表性： 5 太原理1 1 大学硕士研究生学位论文 组成的试卷应该能够区分出不同水平的学生的能力。即全卷的区分度不应该太 低，不然不同考生的分数都趋近于一致，达不到考试的目的。每道试题的区分度事先 由有经验的教师确定，并根据考生的考试成绩不断调整全卷的区分度的数学表达式 为 q = ( q , w , ) i m ( 2 一1 ) j l 式中q 为第i 道题的区分度，为第j 道题的满分值，为全卷的满分值 试卷的编排要合理，试卷的题类比例、题型比例应当根据考试的目的，类型不 同而不同。 组卷就是要从成千上万道试题中挑选出符合要求的题目，使题目构成的集合符合 上面建立的试卷模式。由于试题模式中各约束间的相互制约以及题量的限制，在组卷 过程中很难达到理想状态。如果把条件卡死，有时会陷入无休止的循环，这时适当的 允许误差，采用最小误差的方法可以建立一个最接近用户要求的多目标优化的数学模 型。该数学模型的目标函数是使所选题的总分值与用户要求的试卷总分的差最小，寻 求解集过程重必须满足的约束条件是试题数量要达到用户要求，尽量满足的约束条件 按重要性依次是试题难度分数分_ 布列、内容分数分布列和教学要求度分数分布列。求 解过程中，考虑到组卷的时间问题，只给出了内容大类分数分布列作为约束条件：由 于数学模型中的决策变量过多，传统的多目标优化求解方法的效率低，因此利用罚函 数将这种有约束问题转化为无约束问题，从而降低求解难度，再利用自适应遗传算法 进行求解，在获得一组解的基础上，采用依赖于课程知识结构图的知识点优先入选算 法合理分配试卷的内容，从而保证了试卷的质量，最终根据所获得的各道试题的具体 指标要求值抽取试题库中相应的试题，可根据误差控制知识对各部分试题进行调整， 从而组成一份满意的试卷“1 。 2 2 自动组卷问题组卷原理 自动组卷在本质上就是利用定的组卷算法，自动地从题库中抽取合适的试题， 6 太原岬i ：大学硕士研究生学位论文 使它们组成的试卷既能满足教要求又能满足用户要求。如何自动地抽取试题呢? 返 就是组卷算法要解决的问题，也造组卷系统的核心问题。要想让组卷系统能按用户【盐 求自动地抽题，首先必须要让系统了解用户要求。用户对试卷的要求往往是模糊的， 组卷算法首要解决的问题就是将这种模糊的要求量化，转化成计算机可以理解的要 求，也就是将用户的要求转化戍对试卷指标的具体要求，如考试目的、考试时问、( r 度要求、教学度要求、知识考祭范围等等。知道了用户对系统的这些指标的要求后 我们就只需要找到满足这些指杯要求的试题即可。如何找到这些试题呢? 一般有两种 思路嘲。一种是先从试题库中抽取试题，抽出试题后再验证它们是否和这些指标要求 相符合，若符合了，抽出的这些题就可以组成满足用户要求的试卷：若不符合了，则 继续抽取试题继续验证，直到符合为止。另外一种就是先分析这些指标要求，我们就 会发现用户对这些指标的要求是和用户对每一道试题的要求联系在一起的，因此我f f j 可以根据这种联系建立试卷模式，试卷模式就是用户要求的一种定量反映。我们可以 根据试卷模式分析出哪些试题的组合可以满足这个模式的要求，然后再在试题库中找 到这样的试题即可。后一种算法的思路显然可以避免盲目抽题，而且由于不需要多次 遍历试题库，也因此减少了抽题的时日j 。但是根据试卷模式如何分析出满足试卷模式 的试题组合呢? 这是后一种思路的难点，也是后一种组卷算法的核心和关键。以自u 宵 许多组卷系统都采取前一种算法思路，这种算法有许多明显的缺点，我们在试卷模式 的基础上建立了一个最接近用户要求的多目标优化的数学模型，然后对试卷模型进行 求解，求出的解即是满足当前试卷模式下的各道试题的具体指标要求值，然后在题库 中找到和这些指标值相符合的试题即可为了保证组卷效率以及试卷的质量，抽题过 程中要结合依赖于课程知识结构图的知识点优先入选算法，同时也要考虑到试题的抽 题次数和上次抽题时间的问题，这样才能组成一份合格的试卷。 简单的说，组卷算法的原理就是：首先将用户要求量化成试卷模式：然后基于试 卷模式建立组卷的数学模型，并对模型进行求解：最后根据求出的解在试题库中找到 和求出的解一致的试题即完成了组卷。 7 太原理工大学硕十研究生学位论文 2 3 自动组卷问题数学模型的建立与求解 由组卷系统所生成的试卷必须符合考试学的基本原理，符合各具体课程教学大纲 的要求，同时还必须符合考试组织者( 即用户) 对本次考试的具体要求。对于组卷系统 来说，上述三方面的要求并不是明确给出的，它们只是对命题试卷的一种模糊的约束。 因此，组卷系统的前提是必须能够将这种模糊的约束量化成系统能够使别的具体的试 题指标和试卷指标。一份试卷要控制的指标有很多，对这些指标的控制构成一份试卷 的各种“专家曲线”( 也称分布列) 。全部专家曲线又组成了试卷模式。对任何组卷系 统来说，其功能的实现都必须经过获取用户要求、根据用户要求建立相应的试卷模式、 根据试卷模式建立组卷算法的数学模型和对数学模型进行求解从而实现抽题组卷这 四个步骤。试卷模式是对用户要求的一种定量的反映，是建立组卷数学模型的基础， 也是整个组卷算法的基础。组卷模型建立的好坏关系到求解的难易程度以及整个组卷 算法实现起来的难易和速度的快慢。因此，要实现自动组卷算法必须首先建立自动组 卷的数学模型。能够将这种模糊的约束量化成具体的试题和试卷指标0 1 。 2 3 1 试题指标和试卷指标 试题指标是建立组卷系统中的试题库，实现计算机自动组卷的关键，实践证明试 题本身含有固定的特性指标，因为每个试题含有一定难度、涉及的范围、测量的能力 等内在的特性。这种特性可用一定的指标来描述，这些指标具体介绍如下。 ( 1 ) 试题类型 试题类型有多种划分形式，一般指从试题形式上区分，或者从解答的方式上划分。 ( 2 ) 试题难度 在试卷命题过程中，针对不同的考试对象，不同阶段的考试，命题难度也不同， 所以，应在试题库中增加难度系数，这也是每个试题库几乎都要考虑的结构。本设计 中试题的难度分为5 个档次，分别为：难、较难、一般，较易、易，这些都是模糊的 指标，它f f j 代表相应的试卷得分率为3 2 5 5 5 、5 5 7 2 5 、7 2 5 8 5 、8 5 9 2 5 、 8 太原理工大学硕士研究生学何论文 9 2 j 。9 5 。 ( 3 ) 解答时m 试题的解答时间可以以分钟为单位，取值区间 0 ，t m a x ，t m a x 为最大的时间取 值。 ( 4 ) 涉及内容 试题涉及的内容可以按层次划分，如块大类、中类、小类等。内容可按课程的篇 章、细目：也可以按知识点划分，也可以混合两种方法进行。一道试题可能涉及多个 内容，涉及的程度可用一个关于这些内容的比例分布来表示。 ( 5 ) 已出题次数 ， 在试题库中加入已出题次数及最近一次出题时间字段，这样，每次进行自动命题 时，将出题次数较少且最后一次出题时间与当前时问相距较远的试题选出，可以使本 次命题题目尽量不与往次命题重 复，提高命题质量。 ( 6 ) 区分度 试题的区分度就是鉴别度，它是衡量试题对考生的知识能力水平鉴别和区分程度 的指标。区分度好的试题能够把不同水平的被试者有效的区别) l ：来，计算区分度的方 法有多种，常用高低分分组分析法。 q = ( h - l ) i f ( 2 - 2 ) 式中，h 为高分组学生在该题的平均分，l 为低分组学生在该题的平均分，f 为该题 的满分。评测标准：0 9 以上，优秀题目：0 3 0 9 ，良好题目：0 2 0 2 9 ，勉强合格：0 1 9 以下，差的题目。 ( 7 ) 教学要求度 指试题考察人们掌握知识的能力的程度。可分为”认识了解”、”理解应用”、分 析综合”等层次。其中，认识了解指对内容记忆，背诵了解，但未深刻理解，不会” 举一反三”：而理解应用指对内容可”举一反三”，深刻理解并应用：而第三层的”分析综 合”是对内容更高一层的理解，并可对其透彻的分析综合。 9 奎堡堡三奎堂堡主塑塞竺堂垡鲨奎 ( 8 ) 分值 分值是每一道试题的满分值。对各种类型的题目可以设置不同的分值为了统一 通用，且考虑其他综合因素，对题分应限定最低、最高分数档及最小的分数档间隔， 它一般受到考试时间及试题难度的影响。 ( 9 ) 试题内容的相关性 试题内容的相关性主要是指在命题时避免相同的试题太多，而无法对学生所学f f 知识进行全面的考核，要对题目的相关性进行定量，引入相关性系数n ，对每门课程 其题目的r i 范围为o l o 。 建立题库的目的就是为了克服在命题中人为的主观性和片面性，提高试题命题f i 客观性和科学性，以及命题的质量和效率。同样试卷指标也是控制计算机自动命题屈 量的关键，因此对试卷指杯有一个清晰的概念也是十分必要的。根据用户对组卷系彰 的要求信息及课程教学专家经验，试卷指标主要表现在：难易程度( 难度、方差或刀 格率) 、区分度、效度( 包括内容效度、结构效度、标准相关效度) 、信度、考试目白 和考试对象。 2 3 2 试卷模式的建立 试卷各篇章内容所占分数的比例与教学时数成正比，由考试大纲决定，覆盖面雪 广，每个知识单元都要出题，若考试内容较窄时，则根据知识点的权重取舍，但也可 根据用户要求自行决定。根据平均难度计算出了各个不同难度试题的分数后，再综雀 考虑不同教学要求度的试题分数和不同内容范围的试题分数，就可以建立当的试卷移 式。当前试卷模式的具体描述如下。 ( 1 ) 满分值m f z 答题完全正确所获得的试卷总分，通常为1 0 0 分。 ( 2 ) 试卷的预估时间 可用于控制试卷的试题数量和试题的难度，默认为1 2 0 分钟。 ( 3 ) 题型及分数 1 0 太原理f ：大学硕士研究生学位论文 包括试题类型的敛量、每种题型的总分值和每种题型下的试题数量。 设有m 种题型的集合为：t x = 1 ，2 ，m ，在试卷中的第k 种题型的总分值也为 t k ( k = l ，2 ，m ) ，有 m f z = ，l + ，2 十+ f 。 ( 2 3 ) 通常给出在试卷中的第k 种趣型的敛量：s 。( k = l ，2 ，m ) ，这样可得第k 种题，掣的每 个试题的分数 z = t k s k ，k = l ，2 ，m ( 2 - 4 ) ( 4 ) 难度分布 指不同等级的入选试题占试卷总分的百分比分布。设等级n = l ，2 ，p ，我们 期望第i 种难度的总分值为：矾( i = l ，2 ，p ) ，与满分值关系 m f z = a i + 口2 + + 口。 ( 2 5 ) ( 5 ) 范围分布 指入选试题所测试的内容和具体的知识点范围占试卷总分中的分数百分比。设范 围集合为f _ l ，2 ，q ，我们期望第j 种范围的总分值b ，( j 一1 ，2 ，q ) 与满分值关 系 。 m f z = 岛+ 5 2 + + 吃 ( 2 6 ) ( 6 ) 能力分布 指入选试题所测试考生的能力占试卷总分中的分数百分比，能力集合 1 = l ，2 ，r ) ，我们期望第k 种能力的总分值c 。( k = 1 ，2 ，r ) 与满分值关系 m f z = c l + 乞+ + c ， ( 2 7 ) 从题库中抽题组卷要考虑诸多因素，如：为使所选题目在近几年不重复，势必对 下次选题产生影响：所选题目应涉及大部分章节；重点章节应占较多比例：难易题目应 有比例搭配，题目类型要有多样性、可变性等。究竟该选什么样的题目，是一个决策 问题。一般来讲，决策问题的类型有确定性、风险性及不确定性。在抽题组卷过程中， 太原理工大学硕十研究生学位论文 选择题目问题属不确定型。我们解决的方法是建立当前试卷模式，从而利用试卷中的 题型、难易度、教学要求度、题目的重复度等等条件一一加以限制约束，将不确定型 转化为确定型。 2 3 3 组卷数学模型的建立 在组卷之前，我们首先为自动组卷过程建立控制指标相应状态空间： s = 巴 s 的每一行由某一试题的控制指标组成，如题号、题型、章节、难度等，并且这 些属性指标都进行编码表示成二进制形式，而每一列是题库中的某一指标的全部取 值。这些控制指标可以大致分为以下九项：( 1 ) 知识范围，试题内容所属的知识篇章范 围：( 2 ) 题型，试题的题型有选择题、填充题，计算题、证明题、改错题、问答题、判 断题等等；( 3 ) 层次，反映该题对教学内容的要求层次，分为掌握了解理解：( 4 ) 难度系数，n d x s = i - ( 平均分该题满分) ：( 5 ) 难度级别，分为容易、中等、较难和难题： ( 6 ) 要求，试题对学生知识和能力的要求：分为知识运用灵活应用( 7 ) 区分 度，试题对考生的知识能力水平鉴别和区分程度的指标：( 8 ) 估时，估计答题时间：( 9 ) 题分，试题的分数。 矩阵s 的列元素的分布分别满足用户指定的试卷的总体要求，即各篇章所占的分 数、试卷中各种题型的题数、反映不同教学层次要求的试题所占的分数比例、各种难 度的试题所占的分数比例、各种区分度的试题所占的分数比例、所有试题的估时总和、 所有试题的分数总和这些指标都应等于用户指定的要求或误差最小。在实际应用中， 设定整卷指标f 来综合反映这些个指标与用户要求的误差，由于它们的重要程度不 同，因此整卷的指标就是这些个指标的加权和，同时为了不至于各个误差相互抵消， 这些指标与用户要求的误差都取绝对值。设厂为整卷指标，用下式表示； 1 2 p ( 、， 钆； 太原理工大学硕十研究生学付论文 厂= z ( 2 9 ) i t l 其中，表示第i 个指标与用户要求的误差的绝对值，表示第i 个指标的权值。 组卷就是从题库中抽取试题，使得整卷指标最小。f 1 标状态矩阵应满足如下 条件： m f z = t j + t 2 + + ，卅 ( 2 一l o ) m f z = q + a 2 + + ( 2 1 1 ) m f z = b l + 6 2 + + 吃 ( 2 一1 2 ) m f z = c l + c 2 + + c ， ( 2 - 1 3 ) 五= t k i s k ( 2 - 1 4 ) 式中，试卷总分m f z 和考试时间为系统默认值，也可以由用户指定：题型及分数包括 题型的数量、每个题型的总分值和每个题型下的试题数量，依赖于用户的输入，在试 卷中第k 种题型的总分值、试题数量及该题型下每道题的分数分别用t 。s 。和 f k ( k ：l ，2 ，n 1 ) 表示：难度分布的问题在前面已作解释，第i 种难度的试题总分值用 a ( i = l ，2 ，p ) 表示：范围分布指入选试题所测的内容和具体的知识点范围占总分数 的百分比，第j 种范围的试题总分值用b j ( j = l ，2 ，l ，q ) 表示：能力分布指入选试题所 测试考生的能力占总分数的百分比，在试卷中第k 种能力试题总分值用 c k ( k = l ，2 ，r ) 表示。 公式( 2 一l o ) 至公式( 2 1 4 ) 表明组卷问题是一个多重约束目标求解的问题。我们可 以把组卷要求看成是试卷目标，它是通过试卷模式中各个参数的取值来体现的，因此 可以把各个试卷参数取值的限定作为实现自动组卷的多个目标。公式( 2 - 1 0 ) 至公式 ( 2 一1 4 ) 就可以看作是多个目标函数 多目标优化的数学模型一般为 ( v p ) r a i n f o ) ( 2 1 5 ) 1 3 太原理工大学硕士研究生学位论文 式中，f ( 力= ( 彳( x ) ，正( x ) ，l c x ) ) 7 ，f a x ) ，i - - 1 ，2 ，p 为第i 个目标 g c x ) = ( g i ( 力，9 2 ( x ) ，g ，( 砌7 ，g j ( x ) ，j = l ，2 ，n 为第j 个约束函数 d = x i g f ( x ) o ，i = l ，2 ，打 ( 劢) 础f ( x ) 表示向量极小化，即向量f ( x ) = ( 石( 功，五( 砷，六( x ) ) 7 中的各个子目标函数，( x ) ，f = l ，2 ，p 尽可能的极小化的意思。 可以试着将公式( 2 1 0 ) 至公式( 2 1 4 ) 转化成类似公式( 2 一1 5 ) 的一般多目标优化 的数学模型。称完全达到目标值为“硬约束”，不完全达到目标值为“软约束”。引入 正、负偏差变量，分别表示超过目标值和未达到目标值的部分。d a 。+ 与d a 。分别表示 试卷中所有具有第i 种难度的试题分数之和相对于第i 种难度要求的分数值a 的订、 负偏差变量：d b ；与d b ，。分别表示所有具有第j 种范围的试题分数之和相对于第j 种范 围要求的分数值b ，的正、负偏差变量：d c 。+ 与d c f 分别表示所有具有第k 种能力的试题 分数之和相对于第k 种能力要求的分数值c k 的正、负偏差变量。同时引入变量x 。 用来表示在试卷中第i 种难度、第j 种范围、第k 种能力和第1 种题型的试题数量。 这样我们就可以把公式( 2 8 ) 至公式( 2 - 1 2 ) 表示的完全达到目标值的“硬约束”转化 成尽量使偏差变量的绝对值较小的“软约束”，也就是说尽量使各种难度的、各种范 围的、各种能力要求的试题的正负偏差变量之和较小。因此可以将公式( 2 1 0 ) 至公式 ( 2 一1 4 ) 转化成含有一定约束条件的多目标优化模型。对于本课题来说，具体的目标有 三个 m i l l 彳：兰( 妃+ + d a , ) ( 2 1 6 ) m i n 正：妻( 呜+ + 呜一) ( 2 1 7 ) l = l r a i n f 3 = ( 蛾+ + 蛾一) ( 2 1 8 ) 建立了以下的多目标优化的自动组卷数学模型 1 4 太原理1 人学硕士研究生学位论文 m i 。，：( 石，五，六) ：( 芝( 也+ + d a , 一) ，主( 鸡+ + 鸭) ，主( 地+ + 蛾一) ) ，= lj = l件l 其约束条件为： 4，h 彳铂+ d a ，一d a ，+ = i = 1 2 ，p pr月 z 。+ 呜一一呜+ = 6 j ，= l 2 ，g i - i t 。i - l ，g ， = 墨，= l 2 卅 i - ij - i = l 妃+ d q 一= 0 ，a a , + ，d a , o ，i = 1 , 2 ，p 也+ 孵= o ，呜+ ，蚂o ，- ，= 1 ，2 ，q 呶+ d c k 。= o ，d c k + ，如一0 ，k = 1 , 2 ，r x v l d - 0 ，= 1 ，2 ，月 2 3 4 运用遗传算法对自动组卷数学模型求解策略分析 ( 2 - 1 9 ) 上一节建立的自动组卷数学模型是一个多目标优化的数学模型。对这个模型的求 解是我们设计的这个组卷算法的关键。是否能求出解以及求解的快慢直接影响到算法 能否实施以及算法的快慢1 。本节中探讨该自动组卷模型的求解方法及遗传算法用于 求解的诸多优点。 多目标优化( 印) 最优解分为绝对最优解，、有效解；、弱有效解；，使每个 分量z ( x ) ，i - 1 ，2 ，在d 上最优，；使d 中找不到z 满足每个分量不比f ( 工) 的相应 分量坏，即血d ，w ( x ) z ( x ) ，( - ) ，表明孤d ，玑，厶( 力 厶( - ) 。解；使d 中 1 5 2 = q i l 如 一 叱材 z 。 ，一 圭m 太原理工大学硕十研究盐学位论文 不存在x 满足，( 力 厶( - ) 。解；使d 中 不存在x 满足f ( 力 一 岛乃 x ，、l = 一dx 石 啤m 太原理工大学硕十研究生学仿论文 舶， 聋溉班删) 直至 他， 聋麓吖嗨川2 扩1 ) ) 式中，i = l 2 ，p - l ，t 是充分小的正数，作用实际上是牺牲一些第i + 1 个目标以前 的最优值，获得第i + 1 目标较好的最优值，它的取值范围要根掘实际问题需要来调节。 3 1 3 评价函数法 。 前两种方法中的单目标函数是从多目标函数中选出的，而评价函数法则是使用新 构造出来的评价函数作为单目标函数。 1 理想点法 在约束区域d 上找一个点x ，使各目标在x 处的值与相应单目标的最优值越近越 好，通过构造一个单目标规划来确定x 。首先求出每一个单目标规划的最优值，即 r a m i nf a x ) = ，( f 1 2 ”p ) 令评价函数即单目标规划的目标函数为 ( ，( x ) ) = 厅( 石( z ) ，石( 功( x ) ) = ( ( z ( 曲一z ) 2 ) “2 再求单目标规划r a 。i n ( ，( x ) ) 的最优解。 2 虚拟目标法 与理想点法类似，只是把z 换成r 。取值可小于z ，接近程度可用相对误 差描述，取o ，且对每一个江1 2 - 矿满足f m 。i n f a x ) ，令评价函数为 咿哕= 舢州啊胛 2 2 l 太原理i ：大学硕士研究生学位论文 求m 唤矗( ，( 力) 得最优解。 聪廿 上述求解多目标优化优化的算法各有各的长处，也各有各的适用范围，也各有各 的限制 3 1 4 权重系数变化法 权重系数变化法是对一个多目标优化问题，给其各个子函数，( x ) ，i = l ，2 ，p 赋 予不同权重心，i = 1 ，2 ，p ，w ，的大小代表相应的子目标z 在多目标优化问题中的 重要程度，各个子目标函数的线性加权和可表示为2 ，盯( x ”；杰w z ( 功，f ：1 ，2 ，p 以 i = l 此线性加权和作为多目标优化问题的评价函数，则多目标优化问题可转化为单目杯优 化问题。权重系数变化法就是在这个评价函数的基础上，对每个个体取不同的权重系 数，就可以利用通常的遗传算法来求出多目标优化问题的多个如最优解。 3 2 遗传算法简介 3 2 1 概述 生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规 律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全 局优化算法。 遗传算法的概念最早是由b a g l e y j d 在1 9 6 7 年提出的；而开始遗传算法的理论和 方法的系统性研究的是1 9 7 5 年。这一开创性工作是由m i c h i g a n 大学的j h h o ll a n d 所实行。当时，其主要目的是说明自然和人工系统的自适应过程。 遗传算法简称g a ( g e n e t i c a l g o r i t h m ) ，在本质上是一种不依赖具体问题的直接 搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制， 自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们 太原理f 人。硕士研究生学位论文 认为“遗传算法、自适应系统、细胞i 动机、混沌理论与人工智能一样，都是对今后 十年的计算技术有重大影响的关键技尜”。 3 2 2 遗传算法的基本概念 遗传算法的基本思想足基于d d r “in 进化论和m e n d e l 的遗传学说的。 d a r w i