（计算机软件与理论专业论文）基于整数分段编码遗传算法的自适应考试系统的研究.pdf

江誓独创性声明本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取得的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文中作了明确的说明。本声明的法律结果由本人承担。学位论文作者签名：往毛翻日期：加帆多3学位论文使用授权书本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编本学位论文。( 保密的学位论文在解密后适用本授权书)每位论文作者签名：氆日期：丝! ! ：! ：!学位论文作者毕业后去向：工作单位：通讯地址：指导教师签名：互艺4 孕e t期乡1 0 岁电话：邮编：jj，f一i 譬1( l摘要随着现今信息技术飞速的发展，计算机网络技术的逐渐成熟，人们对很多传统方式方法的合理性产生了质疑，并且尝试利用新兴的技术去改变它们完善它们。用来考核人才的考试手段同样在这种要求下也发生了革命性的变化。传统意义上纸与笔的面向考试已逐渐向计算机网络考试过度。如何使网络化的远程考试能够对被试者能力客观、准确的评估已经成为现今社会人才考核的新目标和新要求，而研发出一套科学智能的组卷方式更是其成功实现的关键。智能组卷系统是自适应考试系统的核心与灵魂，传统的组卷方式存在消耗时间过长，成功估算率低等缺点，主要原因是因为传统组卷方式的算法过于陈旧。传统智能组卷的遗传算法都是基于二进制编码来实现的，本文在通过对传统组卷算法的研究基础上，提出了一种基于整数分段编码的优化改进遗传算法，通过实验验证了该算法可以提高组卷成功率，缩短组卷时间，并能够既快又好地从题库中抽取一套最符合用户指定要求的试卷，使试卷具有随机性、科学性和合理性。本文的主要内容是系统研究了自适应考试的相关理论、以及智能组卷系统的遗传算法的基本理论，在此基础上对传统遗传算法与整数分段编码遗传算法进行了详细的研究，并进行了功能实验比对，最终得出结论，在肯定了整数分段遗传算法的优势的同时设计出一套基于整数分段编码遗传算法的自适应考试系统。关键词：整数分段编码；遗传算法；自适应考试系统；智能组卷d e t a i l e dd e s i g no fas e l f - a d a p t i v et e s ts y s t e mw a sc o n t r i b u t e d k e yw o r d s ：i n t e g r a ln u m b e re n c o d i n g ；g e n e t i ca l g o r i t h m ；s e l f - a d a p t i v et e s ts y s t e m ；i n t e l l i g e n tt e s tp a p e rn1-、k目录摘要“ia b s t r a c t 000000 000 oo oo oo 000 ii目录moo oo i i i第一章引言o0000 00 000 00 000000 0000 00 ooo0 1oooo 11 1 研究背景及问题提出11 2 自适应考试系统的内涵和国内外现状 21 2 1 自适应考试系统的内涵000 000 00 00 00 21 2 2 自适应考试系统的国内外现状? 21 2 3 遗传算法在自适应考试系统中的应用现状31 3 本文的主要工作4第二章自适应考试的基本理论与实现方法52 1 两种基本测量理论52 2 项目反应理论oo oo oo 52 2 1 项目反应理论发展历史00 0o io oo oo oo 52 2 2 项目反应理论的基本假设oooo o moo mom 62 2 3 项目反应理论的基础模型00 0000 ao ooo l 72 3 遗传算法0000 00 oo 00 00 82 3 1 遗传算法概述0000 00 ooe ooo 00 00 00 82 3 2 遗传算法的基本实现技术92 3 3 基于传统遗传算法组卷00 0000 000 000 00 00 1 02 3 4 基于整数分段编码遗传算法组卷o ooe o oo ooo om oo 1 1第三章基于整数分段编码遗传算法的智能组卷研究1 23 1 组卷流程1 23 2 组卷模型ooooom 00 00 00 0000000 0 000 00 0 000 0 1 33 2 1 小步测量模型1 43 2 2 三参数l o g i s t i c 模型1 43 2 3 项目信息函数模型0 1 1ooo 0000 00000 1 53 3 参数估计1 53 4 算法设计1 63 4 1 假设1 63 4 2 编码1 63 4 3 初始化1 7000 odo 1 71 8- - - - 1 8i000 1 91 9析与设计2 0ooo 2 02 1oq2 2oo 0oo 2 2oo 2 32 42 52 5i0000 00 2 64 3 7 组织考试2 74 3 8 统计分析2 74 4 数据库设计2 74 5 自适应测试相关流程2 84 6 主要系统功能实现3 04 6 1 自适应考试系统注册登录界面3 04 6 2 试题管理界面3 14 6 3 试卷管理界面3 14 6 4 成绩管理及查询界面3 2。第五章结论与展望3 3参考文献3 5致谢3 7一心东北师范大学硕士学位论文第一章引言1 1 研究背景及问题提出随着现今信息技术飞速的发展，计算机网络技术的逐渐成熟，人们对很多传统方式方法的合理性产生了质疑，并且尝试利用现有的技术去改变它们，完善它们，用来考核人才的考试手段同样在这种要求下也发生了革命性的变化。传统意义上的纸与笔的面向考试存在着很多条件限制和不足，已经不能够满足现代化人才考核的要求。在计算机网络信息技术空前发展的今天，计算机辅助考试便以其特有的优势慢慢地发展壮大，如何将计算机辅助考试技术在真正意义上取代传统面向考试，客观、准确地评估人才能力水平的高低，己成为大家最为关心的话题。最初的计算机考试系统是建立在d o s 平台上的，其功能的实现也是基于d o s 下的有限应用程序和数据来完成的。随着微机操作系统平台的推陈出新，d o s 系统被w i n d o w s 所取代，计算机考试系统也就随着平台的变化，新技术的诞生，而发生了变化。这种变化不单单是操作平台的改变，同样也对计算机考试系统的功能提出了更高的要求，计算机考试系统需要对考试的全部过程进行整体的管理与监控，也就是从试题生成、到流程处理，再到考生的数据录入，考试的实施与评分，到最后的分数处理，这些要求都由计算机管理与监控，最终目的是实现计算机考试的无纸化、全自动化。后来随着网络技术的不断发展，基于计算机与网络的考试又成为了新的热乜计算机辅助测试软件产品相继诞生。利用这种软件进行考试，题目的选择生成、答题的过程、试卷完成提交、成绩批阅、分数处理分析等等都可以在网络交互中自动完成，只要拥有一套成熟完善的题库就可以实现网络考试的自动化，并且能够根据出题者的要求进行选题组卷。最终目的不单单是要达到考试的无纸化、自动化，而且还要求以被试者作为对象，根据不同被试者在考试过程中体现出来的能力水平，动态地调整相应被试者的试题难度，力求更充分地检测出被试者准确的、真实的能力水平。这就存在一个度的问题，如何才能做到在满足所有要求的前提下，根据不同的被试者动态地调整试题难度? 如何更加充分地检测被测者这的真实能力水平?本文正是在这一背景和意义下，深入研究一种基于整数分段编码智能组卷计算机考试系统，以求在能够满足用户要求的范围内，根据不同的被试者动态地调整其试题的难度，能够充分地检测其真实能力水平。东北师范大学硕士学位论文1 2 自适应考试系统的内涵和国内外现状1 2 1 自适应考试系统的内涵考试不但是衡量人才能力高低的标尺，也是教育的重要环节。传统意义的考试思想，是面向试卷或面向试题的。考试的组成至少有五个步骤，即人为选题，被试者答题，人工批阅，成绩收集以及成绩分析评估。显而易见的是，当被试者数目增大，选题范围变广，考试要求增多时，担任评估的工作量就会不断加大。另一方面，以固定的考题考核每一个被试者，尽管被试者能力水平可能差异很大，但全都接受一套固定模式和内容的试卷测试，其结果对于水平较低的被试者来说，难度大的考题无法作答，失去测试意义；对于能力偏高的被试者来说，难度不大的考题则轻松对答，亦测试不出被试者的真实能力水平。现代的计算机辅助测试，目的只在于计算机的“无纸化”测验，这种测试的方法节省了大部分考试成本，提高了效率，但这只是考试方法的一种进步，所采用的考试策略和纸笔测验是一致的，本质上没有改变面向试题的局面。现如今一种以“因人施测”为中心思想的自适应测试理论诞生了，打破了传统测试“一刀切”的局面。自适应考试的核心是：以被试者作为对象，根据不同被试者在考试过程中体现出来的能力水平，动态地调整相应被试者的试题难度，力求更充分地检测出被试者准确真实能力水平。简单理解就是，兰卜个被试者能力有限时，考试系统会对其做出相应反应，降低该考题的难度，反之，水平较高时，考试系统则提高考题难度，使能力测试者在自己能力水平范围内真正意义上定位自己的能力水平。1 2 2 自适应考试系统的国内外现状追溯历史，考试制度最先是由我国开设的，随着时光的推移，引入海外，世界各国争相采用，早先的考试制度是用来作为选拔官爵的依据。但是考试制度的发展在我国相对国外却比较缓慢，近代的心理计量学在国外已经逐渐发展的时候，这种考试的新思想还没有引入我国。自适应测试理论是在上个世纪7 0 年代初期，由洛德( l o r d ) 奠定了其理论基础，并在计算机上进行了实现。到了2 0 世纪8 0 年代初，韦斯( w e i s sdj )等人对此理论又进行了完善和推进，到了现如今自适应测试理论已经成为国际心理学和教育测量学界最受关注的发展方向之一。另外，美国e t s 的t o e f l 和g r e 英语级别考试都已经实现了c a t 方式的测验，美国的医生与护士资格认证也具备这种c a t 测验。c a t测验技术现如今已经慢慢地走向欧洲乃至世界各地。在2 0 世纪8 0 年代我国就已经开展了针对c a t 测验技术的研究，北京师大的张厚粲先生在1 9 9 0 年撰文总结出c a t 测验技术的六个优点，并提出了c a t 将成为心理测量学科的新方向。1 9 8 7 年江西师范大学一个题库理论的研究小组曾撰文指出，c a t 技术能够在不损害测验信度和效率度的约束条件下缩减题量，削减测验时间，提高测验效率。到了1 9 9 7 年身为中科院心理所院士的韩布新、车宏生两人经过多年的研究也撰文指出，对于计算机自适应测试是可以针对测验目标、选择测题、测验对象等方面具备特异性的技术和理论问题。现如今我国针对c a t 的研究和应用已经有了突飞猛进的发展，但是目2东北9 币范大学硕士学位论文前我国对c a t 的研究和实施还不是很理想，还存在很多问题，这些问题表现在：1 ) c a t 的实用性不强；2 ) 我国开发出的c a t 很大程度上都是只针对单一的或者是特定课程( 或某方面知识) 测验，只注重针对性却忽略了通用性，缺少普适性高的开发平台。3 ) c a t 中能力估计方法，选题策略以及组卷算法的选择依据仅靠开发者的经验探索，其合理性与科学性还有待理论验证以及实践检验。4 ) c a t 的相关算法相对陈旧，缺少能够提高组卷效率的改进算法研究。目前，c a t 在我国虽然还没有具备强大的影响力，但是具备先进理论的自适应考试取代传统纸笔测验已是大势所趋，笔者相信在不久的未来，此种技术一定会在各个领域得到更大程度的应用，势必掀起改变能力测试方法的新革命。1 2 3 遗传算法在自适应考试系统中的应用现状应用遗传算法的优势在于整体搜索策略以及搜索方法的优化，它是不依赖于其它相关辅助知识的，仅单纯的需要能够左右其搜索方向的目标函数以及适应度函数。由此可以知道，遗传算法是一种通用于求解复杂系统问题的普适框架，它的应用不受领域限制，能广泛适用于许多应用领域，下面我们将介绍遗传算法在自适应考试系统中的应用现状：自适应考试系统中的智能组卷其实就是一个组合优化的问题。传统的智能组卷算法虽然在一定程度上也能够满足自适应考试系统的需求，但是随着试题量的不断增大，用户对考试系统的要求不断提高，随之而来的是组合优化问题的搜索空间也急剧增大，利用传统的智能组卷算法是很难在用户要求范围内求出最优解的u 射。这个时候更多的人逐渐意识到寻求满意解是现阶段自适应考试系统的主要任务所在，而遗传算法是寻求这种满意解的最佳途径之一n 羽。遗传算法的真正发展是从本世纪9 0 年代开始的，随着遗传算法在更多领域上的应用，其研究也出现了很多新的动向：d w h i t e y 于1 9 9 1 提出了一种专门针对用表示基因个体的的交叉算子，这种交叉算子是基于领域较差的。随后d h a c k l e y 等人通过进一步研究提出了随即迭代遗传爬山法，其中心思想是一种概率的选举模式，简称为s i g h 。通过多次的实验证明，s i g h 方法与其它神经遗传算法相比，所测试的函数有三分之二的性能良好，并且其求解的速度也要比其他算法快很多引。我们国家近年来也有不少的专家和学者对遗传算法的交叉算子进行改进。不论在理论研究还是遗传算法的应用领域都有了长足的进步。后来，人们了解到传统遗传算法在面对复杂的、规模较大的组合优化问题时搜索的效率偏低，需要有一种能够提高搜索效率的优化遗传算法来是传统算法更新换代。赵宏立教授于2 0 0 4 年提出了一种用基因块编码的并行遗传算法，利用粗粒度并行的方法为核心框架，挑选染色体集合中可能的基因串，并将所挑选的然34样得到的染色体就要比种方法就是整数分段编心思想16 | 。j法的研究，设计了一套基东北师范大学硕士学位论文第二章自适应考试的基本理论与实现方法2 1 两种基本测量理论测验理论是一种有系统的理论学说，我们知道测验资料相互间存在着一些认证关系，而测验理论就是用来解释这种关系的，总体可以把它分成两个学派，古典测验理论以及当代测验理论。古典测验理论以真实分数模式作为其理论支持的框架，按照弱势假设而来，它的理论模式已经经过很长时间的发展，并且已经发展到了相当大的规模，其所采用的计算公式既简单又容易理解，能够普遍适用于大多数的教育与心理测验数据，它现已成为测验学界使用率与适用范围最广的理论依据口3 。但是，古典测验理论也存在着诸多缺点。基于这些缺点的发现和研究，当代测验理论逐渐诞生并得到发展。当代测验理论总结了古典测试理论的不足，并运用项目反应理论作为其理论支持的依据，这种理论虽然启用较晚，并且其算法公式难以理解。但仍然以其严谨的立论与合理的假设深受广大测验研究者们的青睐，并且有取代古典测验理论的趋势h 3 。下面一节我们就来详细描述一下当代测试理论的理论依据项目反应理论。2 2 项目反应理论项目反应理论：在测验过程中，首先定义测试者的特质或能力、估计测试者特质或能力的得分，然后以得分为依据对答题情况做出预测和合理解释。这里的特质或能力以及试题就是i r t 的理念。他们的相互关系就是i r t 的内涵h 3 。2 2 1 项目反应理论发展历史项目反应理论的初步理论框架可以追溯到上世纪三、四十年代，然而在1 9 8 0 年项目反应理论才得以正式的进入理论的研究阶段。1 9 4 6 年，心理计量学者t u c k e r 首次使用试题特征线，该概念目前被认为是项目反应理论的原始概念。到了5 0 年代，更多的项目反应理论学者加入了理论研究的队伍，其中以美国的r o d e 以及丹麦的拉西则为主要代表。美国学者r o d e 在1 9 5 2 年第一次提出了双参数正态肩形曲线模型，这种模型虽然具有很高的理论价值，但是在处理数据的时候相对比较麻烦。这种模型到了1 9 5 7 年被伯恩创立的l o g i s t i c 三参数模型所取代。1 9 6 9 年丹麦的拉西建立的拉西模型在十年内又被编写了i r t 的专用程序，更进一步的推动了其模型的应用。7 0 到8 0 年代各国的研究者出版了很多著名的著作，不断提出了一些新模型理论，并且进一步推动了i r t 的应用。我国的项目反应理论的研究也是从上世纪8 0 年代开始的，在这短短的3 0 年罩，i r t5。东北师范大学硕士学位论文的理论研究已经得到了可喜的成绩。但由于起步较晚，与国外相比还有很大差距，主要表现为应用研究的领域狭窄，理论研究不够透彻等等。表2 1 项目反应理论初期发展历史2 2 2 项目反应理论的基本假设任何一种测量理论都必须有定的假设，项目反应理论也例外，在这些假设的基础上才能进行为其构建数学模型。在项目反应理论中有三条最基本的假设( 1 ) 潜在特质空间的单维性假设；( 2 ) 局部独立性假设；( 3 ) 项目特征曲线假设，并且有些学者公平增加了“知道答对”假设和非速度限制假设。下面对三种最基础的假设分析如下：潜在特质空间的单维假设：在阐述该假设前，先解释潜在特质空间的概念。该概念来自于心理学，指的是潜在特质所组成的抽象空间。项目反应理论中假设测验中所有的项目都测量同一心理变量，或者可以这样理解，该心理变量( 特质空间) 是影响被试对项目做出反应的主要因素。然而实际当中，被试的反应往往受到多种特质的影响，例如英语阅读理解的能力同时也可能受到被试词汇的影响。因此，编制项目及试卷的过程中要通过合适的方式进行单维假设检验，尽量使要测试的特质不受干扰。局部独立性假设：该假设是指被试对于某个项目反应正确的概率不会受到该被试对于其他项目反应的影响。或者可以这样理解，真正影响到被试对于项目反应的因素只包括两点，一是被试的特质( 能力) 值，二是项目的特征值( 难度等，特征值与选取的数学模型相关) 。这个假设为我们利用各个项目得分概率乘积的形成来计算任何得分的概率提供了理论依据。项目特征函数假设：假设每个项目都有特征曲线，该曲线反应了被试的潜在特征( 能力) 与对项目反应正确的概率之间的关系，即口与p o y o 的关系。这里p o y o 是指从能力为秒的一批被试中随机抽取一被试，该被试正确回答该项目的概率。根据局部独立性中影响概率的两个因素，被试样本中各个个体的反应情况互不影响。6东北师范大学硕士学位论文2 2 3 项目反应理论的基础模型经典测验理论没有充分考虑不同被测的不同能力水平，用相同的试卷测试不同能力水平的被测，并假设所有的被试者具有相同的测量误差，因此基于经典测验理论无法依据被试的能力差异进行个性化测试。以外，基于经典测验理论的测试受被试样本情况影响很大，不同样本间进行实际能力的对比分析较为困难。而i r t 能够为以上问题提供较为适宜的解决办法，不仅考虑到试题本身的计量因素，如难度、区分度等，而且将被试的能力( 或称为特质水平) 与被试在项目上的行为( 主要体现在答对的概率) 关联起来并构造为参数化的数学方程式，该种数学方程式也称为项目反应模型。项目反应模型都很多种，但其中最成熟、应用最为广泛的还是逻辑斯蒂克( l o g i s t i c ) 。根据参数个数的不同，l o g i s t i c 模型可以分为四种。下面对四种模型进行简要对比分析。其中，通常令d 取值为1 7 ；矽为被试能力值，p ( 鳓：表示能力为秒的被试答对的概率。表2 2l o g i s t i c 模型对比分析参篓个数学模型数。参数说明假设2( 秒) = 南b 代表项目的难度c ( 秒) = 南三箕萎霉蓦蓦羹：度3e ( 乡) = q + ( 1 一c ，) 南4 毋( 乡) = q + ( 一q ) 南a 代表项目的区分度b 代表项目的难度c 代表项目的猜测系数a 代表项目的区分度b 代表项目的难度c 代表项目的猜测系数r 代表能力高的学生答错题 被试在对项目做出反应时并不存在猜测的成份 每个项目的区分度不存在差异能力很高的学生总能正确回答项目 被试在对项目做出反应时并不存在猜测的成份能力很高的学生总能正确回答项目能力很高的学生总能正确回答项目东北师范大学硕士学位论文的概率为了清晰的表述各个参数的实际意义，我们可以对具有不同特征值的曲线进行对比分析。( 1 )当两条曲线只是a 取值不同时，s 型曲线的坡度不同，可见a 能够反应出曲线的斜率；( 2 )当两条曲线只是b 取值不同时，s 曲线基本平行，可见b 是特征曲线在横坐标上的投影；( 3 )当两条曲线只是c 取值不同时，s 曲线在纵坐标上的截距不同。另外，特征曲线的规律还显示，不论a ，b ，c 如何取值，p ( 秒) 都随着秒的增加而增加，即，被试的能力越强，对项目反应正确的概率就越大。对于前两种三参数模型的公式，其优点较后两种相对简单，参数较少，实现容易，可准确性缺远不如后两者。而最后一种的参数过多，复杂程度也就较第三种更为突出，所以本文在下文均采用的三参数模型的第三种模型公式。2 3 遗传算法2 3 1 遗传算法概述遗传算法( g e e n i t ca l g o r i t h m ，g a ) 是一种借鉴自然生物遗传学思想，对群体中个体进行遗传作用，最终提高群体个体的适应能力的的全局优化算法。自从1 9 6 2 年h o l l a n d教授首次提出了遗传算法的思想开始，便吸引了无数的相关学者，通过不断地摸索和研究，遗传算法迅速地得到了推广和优化哺3 。较为常用的经典优化算法大致有以下几种：枚举法、启发法以及搜索算法等。下面我们对遗传算法和这些经典算法进行比较：1 经典优化算法是针对每个参数进行操作的，是不能够对结构对象直接操作的，而遗传算法可以对参数集合中那些已经编码的个体进行合理地操作和处理，并不需要对参数做任何处理，所以遗传算法的优势就是可以直接作用于结构对象。2 大多数经典优化方法的搜索方式都是单点搜索，这样做就很容易导致该搜索终止后没有找到整个群体的最优解，而是得到了局部的。遗传算法则一改这种做法，一多点搜索作为搜索手段，同时对群体中多个点进行处理，避免搜索停滞于局部最优。3 经典优化算法往往针对不同的领域需要搜索相关的知识以及辅助信息来评估个体，而遗传算法则不需要这么做，适应度函数值是遗传算法唯一评估个体的依据，其所需条件要比经典优化算法要简单得多。4 经典优化算法是采用确定性规则来指引搜索大体方向的，而遗传算法摒弃了确定性规则的固定性，以概率变迁规则作为搜索的方向指引，这种变化使得遗传算法具有多变的适应性搜索手段。，2 3 2 遗传算法的基本实现技术8东北师范大学硕士学位论文遗传算法可总结为五个基本内容：参数编码、初始群体定义、适应度函数定义、对参数控制设定以及遗传操作定义。1 遗传算法的基本流程如图2 2 所示图2 2 遗传算法基本流程图2 遗传编码在研究遗传编码的问题时，先要了解遗传编码问题中的相关概念。在遗传算法中最基本的两个概念是编码和译码。所谓编码，即为由问题空间到编码空间的映射：反过来的逆映射即为译码。在用g a 解决实际问题时通常采用以下编码方式：基于二进制数的遗传编码算法( 用( 0 ，1 ) 组成的染色体位串来描述问题空间的基本参数) 、基于浮点数的遗传编码算法和基于树的遗传编码算法。n 们3 适应度函数适用度函数通常应用在g a 的进化搜索中。在进行搜索时，g a 将待搜索种群中的每一个个体的适应度的具体值作为搜索的根据，而不是取决于外部的信息n 剖。4 遗传算子遗传算法中的常用遗传算子主要有以下三种3 ：( 1 ) 选择算子( s e l e c t i o n r e p r o d u c t i o n ) 一在g a 中，选择算子依据每个个体适应度值的不同从待搜索群体中选择个体，在这种选择中，个体是被成对选中的。具体应用到遗传算子的方法主要有轮盘赌模型，期望值模型等。( 2 ) 交叉算子( c o r s o v e r ) 在g a 中，交叉算子将待搜索群体中的即将被选中的成对个体的基因链按随即位置进行交叉，这种交叉的概率为p ，交叉后最终生成两个新的个体。在具体实现中较为常用的时二进制交叉，又可以进一步分为单点多点交叉、顺序交叉在盘【1 1 1寸0( 3 ) 变异算子( m t u a t i n o ) 顾名思义，变异算子即：在g a 中，对新生成个体的基因链的每个位进行变异的算子成为变异算子，其中变异概率为p 3 。5 控制参数选择9范大学硕士学位论文键参数( 如：个体变异概率等) 会对这个算法的执行因此，要想使得到的搜索算法具备较好在时间性能的选择和算法进行过程中对其的控制都是十分重要2 3 3 基于传统遗传算法组卷一种组卷算法的好坏，取决于该算法设计的组卷系统能否从题库中既快又好地抽取一套最符合用户要求的试题，并且使最终结果做到随机、科学、合理。避免局部最优提高收敛速度是好的组卷算法的准绳。下面我们就来详细了解一下传统遗传算法。传统的遗传算法求解对为二进制编码：设题库总题数为s ，用互，互，ee e9 瓦分别表示各题，组卷的过程实质就是从互，正，疋中抽出刀道题，并且使试卷的整体指标厂最小化，这里的厂表示试题属性与用户需求的误差，接着用一个s 位的二进制串表示该问题的解，表示为只，只，p s 旧3 。对l f s ，若p ，为l 则第f 道题被选取；假如取0 则第f 道题未被选取。假设该试卷所需以道题，那么，只，只的串中必须含有刀个1 。这种以二进制为编码方式的遗传算法优点是较为简单，容易实现，符合最小字符集编码的原则，通用性较强。副二迸制编码对所求问题的结构特征无法反应，亦不能利用具体领域的特定知识，精确度不够高，遗传算子的操作途径也较为有限。假如选择轮盘赌方法，群体的适应度差异相对较大，最优个体的生存几率明显提高，相对较差的个体就会被淘汰，整个群体中很快就会被最优等个体所占据，遗传算法也就过早的丧失了进化的能力，而且传统遗传算法很难得到全局的最优解。单点杂交是传统遗传算法衍生出新一代群体，促使其进化的主要手段；变异则是维持整个群体能够多样性，打破局部极值的最重要手段，而仅仅采用这两种方法，对于不同问题是远远不够的。由于遗传算子的操作方式影响着整个遗传算法，所以应该根据具体的问题来选择适合的操作方式。另外，在运用传统的二进制编码方法时，只需要知道适应函数，对于其它的先验知识几乎不需要，也因为这样传统方法具有很强的适应能力，能够在很多不同领域得到应用。但是，正是因为二进制编码算法的先验知识使用率小，不能够对具体的问题进行具体的分析处理，想得到最好的求解较为困难。并且遇到有些问题的时候，其求解的速度也不尽人意，甚至产生早熟收敛的现象。2 3 4 基于整数分段编码遗传算法组卷整数分段编码依旧是一个基因对照一个参数来编码，将原来问题解空间映射到整数串空间中，接着在整数串空间遗传操作，得到的运算结果再通过解码的过程还原为实体表现的形式，并进行适应度的评估。它与实数编码不同的是，整数编码的每一位基因是1 0东北师范大学硕士学位论文有一个十进制整数构成的，遗传操作也并不是直接作用于题解空间的，这样就更符合遗传计算的规则，尤其适用于离散变量相关的问题。另外，整数分段编码码串的长度要明显短于二进制编码，所以解码的过程也就得到简化，运算速度也就得到提高。本文染色体编码就是采用整数分段编码来实现的，可将其表示为：( q j , q ：”) ，其中q 。表示试题题号，并且同种题型的试题号划分到一起形成段，即每一段反映着一个相应的试题题型，每段的长度则由题库中该类题型的数目来决定。整数分段编码克服了原有二进制编码计算量大，量化引入的误差、权的表示等等精确度受到限制等缺点，省略了编码和解码的过程，大大缩减了求解消耗时间，在进化过程中拥有较好的搜索性能。东北师范大学硕士学位论文第三章基于整数分段编码遗传算法的智能组卷研究智能组卷系统是自适应考试系统的主要内容，也是整个自适应考试系统的核心和灵魂，它的质量将直接影响整个考试系统的性能，在本章我们主要介绍一种基于整数分段编码遗传算法的智能组卷系统。智能组卷是根据用户需要设置组卷条件，通过相应的算法，智能地检索出能够满足用户要求的最优解并最终组成试卷。试卷的决定参数主要为：试题的总分、题型、试题数量及分数、各个章节所占分数的百分比等等。智能组卷的算法有很多，采用何种算法是智能组卷的关键，它决定了所选试题难度是否能够达到用户预期，也决定了选题速度是否能达到用户的要求。其实智能组卷系统就是一个不断满足多重约束条件的优化组合。所谓组合的优化，就是指在离散的，有限的数字结构中，去寻找一个既能够满足约束条件并且使其目标函数值能够接近最大或最小的解。智能组卷系统在某种程度上有些类似于背包问题隅1 。但它比背包问题的约束条件更多，而且还需要确定适当的目标函数。3 1 组卷流程本组卷算法拟解决传统组卷算法的不足，引入项目反应理论，根据被试者的实际能力，因材施测地为该被试生成符合其能力水平的项目。当然，不可能一下子测出被试者的能力，而选择最符合的项目，我们需要在不断获得被试者对项目反应正误的基础上，逐渐推测出被试者的能力水平，并依据不断精确的能力估计值选择最为适合的项目。本组卷算法对用遗传算法解决基于i t r 的自适应组卷问题有如下改进：首先，本文将项目反应理论的根据被试反应情况而一次只出唯一项目，改为一次出小数量的一组项目；其次，提出“小步测量模型，即对每次根据被试反应值而呈现的一组项目，小步测量模型相当于有一个限制的题型模板，有利用解决整卷的题型比例问题，而且与传统的整数编码相比极大的缩减了编码的位数；再次，适应度函数除了考虑到了信息量及离差的影响，还增加了项目的其他属性，保证了选题的科学性：此外，由于本文利用i r t而且应用“小步测量模型”，使得种群随步数增加而规模也增加，并且对遗传算法也是一种补充。整个组卷流程可以用如下步骤进行描述：( 1 ) 确定试题的编码方式，即相当于构造问题空间；( 2 ) 对被试能力做出假定；( 3 ) 根据假定的被试能力，选择最初的一组试题，即我们所定义的第一个小步测1 2东北师范大学硕士学位论文量模型确定具体的项目；( 4 ) 被试对小步测试模型中的项目做出反应，系统进行记录；( 5 ) 根据被试的反应情况，对被试的能力值进行估计；( 6 ) 根据估计出来的能力值及小步测量模型中的项目适应值，对当代模型中的项目进行遗传操作；( 7 ) 被试针对当前最优的小步测量中所含项目，继续进行测验；( 8 ) 根据被试的反应情况，对被试的能力值进行估计；( 9 ) 循环以上步骤，直至达到系统结束条件。该过程可以用图3 1 所示的流程图进行描述。图3 - 1 组卷流程图3 2 组卷模型为了准确表达系统如何进行组卷，有三个因素是最为重要的，这三个因素分别是试卷与项目的关系如何表征、如何将项目与被试的能力建立数学模型以及如何选择项目。东北师范大学硕士学位论文针对这三个最为关键的问题，我们分三部分描述组卷模型。3 2 1 小步测量模型这里的小步测量是指针对重新评估被试能力后，为被试所出的一组试题。这里将传统的i r t 理论进行了扩充，系统根据被试的反应情况，不是一道题一题测试，而是直接出一组试题。小步测量模型相当于“一组项目 的模板，该模板定义了项目组中不同类型的个数，下面所论述的如何选择项目在这我们这里就相当于如何在多组备选中选择最符合目标函数的一组项目。这种做法，能够有效利用遗传算法的全局搜索优点，并且也提高了组卷的效率。此外，这种表示方法也能更好的满足题型的约束条件，并且与现实测验题型顺序基本固定的规律相一致，便于学生接受。多组小步测量模型( s t e p _ m o d e l )s t e p _ m o d e l ：= = ( s m l ，s m 2 ，- ，s m ) 1 单- - 4 , 步测量模型( s m )s m ：= ( i t e m l ，i t e m2 ，i t e m n )项目模型表征( i t e m )( 定义3 1 )( 定义3 2 )s m ：= ( i t e mi d ，i t e md e s c r i ，i t e ml e v e l ，i t e md i f , i t e md i s t ，i t e mg u e s s ，i t e mt i p ，i t e md e s c r i i t e ma n s ，i t e mt i m e ，i t e mm a x t , i t e mu s e d )( 定义3 3 )其中i t e mi d ，i t e md e s c r i ，i t e ml e v e l ，i t e md i f , i t e md i s t ，i t e mg u e s s ，i t e mt i p ，i t e md e s c r i 。i t e ma n s ，i t e mt i m e ，i t e mm a x t , i t e mu s e d 分别表示项目编号、项目描述、项目认知能力、项目难度、项目区分度、项目猜测系数、项目提示、项目题干描述、项目答案、项目预期用时、项目最长用时、项目使用次数。综上所述，如果小步模型中含有项目m 个，则对应的构成一个为mx1 2 的项目矩阵。3 2 2 三参数l o g i s t i c 模型在前面所论述的项目反应理论的基础模型中，最常用的模型就是三参数l o g i s t i c 模型。只( 口) = q + ( 1 一q ) 由( 公式3 4 )其中，a ，b ，c 分别代表项目的区分度、代表项目的难度以及项目的猜测系数，p ( 秒)是指从能力为口的一批被试中随机抽取一被试，该被试正确回答该项目的概率。在该公式所描述的模型中，当项目的参数a 取较大值时，对于一个0 与b 离差较小的被试，该项目能够提供较多的信息；对于一个0 与b 离差较大的被试，该项目则只能够提供较小的信息。而当项目的参数a 取较小值时，尽管该项目对于0 恰好在b 的邻域内的被试所能提供的信息量不大，但是从更加宽广的能力区域中该项目却能提供信息h 舢。1 4东北师范大学硕士学位论文3 2 3 项目信息函数模型项目信息函数用来选择项目。对于我们选择的三参数l o g i s t i c 模型，其所对应的项目信息函数可以表示为：，咖) = 而嚣( 公式3 6 )其中，d 取值为1 7 ，a i 代表项目i 的区分度，l i i 代表项目i 的难度，q 代表项目i的猜测系数。由于在自适应测试当中，被试所做的测试是不可回溯遗忘的，即被试所做的总项目数总是在增加。基于如上所提到的小步测量模型，假设小步测量模型中的项目数为n ，而且已经经历了s 小步。则，当前的测试总信息量可以表示为：1 ( 0 ) = ( p )( 公式3 7 )，其中，当且仅当某个项目被选择的时候，其题号才能成为i 的取值。即，i 的值阈为被选择项目的编号集。3 3 参数估计根据组卷流程的论述，我们需要对被试的能力不断做出估计。对参数进行估计常用的方法有点估计和区间估计。如果采用区间估计，这里我们不知道总体的平方差，只能用t 分布进行拟合，但是由于我们所进行的小步测量总步数不会取值太大，容易出现样本方差不收敛的情况，因此我们用点估计进行参数估计。在对三参数l o g i s t i c 模型进行能力的参数估计的方法中，最为普遍的是极大似然函数。这里我们做一个假定，假设项目的三个参数，区分度、难度和猜测系数是已知的。在这种情况下我们应用的是在项目参数已知的条件下运用极大似然估计法对能力值进行参数估计。以啊，：k i 口) = 兀鼻耐q 1 - 一i m l( 公式3 6 )其中，i 是项目对应的编号，1 1 是被试做出反应的项目总数，毋代表被试对项目i 做出正确反应的概率，2 代表被试对项目i 做出错误反应的概率。这样针对被试对一组项目的反应情况构成的向量( ，：ku n ) ，通过使得该似然函数取值最大，就能够对口进行求解。极大似然函数具有这样的数学特征，当取值最大的时候一阶导数恰好等于零。但由于对于该函数求导后仍含有参数，需要继续求导，并利用n e w t o n r a p h s o n 方法求出能力的极大似然估计值n 刖。东北师范大学硕士学位论文3 4 算法设计3 4 1 假设为了使整个算法更加科学、合理，除了l o g i s t i c 模型本身需要的基础假设外，我们还做了两个假设：( 1 ) 假设所有项目的三个参数是己知的，可信的而且是有效的；( 2 ) 每个项目当被试反应后都能做出对或错的反应，不含人工干预，因此我们暂时不考虑各种客观题型。3 4 2 编码本算法不同于传统i r t ，每次出一个题目；本算法也不同于传统遗传算法进行组卷，编码对象是整个试卷的解空间。本算法实施小步组卷，这样就能够一方面结合了传统遗传算法能够以多个可行解出发并行计算、全局寻优的优点，另一方面结合了i r t 根据被试能力水平与反应情况动态调整试卷的思想。小步测量模型定义了项目组中不同类型的个数，即定义好了题型及对应的题量，这种情况下便于我们采用题号进行编码，并且根据题型进行整数分段编码。而且这种编码方式极大的缩减了编码的位数。按照我们前面的定义，小步组卷的模型为s m ：= ( i t e m l ，i t e m2 ，i t e mn )那么我们现在还需要将其根据题型进行分段编码。如果假设小步组卷模型中定义的试题类型为：m = 互，互k ，乙 ，在实际应用中小步组卷模型采用的题型向量可以表示为 互，互k ，瓦 ，这里七朋，而且每种类型所对应的题数构成的向量值为( 1 ，：，k ，m ) 。那么小步组卷模型就可以编码：s m ：= ( ( 互l ，互2 ，k ，互五) ，( 互。，瓦2 ，k 瓦五) ，k ，( 乙1 ，乙2 ，k ，乙瓦) )( 公式3 7 )整个编码没有符号间隔，本写法是直观起见。那么问题最终的解就是寻找一串最符合目标函数和最满足约束函数的s m 。这里需要对编码的位数进行说明，我们对一个项目的编号分为两部分，一部分是体现的是知识点编号，假设有k 个知识点，则这部分的编码数位为1 9 ( 1 0 ) ：另一部分体现的是项目自己的编号，假设该项目所属于的题型共有t n 个项目，则这一部分的编码位量数为1 甙t n ) 。则总编码位数则应该是( 1 9 ( e ) + l g ( l ) ) 。i = 1例如，假设每类题型中的项目总数均为1 0 0 0 个，而总知识点为1 0 0 个。小步组卷中利用单项选择题和填空题，并且单项选择题2 道，填空题1 道，当选择题对应的编号是1 2 和2 2 ，填空题编号为1 9 。三道题所对应的知识点分别是0 1 ，0 3 和0 7 ，那么对应的小步编码为：0 1 0 1 2 1 0 3 0 2 210 7 0 1 9 。1 6-，东北师范大学硕士学位论文3 4 3 初始化在遗传算法中，初始群体的选择对搜索效率及最终结果都具有很重要的作用，如果初始群体离散程度高一些，更容易实现全局最优化n 引。在自适应测试当中，初始化项目更为重要，将直接影响被试能力的评估，进而能力评估又会进一步影响接下来的项目组选择，不断循环。本文中所指的初始化，包括两个对象。一个对象是被试的能力，另一个对象是测试所用的项目。如果对这两个对象进行估计，分两种情况。第一种情况，即当被试首次利用该系统进行自适应测试的时候，我们利用公式3 4 应用一次遗传算法，选择能够满足i p ( o ) - o 5 i e 的项目。i p ( o ) - o 5 i ：p ；l 置一e ( x ) i( 公式3 8 )其中，j ( 口) 是利用公式3 6 和公式3 7 计算获得的，这里小步测量中一组项目的总信息量；d 代表项目被同一个被试使用过的间隔时间，这是一个均值；t 代表同一个项目在系统中的使用次数，也是一个均值；e il x , - e ( x ) i 是项目与各个离差的累和，也是一个均值，其中e ( x ) 代表某项约束的期望值。在该公式中我们不只考虑到最常用的两个选题模型，而且还有效利用了项目的其他信息，能够从一定程度上降低猜测的发生。3 4 5 选择算子最常见的选择策略是利用每类个体在总体中占有的比例权重。由于我们是在自适应测试中采用遗传算法，尤其是我们将测试定义为通过多个小步测量而完成，后一步必然在前一步完成的基础上进行。因此，我们的选择算子具有父辈保留的特征。在新小步测量取值时，我们选择轮盘赌方式。即，选择满足该条件的小步测量个体：淞一一t 赞j i - ri ，m 剐豇万( 公式3 9 )其中，z 表示某个个体出现的频率，e 表示某个个体的适应度取值。通过这种改变的遗传算法中的选择算子具有了规模递增性，更适应我们所出的组卷数学模型。3 4 6 交叉算子交叉是产生新个体的重要方式之一，如果交叉概率过高，则相关于遍历造成效率低下，而交叉概率过低，则又容易产生个体变化小的情况。在本文所提出的算法中，我们要求每一小步测试的取值都与已经取过的值不同，因此我们需要很好的控制交叉的频率，这里可以采用文献踟所提出的交叉概率自适应算法。只：卜等【只。c f c f 嘿而具体的交叉操作我们选择分段多点交叉，即按照所定义的编码及分段方式，总体中随机两个个体将在知识点基因位和项目编号基本位上分别进行交叉，而且知识点基因位和项目编号基因位可以遵从不同的概率。依据前面编码所进行的限定，假设有两个个东北师范大学硕士学位论文体，他们进行交叉的结果可以产生个体3 。个体1 ：0 1 0 1 2 1 0 3 0 2 2 1 0 7 0 1 9个体2 ：0 1 0 8 9 0 3 0 5 6 0 8 0 31个体3 ：0 1 0 8 9 1 0 3 0 2 2 1 0 7 0 3l由于交叉算子产生的新个体并没有增加新的项目，但是这步操作能够将某些重要知识点的相关项目进行保留。3 4 7 变异算子基于本文所提出的组卷模型，变异算子显得同样重要，对于局部搜索具有很大的影响。在变异概率的控制方面我们仍然采用如前所述类似的自适应算法。己= 卜警【匕-l c 曙l 为了更好的利用变异域算子所起到的调节作用，我们在被试经历较少的小步测验的时候，我们采用非均匀变异的方法，而且在被试经过的小步测验总量比较大的时候，我们将采用均匀变异的方法。这样做的好处是，在自适应测试初期，尽可能大幅度的进行搜索，而在自适应测试进行了一定阶段的时候，可以更加有针对性的在知识点实际分布与知识点期望离差较大的项目中进行搜索。3 4 8 结束条件对于