（计算机应用技术专业论文）网络考试系统的组卷算法及安全策略研究.pdf

摘要网络考试已日益成为一种主要的考试方式。如何把计算机和网络更有效地引进教育领域为教育服务已成为教育学中的一个新课题和发展方向，论文在“湖南省高校学生非计算机专业计算机应用水平等级考试”系统的基础之上，综合人工智能技术和网络安全技术对网络考试系统的组卷算法和安全策略进行研究。针对目前组卷系统耗时长、效率低的难题，通过对组卷问题目标分析，建立了组卷问题的数学模型。在组卷问题的数学建模基础上，结合遗传算法( g e n e t i ca l g o r i t h m s 简称g a ) 的原理和思想，对自动组卷问题进行研究。通过对遗传算法研究，设计了一种适用于目前考试系统的组卷算法。根据组卷的实际情况采用分段二进制的编码策略对组卷问题解进行编码；为了避免遗传算法中出现未成熟和无目标的随机漫游现象，对适应度函数进行定标，同时通过对适应度函数的线性定标，乘幂定标及指数定标的对比分析，证明了指数定标的有效性；由于遗传算子受到了编码策略和约束条件的制约，提出了分段内独立交叉算子和分段内两点变异算子；基于适应度作为衡量群体多样性的标准，提出了一种自适应的交叉概率和变异概率。最后通过实验验证了改进遗传算法的搜索能力和效率。通过对网络考试系统的安全需求分析，建立了网络考试系统的安全模型。在网络与信息安全中密码扮演着非常重要的角色，通过对几种加密算法进行了比较分析，在此基础上结合实际情况，设计了一种适用于考试系统的混合加密算法，最后将它用来加密考试系统中数据。关键词网络考试系统，组卷算法，遗传算法，网络体系结构，加密算法a 。b s t r a c tn e t w o r ke x a m i n a t i o ni si n c r e a s i n g l yb e c o m i n gam a i ne x a mf o i t n i th a sb e e nan e wt o p i ca n dd i r e c t i o nf o re d u c a t i o na n dc o m p u t e ra p p l i c a t i o nt h a th o wt ou s eo ft h ec o m p u t e ra n dt h en e t w o r ki nt h ee d u c a t i o nf i e l d i nt h i sp a p e r , b a s eo nt h ec o l l e g en o n - c o m p u t e rp r o f e s s i o n a lc o m p u t e rr a n ke x a m i n a t i o ns y s t e mo fh u n a np r o v i n c e ，t h ec o m p o s i n gt e s tp a p e ra l g o r i t h ma n dt h es e c u r i t yp o l i c ya r er e s e a c h e dt h r o u g ht h ea r t i f i c i a li n t e l l i g e n c ea n dn e t w o r ks e c u r i t yt e c h n o l o g y a g a i n s tt h ep r o b l e mo fc o s i n gl o n gt i m ea n dl o we f f i c i e n c yi nt h ec o m p o s i n gt e s tp a p e rs y s t e m ，t h eo b j e c to ft h ec o m p o s i n gt e s tp a p e ri sa n a l y z e da n dt h em a t h e m a t i cm o d e li sb u i l d b a s e do nt h i sm o d e l ，t h ep r o b l e mo ft h ea u t o c o m p o s i n gp a p e ri sr e s e a r c h e dt h r o u g ht h et h e o r yo ft h eg e n e t i ca l g o r i t h m ( g a ) b a s eo nt h er e s e a r c ho ft h eg a ，as u i t a b l ec o m p o s i n gp a p e ra l g o r i t h m si sd e s i g n e d a c c o r d i n gt ot h ea c t u a lc o n d i t i o n ，s u b p a r a g r a p hb i n a r ys y s t e mc o d i n gs t r a t e g yi su s e dt oc o d et h ec o m p o s i n gp a p e rp r o b l e m t oo v e r c o m et h ep r e m a t u r ec o n v e r g e n c ea n dt h eg e n e t i cd r i f t i n g ，t h ef i t n e s si ss c a l e d a tt h es a m et i m e ，c o n t r a s t e dw i t ht h el i n e a rs c a l i n gt h ei n d e xs c a l i n gi sp r o v e dv a l i d i t y d u et ot h ec o d i n gs t r a t e g ya n dt h er e s t r i c t i o nc o n d i t i o n ，c r o s s o v e ro p e r a t o ra n dt w o - p o i n tm u t a t i o no p e r a t o rw i t h i nt h es u b p a r a g r a p ha r ea d v a n c e d b a s e do nt h es t a n d a r do ft h a tt h ed i v e r s i t yo ft h ep o p u l a t i o nc a nb es c a l e db yt h ef i t n e s s ，t h ea d a p t i v ec r o s s o v e rp r o b a b i l i t ya n dt h em u t a t i o np r o b a b i l i t yi sd e s i g n e d t h e n ，i nt h ep r o c e s so ft h ec o m p o s i n gt e s tp a p e lt h es e a r c ha b i l i t ya n de f f i c i e n c yo ft h ei m p r o v e dg aa r ep r o v e db ye x p e r i m e n t s b a s e do nt h er e q u i r e m e n ta n a l y s e so ft h en e t w o r ke x a m i n a t i o ns y s t e m ，t h es e c u r i t ym o d a li sb u i l d c r y p t o g r a mi st h ea l l - i m p o r t a n tr o l ei nt h es e c u r i t yo ft h en e t w o r ka n di n f o r m a t i o n c o m p a r i n ga n da n a l y z i n gs e v e r a le n c r y p t i o na l g o r i t h m s ，am i x e de n c r y p t i o na l g o r i t h ms u i tf o rn e t w o r ke x a m i n a t i o ni sd e s i g n e d f i n a l l y , i ti su s et oe n c r y p tt h ed a t ao ft h es y s t e m k e yw o r d sn e t w o r ke x a m i n a t i o n ，c o m p o s i n gt e s tp a p e ra l g o r i t h m ，g e n e t i ca l g o r i t h m ，n e t w o r ks e c u r i t ya r c h i t e c t u r e ，e n c r y p t i o na l g o r i t h mi i原创性声明本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其它人已经发表或撰写过的研究成果，也不包含为获得中南大学或其它单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说明。作者签名：鍪塑趸日期：丛年卫月监日关于学位论文使用授权说明本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省有关部门规定送交学位论文。v -作者签名：盥导师签客至型型旦日期：立竺兰年鱼月生日硕士学位论文第一章绪论1 1 课题来源及研究背景第一章绪论考试是教学过程中的重要环节。传统的考试方式采用纸上作答方式，从选题、监考、评卷和总分的一整套过程中都是采用手工方式，这种传统考试方式存在着工作量大，效率低等弊端。随着计算机与网络的应用和日益普及化，网络考试已经成为目前国际上普遍采用的一种考试和认证方式。网络考试系统的发展是从标准化计算机考试开始到如今的各种网络认证考试。标准化考试，结合了统计分析原理，对考试过程命题、考试、阅卷、统计分析和成绩总结提供支持和指导。这种考试方式一开始主要使用在一些西方国家，试卷仍采用纸，用铅笔在答题卡上涂黑圈，阅卷时使用光标阅读器将答题卡输入到计算机内进行评阅。比起传统的考试方式，标准化考试阅卷速度快、成绩统计效率高，同时费用低。但是标准化考试还是离不开纸介质，仍需要人工出题。我国从1 9 8 1 年开始首次引入标准化考试托福考试，之后的大学四、六级考试也是采用这种方式。近几年来，将网络技术应用于考试系统中，使网络考试系统成为目前一种主要的考试方式【2 】o 美国的思而文公司，是全球最大的计算机化认证考试服务公司，它开创了计算机化考试技术和管理标准，在世界的6 大洲1 4 1 个国家建立认证考试网络，美国研究生入学考试( g r a d u a t er e c o r de x a m i n a t i o n ) 、工商管理类研究生入学考试( g r a d u a t ef o rm a n a g e m e n ta n da d m i n i s t r a t i o nt e s t ) 等都已经采用网上考试的方式。在国内随着各种网校在线教育的兴起，也出现了很多网络考试u j ，如涉及i t 领域证书认证、g r e 、g m a t 和职业证书考试等。网络考试系统在通用题库管理、智能组卷、标准化测试、交互性、考试结构的统计分析等方面已经超越了传统的基于纸和笔的考试方式，综合各个网络考试系统，一般包括以下几部分：( 1 ) 试题库子系统题库是严格遵循教育测量理论，在精确的教学模型上建立起来的教育测量工具3 1 ，这个子系统是整个考试系统中重要的一部分，主要包括：题库维修，即对试题进行增加、删除和修改；考试定义，即对组卷规则或约束条件的定义；题库统计分析，即根据考试结构对试题进行分析，如出题率，得分率。( 2 ) 考试子系统考试子系统是考试系统中的关键部分，完成考生的登陆，根据考生的信息，硕- | ：学位论文第一章绪论从试题库中抽取试题，因而，组卷是这一系统的主要部分。( 3 ) 考务子系统主要包括：报名管理，即实现考生的报名，并将考生信息录入到数据库中；考试管理，即负责返回试题，接受从考点上传的考生答题结果和考试成绩；考场支持，即对考生进行的身份验证，对接受的试卷进行加密和解密。( 4 ) 评分子系统对回收的考试结果试卷根据题库中的正确答案，进行评分，并对考试成绩进行分析，即统计考生的最高分，最低分及平均分。网络考试系统利用网络的传输特性，实现高效、准确和科学的无纸化测试，主要体现在以下几方面的特性：( 1 ) 考试无地域差异，现在计算机化考试让考生在网络环境下接受实时考试，考生可以选择自己方便的时间就近参加考试。( 2 ) 组卷的效率高，在考生开始考试时，根据考生的考试要求能及时地从数据库中组成一份符合要求的试卷，同时保证组卷的速度要快。( 3 ) 反馈速度快，考生考完试，能立即得到考试成绩和非常详细、专业的分析报告，这种及时的信息反馈告诉考生己掌握了什么，还缺少什么，能让考生真正掌握知识。( 4 ) 题库修改方便，出题老师能根据考试的要求及时的更改题库中的试题，同时能及时把试题反应到考试中去。( 5 ) 考试的安全性、客观性，通过安全策略保证考生考试过程中的考试安全，如采用加密手段对考试的题库和考试过程中传输的数据进行加密。同时在同一考场中每个考生的考题可以不相同，由于考试的随机性，避免两份试卷相同。从以上论述中可知，组卷速度和安全策略是网络考试系统的关键部分，组卷速度关系到考试效率和考试是否能正常运行，安全性保证了考试公正性和考试信息保密性。目前网络考试系统存在着以下几个问题：( 1 ) 目前组卷系统大多采用随机选取法或回搠法，在实际操作中，发现它们不仅耗费时间很长而且容易进入死循环。( 2 ) 由于网络考试系统受信息存放分散化、信息处理网络化和系统应用模式的影响，现有的多数系统还不能做到提供足够的信息安全保护。课题来源于“湖南省普通高等学校非计算机专业学生计算机应用水平等级考试系统”，本论文基于该系统，对网络考试系统目前存在的问题，综合人工智能技术和网络安全技术，对网络考试系统的组卷方法和安全策略两个主要方面展开研究，这对于推动和深化网络考试系统的发展及对类似系统的开发，都具有很好的理论和实际应用意义。硕：l ：学位论文第一章绪论1 2 国内外研究现状与水平1 2 1 组卷算法的研究现状自动组卷是考试系统的重要组成部分，如何既好又快的从题库中抽出一份符合考试要求的试题，是考试系统的研究热点之一。自动组卷就是按照教师和教学的要求，由计算机自动从试题库中选择试题，组成一份符合要求的试卷，并具有随机性，科学性和合理性。组卷算法涉及到全局寻优和速度快慢的问题，很多学者对其进行了研究，以前所采用的算法大多是随机选取法和回溯试探法。随机选取法【4 】【5 】【6 1 根据状态空间的控制指标，由计算机随机抽选一道试题加入试卷中，此过程不断重复，直到组卷完毕，或已无法从试题库中抽选满足控制指标的试题为止。乐光学，彭小宁等在概率模型和搜索理论的基础上提出一种新的启发试搜索算法以完成自动组卷过程【6 j ；路平，王敏娟，根据用户命题要求进行量化处理产生的试卷模型，应用随机抽取算法完成组卷过程【7 1 ：黄丽雯，陈渝光，根据命题计划原则，设计了一种随机抽取算法以完成组卷过程【8 1 ：h m a n n i a和r s r i k a n t 都是直接利用随机函数完成对试卷的抽取过程【9 】 1 0 1 ；j r q u i l a n 利用随机函数r a n d ( ) 在试题库中抽取样题进行组卷j ：s c h a n d h u n 和u d a y a l 根据命题的数量及难度系数，随机产生一个在其规定范围内的数，利用随机抽取算法完成组卷过程【l ”。这些随机抽取算法对于单个试题的抽取运行速度较快，但是对于整个组卷过程来说组卷成功率低，花费时间长。回溯试探法【4 1 1 5 1 是将随机选取法产生的每一状态类型记录下来，当搜索失败时释放上次记录的状态类型，然后再依据一定的规律变换一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成完毕或退回出发点为止。胡维华使用回溯试探法实现自动组卷过程【”1 ；h a l lp a v ，p a p a s o g o u l o ss 将随机抽取法和回溯法相结合实现组卷的过程【1 4 】；w b u n t i u n 使用决策树实现回溯试探法完成信息的搜索过程【1 5 1 。这些回溯试探算法对于状态类型和出题量都较少的题库系统而言，组卷成功率较好，但是这种算法对内存的占用量很大，程序结构相对比较复杂，而且选取试题缺乏随机性，组卷时间长。因此随机选取法和回溯试探法存在着很大的缺陷，因而不是很好的组卷算法。生命科学与工程科学的相互交叉、互相渗透和相互促成是近代科学技术发展的一个显著特点，而遗传算法的蓬勃发展正体现了科学发展的这一特征和趋势。遗产算法是由美国m i c h i g a n 大学的j h o l l a n d 教授于1 9 7 5 年首次提出的卅【1 7 1 。它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于剃度信息。它尤其适倾上学位论文第一章绪论用于处理传统搜索方法难于解决的复杂和非线性问题，可用于组合优化、及其学习、自适应控制、规划设计和人工生命等领域，是2 1 世纪有关智能计算中的关键技术之一。遗传算法求解优化问题的基本思想是：把优化的目标函数解释为生物种群对环境的适应性，把优化变量对应为生物种群的个体，由当前种群出发，利用合适的复制、杂交、变异与选择操作生成新一代种群，重复这个过程，直到求得合乎要求的种群停止。遗传算法的主要形式为比例选择、单点杂交和位杂交。遗传算法的一般步骤包括：( 1 ) 确定编码方案：遗传算法求解问题，不是直接作用在问题的解空间上，而是作用在解的某种编码之上。( 2 ) 确定适应函数：适应度值是对解的质量的一种度量，解的适应度值是演化过程中进行选择的依据。( 3 ) 选择策略的确定：优胜劣汰的选择机制使得适应度值好的解有较高的存活概率。( 4 ) 控制参数的选取：控制参数主要包括种群规模，算法执行的最大迭代数，执行不同的遗传操作的概率及一些辅助性的控制参数。图卜1 遗传算法的一般操作近年来g a 这一算法随着神经网络、人工生命、进化计算等研究的兴起，引起了人们越来越多的兴趣，并已应用于搜索问题、优化问题、机器学习、自编制程序、模式识别和人工神经网络等方面【1 8 】f 1 9 】，遗传算法获得巨大成功的主要原因在于它具有如下一些突出特点：( 1 ) 遗传算法是对参数的编码进行操作，而不是对参数本身。硕士学位论文第一章绪论( 2 ) 遗传算法具有并行行，采用同时处理群体中多个个体的方法，即同时对搜索空间的多个解进行评估。( 3 ) 遗传算法使用适应度函数来评估个体，而不用搜索空间的知识或其它辅助信息，从而使问题依赖性减少。、( 4 ) 同时遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。( 5 ) 遗传算法采用概率的变迁规则来指导它的搜索方向，而不是采用确定性规则。( 6 ) 遗传算法在解空间内不是盲目穷举或完全随机的测试，而是一种启发式搜索，其搜索效率往往优于其它方法。正是由于遗传算法具有上述的特点，它作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理等显著特点比其它搜索算法更适用于组卷系统。近几年来国内外学者把遗传算法应用到组卷系统中来。g o r d b e r em w 应用遗传算法的寻优特性为组卷问题建立了寻优模型1 2 0 。国内的应用较迟，杨青通过对遗传算法的编码和遗传算子的改进设计了一种应用于组卷问题的组卷算法【2 l 】；董敏等通过引入惩罚因子，将遗传算法引入到组卷中；闭应洲，苏德富等，通过建立矩阵编码，将改进遗传算法应用于组卷过程【2 3 】；周晓红，通过对遗传算法中最优保留策略的改进，将遗传算法应用到组卷过程中1 2 4 j ：毛秉毅通过数据库结构的研究提出一种新的数据库结构，并结合遗传算法实现组卷过程1 2 5 1 ；张文祥，马银花通过组卷的约束条件建立组卷的数学模型，利用遗传算法完成组卷过程【2 6 1 。张辰等是将遗传算法和模拟退火算法相结合实现试题的组卷过程【”1 。目前采用遗传算法的组卷策略还存在着以下几方面的问题：( 1 ) 遗传算法适应于全局搜索，但应用于组卷系统中，容易陷入局部寻优，得出的不是全局的最优解。( 2 ) 依然存在未成熟和随机漂移现象。( 3 ) 有些组卷算法虽然采用了遗传算法但是由于算法的庞大并没有提高组卷的效率。综上所述，自动组卷系统研究中遇到的主要难题是如何保证生成的试卷能最大程度满足用户的不同需要。而目前的组卷算法往往因为约束条件的局部满足而导致组卷失败，同时组卷过程所需时间开销大，无法满足实时应用。因此，迫切需要能实现全局寻优和收敛速度快的智能组卷算法。1 2 2 信息系统安全策略的研究现状网络考试系统是现代信息系统的一个应用分支。随着信息技术的应用与发硕：f ：学位论文第一章绪论展，信息安全从最初的信息保密性发展到信息的完整性、可用性、可控性和不可否认性，进而又发展为“攻( 攻击) 、防( 防范) 、测( 检测) 、控( 控制) 、管( 管理) 、评( 评估) 等2 8 1 。起初，美国国防部为适应军事计算机的保密需要，制定了“可信计算机系统安全评价准则”( t c s e c ) 郾j 。9 0 年代初，针对t c s e c 准则只考虑保密性的局限，提出“信息技术安全评价准则”( i t s e c ) ，这一准则包括了保密性、完整性、可用性等概念。但是近年来提出了“信息技术安全评价通用准则”( c of o ri t s e c ) 。c c标准于1 9 9 9 年7 月通过国际标准化组织认可，确立为国际标准，编号i s o i e c1 5 4 0 8 2 9 1 。我国在系统安全的研究是从近几年开始的，分别进行了安全操作系统、安全数据库、多级安全机制的研究。1 9 9 9 年1 0 月发布了“计算机信息系统安全保护等级划分准则”【2 9 1 1 3 们，该准则为安全产品的研制提供了技术支持，也为安全系统的建设和管理提供了技术指导。信息安全服务依靠安全机制来完成，而安全机制主要依赖于密码技术，因此，密码技术是信息安全的核心【3 l 】。而密码算法( c r y p t o g r 印h y a l g o r i t h m 用于加密和解密的数学函数) 又是密码的核心，所以，密码算法是保障信息安全的核心之核心，其重要性不言而喻。对密码算法的研究古已有之，它的基本思想是对原始数据进行了复杂的变换，以使非法接收者很难从中破译出原始的信息，而合法用户则可以利用密钥解密。换位和置换在本质上是一种字母游戏。数据本身并没有改变，只是被安排成了另一种不同的格式，所以其破译比较有规律可循，相对简单。主要的置换算法有棋盘密码、恺撒密码、单表置换等1 9 7 6 年d i f f i e 和h e l l m a n 提出的非对称密钥密码体系是现代密码学的里程碑 3 1 1 1 3 2 1o 自此以后，密码算法的改进是沿着对称密钥密码体系和非对称密钥密码体系两个分支发展的。i b m 公司研制的d e s ，即d a t ae n c r y t i o ns t a i l d a r d 数据加密标准，是典型的对称加密算法，1 9 7 7 年美国商业部所属国家标准局正式批准其作为美国联邦信息处理的非机密数据加密标准。自公布以来，d e s 一直超越国界成为国际上商用保密通信和计算机通信常用的加密算法。随后出现的三重d e s 算法使用两个5 6 位的密钥混合加解密，密钥长度达1 1 2 位，加密强度大大增加。但是作为对称加密算法它的特点是：加密算法和解密算法互逆；加密密钥和解密密钥相同，效率较高，可以满足大量信息的加密需求；通信双方需要事先交换密钥，密钥容易泄漏而不能确保安全性；无法实现传输信息的不可否认性；密钥存储、使用和管理困难。硕士学位论文第一章绪论r i v e s t 、s h a m i r 、a d l e m a n 三人于1 9 7 8 年提出r s a 算法，是目前非对称加密领域内最为著名的算法。它的安全性是基于大整数质因解的困难性，即寻找大整数( 几百位长) 的质因子是计算不可行的。由于r s a 涉及到大数的计算，无论是硬件实现还是软件实现，效率都比较低，其中硬件实现的效率是d e s 的1 1 0 0 0 ，软件实现的效率是d e s 的1 1 0 0 。因此它不适用于对长的明文进行加密，常用来对密钥进行加密，即与对称加密算法结合使用【3 ”。当前密码学己成为一门多学科交叉渗透的边缘学科，它综合了数学、物理、电子、通信和计算机等诸多学科的长期知识积累和最新发展成果。被誉为“混沌之父”的洛轮滋本掀起了混沌理论的发展。除此之外近年来国内外还不断涌现出大量的新技术和新概念，如零知识证明( z e r ok n o w l e d g ep r o o f ) 、盲签名( b l i n ds i g n a t u r e ) 、量子密码技术( q u a n t u mc r y p t o g r a p h y ) 、热流密码( h e a tf l o wc r y p t o g r a p h y ) 、图视密码( v i s u a lc r y p t o g r a p h y ) 等。1 3 研究的目的和意义通过对遗传算法的研究和改进，设计一种适合考试系统的自动组卷算法，以达到既快又好的优化组卷目的。通过对网络考试系统的安全策略研究，提出一种使用于网络考试系统的安全体系结构，并针对系统数据加密算法，设计与实现一种使用于考试系统中的混合加密算法，从而保证考试过程传输数据的安全性和保密性，课题的研究内容不仅对当前的网络考试系统的优化具有深远的意义，而且对其它类似系统的设计有所帮助，并对我国的智能计算机教学和网络教学系统的研究和开发具有较高的学术价值和应用价值。1 4 论文的内容结构论文基于“湖南省普通高等学校非计算机专业学生计算机应用水平等级考试”系统，针对目前网络考试系统存在的问题，结合理论研究和实验相结合的方式对组卷算法和安全策略进行研究，内容主要包括如下：( 1 ) 介绍网络考试系统的概述及组卷算法和安全策略的发展现状并指出当前考试系统存在的问题。( 2 ) 对基于网络的计算机等级考试系统的系统结构和功能模块进行介绍。( 3 ) 在组卷算法的研究中，对组卷问题进行目标分析，建立组卷问题的目标矩阵；对遗传算法进行研究，设计了一个适应于组卷问题的改进遗传算法，并将其应用于组卷过程；通过实验验证改进遗传算法在组卷过程中的效率。硕士学位论文第一章绪论( 4 ) 针对当前网络考试系统中存在的安全问题，通过对网络考试系统的安全进行需求分析，设计一种适应于考试系统的安全体系结构；通过对密码算法的研究和比较设计了一种适合考试系统的混合加密算法，保证考试系统中数据的安全性。( 5 ) 对论文进行总结。硕士学位论文第二章基于网络的计算机等级考试系统第二章基于网络的计算机等级考试系统2 1 网络考试系统结构网络考试系统是一个复杂的信息系统，目前，基于网络的考试系统，依据网络布局和规模，可具有不同的体系结构，主要有以下几类：( 1 ) 单机模型这种模型主要由考试系统和试题库组成，试题和考试系统事先安装在单机上，考生考试时，每人发张软盘，插入软盘便可进行考试。软盘上存放着抽题策略，并保存各考生的考试信息。这种考试模型的优点是，结构简单，易于开发。但是存在着题量少、试题安全性差、数据回收工作量大、不利于成绩统计和分析等缺点，基本上被淘汰。( 2 ) 基于l a n 的考试系统这种考试系统是以局域网作为考试环境，采用传统的两层客户机n 务器( c s ) 结构。考试系统放在考生用的客户机上，数据库，考试管理系统及成绩分析系统放在服务机上。考试过程为：考生登陆考试界面，服务器根据考生的登陆信息对考生进行身份验证，并按一定的组卷算法抽取试卷，将结果传给客户机。考试结束后，客户端的考试系统自动评分，并将答卷和成绩返回给服务器。这种考试系统的设计相对简单易于实现，同时便于成绩统计和分析，但是这种模型适用的地域范围相对集中、距离相对较近，比如同一试验室、同一栋楼房，同一校区。( 3 ) 基于i n t e m e t 的网络考试系统基于i n t e m e t 的网络考试系统是一种分布式的结构，一般采用了浏览器n 务器( b s ) 的网络计算模式，即三层c s 结构，包括客户浏览器、应用服务器、数据库服务器如图2 - 1 。客户机应用层数据库服务器图2 - 1 三层c s 模式结构客户端即为考生的用户界面，考生通过浏览器输入考试要求并浏览服务器的考试信息。硕士学位论文第二章基于刚络的计算机等级考试系统应用服务器，主要包括：组卷，评分，考务管理等功能。利用应用程序，完成信息的管理和传递。这种考试系统主要适用于全国、乃至全球范围的考试。如g r e 考试等，与传统的c s 结构相比，这种结构易于拓展，开发周期短，而且移植方便，不须安装客户端( 客户端只使用浏览器) 。但其缺点是客户端的处理能力差，无文件和目录的操作能力，也很难完成与其它程序之间的数据交互，其结构复杂论文所基于的“湖南省普通高等学校非计算机专业学生计算机应用水平等级考试”系统，是由局域网和广域网两部分组成，采用分布式计算和管理的体系结构，结合局域网和广域网两种体系结构的特点，其结构图如图2 - 2 。整个网络考试体系构成一个基于i n t e m e t 的b s 结构，各考点的服务器与考生客户端组成了基于l a n 的两层c s 结构。例如，考生所需要的考卷是通过省教育厅服务器从中心数据库提取，并通过考点服务器返回到考生的客户机上。同时考生客户机和机房服务器又组成一个两层的c s 结构。图2 - 2 湖南省计算机等级考试系统的结构图2 2 网络考试系统的功能模块户机考试系统实现从考生报名、试卷生成、组织考试到阅卷评分、考试结果统计分析，全过程由计算机管理。“湖南省普通高等学校非计算机专业学生计算机应用水平等级考试”系统主要由六大模块组成：省教育厅专用模块、考务管理模块、硕：l 二学位论文第二章基于网络的计算机等级考试系统题库制作模块、客户端管理模块、服务器端管理模块、安全管理模块。其功能图如图2 - 3 。图2 - 3 湖南省计算机等级考试系统的模块图( 1 ) 省教育厅专用模块该模块的参与者是考试中心的管理人员，主要完成的功能：初始化参考学校( 考点) 代码及名称、考试计算机语种、考试时间长度等；汇总出题专家试题库；生成考点的初始化数据库和试题库；回收、汇总考点考试成绩、对考试结果进行各种统计、打印输出参考学生考试通过证书。( 2 ) 考务管理功能主要实现报考省计算机等级考试的考生报名：对参考点信息和考生信息进行增加、删除、查询，实现考生成绩的回收与查询，实现各种数据的汇总；实现数据库中数据的导入与导出。( 3 ) 题库制作功能该模块的参与者是出题老师，对考试试题进行录入工作。主要的功能包括：实现对六种题型( 单项选择题、文字录入题、文件操作题、编辑排版题、表格制作题、程序设计题) 进行增加、删除、修改和浏览；同时实现对出题教师( 一级教师和二级教师) 的基本信息进行增加、删除、修改和浏览。( 4 ) 客户端管理功能该模块的主要参与者是参加考试的考生，考试从用户界面登陆，输入考生信息，根据考生的信息从服务器下载试卷，然后开始作答，所以客户端管理功能的主要功能包括：实现考生登陆：从服务器下载试卷；考生答题操作；考生成绩评判和考生答题操作结果打包等。( 5 1 服务器端管理功能获取考场考试信息：根据参考考生的报考信息实现自动组卷；验证考生身份；硕士学位论文第二章基于网络的计算机等级考试系统监考考试；汇总考试结果。( 6 ) 安全功能模块实现系统外部安全和内部安全。外部安全实现考试过程不受外部入侵者的破坏，内部安全包括：只有经过授权的用户能够对系统进行访问，在系统各模块之间传输的数据如考生报名资料、试卷文件、考生答题结果和考试成绩都必须经过压缩和加密处理保证系统的安全性。根据以上的介绍，系统各模块与其参与者的关系，即用例图如图2 - 4 ，同时各功能模块之间相互协调，根据上节介绍的网络考试系统的体系结构，各功能模块根据需要分别运行于省教育厅考试中心服务器、考点服务器、考试机房服务器、机房客户机上。其中，省教育厅的专用模块、考务管理模块和题库制作模块运行在考试中心的服务器上；服务器端管理模块运行在考试机房的服务器上；客户端管理模块运行在机房的客户机上；安全功能模块，运行在各服务器上。各功能模块之间通过互联网和局域网进行命令传输和数据传输，其过程如图2 - 5 。oo钵坛泰西5m客户端管理模块题库制作模块图2 - 4 湖南省计算机等级考试系统的用例图硕士学位论文第二章共于网络的计算机等级考试系统2 ：请求登骘斗蚴恤6 ：信息查询、7 ：验证成功8 ：验证成功19 ：验证成功【1 0 ：登陆成功r ：输入考试廷、u1 2 ：请求试鼋p ! ：鲨垄堕彗1 4 ：组卷r 11 1 5 ：调用试琶1 6 ：调用试题1 7 ：返回试题挈! 型堂堕堡l1 9 ：返回试卷ii2 0 ：显示试卷i2 1 ：录入答案2 2 ：提交试卷2 3 ：保存答罨7 1 2 4 ：上交答卷。r 鬯：! 奎量萼l 2 6 ：回收试鼋l2 7 ：保存、7 l2 3 本章小结图2 - 5 考试过程中各模块之间的数据传输过程图本章对“湖南省普通高等学校非计算机专业学生计算机应用水平等级考试”系统进行简介，该系统是采用基于结合b s 和c s 两种体系结构建立起来的分布式系统结构。系统分为六大模块：省教育厅专用模块、考务管理模块、题库制作硕：i ：学位论文第二章基于州络的计算机等级考试系统模块、客户端管理模块、服务器端管理模块和安全管理模块。以下几章将对考试系统中的关键技术即，组卷算法和网络安全策略进行展开研究。颂：i ：学位论文第三章改进遗传算法的研究及其在组卷过程中的应用第三章改进遗传算法的研究及其在组卷过程中的应用3 1 组卷问题的数学模型研究在考试系统组卷问题中首先要了解考试系统的要求，然后根据考试的要求特征，设计出相应的试卷数学模式，再按试卷数学模式选取试题组成试卷。根据用户输入的组卷要求。搜索试题库中特征参数相匹配的试题，生成满足要求的试卷。自动组卷的理论基础涉及到组卷要求、数学模型、编码方法、智能组卷算法。3 1 1 组卷的目标分析组卷目标是生成一份试卷的性能要求与特征参数。在考试系统中，要根据用户的要求组出一份符合要求的试卷，试题的组卷应该满足如下的性能要求：( 1 ) 根据组卷算法能组出题目内容不同或题目顺序不同，而试题指标相同的可比性试题。( 2 ) 试题内容能根据考试中心的要求来组织。如按照各个题型所占的分数比例的要求来组织试卷。( 3 ) 试题中难度值要符合考试中心的要求，同时试题难度要适中，能根据不同的时间，不同的考试对象来动态改变。( 4 ) 试题的覆盖面要广，即考察点要分布合理，考试内容要有足够的代表性。( 5 ) 试卷要有一定的区分度，即能区分出不同水平的学生能力。评价一份试卷是否达到上述的性能要求，这就涉及到试题的质量评价指标，传统的试题评价指标主要是以试题的难度、区分度、信度和效度来作为衡量的标准。试题难度【3 6 在试卷中起着很重要的作用，不仅和老师的主观经验有关，还与学生的不同能力有关。试卷难度的计算公式为：md = 1 p $ ：p ，d ，= 1 一y p( 3 1 )百其中，p 为试卷满分值，d ，为第i 道试题的难度值，p ，为第i 道试题的参考分值，m 为试卷的题目总数，y 为该份试卷的全部考生的平均得分值。试卷难度值可以根据各道试题的难度值的d 来估算，而由考生的平均分数又可验证试卷的难度系数是否正确。但d 是需要大量统计数据来估算的，无法精确测量，谚主要有两个途径来取定：是由有经验的教师进行评估；二是随机抽取一些不同能力的学生测试后统计分析。试题的区分度的计算公式：硕士学位论文第三章改进遗传算法的研究及其在组卷过程中的应用乙04 n( 3 2 )f = 上l 一= a j + 6p其中，f 为第i 道试题的区分度，口，b 为常数( 由经验确定) ，j 为试卷考试成绩的标准差。由6 可验证试卷区分度的正确性。试卷的区分度以试题的区分度f 为基础，而f 一般难以精确计算。试题库中试题的区分度初值由专家根据经验确定，再根据考试情况进行调整。试卷的信度和效度一般只能定性评估，由于传统的试卷性能评价需要试卷的属性值，而统计测量与专家经验都难以获得精确的试题属性值。因此，必须结合定量与定性方法，同时结合教学要求、特定用户需要，来确定合适的试题属性值，建立对组卷的科学评价准则，形成组卷的目标要求。根据以上组卷的性能要求和评价试卷质量的指标分析，结合论文实际情况，论文所涉及的组卷目标主要包括：试卷总分，各题型分值，试卷难度，考试时间。在组卷中，预计用时为定量表示，试题的知识点、试题类型、用符号表示，试题难度用模糊分级【3 7 】表示。3 1 2 组卷问题的数学模型建立根据以上对组卷问题的目标分析，下面应用矩阵理论方法来建立组卷问题的数学模型网。自动组卷就是要在题库中生成满足教学和教师要求的试卷，在计算机等级考试中，试卷中每道试题包含有多个属性，其中与组卷有关的有：( 1 ) 分数：本试题的分数( 2 ) 等级：定义为计算机等级考试所属的级别类型，如表3 - 1 。( 3 ) 题型：内容所属的题目类型，如表3 - 2 。( 4 ) 难度系数：在试卷的命题过程中，针对不同考生、不同考试阶段，命题难度可不同，试题难度系数定义为：吐= 1 ( 平均分该项满分) 。一共分为四级，见表3 - 3 。( 5 ) 预计时间：预计学生完成该试题所需要的时问。根据与组卷有关的试题属性，建立目标状态矩阵如下所示：a l ia 1 2c 1 3a 1 4a l5a 2 1a 2 2a 2 3a 2 4口2 5d m l口m 2口3d m 4口m 5( 3 3 )在矩阵s 中，m 表示的是一份试卷的试题数目，d 。中的1 f ，l ，硕二l ：学位论文第三章改进遗传算法的研究及其在组卷过程中的应用每行代表某一试题，每列代表某个属性。矩阵的列表示试题的五个属性，依次为：分数、等级、题型、难度系数、预计时间。组卷过程的问题求解为：，从试题库中抽取m 道试题，组成一个m x5 的矩阵，该矩阵应最大程度满足以下五个约束条件：( 1 ) f s ( 试卷总分数) = 口。试卷总分约束，由用户给定。( 3 - 4 )( 2 ) d s ( 等级题分) 2 c 。，a ，= t d( 第d 等级的题型分)( 3 5 )1 1 1( 3 ) t x f ( 题型分) 2 c ：，q 。= q f( 第t 题型分数)( 3 6 )i = l试卷的题型约束，即某一题型分数总和在试卷总分中所占用比例的要求，q ，由用户给出其中f 1 当d 3 = t 时c2 i2 l o 当d ，3 t 时( 4 ) n d ( 难度系数) = 口。d ，。总分( 3 - 7 )i = 1全卷的难度，即试卷难度约束。( 5 ) t m ( 试卷总时间) = n ，( 3 8 )试卷预见要完成时间的约束，由用户给出。约束条件不易太多，根据实践经验，指标越多就会影响试卷的生成效率38 1 。组卷过程就是一个多约束条件的最优求解过程，它的解不一定唯一。在组卷中，预计用时为定量表示，试题的考试等级、试题类型用数字符号表示，试题难度用模糊分级表示。表3 - 1 试题的等级属性值表等级分类12含义计算机一级考试计算机二级考试柬约级等求要蜘比的分总踹耐耐宁= 所数当当分。龌书啪为级等辛卷试硕士学位论文第三章改进遗传算法的研究及其在组卷过程中的应用表3 2 试题的类型属性值表i 题型分类l23456含义单选题文字录入题文件操作题编辑排版题表格制作题程序题表3 - 3 试题的难度属性值类别1234含义难较难一般容易难度值o 一0 3o 3 0 6o 6 o 80 8 一l3 2 改进遗传算法在组卷问题中的求解根据以上对组卷问题的数学建模，本节结合遗传算法的原理和思想，对考试中的组卷问题进行研究。在对考试系统的组卷过程研究中，遇到的主要难题是如何保证生成的试卷能最大程度满足用户的不同需要，并具有随机性、科学性、合理性。而在网络交互式环境下，用户对组卷速度的要求较高。因此，高效、科学、强壮的组卷算法是实现自动组卷的关键技术，也是目前考试系统研究的热点之一。3 2 1 遗传算法的原理概述遗传算法机制是一切生命与智能的产生与进化过程。它模拟达尔文“优胜劣汰、适者生存”的原理，利用编码技术作用于染色体的二进制数串，模拟这些串组成的群体进化过程。通过基因转换机制，即用上一代串结构中适应型好的位或段来生成下一代群体。因而遗传算法是通过作用于染色体上的基因，寻找好的染色体来解决问题。在遗传算法中，将n 维决策向量x = i x l ，x 2 ，x 。1 。用n 个记号x i ( i _ 1 ，2 ，n ) 所组成的符号串x 来表示：x = x l ，x 2 ，x n把每一个x i 看作一个遗传基因，它的所有可能取值称为等位基因，这样，x就可看作是由n 个遗传基因所组成的一个染色体。一般情况下，染色体的长度n是固定的，但对一些问题n 也可以是变化的。根据不同的情况，这里的等位基因可以是一组整数，也可以是一组范围内的实数值，或者是纯粹的一个记号。最简单的等位基因是由o 和1 这两个整数组成的相应染色体就可表示为一个二进制符号串。这种编码所形成的排列式x 是个体的基因型。遗传算法中决策变量x 组成了问题的空间解。对问题的最优解搜索是通过对染色体x 的搜索过程来进行的，从而由所有的染色体x 就组成了问题的搜索空间。遗传算法通过选择、交叉、变异机理来完成对问题最优解的自适应搜索过程，硕士学位论文第三章改进遗传算法的研究及其在组卷过程中的应用基于这个共同点，g o l d b e r g 总结出了一种统一的最基本的遗传算法简单遗传算法( s i m p l eg e n e t i c a l g o r i t h m s ，简称s g a ) 。简单遗传算法只使用选择