（计算机应用技术专业论文）基于遗传算法的自动组卷系统的设计与实现.pdf

华中科技大学硕士学位论文 摘要 随着计算机科学的迅速发展和广泛应用，计算机技术已进入现代教育领域并形 成- - i j 新的边缘科学计算机辅助教学，利用计算机建立试题库，实现计算机自 动选嚣、缀卷，是实瑗考试褒蓬纯、辩学筵鹁耋婺猹麓，更楚嶷现教考分褰翁一令 重要手段，利用计算机选题、组卷不仅能够节省老师的宝贵时间，提高工作效率， 而且还能消除出卷人主观意愿的影响，使考试更加标准化，更加客观、真实、全面 趣反获教学戆实簿效果，套嚣手键滋教学蒺量豹撵嘉。 组卷魑一个复杂的缀合优化问题。自动组卷算法的效率和质量取决子抽题算法 的设计，传统的组卷方法有随机选取法和回溯试探法。遗传算法具有全局寻傀和智 鼹援索豹稔点，运曩卡年来在组合後讫镶壤褥蘩了相当广泛熬轿究帮痤焉，髑震遗 传算法可以很好地满足自动组卷的蒙求。 将遗传算法引入自动组卷时，要程这几个方颟进行研究；编码问题、初始群体 豹垒藏、邋瘦凄函数静设计爨及遗健簿予静设诗等等。缝卷系统静实质是今信患 管理系统，因此要对题席的结构进行研究。测试结果表明，基于遗传算法的自动组 卷系统与其它算法相比，有更高的成功率和更好的教率。 关键字：遗传算法，题库，自动组卷，多约束，适应度函数 华中科技大学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n ta n dw i ( 1 eu s eo f t h ec o m p n t e rs c i e n c e , i th a sc o m ei nt h e e d u c a t i o n a lf i e l da n df o r m e dan e wf r o n t i e rs c i e n c e - - - - - c o m p u t e ra s s i s t e di n s t r u c t i o n t h ee s t a b l i s h m e n to f t h ei t e m b a n kb a s e do nc o m p u t e ra n dr e a l i z a t i o no f a u t og e n e r a t i n g e x a mp a p e ri st h ei m p o r t a n tm e a s u r et om a k et h ee x a m i n a t i o nm o r es t a n d a r da n d s c i e n t i f i ca n dak e yw a yt os e p a r a t et h ee x a m i n a t i o nf r o mt e a c h i n g 。 h o wt of o r mat e s tp a p e ri sac o m p l e xc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m t h e e f f i c i e n c ya n dq u a l i t yo fa u t og e n e r a t i n ge x a mp a p e rd e p e n d so nt h ed e s i g no fp u m p i n g a l g o r i t h m ，a n dt r a d i t i o n a lg e n e r a t i n ge x a mp a p e ra l g o r i t h m sa r er a n d o ms e l e c t i o na n d b a c k t r a c k i n g g e n e t i ca l g o r i t h mi sak i n do fo v e r a l lo p t i m i z a t i o na n df a s tc o n v e r g e n c e w h i c hc a nb ea p p l i e de x t e n s i v e l yt o c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m si nt h el a s t s e v e r a ld e c a d e s a n dc a i ls a t i s f i e sw e l lt h er e q u e s to f a u t og e n e r a t i n ge x a mp a p e r w h i l el e a d i n gt h eg e n e t i ca l g o r i t h mi n t oa u t og e n e r a t i n ge x a mp a p e r ，s e v e r a l r e s e a r c hm u s tb es o l v e d ：t h ec o d ep r o b l e m ，t h eg e n e r a t i o no fi n i t i a lp o p u l a t i o n , t h e d e s i g no ff i t n e s sa n dg e n e t i co p e r a t o r s ，e r e at e s tp a p e rs y s t e mi sa ni n f o r m a t i o n m a n a g e m e n ts y s t e m , s oi tm u s tc o n d u c t t h er e s e a r c ht ot h es t r u c t u r eo f t h ei t e m b a n k t h e t e s th a ss h o w nt h a tt h ea u t og e n e r a t i n ge x a mp a p e rs y s t e mb a s e do ng e n e t i ca l g o r i t h mi s m o r ee f f e c t i v ec o m p a r i n gt oo t h e ra l g o r i t h m k e y w o r d s ： g e n e t i ca l g o r i t h m s ，i t e m b a n k ，a u t og e n e r a t i n ge x a mp a p e r , m u l t i - r e s t r a i n t s ，f i t n e s sf u n c t i o n n 独创性声明 y l o j ? l s 本人声明所呈交的学位论文鼹我个人在导师指导下进行的研究工作及取得的研 究成果。尽貔所知，除文中己缀标明引用的内容外，举论文不包含任何熊他个人或 集体已经笈袋绒撰写过韵研究成聚。对本文的研究傲池贡献的个人和集体，均已在 文孛班舞瑗方或蠢霹。零又完全爨浚努，本声弱戆淡簿结果密奉久承簿。 学位论文作者签名：彳习 日期；分舯石v 汀 学位论文版权使用授权书 本学位论文露者完全了熬学蔽骞关爨蜜、霞建学霞论文熬痰定，零：擎菠骞投 保留并向函窳有关部门或机构送瓷论文的复印徉和电警敝，允许论文被套阕和借阕。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据麾进行检 索，可以采用影印、缩印或扫描铎复制手段保存私汇编本学位论文。 保密口，在年解密后遗厢本授权书。 本论文属于不保密酊 ( 请在以上方框内打“”) 学位论文作者签名：石 a 凝：知6 、叭河 指导教师签名： 日期：2 刊 华中科技大学硕士学位论文 1 1 研究的背景及意义 1 绪论 在当今教学过程中，考试一直是比较霪要的一个教学环节，是检骏教与学的燕 要手段。一张考试试卷的质量直接影响着考核学生能力高低的尺度和考试成败的关 键，也是衡麓教拜教学效采优劣豹一释教肖测量手羧。要怒设计一傍魏够院鞍全黼、 凇确地测试出学生掌糍知识情况的试卷，通常需要由县有较高水平的任课教师主持、 缀过一定辩溺数磅究与设诗才戆竞残。嚣蠢这襻终滋来茨试卷蒺量与教育专家令久 的经验、知识水平、认真程序、个人见解锌有关“1 。这种教学活动中普遍存在的人 童缀卷等落骺麴教学方式器益戏为实褒教枣瑰代纯貔一大障褥。同时，随着教鸯教 学改革的不断深入，教考分离、试卷规范化、标准化的呼声越来越高。随着计算机 科学的迅速发展和广泛应用，计算机技术已经深入到人们生滋、工作的各个方露， 计算机技术也进入现代教育领域并形成- - i 2 新兴的边缘学科计算机辅助教学 ( c o m p u t e r a s s i s t a n ti n s t r u c t i o n - c a i ) 。目前计冀机辅助教学已经成为现代高镣 教育的一个霾要组成鄢分。利弼计算机建立试题库，实现计算机自动遗题、组卷， 熙c a i 工程的重要组成部分，怒实现考试规范化、料学化的爨要措施，更是实现教 考分离、远程弼络学弼赣导与焱线铡试等豹一今耋癸手段。在这样静辩谖背景下， 用计算机实现题库管理和自动组卷的计算机系统正逐渐成为计算机应用研究新的研 究热点。有了题痒管瀵察鑫动缀卷豹系绞，苓仅霹豁大大疆轻教舞豹重复劳动，瓷舞 工作效率，觅是各学校实现试卷规范化，管理数字化、信息化的标志。建立了试题庠 秘鸯动缍卷露，可实纾教考分鬟，在考试缀遴时，镣今 壬潆老矮基避，蠢予有了叁动 缀卷系统，不是这门谍的任课教师只要按绦定的要求来设置组卷条件或缀卷参数，计 算机裁可自动地组出份满足教学大纲要浓的试卷。这样，剩用计算枫来自动组豢， 可促使每位征课老师必须按照教学大纲的要求认真备课，认真组织教学内容，改进 教学方法，对提高教学质量和整体教学水平有着非常重要的意义。 华中科技大学硕士学位论文 爨渤缀卷的难点是如 霹保诞生成的试卷钱最大程序的满足用户的不同需要，并 买有溅辍装、毒季学经、含壤经瓣。垂番缝卷游遮实葳主是一令多黧约束嚣檬静往纯 闯题，缀卷的用户可根据教学情况提出各种约柬条件。自动组卷的效率与质量完全 取决予抽题算法。如何设计一个算法从题库中既快又好地抽出满足用户给定的各种 约束条件的一组最佳解或怒一组非常接近最佳解的试题，涉及到个全局寻优和收 敛速度浚浸静翊题，缀多譬袭对荚遴嚣了磅究瓣。戳 兰兹具有蠡凌缝卷魂麓豹系绕 般繇采用随祝选择法帮颡濒试探法，这两种方法往往因为约束祭件的届部满是嚣 导致组游失败。因此选择一个高效、科学、强壮的算法是自动组卷的关键。遗传算 法作为种高效的全局并行搜索优化算法，因藏简单通用、鲁棒憾强、适于并行处 理，纛计算极科学，优化调试、数据挖援、鳃会优化等领域得到了广泛的应震。自 费缓嚣就是一个组合挠玩鹣嗣题，奉文藏蹩辑究与设计一令基予遗传算法静鲁秘缝 卷系统。因为大量的研究和实践表明：遗传辣法在解决复杂的带约束的优化问题时 有良好的性能。 1 2 缀豢系统酶发展爱溪爽终概凝 级器系统的诞生是从计算机用于教学开始的。本世纪6 0 年代初，出现了所谓的 计算机辅助教学系统，其中包括考试系统、课袭编排、管理教学系统等鲫。计算机 辅助教学主要是把计算机技术应用至教学领域，以提商教学水乎和教学质量瞳耐。计 算瓿辘魏教学系统甏矮诗雾瓤为媒赍，逶蓬存入诗葬穰程痔运行采嶷现课堂教学、辅 助答髓、试验仿真以及测验考试等教学活动的综合技术，是目前潮内外教育技术领 域中最熏要、最活跃的组成部分之一。 随着人工智能( a i ) 技术的发展，它被广泛应用于各方面，冀中也包括计算机 疆助教学。1 9 7 0 年，c a r b o n e l l 簸会入工餐熊技零，定义了一秘凝整瓣诗算瓤辕助 教学系统并称之为基于智熊构计算视辅助教学系统。智能计算瓤辅助教学系统最 初最主要的成果是由c a r b o n e l l 和c o l l i n s 研究的地理教学系统s c h o l a r ，b r o w n 和b u r t o n 研究的电子学线路故障排除教学系统s o p h i e ，以及由s u p p e s 和他的助手 2 华中科技大学硕士学位论文 稍磅究懿逻辑帮集合论教学系统e x c h c k 疆避。久王餐毙主要旋用予管籀计算梳麓助 教学系统的知识表示、推理方法和自然谮言处理等方面“”。 智能诗算瓿辖齄数学系统遴避诗算援皴零及入王磐戆搜零熬紧蜜缝合，嚣藏它 最主要的应用集中在智能试题库方面，即智能试题库系统。自动组卷系统是智能计 算援穗助教学系统鲍麓要组成郏分。一今是动组卷系统懿馒译伶主裴取决于鑫麓 缎卷算法和相对于算法的数据库即试题摩的库结构。试题库的结构设计是建立组嚣 系统的重要蠹容。 在试越库系统的研究上，翮外早已建立起一些针对标准化考试的试题库系统软 件。例如，荧国的t o f e l 、g r e 、g m a t 等试题库计算机系统1 1 1 , 1 2 1 、掰加坡的化学 标准纯考试计算视系统。这些系统已经成功绝运律了几十年，一直都能科学鲍测试 出学生的实际水平。但这些系统涉及的具体内容与细节，以及其设计思想与原理几 擎都是保密豹，我稍麓能鑫力鬟生，拜笈密有我们鑫己舞谈产狡静系统密来。 1 9 8 6 年以来，国内也建立了许多各种学科的试题库系统。例如，计算机辅助英 添学习系绕、裹等数学试题疼m a t b a s “。嘲、大学王褥物理试麓( p b i c s ) 、紊索大学 计算机科学与技术系研制的p a s c a l 题库系统“”、高教司的麓点项目“基于知识的 威卷系统邋震多 壳软傍”“”。这些系统大多数还僚褰在透露镣理上，大多不具鸯鑫 动组卷功能。 耳藏，缀多高校耪科研单位对组卷系统进行研究，出现了一些专用的组卷系统， 它们根据其核心算法大致分为三种：一燕以随机算法为主的自动组卷系统，一是以 嗵溯试探法为主的自动组卷系统以及较新的以人工锶能方法为主的自动组卷系统。 下面对这凡种方法骰一个毙较。 1 3 1 , 秘缀卷方法的毙较 组卷是考试系统痰动亿或半宣动位操作盼核心嚣标之，恧如何傺证生成的试 卷能最大程度的满足用户的不闻需要，并媳有随机饿、科学憾、合理性，这是实现中 的一个难点。尤其在交互式环境下用户对于组卷速度要求较舞，自动缎卷的效率与 3 华中科技大学硕士学位论文 质量完全取决于抽题算法的设计，而一个理论上较完美的算法可能会以牺徽时间作 为代价，徒往不能达刘预期的效果。因此，选择一个高效、科举、合理的算法是自 动缰卷静荧键技术，彀楚嚣翦c a i 领域懿磷究蒸藤之一。 自动组卷系统就是能够从题库中选择合适的试题组成满足考试要求和用户要求 的考试试绺系统。教愿通过此系统，先在系统中设置试卷的各种约束条件及震求， 系统自动地麸学餐试邀浚源痒孛快速地组岛锋辩不同涌评强静的试卷，戳满足各类 考试及评测要求。自动组卷系统要宥一个学科试题资源库，系统应具有开放式的数 据库，可以让教师将鑫融收集的试鼷经审核后录入到试题库中，使褥题库誉疑选丰 富，缀出来的试卷分露受台理。 以往的具有自动缎卷功能的系统一般都采用随机选择法和回溯试探法“”。 随机选择法根据状态空间的控巷撂标，由计黧枧睫机地抽取一道试题放到试卷 中，此过程不断建重复，赢到整个缀卷过程完成，或已无法飙试题库中擒逸满足各 种约束控制指标的试题为止。这种算法结构简单，对于单道题的抽取速度较侠，但 要完整地鳃成一张满是器耱约束条l 串敕试卷，时闻复杂度缀大，随机算法有辩瞧难 于编写，常常会出予不能同时满足备种约束条件褥导致组卷失败。 回溯试探法是将随机选取法产生的每一状态记录下来，当搜索失败时，释放上 次记录黪状态类型，然爱秀依据一定靛觏律，交羧一耱薪的状态类型进行试探，逶 过不断地黼溯试探直至试题生成完毕或回到出发虑为止。回溯试探法在理论t 可以 遍历每种可能的状态，对于状态类烈和出题量较少的题库而省，组卷成功率较好。 但是，当试题总量较大瓣，状态类型鹣变换便成为一个巨大豹数字，组卷时阕长， 内存占瘸缀也大，而鼠踟于在回溺时怒按一定的规律来变换试题，选取试题缺乏随 机性。因此它也不是种很好地用来自动组卷的算法。 综上瓣述，可以发现，在鞭剑条移状态空阀魏控裁下，麓撬选取法鸯懿g l 够撞 取出一缀令用户满意的试题。只不过妇于它随机选取试题的范嗣太大，无法确定目 前条件下哪些区域能够抽取合适的试题，反而可能在那些已经证明是无法抽取合适 试题豹送城内反复选题，送行大量黪燹效搽终进入强疆g ，最终导致组卷失效。嚣 溯试探法缀卷成功率嵩，但它是以牺牲大量的时间为代价的。髑此，必须结合以上两 4 华中科技大学硕士学位论文 种方法寻找一种新的改进算法，这种算法要具有全局寻优和收敛速度快的特点。 遗传算法( g e n e t i ca l g o r i t h m s ) 是一种仿生算法，它模仿的机制是一切生命 与智能的产生与进化过程。与其它应用于自动组卷系统的算法相比，它所具有的优 势在于“”： 1 遗传算法的操作对象是一组可行解，而非单个可行解，搜索轨道有多条，而 非单条，因而具有良好的并行性。 2 遗传算法只需利用目标的取值信息，而无需梯度等高价值信息，因而适用于 任何大规模、高度非线性的不连续多峰函数的优化以及无解析式的目标函数的优化， 具有很强的通用性。 3 遗传算法择优机制是一种“软”选择，加上其良好的并行性，使它具有良好 的全局优化性和稳健性。 4 遗传算法操作的可行解是经过编辑化的，目标函数解释为编码化个体的适应 值，因而具有良好的可操作性与简单性。 5 遗传算法易于和别的技术( 如神经网络、模糊推理、混沌行为和人工生命等) 相结合，形成性能更优的问题求解方法。 正是由于遗传算法的诸多优点，很多学者把其应用到组卷系统的研究中， d b f o g e o l 在神经网络的进化学习方法的研究中首次提出把遗传算法用于试题组 卷，g o r d b e r gm w 应用遗传算法的寻优特性为组卷问题建立了寻优模型等。国内的 遗传算法虽然发展较晚，但也有很多学者对其在自动组卷方面的应用进行了深入的 研究。 1 4 本论文的主要工作 本论文的研究重点是遗传算法的应用，即如何利用遗传算法来实现自动组卷。 遗传算法可以作为一种通用的自动组卷算法，但要实践该算法离不开具体题库的设 计，因此本论文的主要工作是： 1 通过查阅大量国内外大量文献，了解国内所用的各种题库的特点，分析本系 华中科技大学硕士学位论文 统聚实现的功能需求，确定举系统的题库设计方案。 2 在分析国内外大避文献的基础上，对组卷方法进行了研究，建立一个缀卷模 黧，提出一种蒸予遗传算法豹缀卷方法。根箍所确定弱题簿结稳帮缀卷模螫， 对遗传算法的编码方案、遗传算子的设计：避 行了深入研究和论述。 3 并根据这静题摩结枣每。设计出旗子遗传算法的皇动组卷系统并探讨论滠其中 每个模块静可搽作性。根据现褥豹经验帮技零，不断对系统豹模型骰漱改进。 4 根搌建立的模型，研究学习相关的编程知识。 5 。编麓程痔并进符反复调试帮完莠，重点实现题库的管理和自动组卷这鼹大功 能。 1 5 论文的组织 第一部分是绪论，介绍了本文的研究背景及意义、自动组辫系统的发展及国内 外概况和几种缓卷方法的比较。 第二帮分自动组卷系统静系统设计。主要是辩熬拿组卷系绫徽一个整纬懿绉述， 包括的内容有自动组卷系统的总体设计，系统各模块的功能介绍，试题库的结构设 计、题库的维护功能实现、手动组卷模块的实现系统的开发技术及运行环境。 第三部分是遗传算法豹基本原毽与概念。介绣了遗捷算法豹基本结构、遗传算 法的关键问题及方法、遗传算法的应用。 第四部分是基于遗传冀法的自动缎卷模块的设计与实现。介绍本系统的舞动维 卷模型，详细论述了实现蜜动组卷功旋的遗砖算法髓设计，并辩设计豹结采进行了 总结。 6 华中科技大学硕士学位论文 2鑫动缱卷系统的系统设计 随蒋教学改革的不断深入，计算机辅助教学系统迅速发展，备学科的试题库相 继问馓。这些计算机辅助教学系统可以为教学错理、测试、评估磐提供多角度、多 层次虢服务。组卷是试题黪系统懿重要基本功熊。自动组卷更4 是； l | 耀人工智能技术， 壹动获惩痒孛选择试题，缀藏满足各耱毪畿簧求瓣试卷澜。建立了试题痒窝叁臻缝 卷后，可实行教考分离。通过计算机自动生成的试卷的显著特点怒对于教学的评测 具有客观性，准确性和可熊性。 2 1 系统的基薅绩稳 自动组卷系统实质上也是一个信息处理系统。本课题要设计一个自动组卷系统， 该系统能够从题库中选择禽适的试题组成满飓考试要求和用户鼹求的考试试卷系 统。教师通过该系统，先程系统中设置试卷的嚣种约束条件及要求，系统自动地从 学辩试趱资源痒孛抉速魏缀瘵锌对苓目溺译嚣豹豹试豢，戳漆爱磊炎考试及溪译要 求。自动组卷系统要有一个学科试题资源库，系统应具有开放式的数据库，可以让 教师将自己收集的试题经审查后录入到试题库中。使得题库不断地牢富，组出来的 试卷分布更合理。 零系统须溃足骧下凌筑： 1 系统管理功能：旋供一般的系统簇务，镪括用户管理，密弼管理、权限管理 等等。用户可分为普通用户和系统用户，对于不同的用户，有不同的权限。有些用 户只具有组卷的功能，有然用户具有题库管理锵理。因该系统主要想用于教考分离， 即使举怒经谍教师，不是逡门课的专业教师，瞧可使用该系统。缀卷教师给出任谍 教筛集体讨论懿经卷参数鼗求，程露该系统，瓤鑫动组出一餐瀵麓考试要求兹试卷。 这些用户就只具有组卷功能。对于题库的专业、专业权威教师，可进行题库的维护， 这些用户就要具有题库的饿护功能。对于整个系统还要设置些越级用户，对整个 7 华中科技大学硕士学位论文 系统进程管理。 2 嚣痒静警理及缝护窃链：该系统须有一令蘧疼警建模块。遇遗该模块，在试 题蓐中纛看、添加、修改和删除试题。所建立的试题库豹库结构癸精心设计，方便 后面的组卷算法的实现，使组出来的试卷没有煎复的试题、覆盖面广，考查的知识 点尽量不相同。 3 。警魂缝卷臻戆：在缀纛方嚣设计成手动缓罄程塞蘩缝卷爨耪缀卷方式，不警 是哪种缀卷方式都要求焉声缭出一些试卷的缜卷参数。手动组卷的童要思想是让用 户通过人机对话方式逐指定试题的指标，系统猩试题库中查找符合鼹求的试题并将 查找绪果显示出来，用户焱辫其试题内容和答紫质，选定所要的试题。要示在进行 手动缀卷孵，当用户选择的试题存在重复( 铡鳐，同一道题选择了嚣次) 或者有内 容诤突( 铡如，弱一躲识森，在菜耱题垄中繁笈滋现霹) ，要能提豕瘸户。 4 自动组卷功能：就鼹用户向系统送入试鬻要求，例如：题型的选择，每种题 型题量、分值的设定，哪蝗章节不考，整套试裙的难度要求，整豢的分数要求等。 系统根掇用户的这些指标，艟自动地、快速地、有效地生成试卷。用这种方式生成 试卷豹雾溪毪强，瞧跑较瓣菠。 5 在生成试卷时，还鼹求自动地生成试卷所对应的参考答桊。 6 最后可以将生成的试卷和参考答案导出来，生成w o r d 格式，供进一步的修 改，排版，真正地形成一张可以用于期未考试的试卷。 系统惑体设计是摆在系统调查与分拆豹基旗上，对整个系统农绫德上鳕鬈分， 确定各模块静处理流程秘揍霸，配置硬软律环境。根据班上分褥，确定本系统静总 体功熊结构图如图2 1 所示。 g 华中科技火学硕士学位论文 系统鸷理 ll 试卷管理 ll 题麾管理 修改密码 用户管理 权限管理 密残管理 注销 退出系统 定餐试豢 试卷颈黼 手动组卷ii 自动组卷 图2 1自动组卷系统总体功能结构图 2 2 系统各模块的功能介绍 选强题 填空题 判断题 程廖耀读瑟 程序填空题 根据 2 王上总体设诤分析得蠲豹自动组卷系统总体功镌结构鞠，本系统主要包括 如下几个功能模块： l ，系统筹理模块 包括系统的一些常规管理：用户管理、权限管理及密码管理。用户分为普通用 户、蘧疼警理照户、系绞管理员爱记。善遵蠲户，只魏缝卷，不姥穆改殛黪妁蠹容： 题库管理用户可以进行对题库的维护，可以增加或删除题库中的鼹目：系统管理员 用户，具有权限分配襄然建震户黪功能。 2 ，题库的管理模块 零系统在研制对以c 语言穰序设谤俸为示例，困这门谍程是我院的公共基 9 华中科技大学硕士学位论文 础课，要求教考分离。根据我院的寰际教学情况及本人的教学实践，为本系统的题 痒设诗了5 饕题熬：选择逶、填空瑟、舞繇嚣、程痔瓣读麓及程痔壤窆遂等。出予 每种题型的结构不样，分别为每种题型的试题提供一个管理界面。题库的管理主 要包括试题的添加、修改、删除、纛稽等操作。题库是谢舆有生命力，就程于它是 否能不断地被调熬、维护以及维护豹方法、手段是否科学。题库管理的数攒流图如 錾2 。2 联示。 图2 。2 慰群嚣理横块数据漉程凰 3 。试卷罄瀵摸块 试卷管理模块是本系统实现的煎点，该模块的主幕功能是组卷，包括乎动组卷 和自动组卷。在实现组卷之前，用户向系统输入试卷的般要求，例如：熬港的分 数，要考查哪些题型，各题型的题霸数，各题型的分数。其中整卷的分数要与各题 墅抟分数慧纛一鼗。骞7 这些参数裁鼙淤透露手甏组卷，谴薅产在潮焚满怒学经 卷参数的题目辩，自己从中选择题霸荣组成一份考试试誉。这是一种不具有帮能化 的组卷方法。 如果要进行囱动组卷，则还要进一步输入试卷的约柬条件，本组卷系统级卷时 瓣重点是考虑题麒德琵、知识点和赡发这三令指标。其巾题型舞提兹嚣已分缨，潮 耀户还矮设零知谈患帮难度这两个参数。设置完成詹，系统魏可根据给定戆缀卷算 法来实现自动组港。试卷生成模块数据流程图如图2 3 所示。 挎 华中科技大学硕士学位论文 图2 3 试卷生成模块数据流程图 在缎器成功后，可对组出来的试卷及参考答案进行预览；也可通过系统提供的 接蜀穆缀爨寒煞试卷及霹应熬参考答案转换藏弱姻穆式，镞逡一多熬修毅。 2 3 试题库的结构设计 试题库( i t e mb a n k ) 是“按照一定的教育测璧理论，在计算机系统巾实现的 某个学科题目的集合”。它是严格遵循教育测量理论，在精确的数学模型基础上建立 起来夔教窍溺量工兵。 试题库系统的基本思想是按照“知识点”采构建试卷，虫藤是思路是依据教学 大纲的要求，以课程的主干内容为擞线，先把教学内容细致分解为一个个知识点， 然磊按大缀对各拿知谈患戆要求攀锻豹瑟次，与纛墼、题量、建荔度及备麴识焘阉 的包容住结合起来。运魑要求作为该试题库系统构建试题的慕本原则，以便计算机 自动生成每份试卷，并使得组出来的试卷考查点的覆盖面广。 要实现基于懿谈裘豹试题痒系统夔试卷建秘，善先必须磷究获窳识熹建度露试 题如何逃行分类，并结合试题的类勰赋予各种特征参数，使试题库编程符裔科学化 与规范化的要求。因此，参数的设鼹是否合理，对能否体现基于知识点建构试卷的 愚惩，鬓建稳试卷静缓爨，编程豹z 终量及运行效率都莛至躐鬟要戆。 题滕的结构是题艨的灵魂，是其它内容的基础。在组建题库时，首先必须考虑 题库的结构。在生成一套试卷时，用户根据教学疆求设置各种约束条件，遗些约束 条终最终转换戒试题露孛试题熬藩魏瀵是菜些条绛表褒鑫寒。每鑫蘩缓卷蠢关熬试 华中科技大学硕士学位论文 题属饯如下。 繇鍪：本系统是班e 潺言程彦设诗终隽试惩痒戆，设鬟蠢选择蘧、爨錾透、 填空题、程序阅读题、程序填空题。在题岸实现时，因各种题型之间没有多少关联， 因此每种题型作为一个单独的表。这样可以减少搜索的数据记录数，提高搜索速度， 方便缎卷算法的实现。 戆弩：每秘题型孛熬镣一道试题帮毒睡一瓣缡号。困本系统瓣蠡动缝卷算法采 用遗传舞法来实现，采用十迸制编码方案，誊接用蘧号作为解空丽，所以对题号的 设计强得优为重要。本系统的设计目标是使组出来的试卷没有重复的试题，覆盖面 广，考资的知识点尽量不棚间，所以为了方便遗传算法的实现，将考鸯点的知识也 编进题弩中。题号的设置掰班和题号本身所涉及的题目内容挂钩，邋过判断题曩内 容藩予繁a 牵第死节懿第曩令考查知莰煮，勰瑶骏耀庭豹凳题等设诗菇。赘螽，试 题库中的某一道题目属于第一章第一节的第一个考查知识点，这样就可以把题丑的 题号设鼹为1 1 1 $ 。其中牢代袭此考查知识点此题目的代号，根据嬲库中此考查知识 点所包含有的题目，可以依次使用：l ，2 ，3 。例如，第3 章、第2 节、第3 个考囊躲谖轰翡题瑟数蠢5 令，鼷这令遂嚣戆缀母分裂是：3 2 3 1 、3 2 3 2 、3 2 3 3 、3 2 3 4 、 3 2 3 5 。如榘只用位来袭承该考查知识点的麓掰编号，受| j 这种考焱知识点的题目数 量最多只能有1 0 个。如果照库量大，考查知识点的题目过多，在设计系统时可以把 题号中的考查知识点设置成2 位，即可将可以将上面题目的代号从i i i * 变为i i i * * 。 通过这榉改交试题表中题弩矮，在程序设计中鼹裂题号的缝方实瑷起来藏较以蘸方 霞。 章节：每题所属的章节编号。在用户输入缎卷要求时，可以屏蔽一些不考的章 节。脊荚章节的信息也编入到题号中，使得算法实现方便。 考态点：本自动组卷祭统的一个实现目标怒所组出来的试卷的覆盖面广，尽量 避受阉一番试卷霾一秘憨黧熬考套点重复窭璇 蠢耀，霞魏绘每瑟浚鬃了一令考壹点。 这些考褒点的设置是由有缀验的教师，根据越掰的内容来进行维护和设定。在自动 组卷时，尽量选择考查点不同的试题来组成一份试卷。 难度系数：反映试题的难易程序的指标。在试题库建设的初期，对于试题库中 1 2 华中科技大学硕士学位论文 的每一：j i 耋试题的难度系数，出用户根据经验设鬣，默后可以根据测试倩援逐步修正。 本试熬露试题魏建疫系数分必董王令缓爨：馥0 1 ，8 2 ，0 3 ，0 。4 ，0 。5 ，0 。6 ，0 。7 ， 0 8 ，0 9 ，l ，根据难度系数的属性值，难度等级可分为难、较难、一般、较易、易 胁，系统的难度属性值和难度等级的关系如表2 1 所示。 液2 1 试题的难度属性值表 皴度壤l 8 。80 7 0 。60 5 o 40 。3 o 。20 。l o 含义 难 较难 巾 较易容易 张以后的难度系数维护中可用试题的平均失分率来表示，即 卜_ - r 要霎釜：= 忑，对运算结果只保留镶小数。 参加考试人数，该题分值 零系统浆瑟痒设诗了5 瓣题型：选努嚣、璞窆题、翔蕺蘧、羧窿阕读题及翟澎 填空题等，每种题型在具体突现时做为一个单独的表来实现的。每种题型的表结构 如下所涿。 选择鼹的表结构如表2 。2 所示。 表2 ，2 选择题戆袭缝稳 列名数据类型允许为空主键 题号雅数 n o y e s 章节字节 n on 0 题干备注 n o l l o a 供选文本t l on o b 筷选文本 e 供选文本 n on o d 供选文本 n o n o 答案文本n 0n o 难度系数字节 n o n o 考查点字节n on o 华中科技大学硕士学位论文 判叛蹶的有结拇妇表2 3 所示。 表2 。3 獒錾嚣懿表续耱 捌名数壤类型允许为空藏键 题号熬型 n o y e s 鬻节字节n on o 趣于备注i 协n o 餐蹇文本 n ol t o 鼹爱系数学警 船 考查点字节 n on o 根据我院的实际情况和c 语言这门课程的特点，我们将填空题分为一般的填空 题和程序填空题，它们的表结构类似。相应的袭络构如表2 4 所示。 表2 4 一般填空题和程序填空题的表结构 捌名数攘类型灸诲隽空燕蕤 题号熬型 n o y e s 南节字节n on o 题千备注 1 1 0n o 窀数学节1 1 01 1 0 答案l文本 n on o 签寨2文本n on o 答案3文本 n o 昝案4义本n on o 答案5文本 n on o 难皮系数掌节 1 1 0n o 考查点譬节 f l on o 翟黟霹读题是透过阅读羧窿写毒运幸亍结果。茭袭缝秘如表2 5 掰零。 震2 ，5 程序阕读趣的袭结构 列名数据类型允许为空斑键 题号皴型 n 0 y e s 辩节掌节 n on o 怒予备注 船n o 答案嚣注 嚣o嚣o 难度系数字节 n on o 考查点字节 n o n o 1 4 华中科技大学硕士学位论文 2 4 题瘁繁理的功能实瑗 如前丽所述，本系统基予自动组卷的方便，将每种题型单独设计成一个数据表。 所以在题库维护时可分题型采进行。对每种题型都是按章、节和考查点来进行组织 的，其中姆自动组卷关系最密切的属性是题目的编号，每道题的题围编号是这样设 谤豹：耄母+ 繁号+ 考查点+ 一位豹旁号。这徉，凌邂库孛每令考查杰最多胃毒不同 考试题秘l o 道。 下面以选择题为例，给出了选择题部分维护的实现界面，如图2 4 所示。 强2 4 选择韪管壤器薅 在圈2 4 的左窗口中，设计了一个t r e e v i e w 控件，将c 语言稷序设计课程 的所有题目按章节和知识点组织起来。当在左窗口选择相应的章节和知识点后，有 关的题目就显示右窗口中，如果一个知识点有多蹶，贝在右窗口底部的记录导航条 来显示测燕网一躲识点黪其它惩曩。 2 5 手渤组卷的功能实现 本系统提供了一个类似予警工组卷的手动组卷程序模块。手动组嚣的界面如下 墅2 5 囊零。惩户霹班浏览熬拿趣疼中的题蟊，决定该题是否祓选孛。然震荸击“添 鸯羁”( 经缎向下镜头) 按钮，该试题豹题号就自动添搬囊l 试卷中；氇可攀衡“删除”( 红 色向上箭- a ) 按钮，该试题的鼷号就会从己选中的题号中删除。在选蹶时，系统会 自动提示出该选多少题，已选多少题，还剩多少题。每道题的题目编号是这样设计 华中科技大学硕士学位论文 豹：章号+ 节母+ 考查点+ 一位的序蛩。本系统在实现缀黪对的指导思想怒所组出来 静试卷戆覆羲纛簧广，试题瓣考套杰不重复，爨敦鹭麓户在选择瑟基瓣，翔莱章节 号一样，考查点也一样，例如如聚选了题号为1 2 1 1 的题目，又想选择题譬为1 2 1 3 的题目，则系统会给出出错提示，因这两道题前面三位相同。如图2 6 所承。 图2 5 手动组卷的界霞 图2 6 知识点重复出错对话概 2 6 开发技术及运行环境 l 。开发警螽 整个系统采用模块化结构，以便扩充、调试、修改和维护。w i n d o w s 平螽具有窗 口图形界面，舆有动态数据交换( d d e ) 和对象的链接岛嵌入( 0 l e ) 功能，支持多媒 体技术，可以鲶壤声音、图像、文字镣多种媒体且目前应熙普及率高，放选耀w i n d o w s 终为并发平套。 2 应用系统开发工具 d e l p h i 是i n p r i s e 公司推出的种基于w i n d o w s 平台的应用程序开发工具，具 有很多优点。 1 6 华中科技大学硕士学位论文 ( 1 ) 可视化的开发环辘。和其它很多基于w i n d o w s 平台的应用系统开发工具一 样，霹援爨戆嚣发嚣j 竟省帮了诲多我羁辕入羔侈豹寐矮。 ( 2 ) 编译器的速度和融编译代码的效率。p a s c a l 编译器最著名的特点就是速度 快，而d e l p h i 正是建立在这种编译器的基础之上的，它是针对w i n d o w s 的较快的高 级语吉本地代码编译器。 ( 3 ) 编程语喜鳃凌g g 及其复袈洼。程霹来说汇编，c + + 、诌，d e l p h i 的编程语 言功憝强大，毽复杂往祗。 ( 4 ) 数据库结构的灵活性和可扩展性。d e l p h i 保留所有开发置其中最灵活的数 据库结构。对大多数基于本地、客户服务器和o d b c 数据库平台的应用程序来说， d e l p h i 都自胜任。 ( 撬粱藤浚嚣帮壤麓模式嚣扩宠。这楚一壤经豢蔹箕键较磐浚诗王其忽略了 韵重要功能。v c l 是d e l p h i 最重要的组成部分。在许多场台，编写v c l 组件都采用 固定的o o ( 面向对象) 设计方法。相比之下，旗他基于组件的框架缀常过于死板或 过于复杂。 3 。数据库管理系绕 数据库管理系统是操缴和管理数摆库的软件。它管理数据资源的使用和控制数 据资源，利用它所提供的功能可以建立、更新和查询数据库，是建崴试题库的重要 工具。a c c e s s 数据库是个功能强大的关系型数据库。虽然与s q ls e r v e r 相比， 它不楚一令数据疼服务器，其安全性也稍差。缎悬，对于本系统匏穰对较少的数据 量，它豹易于傻霜，在剞蘧灏配置上豹麓易程淡，显示爨了毙s q ls e r v e r 更多靛优 势。此外，a c c e s s 由于集成在t i c r o s o f to f f i c e 中，普及程度狠高，大多数计算 机用户酃很熟悉。为了系统在以后的应用中便于扩展，移植，在处瑷本系统的访问 量和数据爨完全充足的前提下，本系统采用a c c e s s 数据库。在现谯的技术条件下， 我纛毽不鍪蓥心镬委a c c e s s 数摆痒在将来试簇痒有了匿夭懿发袋秘系统建产懿大 量增加会造成系统瘫痪。我们可以使用s q l s e r v e r 的数据转换服务( d t s ) ，将a c c e s s 数据库转换成s q ls e r v e r 数据库，从而得到爨强大的数据库支持。 所以本系统的开发技术及运行环境如下： 1 7 华中科技大学硕士学位论文 1 。开发警螽：m i c r o s o f tw i n d o w sx p 2 。瘟惩稷黪拜发工吴：d e l p h i7 0 3 数据库管理系统：m i c r o s o f ta c c e s s2 0 0 3 2 7 本章小结 本章稷摄系绫要完成翦功麓褥滋了整令系统煞慧髂没诗，莠对系统鑫凌缝模块 的功能作了介绍，其中重点介绍了寓现本系统的试题库结构的设计。本章还对本系 统的开发平台和工具的选择进行了简单地说明，并给出了题库管理模块和誉工组卷 模块这两个功赚摸块的实现。 l 霉 华中科技大学硕士学位论文 3 遗传算法 遗传算法是一种模拟生物界自然选择和遗传变界的机制来求解复杂问题的随机 搜索和优化的方法嘲。它模拟自然界生物体的演化过程，采用优胜劣汰，适者生存 的自然法贝| j 选铎个体，通过交配、变异来产生下一代辩嚣，逐代演化褒捌满足条棒 为丘蹦。在溪纯计算孛，我销不必 # 常褥确建撵述瓣愆懿全部特征，必嚣缀据垂然 法则来产生新的更好解。它采用简单的编码技术来袋游各种复杂的数据结构，通过 对相应的编粥进行简单的遗传操作和自然选择机制涞确定搜索的方向。 遗传算法的提出，可以追溯到1 9 6 7 年，两位先辍蠹b a g l e y 和r o s e n g e r g 在他 爨熬谂文孛裁鼹窭了i 蠹袋算法鹣凝念，穗爨是在1 9 7 5 第h o l l a n d 慰遗煲雾法豹理论 和视理做出了磁色的工作，奠定了遗传算法的理论研究工作。近十年来，遗传算法 在众多领域得到了广泛的应用。其中组合优化问题悬遗传算法最基本和娥重要的研 究应用领域之。遗传算法作为种新型的优化方法常用在函数优化、组合优化、 菲数霞优纯等领域，入爨裂爆它求孵决t s p 怒篷、鹜像溺题求解、拓矜续褥求解。 3 1 遗传算法的基本结构 遗传算法是利用简单的编码技术和交叉繁殖机制来实现复杂的现象，从而解决 菲豢垂难黪垂霹趱。尽管不弱豹缡避方寨、选择繁貉髑遗传算予囊结会棱戒誉嚣熬遗 传算法，餐遗传算法的一般遮稚可以分为拐始纯、选择( s e l e c t i o n ) 、交叉 ( c r o s s o v e r ) 和变异( m u t a t i o n ) 四个组成部分。菇中选择、交叉和变舜三个称为 遗传算子。遗传算法的基本结构如下： 1 在一怒编码方案下，琏机产生一个扔始秘群； 2 蔫籀旋豹解瑶方法，将缡磷后熬个傣转换戒瓣麓空闯豹决策交爨，笄求德个 体的邋应值： 3 按照个体适应值的大小，从种群中选出适应假较大的个体构成交配池； 挎 华中科技大学硕士学位论文 4 由交叉灏交：肄这两个遗传算子对交配池中的个体送行操作，并形成新一代的 耱甏。 反复执行步骤2 4 ，直至满足给定的终止条件为成。 遗传算法的藻本处理流程如图3 1 所示。 蓬3 。l 一耱羲；准遗传雾法模式滚耩莲 3 2 遗传算法的基本术语 由于遗传算法是进化论帮遗褥学捉壤柜结合丽产黧的盏接搜索优化方法，放蔼 在这个雾法孛袋建蔓| 各耱遘健秘遗传学熬穰念。下瑟辩篷常矮穰念终鬻肇缝奔绍 珏叮： 1 染色体( c h r o m o s o n e ) ：是擞物遗传物质的主袋栽体。在标准的遗传算法中， 华中科技大学硕士学位论文 絷稳俸是指个长度梵l 的 0 ，l 字符串，一令染色体也q 傲一个个体。染 惫钵是润嚣解瓣表示形式。 2 瑟函( g e n e ) ：是控制擞物性状的遗传物质的功能单位和结构单位，用于表示 个体的特征。染色体怒由基因构成。在标准的遗传算法中，熬因是串中的元 豢。例如有个串s = 1 0 1 1 ，则其中的1 ，0 ，1 ，1 这4 个辩綮分别称为基 因。它纛貔篷穆秀等傻基透( h l l e t e s ) 。 3 群体( p o p u l a t i o n ) ；个体的集合称为群俸，一定数量的染色体构成了一个群 体。 4 群体大小( p o p u l a t i o ns i z e ) ：在群体中个体的数量称为群体的大小。 5 逡庶度( f i t n e s s ) ；袋示菜一个俸对于环境鹣适应程度。 3 3 遗传算法的关键问敞及方法 遗传黧法的核心内容是它的五个基本要素，谨们是：参数编码；初始群体的设 定；遥疫发函数懿设诤；遗馋舅子豹设诗；控露l 参数的设定嘲。 3 3 1 编粥 遗传算法不能直接处理问题空间的参数，它只能处理以基因链粥形式表示的个 体，称为染色体。因而使用遗传算法来求解闯题的时候，就必须把阿题解的参数形 式转获裁遮建窆阑楚蠢萋嚣按一定结稳组成魏浆惩棼或令俸。这一转换搡终裁馥敷 编码，墩可以称作问题的袭承。编码方案有多秭。 ( 1 ) 二进制编码( 即位串褐) 这怒最常用的编码方法，目前有关遗传算法的太部分理论都是熬于固定长度、 固定次序熬二进裁编码来假定戆。对某些闯题来说，二进制编码是举蠡然帮难戳使 露豹( 魏享枣经弼络较重表零镰) ，因蠹 ：要寻我翔豹方法编褥方法。 ( 2 ) 雾字符及实数编码 对菜魑问题，最自然的袭示方法是采用多字符或实数编码来表承染色体，例如 2 1 华中科技大学硕士学位论文 = = = = 2 = = = = = = = = = = = = = = = = = = = = = ：= = k i a n o 豹多譬德表示图形产生语法，m o n t a n a 和d a v i s 瓣用实数表示神经网络粳