（计算机应用技术专业论文）智能组卷系统的研究与实现.pdf

摘要 随着互联网和计算机技术的发展，教育领域与计算机技术更加紧密 地结合，越来越多的教学内容正在电子化和网络化，在教学活动中一直 扮演重要角色的考试环节也发生了巨大的变化，使用计算机化的考试系 统可大大缩短考试周期，减少教师重复劳动，提高工作效率。而其中的 智能组卷系统能提高试卷质量，增加考试的科学性和客观性。 在智能组卷系统中，一个非常重要的课题是怎样在已生成的试题库 中根据教师和教学的要求自动生成试卷。目前已经出现了多种算法用于 自动组卷，有优先权算法、随机抽取算法、回溯试探算法、遗传算法等， 这些算法在大解空间、多峰值的问题上往往容易陷入局部最优或算法复 杂度过高。 论文首先分析了试卷的评价指标、各项指标的作用及几个重要指标 间的关系。在此基础上采用各种指标的加权和构建了组卷的总体评估函 数。 然后针对传统遗传算法的后期搜索效率低并极易出现未成熟收敛 的情况，提出了一种渐进式遗传算法，该算法包括了组卷策略、编码方 案、适应度函数的确定，选择交叉变异算子及遗传算法的实现等。并将 混沌理论引入到遗传算法的交叉操作和选择操作中。通过实验对渐进式 遗传算法的全局搜索性能、效率和有效性进行了验证。实验表明，进式 的遗传算法在全局搜索性能及收敛速度上较传统遗传算法有显著提高。 论文最后采用c 稃和a c c e s s 数据库，设计并实现了相应的基于渐进 式遗传算法的组卷软件，并且进行了大量组卷测试。测试结果表明渐进 式遗传算法组卷速度快，组卷质量较好，组卷成功率也高于传统遗传算 法，该算法是合理、有效的。 关键词智能组卷，加权离差模型，渐进式遗传算法，混沌遗传算法 a b s t r a c t w i t ht h ei n t e r n e ta n dc o m p u t e rt e c h n o l o g yd e v e l o p i n g ，t h ef i e l do f e d u c a t i o ng o e sc l o s e ra n dc l o s e rt ot h ec o m p u t e rt e c h n o l o g y , a n dm o r ea n d m o r eo ft h et e a c h i n gc o n t e n t sb e c o m ec o m p u t e r i z a b l e ，t h ee x a m i n a t i o n l i n kw h i c hh a sp l a y e da l li m p o r t a n tr o l ei nt e a c h i n ga n dl e a m i n ga c t i v i t i e s h a sa l s ou n d e r g o n eag r e a tc h a n g e ，t h eu s eo fc o m p u t e r i z e de x a m i n a t i o n s y s t e mc o u l ds i g n i f i c a n t l yr e d u c et h ee x a m i n a t i o nc y c l e ，r e d u c ed u p l i c a t i e w o r ko ft e a c h e r s ，a n d i m p r o v i n gw o r ke f f i c i e n c y u s i n g t e s t p a p e r a u t o g e n e r a t i o ns y s t e mc a l le n h a n c et h eq u a l i t yo ft h ep a p e r sa n di n c r e a s e t h ee x a m i n a t i o no ft h es c i e n t i f i ca n do b j e c t i v e i nt h et e s tp a p e ra u t o - g e n e r a t i o ns y s t e m , av e r yi m p o r t a n ti s s u ei sh o w t h eq u e s t i o n sw o u l db es e l e c t e di na c c o r d a n c ew i t ht h er e q u i r e m e n t so f t e a c h e r sa n dt e a c h i n gw o r kt og e n e r a t ed e s i r e dp a p e r s a tp r e s e n tt h e r eh a s b e e na v a r i e t yo fa l g o r i t h m sf o rt e s tp a p e ra u t o g e n e r a t i o n , s u c ha sp r i o r i t y s t r a t e g y , r a n d o ms a m p l i n gs t r a t e g y , r e t r o s p e c t i v et e s t i n gs t r a t e g i e s ，g e n e t i c a l g o r i t h m s b u tt h e s ea l g o r i t h m so f t e nt e n dt of a l li n t ot h el o c a lo p t i m a l p o i n to rs p e n dt o om u c ht i m eo nt h ei s s u eo fh u g es o l u t i o ns p a c eo r m u l t i - p e a kp r o b l e m s i nt h et e x to ft h i sp a p e rw ea n a l y s ea l lk i n d so fe v a l u a t i o nf a c t o r s , t h e e f f e c to ft h e s ef a c t o r sa n dt h er e l a t i o n s h i pb e t w e e nt h e m o nt h eb a s i so f t h e s ek n o w l e d g ew ea d o p tt h es u mo ft h ew e i g h t e di n d i c a t o r st oc o n s t r u c t f i t n e s sf u n c t i o no ft e s tp a p e ra u t o - g e n e r a t i o na l g o r i t h m a i m i n g a ti n e f f i c i e n ts e a r c ha n dv u l n e r a b l e e m e r g i n g i m m a t u r e c o n v e r g e n c eo ft h eb a s i cg e n e t i ca l g o r i t h m ，t h i sp a p e rb r i n g sf o r w a r dan e w p r o g r e s s i v eg e n e t i ca l g o r i t h m t h ea l g o r i t h mi n c l u d e st h e t e s tp a p e rs t r a t e g y , c o d i n gs c h e m e s ，t h ed e t e r m i n a t i o no f f i t n e s sf u n c t i o n , s e l e c tc r o s s m u t a t i o n o p e r a t o r , a n dt h er e a l i z a t i o no fg e n e t i ca l g o r i t h m s ，a n du s e sc h a o st h e o r yi n c r o s so p e r a t o ra n da b e r r a n c eo p e r a t o ro fg e n e t i ca l g o r i t h m s t h r o u g h e x p e r i m e n t st h i sp a p e rv e r i f i e st h eg l o b a ls e a r c hp e r f o r m a n c e ，e f f i c i e n c ya n d e 毹c t i v e n e s so ft h ea l g o r i t h m t h ee x p e r i m e n t ss h o wt h a tt h ep r o g r e s s i v e c h a o sg e n e t i ca l g o r i t h mh a ss i g n i f i c a n t l yi m p r o v e di n t h eg l o b a ls e a r c h p e r f o r m a n c e a n dc o n v e r g e n c er a t 己 ， u s i n 2c 群a n da c c e s sd a t a b a s et e c h n o l o g y , t h i sp a p e r d e s i g n sa n d r e a l i z e st h ec o r r e s p o n d i n gt e s tp a p e ra u t o g e n e r m i o ns o f t w a r eo n t h eb a s eo f g r a d u a lg e n e t i ca l g o r i t h m t h ee x p e r i m e n t a lr e s u l t ss h o w t h a tt h eg r a d u a j g e n e t i ca l g o r i 吼i sr a p i da n d t h ep a p e rq u a l i t yi sg o o d ，a n dt h es u c c e s s r a t e i sa l s oh i g h e rt h a nt h a to ft r a d i t i o n a lg e n e t i ca l g o r i t h m ，s o t h ea l g o r i t h m1 s r e a s o n a b l ea n de f f e c t i v e k e yw o r d st e s tp a p e ra u t o g e n e r a t i o na l g o r i t h m ，w e i g h t e d d e v i a t i o n s m o d e l ，g r a d u a lg e n e t i ca l g o r i t h m ，c h a o sg e n e t i ca l g o r i t h m i i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的 同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：盔盗宴 日期：翌壁年羔月2 翼 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学 位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以 采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络 向社会公众提供信息服务。 作者签名：垄垒窆、导师签名! 塾兰垒三日期：旦坠- 年月盟日 硕士学位论文第一章绪论 第一章绪论 在学校教学工作中，考试是其中的一个重要环节。特别是在中学，测验和模拟 考试显得尤其重要。每次考试为了能出一份难易适中，又能体现对能力和知识点全 面考察的试卷，教师需花费相当多的时间和精力。即使如此，也很难保证所出的试 卷的科学性、合理性，甚至可能会出现试卷偏难或偏易的现象，达不到预期的考察 目标。智能组卷系统通过建立标准化题库系统，能解决试题的科学性问题，提高试 题质量。智能组卷系统的试题库建设要根据考试大纲要求和教育测量学理论来进行 命题，具体要求是：要给出每道试题的难度系数，保证试题的科学性；试题要有一 定的覆盖面，体现教学要求；给出每一道试题的参考答案和评分标准；为减少抽取 试题重复率，题库应保持一定的试题数量。而大多数传统考试没有建立标准化题库， 教师出卷的随意性较大，造成试题的科学性存在一定问题。智能组卷系统能适用于 各种题型，组卷效率高。无论是什么科目，只要按要求建立好标准化试题库，就可 以利用该系统进行随机抽题组卷。 1 1 智能组卷系统研究的目的及意义 随着计算机技术的飞速发展和社会信息化水平的不断提高，计算机在教学领域 也得到了广泛的应用。计算机辅助评价在教育、教学和学习评价过程中的应用，引 发了评价内容、方法和形式的深刻变革。开发、应用能够整合教育测评理论、方法 和现代信息技术手段的智能组卷系统，为学生个性化学习提供“灵活、方便、科学、 公平”的“个别化学习测评服务”， 已成为教育工作者所面临的一项重要任务。通 过智能组卷系统可对学生的学习进行考核，了解学生的学习效果，为改进教学提供 依据；对试题库的及时更新和维护，保证试题库中的试题更好地适应教学要求，在 考试时就可减少老师的出卷工作量，提高老师的工作效率。 本课题是为解决现有考试系统组卷模块难以满足实际考试需求这一问题提出 的。目前，考试系统在组卷方面远远不能满足实际考试的需求，为了得到满足要求 的试卷，很多系统都还必须采用手工组卷的方式生成试卷，这使得考试系统的效率 大打折扣。解决组卷这一难题，对于合理高效地利用现代化手段进行教育教学，实 现考试规范化，减轻教师工作量，提高教学效率和质量具有重要的实际应用价值。 本人希望通过本课题的研究，开发出一套切实有效的智能组卷系统，能在实际学院 硕十学位论文 第一一章绪论 教学科研方面起到辅助功能，提高现代教育技术水平。 1 2 智能组卷算法的研究现状 计算机辅助考试在美国诞生，历经多年，已经在国外得到了广泛的应用。国外 有许多专门的考试机构采用计算机辅助测试对参加考核的对象进行评价。著名的考 试机构有美国思而文学习系统有限公司( s y l v a nl e a r n i n gs y s t e m si n c ) ， 它在世界 的6 大洲1 4 0 多个国家和地区有2 2 0 0 多个考试中一t 3 。当今大部分的授证机构均委托思 而文公司为其进行测试、评估。如全球领先的计算机公司的授证考试以及对医护人 员的专业测试、对美国飞机驾驶员( f a a ) 的考试等。世界上最大的考试机构一美 国教育考试服务中心( e t s ) 从1 9 9 3 年开始在研究生入学考试中采用自适应考试模 式，同时逐步减少纸卷一笔试为基础的考试方法。在信息产业中，美国n o v e l l 公司 于1 9 9 1 年成功的应用了c a t 进行认证考试，使参i j n n o v e l l 自适应考试的人数超过了 l ，0 0 0 ，0 0 0 人次。 我国政府非常重视现代远程教育工作，在全国教育考试科研工作“十五 规划 中，明确要求教育考试的科研工作要在教育评价体系中发挥重要作用，在考试研究 领域创造出与我国教育事业蓬勃发展相适应的成果，以全面提高教育考试质量，为 改革和完善教育考试制度工作服务。目前，我们国家已经开展了建立题库的工作， 一系列实用的题库系统己经陆续建立，如高等教育基础学科系列题库、国家医学水 平考试题库等。目前部分高校已联合开发了一些基础学科的试题库系统，但就使用 范围而言，这些系统大多是某一学科的“专用题库”，而且有很强的封闭性，不能根 据自己学科的实际情况进行调整，缺乏可扩充性和灵活性。这样，同一所学校要实 现所有学科的计算机命题成卷，就必须为每一学科都开发或购置一套相应的试题库 系统，这就必将导致大量的重复性劳动、浪费大量的资金。显然这种系统在一定程 度上给人们的使用带来不便，也阻碍了系统的推广。在国内，从组卷方面看，现有 的试题库系统大体分三种：一种是将试题库看作试题集，命题时由具有丰富经验的 教师逐题抽取。二是将试题库看作试卷集，将已经出好的试卷存储起来，在组卷时 任意抽取一份。三是有自动形成试卷的功能，利用某种组卷策略，自动形成合理的 试卷。前两种虽能保证试卷质量，但第一种与人工命题无异，第二种只能出有限份 试卷，第三种则是随机出题，又有组卷策略可遵循，会形成千变万化的试卷，但所 使用的组卷技术和策略有优有劣。 组卷系统是考试系统的核心，也是题库系统的重要组成部分。自本世纪6 0 年代 硕士学位论文第一章绪论 出现计算机辅助教学系统( c a i ) 和智能计算机辅助教学系统( ( i c a i ) 开始，最近2 0 多年来组卷系统发展迅速，计算机技术等新技术、人工智能、信息处理技术和数据 库系统的迅速发展也给组卷系统的发展提供了新的发展动力。智能组卷问题涉及算 法分析、数学建模、优化控制、人工智能等诸多领域。为了提高计算机考试系统组 卷模块的实用性及有效性，组卷算法研究成为计算机考试系统研究的一个重要方面。 2 0 世纪8 0 年代中后期，荷兰的林顿等人针对组卷问题的特点率先把随机线性规划 法引入测验编制领域，经过十几年的发展，产生了多种以线性规划为基础的智能组 卷算法。其中具有代表性的有优先权算法、随机抽取算法、误差补偿算法位1 、回溯 试探法捌及遗传算法等h 1 。 1 2 1 优先权算法 这种算法从数量、题型的平均分数、完成率和累计值与指标值差距四个方面综 合解决了在选题组卷开始阶段，由于各项属性都有较大的取值范围，指标间的牵涉 问题反映缓慢，随着试题增加取值逐渐缩小的矛盾。 1 2 2 随机抽取算法 随机抽取法哺1 是最常用的组卷算法，它根据状态空间的控制指标，由计算机随 机地抽选一道试题加入试卷中，此过程不断重复，直到组卷完毕，或己无法从试题 库中抽取满足指标的试题为止。随机策略有两种情况：一是从试题库中随机抽取试 题，然后判断是否符合试卷的约束条件；二是从符合试卷某项要求的试题库子集中 随机抽取试题，然后判断是否符合试卷的其它约束条件。 这种方法结构简单，对于单道题的抽取运行速度较快，但是这种方法的效率不 高，最主要的问题是要求试题库不但试题量大，而且要分布良好。若要完整地组成 一份试卷，其时间复杂度较大，而且在复杂的组卷条件下，常常由于约束条件的局 部失配而导致组卷失败。因此，该算法只适用于组卷约束条件较少的小型试题库系 统的组卷。 1 2 3 误差补偿算法 误差补偿算法哺1 就是在试题生成过程中当不满足约束条件时，适当地放松约束 条件，让试题生成在允许的误差区域内完成。这种策略在允许一定误差的前提下减 少不必要的循环搜索，提高组卷的效率和成功率，解决在实际组卷过程中由于指标 问的相互牵制和试题库题量的有限性容易使计算机的筛选陷入死循环的问题。 1 2 4 回溯试探算法 回溯试探算法是对随机抽取法的改进，它将随机选取产生的第一状态记录下来， 如果搜索失败时，释放上次记录的状态类型，然后再根据一定的规律变换一种新的 硕叶中位论文第一章绪论 状态进行试探，通过不断地回溯试探直到试题生成完毕或回到出发点为止。 回溯法对于约束集r 维数小的组卷模型( 即组卷指标简单的试卷) 而言，组卷 成功率较高。但是这种算法对内存的占用量很大，程序结构相对比较复杂，而且选 取试题缺乏随机性，组卷时间长。按照上面提到的三种方法选取试题，随着选题数 的增加、指标间的约束增大，选出来的试题可能不是最优的，此时回溯法往往是行 之有效的，充分利用这一方法一般都能成功地生成试卷。但是其组卷速度较慢，而 且难以满足所有约束条件盯1 。 1 2 5 遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 阻1 是一种模拟自然选择和自然遗传机制的 随机优化算法，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不 依赖于梯度信息，因而对目标函数没有可微的要求( 目标函数可以是离散的) 。它尤 其适用于处理传统搜索方法难于解决的复杂问题和非线性问题。是目前自动组卷中 常用的算法。 1 遗传算法的发展历史 遗传算法早期的研究工作始于本世纪6 0 年代。5 0 年代末6 0 年代初，一些生物 学家开始利用计算机对遗传系统进行模拟。在此期间，h o l l a n d 正在从事自适应系统 的研究，受生物学家们模拟结果的启发，他首次应用模拟遗传算子来研究自适应性 中的人工问题。6 0 年代中期，h o l l a n d 在f r a n s e r a s 和b r e m e r m a n nhj 等人工作的 基础上提出了位串编码技术。这种编码技术既适用于变异操作，又适用于交叉操作， 并且强调将交叉作为主要的遗传操作。随后，h o l l a n d 将该算法用于自然和人工系统 的自适应行为的研究中，并于1 9 7 5 年出版了其开创性著作“a d a p t a t i o ni n n a t u r a la n d a r t i f i c i a ls y s t e m s ”。以后，h o l l a n d 等人将该算法加以推广，应用到优化及机器学习 等问题中，并正式定名为遗传算法。遗传算法的通用编码技术和简单有效的遗传操 作为其广泛、成功地应用奠定了基础。 自1 9 7 5 年以来，众多学者对遗传算法的编码方式、选择方式、交叉机理和参数 控制的确定等进行深入的探究，引入了自适应等各种策略以改善遗传算法的性能， 提出了各种改进的遗传算法，像分层遗传算法、c h c 算法、自适应遗传算法、基于 小生境技术的遗传算法、混合遗传算法和并行遗传算法等，并将之成功地应用于各 种优化问题中。 遗传算法适用于最优化问题，归功于h o l l a n d 的学生d ej o n g 旧1 ，而g r e f e n s t e t t e 开发了第一个遗传算法软件g e n e s i s ，为遗传算法的普及推广起了重要作用。对遗 传算法研究影响力最大的专著，属于1 9 8 9 年美国伊利诺大学的g o l d b e r g 所著的 4 硕士学位论文第章绪论 “g e n e t i ca l g o r i t h m si ns e a r c h ，o p t i m i z a t i o n ，a n dm a c h i n el e a r n i n g 。这本书对遗传 算法理论及其多领域的应用展开了较为全面的分析和例证。1 9 9 4 年，m i c h a l e w i c z n 出版了另一本很有影响力的著作“g e n e t i ca l g o r i t h m s + d a t as t r u c t u r e s = e v o l u t i o n p r o g r a m s ”，对遗传算法应用于最优化问题起到了重要的推动作用。 2 0 世纪9 0 年代，人们提出了很多新的遗传算子，并对其进行了深入的研究。 本质上，种群各代之间的差异通过下面几种方法来获取并保持下去：交叉、变异、 基因插入、复制、删除和移动等过程n 1 1 。h o l l a n d n 列除了使用交叉和变异两种算子， 还引入了倒置算子，倒置算子的思想在于产生次序关系以使得优良的序列能够更好 地保留。在h o l l a n d 之后，遗传算子的研究工作被导向了问题解空间n h 5 1 ，而算子 的研究则处于停滞状态，h o l l a n d 的倒置算子也被抛弃了。随着分子生物学的兴起， 一些学者m “刀在基因重组的启发下认为仍然需要研究更多的遗传算子。这些学者认 为类似于联结、换位、移植的算子应该加以仔细研究并将之应用于进化计算中。 f u r u h a s h i 等人n 射介绍了一个机器人避障问题的例子，在这个例子中，受细菌感染 机理的启发，提出了一种新的寻找模糊路线的感染机制。结论显示感染机制可以局 部改善染色体，能够更加有效地找到问题的解。y o s h i k a w a 等人n 卅和n a w a 2 等人 也用到了这种机制。h a r v e y 陋1 提出了一种简化的遗传算法一微生物遗传算法，在这 种算法中采用联结算子替代交叉算子。s m i t h 乜3 矗们采用同样的机制求解复杂的可满足 性问题，并提供了联结机制的另一种版本。s i m s e s 等人引入了一种基于转位子或跳 跃基因的新机制。这个被称为换位算子的新机制被证明是交叉算子的一个很好的替 代品。s i m s e s 进行了进一步的深入研究，并证实在正确选择遗传算法的参数时，用 换位算子替代交叉算子甚至可以用更小的种群获得更好的结果瞳羽，并对参数选择的 方法啪进行了深入的研究。 我国有关遗传算法、进化计算的研究，从2 0 世纪9 0 年代以来一直处于不断上 升的时期，特别是近年来，遗传算法、进化计算的应用在许多领域取得了令人瞩目 的成果心7 1 ，其中在基本遗传算法及其改进方面做了许多工作，已开发出许多应用系 统圆。在遗传算法的改进应用方面不少学者作了成功有效的搜索。周远晖乜钔等提出 了基于克服过早收敛的自适应并行遗传算法；熊辉等提出了基于神经网络的遗传 算法，宋维等口提出了一种与小生境技术和单纯搜索相结合的混合遗传算法；张著 洪等口2 1 提出了一种免疫算法：韩炜等侧提出了一种与单纯形法相结合的混合遗传算 法；唐巍等m 1 提出了一种混沌遗传算法，算法利用混沌运动的随机性、遍历性和对 初始条件的敏感性等特性进行群体的混沌初始化和最有个体的混沌变尺度载波寻 优；模拟退火和多种群并行遗传进化思想分别被引入遗传算法中阱1 ，也显现出良好 硕士学位论文第一章绪论 的应用前景。遗传算法在机理方面具有搜索过程和优化机制等属性，数学方面的性 质可通过模式定理和构造块假设等分析加以讨论，m a r k o v 链也是分析遗传算法的一 个有效工具。遗传算法的选择操作是在个体适应度的基础上以概率方式进行的，在 概率选择方式上与模拟退火有些类似。 2 遗传算法的特点 从数学角度看，遗传算法是一种搜索寻优技术，它从某一初始群体出发，遵循 进化规则，不断迭代计算，逐步逼近最优解。相对于枚举法、启发式算法和搜索算 法等传统的搜索和优化方法。遗传算法具有如下特点啪1 。 ( 1 ) 自组织、自适应和自学习性。应用遗传算法求解问题时，在编码方案、适 应度函数及遗传算子确定后，算法将根据“适者生存的自然选择策略利用进化过 程中获得的信息自行组织搜索。因而适应度大的个体具有较高的生存概率。适应度 大的个体具有更适应环境的基因结构，再通过基因重组和基因突变等遗传操作，就 可能产生更适应环境的后代。进化算法的这种自组织、自适应特征，使它同时具有 能根据环境变化来自动发现环境的特性和规律的能力，自然选择消除了算法设计过 程的需要事先描述问题的全部特点，并要说明针对问题的不同特点算法应采取的措 施。因此，利用遗传算法可以方便地解决那些复杂的非结构化问题。 ( 2 ) 遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目的点，而 不是单点。它的并行性表现在两个方面。一是遗传算法的内在并行性( i n h e r e n t a r a l l e l i s m ) ，即遗传算法本身非常适合大规模并行。这种并行处理方式对并行系统 结构没有什么限制和要求；遗传算法适合在目前所有的并行机或分布式系统上进行 并行处理，而且对并行效率没有太大影响；二是遗传算法的内含并行性( i m p l i c i t p a r a l l e l i s m ) ，由于遗传算法采用种群的方式组织搜索，因而可同时搜索解空间内 的多个区域，并相互交流信息。使用这种搜索方式，虽然每次只执行与种群规模n 成正比例的计算，但实质上已进行了大约0 ( n 3 ) 次有效搜索，这就使遗传算法能以 较少的计算获得较大的收益。 ( 3 ) 遗传算法不需要求导或其他辅助知识，而只需要影响搜索方向的目标函数 和相应的适应度函数。 ( 4 ) 遗传算法对给定问题，可以产生许多潜在的可行解，最终选择可以由使用 者确定，具有较大的灵活性。搜索过程不直接作用在变量上，而是作用在将变量编 码后的字符串上。 ( 5 ) 智能式搜索。遗传算法的搜索策略，既不是盲目式的乱搜索，也不是穷举 式的全面搜索，它是有指导的搜索。其指导依据是其适应度，利用适应度，使遗传 6 硕士学位论文第一章绪论 算法逐步逼近目标值。 ( 6 ) 逐步优化。遗传算法利用复制、交叉、变异等操作，使新一代的群体优于 1 日一代，通过不断迭代，逐渐得出最优解，其优化过程具有渐进性。 ( 7 ) 通用性强。遗传算法对搜索空间没有特殊要求，它只研究输入与输出的数 量关系，并不深究造成这种关系的原因，也不要求求解的问题有明确的数学方程及 导数表达式，因此便于处理各种因果关系复杂的问题，算法通用性强，可应用于离 散问题及函数关系不明确的复杂问题。 ( 8 ) 可扩展性。遗传算法利用随机规则而不是确定性规则来引导搜索，而且遗 传算法易于同其它的技术结合使用，容易介入到已有的模型中，具有可扩展性。 3 遗传算法在组卷问题中的应用 遗传算法同时具有内在的并行性，全局寻优和收敛速度快的特点，并且对目标 函数和约束条件不作更多要求，这些都适宜于处理试题库自动组卷的问题。近年来， 已有不少研究人员将遗传算法及其改进算法应用于组卷问题，并取得了一定的成绩， 为智能组卷问题提供了新的解决办法。毛秉毅等田1 采用传统的遗传算法( s g a ) 来实 现试题库的自动组卷，取得了较好的实际效果。但遗传算法主要通过交叉算子繁殖 后代，当交叉算子所作用的两个个体相同时，不能产生新的个体，因此要求初始种 群具有广泛多样性。当群体进化到其中的各个个体均相同时，交叉算子无效，此时 仅靠变异算子产生新的个体，遗传迭代难以进行下去，即发生所谓“早熟收敛”现 象。目前己经有很多研究人员把改进的遗传算法应用到组卷中，以提高组卷运行效 率。刘彬等啪3 对题型确定过程中的知识进行改进，相对于简单遗传算法均取得了较 好的结果。管宝云、尹琦将遗传算法与模拟退火算法相结合的混和算法应用于自动 组卷系统的设计，较好的发挥了两种算法的长处；刘曼平、邹羚在系统分析组卷 理论的基础上提出了一种基于自适应多点变异混合遗传算法的智能组卷方法m 1 ；董 敏，霍剑青等将项目反应理论与自适应遗传算法相结合，有效地解决了基于i r t 的 智能组卷问题h ；陈宇、陈治平等将启发式思想应用于遗传算法，确保进化过程沿 着有利于最终问题求解的方向进行，有效地降低了非可行解造成的系统开销1 。谭 新良改变了传统的遗传算法编码方式，根据组卷问题的特点提出了基于整数编码和 自适应遗传算法的智能组卷算法，试验表明该方法取得了比传统二进制编码更好的 效果，缩短了求解时间h 3 1 ；王萌、金汉均等h 4 1 提出了一种基于集合的随机抽选的智能 组卷算法，通过集合来缩小数据搜索的范围，提高了组卷效率。 将遗传算法应用于组卷问题仍处于研究阶段，针对遗传算法自身存在着不足以 及组卷问题的特点，需要探索出更加符合组卷问题特点并能够克服遗传算法缺陷的 7 硕士学位论文 第一章绪论 改进算法。 1 3 本文的主要工作 本文针对现有的计算机智能组卷技术进行了深入、系统的研究，综合现有算法 的特点，根据教育心理测量学理论及教师组卷心理，对组卷中涉及的参数指标和组 卷要求进行分析，建立组卷问题的数学模型；通过对遗传算法及其存在的问题进行 分析，提出了一种渐进式的遗传组卷算法。并在此基础上利用c # 开发实现一个简 单的比较实用的智能组卷系统。主要内容如下： 第一章介绍智能组卷算法的研究现状，包括优先权算法、随机抽取算法、误差 补偿算法、回溯试探法及遗传算法等，并简要介绍本课题的研究目的、意义及本文 的主要工作； 第二章介绍了智能系统组卷的基本原则，分析试卷的评价指标、各项指标的作 用及几个重要指标间的关系。在这些知识的基础上采用各种指标的分布构建了成卷 模式，并根据成卷模式定义了如何评价试卷的质量，最终得出了组卷的总体评估函 数： 第三章首先介绍了传统遗传算法的运算流程，针对传统遗传算法搜索后期效率 低并极易出现未成熟收敛的情况，提出了一种改进的渐进式遗传算法。并且利用 l o g i s t i c 方程构造混沌算子，形成混沌算法，将混沌算法应用到渐进式遗传算法的 交叉操作和变异操作中； 第四章介绍了智能组卷系统的设计工作，针对智能组卷算法，设计了一个简单 的应用系统，其中包括试题库的基本组织，数据库的设计，以及各个系统功能模块 的详细设计步骤； 第五章介绍了系统的开发环境、系统的组成和功能，实现了智能组卷的主要模 块，并对其中的关键代码进行了分析： 第六章对文章进行了总结，指出了智能组卷系统中还存在的问题，并对论文下 一步的工作进行了展望。 8 硕士学位论文第二章组卷的评价体系与数学建模 第二章组卷的评价体系与数学模型 组卷是c a t 系统的核心环节，提高考试质量，试题质量是关键。试题质量又依 赖于组卷工作的科学性。组卷工作的科学性主要体现在代表性和针对性。代表性是 指试题取样能足够反映考试内容。针对性是指试题本身编制要合理，对不同的考试 对象能有不同的体现。因此，研究智能组卷系统的原则，试题的评价指标，提高试 题的科学性，建立计算机管理的标准化试题库，对智能组卷系统来说具有极为重要 的作用。 从学科角度来看，组卷问题属于测验编制范畴，是心理和教育测量学的核心内 容。在心理与教育测量学中，存在着两种主要的测验理论：经典测量理论和项目反 应理论。经典测量理论将测试者的能力水平分布假设为正态分布，因此，测验后的 成绩分布也应该呈正态分布，只有测验分数呈正态，测试才可以认为是客观有效的， 而且测验的编制也以追求测验总分呈正态分布为最高目标h 副。经典测量理论是测验 的最一般、最基本的理论，应用极为广泛，现阶段大部分考试试卷编制及考试评估 都是以经典测量理论为基础。项目反应理论是一种建立在潜在特质理论基础上的新 兴的心理与教育测量理论。目前，也有少部分考试系统采用项目反应理论，考试时 系统根据测试对象的答题情况给出下一道测试的题目，不同能力水平的测试对象测 试的题目也各不相同。鉴于项目反应理论成立的假定条件较强，目前通用的考试规 则不能很好的满足其假定条件m 1 ，本文仍采用经典测量理论作为智能组卷问题的理 论基础。 本章将根据组卷的基本原则、试卷的评价指标及各指标间的关系等基本组卷知 识建立成卷模式，并在此基础上构建组卷问题模型。 2 1 组卷的基本原则 对于一般的测试来说，一方面主要是用于学生自测，检验自己对学科知识的掌 握程度；另一方面用于教师对学生进行考试，考察教学效果，进而改进教学方式。 这两个方面的用处均在于考察学生知道什么，能做什么，因此属于目标参照性测验。 对于目标参照性测验，组卷的基本原则h 7 3 主要体现在： 1 组卷的主要依据是考试大纲，组卷必须全面反映大纲的广度和深度。 考题要体现教学大纲的基本要求，既要反映出考生对基本知识、基本理论和基 本技能的掌握程度，又要考核考生灵活运用所学理论去分析和解决问题的能力。要 9 硕士学位论文第二章组卷的评价体系与数学建模 使组卷全面反映大纲的广度和深度，试题数量要足够，覆盖面要广，重视“三基” 能力的考核。 2 组卷要有利于考核考生的能力和促进考生的智力发展。 考试不仅考核考生知识掌握情况，而且通过考试，可以促进考生智能的发展和 提高。要使试题类型多样化，从不同侧面考核考生的基本知识与应用能力。在组卷 时，要考虑试题多种类型和功能，选择最佳组合结构。 3 组卷要讲究层次，要有难度台阶，才能在分数上拉开距离。 难度过大或过小都会降低试题的区分度。如果试题太容易，就不能激发考生的 积极性，考不出真实水平；如果试题太难，超出考生的实际程度和能力，容易使考 生失去信心，同样考不出考生的真实水平，太难太易都不符合组卷要求。组卷的难 度，应从大多数中等水平考生出发，形成难度台阶，使大多数考生的成绩形成差距 和梯度，即组卷要有一定的难度和区分度。 4 命题要注重发挥考题对考生学习方法的引导作用。 众所周知，考生一般都重视考试，自觉或不自觉地受到考试“指挥棒的影响。 当然，不能把考生引向为分数而学习，为了应付考试而学习。但是，要充分估计到 考试对学生的引导作用。如果考题偏重记忆，考生就要去死记硬背，如果考题着重 灵活应用，学生就要开动脑筋，思考钻研问题。因此，可以通过命题来引导学生掌 握正确的学习方法。 5 命题的表达语或指导语要表达清楚、准确无误，以提高考试的信度。 组卷工作是一项复杂的智力劳动，组卷工作者首先要研究考试大纲和命题计划， 明确考试的目的、对象、性质；试题的形式、数目：试题数量和分数在各部分中的 分配比例，考查的重点和其它要求。其次，根据命题计划编制试题，给出答案。并 对编出的试题进行审查、修改和筛选，同时注明各试题的预计难度、区分度、所属 章节、认知层次，分数及评分标准。 2 2 衡量试卷质量的几个重要属性指标 考试的科学性包括考试形式与考试内容的科学性两个方面。判断考试科学与否， 必须用评价指标进行度量。考试的评价指标是考试质量分析的依据，也是组卷的依 据。组卷就是从大量试题中选取一定数量的试题，组成一份合乎考试要求的试卷。 不同的试题组合而成的多份试卷在质量上也不尽相同，试卷中试题的质量及其他属 性指标对试卷的检验能力起到了决定性的作用。因此，在组卷前，需要对试题进行 分析以确定每道试题的属性。而一套试卷的构成需要满足多个约束条件，如：难度 l o 硕士学位论文第二章组卷的评价体系与数学建模 系数、总分、区分度、知识点、题型等。因此在构建试题库时每一试题包含有许多 属性，我们考虑与组卷有关的七项属性指标，即：题型、试题分值、难度系数、区 分度、知识章节点、重要性和曝光率。 试题的难度、区分度都是试题的重要质量指标，但它们不是试题自身的性质， 而是试题针对参加统计的这组学生反映出的特性，因此，它们的数值总是和不同批 次的学生有关，难度和区分度的确定也比较困难。然而，对于学校的教学考试，虽 然每年的学生不同，但情况类似，所以可用学生成绩统计结果，并逐年修正，作为 试题对该校学生的属性值。所以实际建立题库的时候，常常让有经验的老师给试题 的难度和区分度确定一个初始值，然后根据每年考试的结果，依据一定的算法进行 修正。 2 2 1 试题的难度 难度是衡量试题质量的一个重要指标。试题的难度是指参加测试的学生群体在 该题上的失分率。根据试题的记分方式不同，难度计算公式也稍有不同。若试题为 采用“全或无方式 记分方式的客观题，难度的计算公式为： 尸= l - 二 ( 2 一1 ) 其中，为答对该题的人数，刀为参加考试的总人数。在上面公式中定义的难 度，是指某一道试题的难度。一次测验的难度，是指测验卷中所有试题的平均难度。 测验的难度，要根据测验的目的、测验的性质和测验项目的形式等因素来确定。当 测验用于考查被试者对某种知识技能的掌握情况时，对难度可以不作严格限制，只 要是应该掌握的内容，即使它的难度值为0 或者难度值接近于l ，也应该采用。 若试题为有错酌情扣分的主观题，难度的计算公式为： 尸= 1 一羔 ( 2 二2 ) k 、。7 其中，x 为参加考试的学生在该题上的平均得分，k 表示该题的满分分值。由 难度的计算公式可知，难度值p 【0 ，l 】并且尸越大，试题的难度越大，答对的人数 越少。当测验用于最大程度地区分考生时，难度恒定在0 5 0 左右最为合适。例如全 国高等学校入学考试其难度规定为3 ：5 ：2 ，即较容易的题目占3 0 ，中等难度的 题目占5 0 ，较难的题目占2 0 ，整个试卷的平均难度大约为0 5 0 。 一般情况下，我们把试题难度划分为五个等级，难度区间与难度等级间的对应 关系如表2 1 。 硕士学位论文第二章组卷的评价体系与数学建模 表2 - 1 试题难度等级 难度等级易较易 中等 较难 难 难度区间 0 ，0 2 3( o 2 ，o 4 ( 0 4 ，0 6 ( 0 6 ，0 8 ( 0 8 ，1 2 2 2 试题的区分度 区分度是衡量试卷质量的又一重要指标，用于反映试题对参加测试的不同能力 水平学生的区分程度，用字母d 表示。区分度一般可采用高低分组法计算，计算公 式如下： d ：生一生 ( 2 3 ) kk d 为试题区分度的估计值，x 和x ，分别为高分组和低分组在该试题上的平均 得分，k 为试题的满分分值。 根据公式，试题区分度的取值范围在一1 和1 之间，区分度过低表明该试题的 质量不佳，这种试题对测验总分起着不良的干扰作用。具体的区分度评价标准如表 2 - 2 所示。 如果题目的区分度高，那么水平高的被试者在题目上的得分就会高，而水平低 的被试者就会得分低，这样就可以把不同水平的被测试者区分开来。区分度属性在 题库中的作用也是挑选题目。对于常模参照性测验来说，希望测验的结果能把学生 水平拉开，以便择优或进行分组编排，所以用于常模参照性测考的习题，就需要有 较高的区分度。对于目标参照性测验，则主要是按照预定的标准，考核学生是否达 到标准要求，达标程度如何，或者考核学生知道什么，能做什么。目标参照性测验， 是把考生的成绩和特定的目标作比较，因此它无需强制性地把学生的水平拉开距离， 对被测题的区别性能的要求并不非常重视。 试题的区分度一般是由该题的成绩与整个测验成绩之间的相关程度来表示。相 关程