硕士学位论文-基于校园网的无纸化考试系统的设计与实现.pdf

c l a s s i f i e di n d e x ：t p 3 1 1 u d c ：6 2 1 3 s e c r e c yr a t e ：p u b i z i e d u n i v e r s i t yc o d e ：1 0 0 8 2 h e b e iu n i v e r s i t yo fs c i e n c ea n d t e c h n o l o g y d i s s e r t a t i o nf o rt h em a s t e r d e g r e e b a s e no nc a m d u s n e td a d e r l e s se x a m l n a t i o n 1 、 l 1 一 - s y s t e md e s i g na n di m p l e m e n t a t i o n c a n d i d a t e ： s u p e r v i s o r ： a s s o c i a t e s u p e r v i s o r ： a c a d e m i cd e g r e e a p p l i e df o r ： d i s c i p l i n e ： u n i v e r s i t y ： w a n g j i a n s h e p r o f p a n gz h i f e n g q ix i a n s h e n g m a s t e ro fe n g i n e e r i n g ( p a r t - t i m e ) c o m p u t e rt e c h n o l o g y h e b e iu n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g y 河北科技大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。除文中己经注明引用的内容外，本论文不包含任何其他个人或集体已经发 表或撰写过的作品或成果。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：主轨 加f 7 年f 月厂6 日 河北科技大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权河北科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 口保密，在一年解密后适用本授权书。 本学位论文属于 日不保密。 ( 请在以上方框内打“4 ) 学位论文作者签名：弓撅 p i f 年f 月76 日 名1 去 秘 ，日 脑 名 一月 徘 西 师 事 溯 年 导捌 加 上百厂 乙于 老 ，膨眙 名 、月 龋 n 师 事 狮 年 指 刃 力 摘要 摘要 考试是教学活动中的重要环节，随着计算机网络技术及数据库技术的发展，无 纸化考试系统越来越受到重视。传统的考试形式已经不能适应现代考试的需要。基 于校园网的无纸化考试系统将成为现代教育考核方式中的一种重要手段。 本文综述了网上考试的重要意义、现状、研究目的和内容。详细地分析了当前国 内外考试系统的设计思想与实现技术以及当前各种在线考试系统存在的问题，并在 此基础上提出了一套基于w e b 的网上考试系统的设计方案，对其应用的相关技术理 论、各构成模块的设计思想及具体的实现方法进行了详细论述。 研究内容：一是自动组卷技术，应用了p s o 算法解决组卷问题，能够保证生成 的试卷最大程度地满足用户的需要，而且符合随机性、科学性、合理性等的组卷要 求，应用p s o 算法有效的提高了组卷效率：二是针对o f f i c e 操作题建立题库的方式、 答案上传方法以及计算机自动阅卷模式都进行了有益的探讨和尝试，并给出了相应 的实施途径；三是在考试系统的安全方面作了一定的探索和研究，分别从考试过程 到题库和成绩的安全性作了相应的设计。 本系统采用n e t 框架，利用b s 架构，充分吸收了软件工程的设计思想，不仅能 很好满足考试需要，还有具有实用性、先进性、可扩展性和可靠性等优点，实现了 信息资源最大限度的共享。 关键词考试系统；软件工程；b s 模式；p s o 算法；3 d e s 加密技术 河北科技大学硕士学位论文 a b s t r a c t e x a m i n a t i o ni sa ni m p o r t a n tp a r to ft e a c h i n ga c t i v i t i e s w i t ht h ed e v e l o p m e n to f c o m p u t e rn e t w o r kt e c h n o l o g ya n dd a t a b a s et e c h n o l o g y , p a p e r l e s se x a m i n a t i o ns y s t e mi s p a i dm o r ea n dm o r ea t t e n t i o n t 1 1 ef o r mo ft r a d i t i o n a le x a m i n a t i o nc a i ln o ta d a p tt ot h e n e e d so fm o d e m e x a m i n a t i o n p a p e r l e s se x a m i n a t i o ns y s t e mb a s e do nt h ec a m p u si n t e r n e t w i l lb e c o m ea l li m p o r t a n tm e t h o dt ot h ee x a m i n i n gw a yi nt h em o d e me d u c a t i o n p a p e rs u m su pt h ei m p o r t a n ts i g n i f i c a n c e ，p r e s e n tc o n d i t i o n ，t h er e s e a r c h p u r p o s ea n dc o n t e n to fo n l i n ee x a m i n a t i o n i ta n a l y z e si nd e t a i lt h ed e s i g n i n gt h o u g h ta n d r e a l i z a t i o no ft h ee x a m i n a t i o ns y s t e ma th o m ea n da b r o a da tp r e s e n t ，d i s s e c t st h ep r o b l e m s e x i s t i n gi nv a r i o u so n l i n ee x a m i n a t i o ns y s t e ma n dp u t sf o r w a r das e to fd e s i g n i n gs c h e m e s o fo n l i n ee x a m i n a t i o ns y s t e mb a s e do nw e ba sw e l la sg i v e sa no v e r a l li n t r o d u c t i o nt ot h e a p p l i c a t i o no ft h er e l a t e dr e l a t e dt e c h n i q u et h e o r i e s ，t h ed e s i g n i n gt h o u g h to fe a c h c o m p o s i n gm o d u l ea n d t h ep r a c t i c a lw a yo fi m p l e m e n t a t i o n n l ec o n t e n t so fr e s e a r c hi nt h i sp a p e ra r ea sf o l l o w i n g ：is t ，a u t o m a t i cg r o u pv o l u m e t e c h n o l o g y , t h i sp a p e rh a sa p p l i e dt h ep s oa l g o r i t h ms o l u t i o ng r o u pv o l u m eq u e s t i o n ，i t c a ng u a r a n t e et h ep r o d u c t i o nt h ee x a m i n a t i o np a p e rg r e a t e s td e g r e es a t i s f i e st h eu s e rt h e n e e d , m o r e o v e rc o n f o r m st or a n d o m n e s s ，t h es c i e n t i f i cn a t u r er a t i o n a l l y , a n ds oo nt h e g r o u pv o l u m er e q u e s t ，a p p l i e dt h ep s oa l g o r i t h me f f e c t i v eg r o u pv o l u m ee f f i c i e n c y 2 n d ， i nv i e wo fo f f i c es u b j e c t i v et o p i co p e r a t i o nt o p i ce s t a b l i s h m e n tq u e s t i o nb a n kw a y , i nt h e a n s w e rp a s s e do nt h em e t h o da sw e l la st h ec o m p u t e ra u t o m a t i c a l l ye x a m i n e st e s tp a p e r s t h ep a t t e r na l lt oc a r r yo nt h eb e n e f i c i a ld i s c u s s i o na n dt h ea t t e m p t ，a n dh a sp r o d u c e dt h e c o r r e s p o n d i n gi m p l e m e n t a t i o nw a y 3 r d ，h a sm a d et h ec e r t a i ne x p l o r a t i o na n dt h er e s e a r c h i nt h ee x a m i n a t i o ns y s t e ms e c u r i t ya s p e c t , s e p a r a t e l yh a sm a d et h ec o r r e s p o n d i n gd e s i g n f r o mt h et e s tp r o c e s st ot h eq u e s t i o nb a n k a n dt h er e s u l ts e c u r i t y t l l i ss y s t e ma d o p t st h el a t e s t n e tf r a m ea n dm a k e su s eo fb ss t r u c t u r e i tf u l l y a b s o r b st h ed e s i g n i n gt h o u g h to ft h es o f t w a r ee n g i n e e r i n ga n dt h u si na d d i t i o nt ow e l l s a t i s f y i n gt h ed e m a n do fe x a m i n a t i o n ；i ta l s op o s s e s s e ss u c hq u a l i t i e sa sp r a c t i c a b i l i t y , a d v a n c e m e n t , e x p e n d a b i l i t ya sw e l la sr e l i a b i l i t y i ta c h i e v e st h eg r e a t e s ts h a r et ot h e i n f o r m a t i o nr e s o u r c e k e yw o r d se x a m i n a t i o ns y s t e m ；s o f t w a r ee n g i n e e r i n g ；b sm o d e ：w e bt e c h n i q u e ： 3 d e se n c r y p t i o nt e c h n o l o g y i l 目录 目录 摘要i a b s t r a c t - i i ，第1 章绪论1 1 1 课题研究的背景及意义1 1 2 国内外文献综述1 1 3 课题来源及主要研究内容3 1 3 1 课题来源3 1 3 2 主要研究内容3 1 - 3 3论文的组织结构4 第2 章相关技术原理综述5 2 1 自动组卷算法5 2 1 1 组卷算法研究现状一5 2 1 2 组卷算法分析7 2 1 3 自动组卷数学模型”8 2 1 4 试卷量化模型1 0 2 2 操作题的自动评测技术1 1 2 2 1 技能测评的一般模型”1 1 2 2 2自动化技术1 2 2 3 数据加密技术1 4 2 4 本章小结1 6 第3 章考试系统的总体设计1 7 3 1 系统需求分析1 7 3 1 1 系统总体功能结构图1 8 3 1 2 系统数据流图1 9 3 2 系统设计的基本原则2 0 3 3 系统的体系结构2 1 3 4 数据库设计2 2 3 5 基于粒子群优化( p s o ) 算法组卷2 5 3 5 1p s o 算法”2 6 3 5 2p s o 算法组卷步骤：2 6 3 5 3 组卷算法的比较与分析“2 6 i i i 河北科技大学硕士学位论文 3 6o f f i c e 操作题的自动评分系统设计“2 9 3 7 考试系统的安全设计3 0 。，3 丁l 考试系统题库的安全性一，一3 1 3 7 2 考试系统成绩的安全性”3 2 3 8 本章小结3 4 第4 章考试系统的实现3 5 4 1 系统的开发平台3 5 4 1 1 系统的开发工具3 5 4 1 2 系统的运行环境3 7 4 1 3 数据库服务器”3 7 4 2 考试系统各模块的实现3 7 4 2 1 登录系统实现”3 8 4 2 2 考试模块实现4 0 4 2 3 组卷模块实现4 l 4 2 4 题库管理模块实现4 2 4 2 5自动评分模块实现4 3 4 3 考试系统安全性实现4 5 4 3 1成绩和题库安全性实现4 5 4 3 2 考试过程中的安全性实现”4 6 4 4 系统测试与应用4 6 4 5 本章小结4 7 结论4 8 附录4 9 参考文献”5 8 致谢6 1 个人简历“6 2 i v 第1 章绪论 第1 章绪论 1 1 课题研究的背景及意义 推广并应用计算机实现无纸化考试，是近年来计算机技术的一个非常活跃的研 究领域。各式各样的资格证书考试、学历考试应接不暇。各种考试类型也在不断增加， 考试要求不断提高，而传统的人工出题阅卷、成绩统计以及试卷分析的考试形式已 不适应现代考试的需求和发展。随着互联网和计算机技术水平的不断提高，考试形 式也发生了巨大的变化，如由纸质考试向网络考试发展。从传统的纸笔考试到计算 机辅助考试，已经发展到最新的基于网络的无纸化考试【l 】。运用网络技术，准确、公 平、客观、合理地考查学生运用知识能力水平，是当今各大高职院校关于考试改革 的热点问题。特别是关于计算机方面实践性强的课程，利用无纸化考试更是大大提 高了考试过程的自动化和科学化。 利用计算机实现无纸化考试是目前研究和应用十分广泛的领域，是一种新兴的 ” 考试模式1 2 1 ，它极大地提高了考试效率，同传统的考试方式相比，使传统考试变得更 加透明，更加简单化、模式化。同传统意义上的考试相比，基于校园网的无纸化考 试系统是传统考试和考场的延伸【3 】，网络空间非常宽广，学生利用它不受时间、不受 地域限制的进行模拟练习和仿真考试，尤其是网络数据库技术在网络方面的运用， 使考试过程更加简单化，为学院的考试改革和教学评价体系的建设提供了很好的指 导意义。 ” 在高职高专院校中，通常把计算机信息技术课程作为非计算机专业一门公共必 修课，在这门课中，上机实践教学是重要环节之一。由于高校学生人数逐年增加， 对任课老师而言，每次结课考试都是又费时又费力，上机考试已经成为任课教师的 沉重负担。目前我们所接触的计算机考试，如微软认证考试、计算机等级考试，计 算机n i t 考试等，考试题型全部由客观题组成，不能正确的反应出学生对这门课知 识点的掌握情况。在o f f i c e 操作题技能测试中，如w o r d 文档编辑、e x c e l 制表、 p o w e r p o i n t 幻灯片处理等是这门课的重点和难点内容，也是任课教师用于检验教与 学效果的重要环节，考试测验如果仅以客观题形式出现，那么这样的考试是没有任 何意义的，因此，利用先进的w e b 技术研制开发网上考试系统很有必型引，它是网 络与教学的有机整合，为学校教育教学工作提供新的环境和平台，可以大大提高教 学效率，在更大范围内实现教学资源共享。 1 2 国内外文献综述 当前，全球经济飞速发展，为了在未来的信息社会中让教育处于优势位置，世 1 河北科技大学硕士学位论文 界各国都加大了对教育的投入，都积极努力把信息技术应用于教育中，同时非常重 视教育的发展，让教育走在社会发展的前列。在信息产业中，美国n o v e l l 公司于1 9 9 1 年成功的应用了c a t 进行认证考试，使参加n o v e l l 自适应考试的人数超过了1 0 0 0 0 0 0 人次【5 1 。美国政府在1 9 9 6 年提出了“教育技术规划( e d u c a t i o n a lt e c h n o l o g y i n i t i a t i v e ) ，指出到2 1 世纪初让全美国的每间教室和每个图书馆都将联上信息高速 公路【6 】。美国、英国、加拿大、澳大利亚等国家都提出了不同的1 2 1 号，大力发展本国 的计算机考试，如美国的教育考试中心就面向美国社会推出了“高级就业计算机科 学考试“ ，“计算机文化考试“ 和“专业领域考试”三类考试【_ 丌。在英国的计算机学会 中组织的计算机考试，已经普及到英联邦和其它周边国家。澳大利亚国家的澳大利 亚教育网络覆盖了全澳大利亚所有的中小学和全部高等院校。 在我国，为了达到教育信息化和教育手段现代化的目标，政府一直把它作为一 项政府行为进行规划和管理。在借鉴西方各国的成功经验同时，结合我国的实际情 况，已经设立或引进了各类计算机考试。目的是全方位、多层次地培养各类计算机 应用人才，在全民中普及计算机知识和应用技能。例如，由国家人事部和电子工业 部组织的“中国计算机软件专业技术资格和水平考试“ ，国家教委从剑桥大学引入的 “剑桥信息技术( c i t ) 证书考试“ 【引，为了规范和加强高校非计算机专业的计算机教 学工作，提高非计算机专业学生的计算机应用能力，由各省、市、自治区教委( 高教 厅) 统_ 组织的全国高校计算机等级考试( 简称c c t ) 9 1 。 教育信息化地发展对考试形式、技术和方法提出了更新的要求，网络考试是我 国高职院校中考试形式的又一次飞跃，随着和网络技术相关的其它技术在网络中的 运用和发展，将互联网作为一个大考场进行网络上的考试己成为可能i l 州。基于网络 无纸化考试在我国主要面向是社会上的资格认证考试( 如工信部的各种认证考试) 和 远程网络教育的考试。要想实现无纸化在线考试必须满足要有好得网络环境、好得 题库和好得考试平台。但一个真正的智能化的基于w e b 的考试系统的实现是一个复 杂的过程【l l 】，要想实现无纸化考试系统，是由软件开发专家、学科专家和精通考试 命题专家三者相互合作来实现的。 纵观国内外远程教育的发展趋势，实现网络化考试势在必行。远程教育的发展、 教育考试人数的增加对考试的形式提出了新的要求；社会科技的发展对考试内容提 出新的要求：计算机技术已经深入到社会生活的方面，多种行业的运行都要计算机 技术的辅助，特殊课程的考试需要，如计算机基础、会计电算化，工程设计等对考 试的特殊要求，因此，不论是工程技术人员还是一般的操作人员，都需要计算机操 作技术，所以计算机操作考试已成为一种新的考试内容。为了能极大地减轻考试前 后出题及阅卷的工作量，同时使考试更公平合理。急需重新设计开发一套适合新的 教学大纲及考试要求，并能与省计算机等级考试从形式到内容能接轨的新的网络考 2 第1 章绪论 试系统，换句话说，使考试过程全部在局域网上实现。 现有的网络考试系统存在的主要不足有： 多样化：现在高校所用的网络考试软件大都是自行开发的，其处理流程或数据 结构都自行定义，各自不同，因此并不适合作为网络考试系统。 维护困难：由于网络考试系统采用的是c s 结构，采用这种结构，当考试时， 每个客户端必须安装相应的客户端应用程序，客户要是很多，可想而知工作量有多 大，如果系统需要修改或升级时，给工作带来了很大地不便，同时对客户来说，也 是很不现实的事。 资源共享不能实现：在c s 结构中，试题及试卷多用数据库表地形式存储，如 果他或她对系统实现细节了解不多，这些考试资源会不能共享，造成资源浪费。 我们开发本系统地思路设想是：借鉴以往网络考试系统的成功之处，采用b s 结构，取长补短，改进缺点和不足，使考试功能更加完美、完善、性能更稳定的网 络考试系统。在使用功能上，以人机交互的方式实现命题，系统自动组卷、判卷、 阅卷功能。对于客户端来说，无需在主机上安装考试系统的客户端程序，也不做任 。 何配置。维护性能高，考试内容发生变化时，只做局部调整，对整个系统来说，无 须做大的修改。对于系统的安全性和保密性上来讲，力求做到最佳。 ； 1 3 课题来源及主要研究内容 1 3 1 课题来源 课题来源于本人所在单位一河北政法职业学院计算机信息技术基础课教学考试 麓 的需要。这门课为全院公共基础课，面向新生开课，学院每年招生新生4 3 0 0 名左右， 不同专业的学生开课学期不同，但必须在大一期间学完，因此每学期期末关于这门 课的考试工作对认课老师来说，任务是相当繁重的，尽管也有网上考试系统如由河 北工业大学开发的2 0 0 2 2 0 0 3 开放式考试系统、全国计算机等级考试m s o f f i c e 等 考试系统，但这些都不适合我院高职高专的学生，因此根据我院实际需要开发本考 试系统，同时根据对该课程考试的需求分析，以w e b 数据库技术为依托，利用校园 网强大的服务功能，使用n e t 技术，运用软件工程的设计思想，开发出一套基于校园 网的无纸化考试系统。该系统以校园网为平台、使用浏览器朋艮务器( b r o w s e r s e r v e r b s ) 模式、与因特网( i n t e m e t ) 技术充分相结合，方便在校学生上考试主页网就可以 在进行网上考试，对教师来说，可方便地进行试题库首页，对试题可进行修改和编 辑，系统管理员具有最高权限，对系统及系统信息进行监督和维护工作。 1 3 2 主要研究内容 课题的主要目标是设计并实现一个基于校园网的无纸化在线考试系统，为本学 3 河北科技大学硕士学位论文 院教学考试提供服务。同时也为解决远程教育中的远程考试问题提供参考。通过w e b 数据库访问技术的实践应用，为开发w e b 方式的企业管理信息系统做技术准备。从 方便性、安全性、通用性、可扩展性及高效率等多方面入手，克服传统网上考试系 统的局限性，提高软件系统工程的质量。 在分析了国内外网络考试系统技术发展的基础上主要研究以下内容： 1 ) 研究应用粒子群优化算法自动组卷，该算法种新兴的组合优化算法，组卷 效率高，收敛快，可以充分满足自动组卷算法随机性、科学性、合理性的要求。 2 ) 研究并总结了利用o f f i c e 的宏代码序列比较的方法对操作题的操作过程和 答题结果两方面进行评测，使评测结果更加准确，保证了考试的公平公正性。 3 ) 提供可靠的安全机制，分别针对考试过程、题库和成绩的安全性通过用户认 定和授权功能，数据传输过程的加密及数据库事务级操作等多种措施在一定程度上 保证了考试系统的安全。 1 3 3 论文的组织结构 本文主体分为五大部分： 第l 章绪论分析了国内外考试系统发展及应用现状，提出了本课题的来源 及其优势。 第2 章相关技术原理综述对开发基于校园网的网上考试系统所使用的p s o 算法自动组卷的原理、数据加密技术及实现o f f i c e 操作测试的技术要点进行了综合 介绍和评述。 第3 章考试系统的总体设计介绍基于校园网的网上考试系统的设计原则、 设计思想及各基本模块的设计方法。并着重介绍了p s o 自动组卷算法的基本原理及 应用方法。 第4 章考试系统的实现依据第3 章提出的设计原则和设计方法成功地实现 了一套基于校园网的网上考试系统，并通过软件测试和应用，证实了设计思想的正 确性和可行性。 最后是结论部分，对本考试系统的创造性成果及理论特点进行了总结，提出了 其社会经济价值，并对其不足之处提出了设想。 4 第2 章相关技术原理综述 第2 章相关技术原理综述 开发网络考试系统的关键性技术是自动组卷技术及自动评测技术以及动态网页 制作技术、w e b 数据库访问技术。在基于i i s ( i n t e r n e ti n f o r m a t i o ns e r v i c e s ，互联网 信息服务) 模式的多层分布式在线考试系统的开发中，目前流行的a s e n e t 技术可以 充分满足我们的动态网页制作、w e b 数据库访问两方面的需要。 2 1自动组卷算法 2 1 1组卷算法研究现状 一般来讲，开发无纸化考试系统，自动组卷算法必不可少，是该考试系统的核 心内容，关于自动组卷算法的研究当前主要有如下4 种： 随机选取法：这种方法的原理结构简单由计算机随机地抽取一道试题放入试题 库，不断反复此过程，直到组卷完毕。但该方法组卷成功率不高，花费时间不短， 其优点仅仅是对于单道题的抽取运行速度较快。当题库中各状态类型平均出题量较 低时，组卷往往以失败而告终。 回溯法：也叫试探法，是一种系统地搜索问题的解的方法。其基本思想是：从 一条路往前走，能进则进，不能进则退回来，换一条路再试，通过不断的试探直到 试卷生成完毕或退回出发点为止，这种有条件的深度优先算法，对于状态类型和出 题量都较少的题库系统而言，组卷成功率较好，但是在实际应用时我们会发现这种 算法对内存的占用量很大，程序结构也是比较复杂，而且选取的试题随机性不高， 组卷的时间也较长，后两点是用户无法接受的，因此它也不是一种很好的用来自动 组卷的算法。 遗传算法( g e n e t i ca l g o r i t h m ) 近几年才发展起来的，是一种崭新的全局优化算 法，通过自然选择、遗传和变异等作用机制，实现各个个体的适应性的提高。由美 国j h o u a n d 教授提出。其主要特点是直接对结构对象进行操作，不存在求导和函数 连续性的限定。从某种程度来讲是一种数学方式仿真，是一种对生物进化过程进行 的仿真。我们知道，动物( 包括人类) 的进化都是朝着好的方向发展，虽然有的也 往坏的方向发展，但是总体都是往好的方向发展来适应大自然。我们觉得并不奇怪， 因为人类的基因组合是随机的，没有上帝约束。这种随机过程的结果却是一致的! 我们的遗传算法就是从这里得到启发。比如我要求黟，嘞的最大值，两个变量，我 不用传统的数学方法，就用幼儿园的方法，把所有可能取值带进去算，然后找出最 大的就行了。但是，如果取的值是连续的话，我们可以使其离散化，就像把模拟信 号变成数字信号一样! 还有一个重要的问题是如果取值太多咋办? 我们可以采用下 5 河北科技大学硕士学位论文 列方法来解决：首先，我不用取所有可能取值，我只取几十个或者几百个( 自己定) ， 然后进行处理，怎样处理呢? 让我们回到刚开始的人类进化问题，虽然没有上帝的 帮忙，但是我们知道，自然界遵循优胜劣汰的发贼，遵循交叉变异的法则，虽然不 能数字化，但是这是个趋势! 我们就是把这种法则数学化! 所取的几十个值我要剩 下哪些? 要抛弃哪些? 要处理哪些? 这都要我们自己选择，肯定是选择最合适的取 值留下，经过一系列的处理，就生成了新的群体，然后再处理，自己约定处理到第 几次就可以了，取出现过的最大值，不用担心取到的是不是最大值，因为数学上已 经有了证明，这种方法是收敛的，概率是l ，所以尽管放心的做。遗传算法的最大用 处就是解决数学理论不能解决的问题! 比如路径规划，调度问题等。 粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，简称p s o ) 又翻译为微粒群优化算 法。是通过模拟鸟群觅食行为而发展起来的，是一种基于群体协作的随机搜索算法。 通常认为它是群集智能( s w a r mi n t e l l i g e n c e ，s i ) 的一种。可纳入多主体优化系统 ( m u l t i a g e n to p t i m i z a t i o ns y s t e m 。m a o s ) 。最早是由k e n n e d y 和e b e r h a r t 两位博士于 1 9 9 5 年提出的，受到人工生命的研究结果启发，p s o 的基本概念源于对鸟群捕食行 为的研究【1 2 】。可设想下列场景：一群麻雀悠闲地在某个地方四处搜寻食物，而此区 域里只有一块面包。所有的麻雀都不知道哪里有面包，但是它们知道离面包还有多 远。那么找到面包的最可行、最行之有效的方法就是寻找离面包最近的麻雀的周围 地方。p s o 算法正式从这种模型中得到启示并用于解决优化问题【l3 1 。p s o 中，把搜 索空间中的每一只麻雀称为“粒子“ ( 最优潜在解) 。所有的“麻雀”都有一个被优 化的函数决定的适应值( f i t n e s sv a l u e ) ，每个“麻雀“ 都靠速度来决定他们飞翔的距 离和方向【1 4 】。然后麻雀们就追随当前的最优解在空间中进行搜索【1 5 】。p s o 首先初始 化随机解，而后通过迭代找到最优化解。在每迭代一次麻雀可通过两个极值来更新 自己：个体极值( p b e s t ) 和全局极值( g b e s t ) 。把“麻雀本身所找到的最优解称为 个体极值( p b e s t ) 。把整个种群目前找到的最优解称之为全局极值( g b e s t ) 。另外还 可采取其中一部分作为麻雀们的邻居而不是整个种群，则在所有邻居中的最优解就 是局部极值( 1 b e s t ) 【1 6 1 。粒子j 的信息可以用d 维向量表示，我们把粒子的位置表 示为a q = ( x i x i 2 , ，砌t ，速度表示为圯= m ，o 训1 。p s o 算法采用下列公式来更 新粒子的速度和位置： 争1 = k + c l r a n d ? ( p b e s t 刍一z 耐k ) + c 2 r a n d ；( g b e s t k 一k ) ( 2 一1 ) x 岔1 = k + v 2 1 ( 2 2 ) 其中：以是粒子j 在第k 次迭代中第d 维的速度，瑶是粒子j 在第七次迭代 中第d 维的位置，卢l ，2 ，戢d = l ，2 ，d ；p b e s t 是个体极值，g b e s t 是全 局极值；学习因子c l 和c 2 是非负常数，通常c 1 = c 2 = 2 ；r l 和r 2 是介于 o ，1 之 间的随机数。以 v m a x ，v r n a x ，v m a x 是常数，由用户设定。在每一维粒子的 6 第2 章相关技术原理综述 速度都会被限制在一个最大速度v m a x ，如果某一维更新后的速度超过用户设定的 v m a x ，那么这一维的速度就被限定为v m a x 。 基本p s 0 算法操作简单，容易实现，且没有许多参数需要调整。p s o 算法在系 统识别与设计、多目标优化、信号处理、机器人应用等领域内广泛应用。但这种基 本p s 0 算法有个致命的缺点：结果准确率不高，局部极小点容易产生，后由专家认 真研究，对其又作了各种改进，提出了自适应p s o 算法【1 7 】、杂交p s o 算法【1 引、协 同p s o 算法【1 9 】、以及离散版二进制版的p s o 算法1 2 0 等。本文利用p s o 算法智能搜 索收敛快，效率高的特点独创性地应用于组卷问题上，取得了良好的效果。 从操作步骤看，粒子群优化算法要好于遗传算法，即由麻雀自己本身的速度来 决定搜索速度，同时还具有记忆功能。没有遗传操算法中交叉和变异地特点。另粒 子还有一个重要的特点，就是有记忆功能。p s o 的信息共享机制是单向的信息流动， 只有g b e s t ( o rm e s t ) 给出信息给其他的粒子。整个搜索更新过程是跟随当前最优解 的过程。与遗传算法比较，在大多数的情况下，所有的粒子可能更快的收敛于最优解。 粒子群优化算法是对优化问题的求解，收敛速度较快。在较少的进化代数内，其解 群就向最优解的方向收敛，这说明粒子群优化算法的优化效率较高。 2 1 2 组卷算法分析 组卷系统在本考试系统中是最重要的一部分，其目的就是组出一份符合用户要 求的、试题水平适中的试卷。用户对命题要求有如下几个方面： ( 1 ) 试卷的总分值； ( 2 ) 试卷的期望值； ( 3 ) 试卷所涉及的考试内容范围： ( 4 ) 各章节考试内容在试卷中所占的百分比： ( 5 ) 题型类型及各题型在试卷中所占的百分比： 在组卷时，用户可根据某些约束条件，才能从题库中进行选题，要使试卷最终达 到各项要求间平衡，是构成了整卷的全局约束条件。我们在这里定义四个向量： 乒 鼠s 2 , ，鲥为属性集，与试题的类型、章节、难度、认知类型、估计用时 等变量相对应。 仁 厶厶o oo p 砧为取值集，+ 对应s ( 属性集) 中各个变量的取值范围。 庐 “易o o o p 厶) 约束集，与上中的不同取值之间的约束关系相对应。假如试题 平均难度为o 6 ，要求总分为1 0 0 且第三章的题要占总分的9 等组卷指标。 卢 j 厶厶铂为试题集，自动组卷可描述成一个约束满足的问题。从试题库中 随机选出一组试题厶试题，中的属性变量s 要同时满足和r 的要求或约束条件。 通过翻阅资料可看出：尽管随机选取法、试探法、遗传算法等在组卷中都取得了 7 河北科技大学硕士学位论文 不错的效果，但都有或多或少的不足，如内存占用较大，收敛性速度较慢等。所以 本文提出用粒子群优化算法组卷，该算法与其它算法相比，不仅克服了以上各种算 法的不足，提高了收敛速度，还很好地满足了用户的要求。 一 一一 2 1 3自动组卷数学模型 我们把自动组卷问题分为硬约束和软约束两种，利用数学模型进行详细分析： ( 1 ) 硬约束数学模型为了描述清楚此数学模型，我们用矩阵来表示，一道试题 是由n 项指标来决定的，在1 1 维向量( 题型要求a ，估时如章节如难度钆题型类 别a 岛题分岛，) 中，a ，相当于第j 项指标，决定了一个用木力的矩阵，即决定一套 试题【2 。m 在送堡措试卷所含的题目数值。 在s 矩阵中，一行表示一个题目；而各个属性的取值是由列来决定的。目标矩 阵应满足以下约束条件： a ，声a ，矗1 0 0 = s d ，肋指用户指定的试卷难易度。 试题难度的确定：得分率( d ) ：1 - ( 平均分该题满分) 。 c 1 ，a 矿缈( 0 e 为第e 题型题分) ，其中 ，1 当口庐p 时 除 l o 当口础时 哆e = 、i l l l l 口 n 巩 锄 砧 膳 嚣 以 缸 劭 缸 ” 拼 引 鼽 如 磊 第2 章相关技术原理综述 ，1当a i 2 = k 时 舒 l 0 当a o - - ：k 时 用户可以给定教学要求的取值范围和所占分数，包括知识应用、综合、理解等具 体种类，k 即为教学要求约束。 e a i 5 = r ( r 为整套题的估计时间) a ，6 = g ( g 为试卷的总分) 除必须满足以上6 个单项模型外，还可定制其他一些指标来满足不同的需求，可 通过与难度系数的关系得到。 ( 2 ) 软约束数学模型我们把上面的一公式称之为目标函数，在实际组卷 过程中以上所有目标一般不可能都满足，也就是说要求很难能全部满足。我们把完 全满足要求的称为“硬约束”，不完全满足要求的称为“软约束”。因为组卷问题是 一个多重约束目标求解的问题，组卷要求是通过试卷模式中各个参数的取值来体现， 的，为了使目标函数与目标值的偏差极小化，我们要建立一个优先级，目的是对所 有目标进行排序，来最大限度地实现更多的目标。而优先级的确定是由其在组卷过 程中的重要性建立的，用户根据自己对知识的掌握情况可对优先级进行合理安排， ! 一 如按优先级别从高到低进行排列：考查知识范围、试题类型、试题数量、试题难度、 试题题分等。 为了更好说明问题，我们引入正、负偏差变量，负偏差变量表示未达到目标值， 。 正偏差变量表示超过目标值，因此组卷过程实质是求软约束目标值的过程。其基于 “软约束“ 的多目标优化模型建立如下： m i nz 印ll ( 如j 一+ 如，+ ) l 切2l ( d a 一+ 出+ ) l ( 2 3 ) s t 以+ a a t + a a ? = a 。 j l l 七 以x 独+ 彩i + 彩? = b j = l 圭羔毪 i _ 1 2 。p j = 1 2 q k - - l , 2 1 7 只为优先因子，表示各个目标的相对重要性，且对所有的f 有尸，优先于p 什，i = 1 ， 2 ，3 。琢表示在试卷中第i 种难度、第种试题数量和第七种题型的范围；d a t “ 、d a t + 分别表示试卷中所有具有第f 种难度的试题分数之和相对于难度要求a ，分数