基于遗传算法的C语言程序设计在线考试系统的设计与实现毕业设计

《基于遗传算法的C语言程序设计在线考试系统的设计与实现毕业设计》由会员分享，可在线阅读，更多相关《基于遗传算法的C语言程序设计在线考试系统的设计与实现毕业设计（85页珍藏版）》请在装配图网上搜索。

1、信息科学与技术学院学士学位论文JIU JIANG UNIVERSITY毕 业 论 文题 目 基于遗传算法的C语言程序 设计在线考试系统 英文题目Based on Genetic Algorithm C Programming Language Online Examination System 院 系 信息科学与技术学院 专 业 计算机科学与技术 姓 名 李志祥 班级学号 A081152 指导教师 袁媛 二一二年五月IV摘 要随着国家科技兴国战略的逐步实施，教育由精英化向大众化推进。面对为数众多且能力参差不齐的受教育者，传统的考试已经满足不了“因材施教，以人为本”的要求，教育和考核手段的改变以

2、势在必行。智能化在线考试是信息化发展下教育考试改革的一个必然趋势，它具高效率、更新快，可节省大量的人力物力财力，等特点。“基于遗传算法的C语言程序设计在线考试系统”是基于校园网络的考试模式，与传统的纸张考试相比，具有科学组卷、半自动评分、随时随地参加考试、快速高效实施的优势。本课题，研究了在线考试的应用背景、开发所采用的架构，比较并确定了.NET开发平台，选择了SQL Server 2008存储数据，使用了基于试卷难度和区分度为参数的遗传算法组卷，整体提高了系统的科学性。它由管理员模块、教师模块和学生模块组成，严格地控制角色的权限，合理地将管理系统、管理考试和参加考试分开，实现了在线考试的用户

3、登陆、信息修改、通知管理、试题库管理、自动组卷、半自动评分、倒计时、数据备份与还原等功能。经过具体测试分析，系统可以正常运行，具有界面简洁美观，操作简单方便等特点。关键词：遗传算法，数据库，考试系统AbstractWith the gradual implementation of the national science and technology, strategy, education from elite to mass forward. Educated uneven face of the large number and capacity, the traditional ex

4、amination has failed to meet the individualized, people-oriented requirements, education and assessment tools to change is imperative. Intelligent online test of the Educational Testing reform is an inevitable trend in the development of information technology, it is highly efficient, fast update, c

5、an save a lot of manpower, material and financial resources, and so on. Based on the genetic algorithm, C Programming Language online examination system is the mode of examination based on the campus network, compared with the traditional paper examinations, scientific test paper, semi-automatic sco

6、re anytime, anywhere to take the exam, fast and efficient implementation of advantages.This topic, research the background of the online exam application development framework, compared and identified. NET development platform, select the SQL Server 2008 stored data, using a genetic algorithm test p

7、aper based on the papers of difficulty and discrimination parameters, the overall improvement of the scientific nature of the system. Strict control of the role permissions by the administrator module, teacher module and student module, reasonably separated from the management system, administer the

8、 exam and take the exam, online test user login information to modify, notification management, test library management automatic generation of semi-automatic score, countdown, data backup and restore functions. After a specific test, the system can operate normally, the interface is simple and beau

9、tiful, easy to operate features.Keywords: Genetic Algorithms, Databases, Examination System目 录摘 要IAbstractII1 绪论1.1研究背景及意义(1)1.2国内外在线考试系统的研究现状(1)1.3开发平台的比较与选取(2)1.4系统环境分析(3)1.5系统开发的目标(6)1.6本章小结(6)2 系统分析2.1系统可行性分析(7)2.2系统需求分析(7)2.3系统功能分析(9)2.4本章小结(10)3 遗传算法组卷设计3.1遗传算法(11)3.2组卷理论简介(16)3.3传统组卷算法的分析(18)

10、3.4遗传算法组卷原理(19)3.5遗传算法组卷设计(19)3.6本章小结(26)4系统设计4.1系统硬件平台设计(27)4.2系统软件平台的选择(28)4.3系统总体功能设计(28)4.4系统主要功能模块设计(28)4.5系统数据库设计(30)4.6本章小结(40)5系统实现 5.1登陆界面的实现(41)5.2管理员模块的实现(41)5.3教师模块的实现(42)5.4学生模块的实现(48)5.5本章小结(49)致 谢(50)参考文献(51)核心源代码附录(53)1 绪论1.1研究背景及意义随着国家科技兴国战略的逐步实施，教育也由精英化向大众化推进。面对为数众多且能力参差不齐的受教育者，传统的

11、考试已经满足不了“因材施教，以人为本”的要求，教育和考核手段改变以势在必行。在计算机网络技术的推动下，产生了一大批计算机辅助教学设施。如在高校，使用多媒体进行远程教学、电子管理系统管理学生的基本信息等等，都达到了比较好的预期效果1。在学院，依旧沿用传统的人工出卷、纸质考试、人工批阅、分数采集的考试方式，教师有大量繁重的考务工作要做，由此在批阅、分数采集时更容易出现错误；另一方面，学生容易根据出题老师的课堂内容，进行突击复习，采用猜题押题的方式来应付考试。因此，这种考试不能达到对学生实际学习情况的有效评估，学生不能及时发现自己在学习中存在的问题，教师不能根据考试结果进行合理的教学调整，达不到不断

12、提高教学质量的要求。相比国内外网络公开课的发展,学院有必要进行网络考试的尝试，为今后的发展提供一个方向。网络考试具有不受时间地域限制、提高考试工作的效率、避免资源浪费降低教育成本的特点。同时，针对在外实习毕业生，往返学校参加考试确实不便，如能实现远程在线考试，将是非常不错的选择。“基于遗传算法的C语言程序设计在线考试系统”是关于如何从题库中抽取一定数量的试题来形成一份高质量试卷的组合优化问题的研究，模拟自然界生物进化的方式，动态自适应性地满足试题库不断变化的要求。相比简单随机搜索算法、回溯试探算法、误差补偿算法、优先权算法，它具有组卷成功率高、速度快、容易控制、算法复杂度低等特点。它可以作为一

13、个实验平台，推进学院无纸化考试改革的进程。1.2目前国内外在线考试系统的研究现状在线考试系统是计算机辅助测试系统的外延，人们已经利用它取得了很丰硕的成果。在国外，TOEFL、GRE、RHCA、OCM、CCIE等各种在线认证考试均已成功运营；在国内，计算机等级考试、华为的网络认证考试等都如火如荼的展开2。这些网络在线考试系统，具有自动组卷、题库量大、安全可靠、使用方便和界面友好等诸多特点，显示了在线考试系统的强大生命力和广阔的市场空间。目前，主要有三类考试系统模式：（1）单客户机模式用户只需要独立的将考试系统安装到计算机中而无需联网就能模拟出考试环境，这种考试系统类似软件而又没有相应的服务支持，

14、系统维护升级非常困难。（2）C/S模式C/S模式，即客户端/服务器结构模式。前端大部分是个人PC机，完成界面显示、数据输入、向后台发送请求、接受服务器返回的结果等。后端是服务器，提供数据库的查询和管理。模式的灵活性差，且所用客户机都要安装客户端软件。（3）B/S模式B/S模式，即浏览器/服务器结构模式。客户端运行浏览器软件，浏览器以超文本形式向Web服务器提出访问数据库的要求，Web服务器接受客户端请求后，将这个请求转化为SQL语法，并交给数据库服务器，数据库服务器得到请求后，验证其合法性，并进行数据处理，然后将处理后的结果返回给Web服务器，Web服务器再一次将得到的所有结果进行转化，变成H

15、TML文档形式，转发给客户端浏览器以友好的Web页面形式显示出来。B/S模式在线考试系统不需要客户端安装软件程序，系统易于维护和管理，应用广泛。1.3开发平台的比较与选取J2EE (Java 2 Enterprise Edition)由Sun公司推出，J2EE平台提供了一个基于组件的方法，用来设计、开发、装配以及部署企业应用程序。微软公司推出的.NET系统在安装了公共语言运行库(CLR)的任何一个操作平台上都可以运行。.NET和J2EE非常相似，但这两种技术在实现方法和具体实现技术上有很大的差别。通过J2EE与.NET支持的语言、标准及平台进行比较，本系统可采用.NET架构下的ASP.NET开

16、发环境。其具体比较如下。1.3.1支持的语言和语言标准.NET支持C+, VB, C#和J#等开发语言，支持下一代互联网内容表示的XML/SOAP标准。.NET下，开发人员可以很容易的找到适合自己的开发语言。J2EE只能够支持Java语言，因此对语言的选择比较的狭窄。1.3.2跨平台在.NET平台上开发程序真正实现了代码重用，即运行时和具体语言分开，所有的资源管理，内存分配和变量类型均有公共语言运行库处理。例如，用C#写的类就可以直接用在C/C+程序中。而在J2EE平台上只能用Java来开发程序，运行是和具体的语言混在一起3。1.4系统环境分析 1.4.1系统开发环境系统开发环境：Micros

17、oft Visual Studio 2010 集成开发环境 ；系统开发语言：ASP.NET + C# ；系统后台数据库：SQL Server2008 ；开发环境运行平台：Win7（SP1）。1.4.2服务器端操作系统：Win7(SP1) ；Web服务器：Internet信息服务（IIS）管理器；数据库服务器：SQL Server2008；浏览器：IE8.0；客户端浏览器：IE8.0。1.4.3开发环境和语言简介ASP.NET是Microsoft公司推出的Web开发平台，是目前最先进、特征最丰富、功能最强大的Web开发利器4。ASP.NET具有方便灵活、性能优越、生产效率高、安全性高、完整性强等

18、特点，支持多种开发语言，并包含许多先进技术，如ADO、.NET、AJAX无刷新技术、LINQ数据库访问技术母版页、Web Server、主题等等，是目前主流的网络编程环境之一。系统主要用到的ASP.NET对象如下：（1）Response对象常用的方法Redirect：将网页重新导向另一个地址。Write：将数据输出到客户端。（2）Request对象的方法MapPath：为当前请求将请求的URL中的虚拟路径映射到服务器上的物理路径。SaveAs：将Http请求保存到硬盘。（3）Session对象常用方法及其说明 Abando：此方法结束当前会话，并清除会话中的所有信息。如果用户随后访问页面，可以

19、为它创建新会话。C#语言是一种功能强大、面向对象的编程语言，它从C语言和Visual C+派生而来，是Microsoft公司.NET技术核心开发语言，能很好的与ASP.NET 配合使用。IIS是Internet Information Server的缩写，是微软提供的Internet服务器软件，包括Web、FTP、Mail等服务器。其主要功能：安全通信，IIS采用各种安全协议，保证了服务器端、客户端和服务器端与户端信息交换时的安全；权限向导，通过向虚拟目录和文件分配访问策略，可以简化配置Web站点访问的任务；IIS进程限制，能够限制CPU在处理单个Web站点的应用程序时的时间百分比，还可以终止

20、新启动运行失常的进程；应用程序保护，IIS为Web应用程序提供了更大的保护和更强的可靠性。1.4.4所用FCKeditor插件和倒计时技术简介：FCKeditor在线编辑器是专门应用在网页上实现“所见所得”的文字编辑器，可以减轻试题库输入时工作量，其主要实现如下功能：（1）现实文本对齐、缩进和项目符号等格式化；（2）实现设置文字颜色、样式、字体和类型等格式化；（3）实现剪切、粘贴、撤销和重做等操作；（4）实现从word粘贴并自动清理的功能；（5）支持CSS，可以为文本内容设置样式；（6）支持插入表情符号，定制个性化内容等。倒计时采用的是Ajax技术中的JavaScript方式。会话开始时，浏览

21、器加载一个图1-1 Web工作模式和Ajax工作模式Ajax引擎，采用JavaScript编写并且通常在一个隐藏的框架中。这个引擎负责绘制用户界面以及与服务器端的通信。Ajax技术允许用异步的方式实现用户与程序的交互，就是说不用等待服务器端的通信，帮助用户节省了等待时间5。Ajax模式和传统Web模式工作方式如图1-1所示。 1.5系统开发的目标本系统将要实现如下目标：（1）考试界面简洁美观，方便学生和教师操作；（2）试卷编排合理，按教师设定难度和区分度自动组卷；（3）考试系统公平公正，考试设有倒计时方便学生掌握考试时间；（4）考试时间到后系统自动保存并且提交试卷；（5）系统能够半自动阅卷并且

22、显示考试结果；（6）考生能够查看成绩、浏览通知、修改密码和进行考试；（7）教师能够添加、修改、删除考生信息、试题信息，修改自身密码，对组卷参数进行设置并组卷，对考后的试卷进行批阅和删除；（8）管理员能够添加、修改、删除通知信息、教师和考生的信息，修改自身密码，添加、修改、删除，对系统进行维护。1.6本章小结本章通过研究在线考试的意义和现状，得出在线考试系统将在未来的教育中发挥巨大作用，故选择在线考试系统作为开发对象；其次，为将进行的开发选择了开发平台、所需环境和开发工具；最后提出了系统开发的所要完成的功能目标。2 系统分析在进行可行性研究和项目开发计划以后，如果确认开发一个新的软件系统是必要的

23、而且是可行的，那么就可进入分析阶段。需求分析是指开发人员要理解用户的要求，进行详细的市场调查，确定系统的新目标6。为了满足用户的需要，回答系统要“做什么”的问题。2.1系统可行性分析（1）在系统开发的技术方面，“基于遗传算法的C语言程序设计在线系”统属于一个微型系统，使用的前台开发工具是Microsoft Visual Studio2010，后台数据库使用SQL Server 2008，系统主要是通过前台的操作对后台数据库进行相应的操作，如对数据的修改、添加、删除和查询。开发本系统时，使用Microsoft Visual Studio2010进行即见即得的前台界面设计，通过SQL语句使用户实现

24、读取后台数据，然后进行相应的数据操作，再将操作结果实时返回到数据库中并保存，以便随时提供查询。因此系统开发的技术方面是可行的。（2）经济可行性方面：系统开发时，需要一台处理器性能为PIII或以上，内存为512MB，硬盘至少10G，大家学习使用的计算机就可满足要求。同时，本系统不涉及商业应用，只作为学习应用研究，因此可以免费使用系统开发所需软件，例如Windows操作系统，Microsoft Visual Studio2010和SQL Server 2008数据库等。可以得出，系统开发的经济方面是可行的。2.2系统需求分析2.2.1 功能需求分析一个完整的在线考试系统通常包括试题库的建立与管理、

25、参与角色的分类与管理、考试的实施与管理、考后相关信息的发布与管理。本系统根据参与角色将需求分析具体分类如下。学生用户需求：能使用用户名和相应的密码登录系统。登录后，可实现浏览通知、参加测试和查看成绩的功能。考生用户名由教师给出，考生仅可以修改自己的密码。若考生选择浏览通知，则进入通知浏览页面；若考试完成，在规定的时间内可以查询自己的成绩；若考生看完考试规则后选择开始考试，系统自动计时，当考生选择交卷或者考试时间到时，系统自动将考生当前的测试答案提交保存至后台数据库。试卷提交之后，考生可再次进入系统，但不可再次测试，只可进行无关考试的操作。教师用户需求：可修改自身除“教师户名”字段之外的信息，调

26、阅考过的试卷和学生的答卷，查看、增加、删除、修改试题信息、通知信息和考生信息，设置组卷参数，组卷，批阅学生答卷，统计试卷得分，得出数据分布情况，重新计算试卷中出现的各个试题的难度和区分度，赋予其相应值。管理员用户需求：能够对学生信息、教师信息、通知信息进行查看、增加、删除和修改操作，添加其他管理员，查看其他管理员户名和管理员姓名，修改自身除“管理员户名”字段之外的信息，还能够进行系统数据的备份与还原。2.2.2工具软件需求分析由于选择在.NET平台上进行开发，开发工具就必须全面支持.NET架构。而Visual Studio2010是微软一款基于.NET架构的集成环境开发工具，具有天然的三层架构

27、，很适合在线考试系统的开发。由于前台界面开发工具为微软的Visual Studio2010，所以就选择同为微软产品的SQL Server2008数据。因为两者配合程度非常高，数据的处理上不会存在任何问题。2.2.3数据库需求分析针对考试系统的需求，设计如下所示的数据项和数据结构：管理员信息，包括的数据项有：管理员姓名、密码等。教师信息，包括的数据项有：教师姓名、密码等。考生信息，包括的数据项有：用户名、密码、班级等。试卷信息，包括的数据项有：单项选择题分值，单项选择题数量；填空题分值，填空题数量；程序设计题分值，程序设计题数量。选择题信息，包括的数据项有：单选题编号、题干、正确答案、备选项（A

28、、B、C、D）等。填空题信息，包括的数据项有：填空题编号、题干、正确答案等。程序设计题信息，包括的数据项有：填空题编号、题干、参考答案等。成绩信息，包括的数据项有：考生学号、成绩、考试时间等。通知信息，包括的数据项有：通知内容、通知时间、通知发布者等。本系统应该建立一个稳定的后台数据库系统，通过该数据库管理整个考试系统所需的信息（用户信息、试题信息、试卷信息、考试信息等），还应该包括学生、教师和管理员的账号、考试过程的控制机制。2.3系统功能分析本系统的用户可分为管理员、教师和考生，其功能应满足如下要求：（1）考试界面简洁美观，方便学生和教师操作；（2）试卷编排合理，按教师设定难度和区分度自动

29、组卷；（3）考试系统公平公正，考试设有倒计时方便学生掌握考试时间；（4）考试时间到后系统自动保存并且提交试卷；（5）系统能够半自动阅卷并且显示考试结果；（6）考生能够查看成绩、浏览通知、修改密码和进行考试；（7）教师能够添加、修改、删除考生、试题、通知的信息，修改自身密码，设置组卷参数，并组卷，批阅和删除考后的试卷；（8）管理员能够添加、修改、删除教师、考生、通知的信息，添加其他管理员，查看其他管理员户名和管理员姓名，维护自身信息和系统信息。从上面的结论得出系统的具体模块划分如下：学生模块：（1）系统管理：修改密码，退出系统；（2）考试模块：进行考试，计时功能，交卷功能；（3）成绩查询：只可查

30、询自己的成绩；（4）通知浏览：浏览通知。教师模块：（1）系统管理：修改密码，退出系统；（2）试题管理：对题目的增加、修改和删除；（3）自动评分：对提交的试卷客观题部分进行自动评分；（4）数据统计：统计考生分数，重新计算各个试题的难度和区分度；（5）试卷管理：批阅考卷主观题，考卷参数设置并自动组卷； （6）学生信息管理：浏览学生信息，并能进行增删改操作；（7）通知浏览模块：教师对通知进行增删改操作。管理员模块：（1）系统管理：修改密码，退出系统；（2）系统维护：系统备份、还原；（3）通知管理：添加、修改、删除通知信息；（4）用户管理：添加、修改、删除教师、学生的相关信息，查看其它管理员的管理员户

31、名、管理员姓名。2.4本章小结本章通过系统可行性分析、系统需求分析和系统功能分析，确定了所开发系统需要的工具软件、系统的结构、各模块基本功能，对系统有更进一步的认识。3 遗传算法组卷设计3.1遗传算法遗传算法是一种通过模拟自然进化过程的全局最优解搜索方法，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，是用来解决在多目标约束条件下求最优解问题的算法，具有广泛的应用。3.1.1遗传算法基本描述遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初是由美国Michigan大学J.

32、Holland教授于1975年首先提出来的，并出版了颇有影响的专著“Adaptation in Natural and Artificial Systems GA这个名称才逐渐为人所知，J. Holland教授所提出的GA通常为简单遗传算法7。遗传算法抽象自生物体进化过程，通过全面模拟自然选择和遗传，形成一种“生成+检验”特征的搜索算法。遗传算法以编码空间代替问题空间，以适应度函数为评价依据，以编码群体为进化基础，以对群体中个体位串的遗传操作实现选择和遗传机制，建立起一个迭代过程，直到得到满足条件的结果,遗传算法同时具有内在的并行性、收敛速度快和全局寻优等的特点，父代与子代之间维持由潜在解组成

33、的种群来实现多样性和全局搜索。遗传算法的内在并行性和群体搜索策略为多目标优化问题提供了较好的解决方案，因此适宜于处理类似自动组卷这种多目标优化的问题。3.1.2遗传算法基本概念由于遗传算法是由生物遗传学和计算机科学相互结合渗透而成的一种新的计算方法，因此遗传算法中经常使用一些生物遗传学中的基本概念。了解这些基本概念对于讨论和应用遗传算法是十分必要的。（1）染色体(Chromosome)：在使用遗传算法时，需要把问题解编码成具有固定结构的符号串，它的每一位代表一个基因。一个染色体就代表问题的一个解，每个染色体称为一个个体。（2）种群(Population)：每一代所产生的染色体总数。一个种群包含

34、了该问题在这一代的一些解的集合。（3）适应度(Fitness)：每个个体对应一个具体问题的解，每个解对应的函数值即为适应函数，它是衡量染色体对环境适应度的指标，也是反映实际问题的目标函数。（4）基因座：染色体中基因的位置称为基因座，而基因所取的值叫做等位基（5）模式定理：在遗传算子选择、杂交、变异的作用下，低阶、定义长度短、超过群体平均适应值的模式生存数量，将随着迭代次数的增加以指数级增长。（6）最小字符集编码规则：编码采用最小字符集，使问题得到自然简单的表示和描述。3.1.3遗传算法基本流程遗传算法在整个进化过程涉及五大要素：参数编码、初始群体的设定、适应度函数的设定、遗传操作的设计、控制参

35、数的设定。（1）选择编码策略，把参数集合X和域映射到位串结构空间S；（2）定义适应值函数f(x)；（3）确定遗传策略，包括选择群体大小n,选择、杂交、变异方法，确定杂交概率Pc、变异概率Pm等遗传参数；（4）随机初始化生成群体P；（5）计算群体中个体的位串适应值f(x)；（6）按照遗传策略。运用选择、杂交和变异算子作用于群体，形成下一代；（7）判断是否达到预定目标，或者完成预定迭代次数，不满足则回到（6）。遗传算法流图如3-1图所示。图3-1遗传算法流程图3.1.4遗传算子介绍遗传算法操作算子一般都包括选择、杂交、和变异三种基本形式，他们构成了遗传算法具有强大全局搜索能力的核心，是模拟自然选择

36、以及遗传过程中发生的繁殖、杂交和变异现象的主要载体。遗传算法利用遗传算子产生新一代群体来实现群体进化。（1）选择算子，从当前群体中选择适应值高的个体以生成交配池的过程，有适应值比列选择、排序选择、精英选择等形式。（2）杂交算子，是进化算法中遗传算法具备的原始性的独有特征，它模仿自然界有性繁殖的基因重组过程。杂交一般包括一点杂交、两点杂交、多点杂交、一致杂交等。杂交操作分以下三步：从交配池中随机的取出要交配的一对个体；根据位串长度L，对要交配的一对个体，随机选取1，L-1中一个或多个的整数K作为杂交位置；根据杂交概率Pc（0Pc=1）实施杂交操作，配对个体在杂交位置处，相互交换各自的部分内容，从

37、而形成新的一对个体；变异算子，是模拟自然界生物进化中染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。变异操作是作用于个体位串的等位基因上，由于变异概率较小，在实施中根本不发生变异，所以现对个体层次的变异发生概率进行判断，然后实施基因层次上的变异操作。变异算子可以使群体进化过程中丢失的等位基因信息得以找回，以保持群体中的个体差异，防止发生早熟收敛；此外，当种群规模较大时在杂交操作上引入适度的变异，可提高遗传算法的局部搜索效率。3.1.5种群设定和初始化种群是遗传算法的作用域，作用域的大小直接影响遗传算法并行性、全局性和鲁棒性。根据模式定理，若群体规模为N，则遗传算子可以从这N个个

38、体中生成和检测O(N*N*N)个模式，并在此基础上不断形成和优化基因模块，一直逼近问题的全局最优解。初始化中种群的个体一般是随机产生的。在不具有关于问题解空间的先验知识的情况下，很难判定最优解得数量及其在可行解空间的分布状况8，因此，往往采用问题解空间均匀采样的方法，随机生成一定数量的个体（为初始群体规模的两倍），然后从中挑选好的个体构成初始种群。3.1.6终止循环条件（1）采用设定种群的最大代数，即进化代数到达限定的最大值便停止，该方法简单易行，但不准确；（2）根据种群的收敛程度来判断，通过计算种群中的基因多样性测度，即所有基因位的相似程度来进行控制；（3）根据种群的整体性能、进化能力、遗传

39、算法的搜索能力等的变化进行判断；（4）在采用精英保留选择策略的情况下，按每代最佳个体的适应值的变化情况来确定。3.1.7遗传算法搜索遗传算法应用于优化问题求解，是一个启发式搜索过程。在该搜索过程中，遗传算法不仅需要探索解空间上的全局性最优解，而且应当充分利用已获得解空间信息逼近当前局部最优解。遗传算法通过群体和遗传算子可以实现扬弃性的探索，克服局部极值陷阱，实现整个解空间范围内的搜索，提高全局寻优能力。通过续承的发展，维持群体的可进化性，同时克服早熟，实现领域搜索，提高搜索逼近能力。扬弃是通过遗传算法中的选择算子选出优良个体淘汰劣质个体，从而维持群体整体的优良性。续承与发展靠交叉算子、变异算子

40、来对群体中的个体操作从而达到群体整体的进化。其搜索能力如图3-2所示。图3-2 遗传算法搜索能力3.2组卷理论简介3.2.1试题库建设的理论基础试题库由各种题型和试题组成。试题库对加入其中的试题都有一定的要求。主要是按照经典测量理论或项目反应理论来进行设计。经典测量理论采用的是线性的定性模型，项目反应理论采用的是非线性的概率模型9。本系统采用的是经典测量理论。（1）经典测量理论数学模型是经典测量理论的核心。而真分数数学模型是经典测量理论的基础，也是这个理论的核心，其理论基础是弱假设10。所谓弱假设是指这些假设很容易验证并易被绝大多数测验数据资料所满足。经典测量理论在此基础上建立一整套理论及统计

41、分析方法。利用经典测量理论进行教育测验，要求被测者在完成一定题目的基础上，根据一定的指标，通过作答情况来判断其发展水平。系统所涉及的指标介绍：难度,是指测验试题的难易程度。在教育测量中，客观题的难度一般用正确解答试题的人数与参加测验的学生总数的比值来表示。难度是试题对学生知识和能力水平适合程度的指标。区分度,是测验试题对被试者能力高低的鉴别，是评价试题质量，筛选试题的主要指标和依据。如考生实在考试测验中，所得分数都相差不大，就说区分度不好；当学习好考生得高分，不怎么学习的考试得低分，即这份试卷有良好的区分度，符合考试教学规律。经典测量理论的优点在于统计方法简单明了，容易计算。指标是量化的，意义

42、易于理解和掌握;缺点在于试题指标受样本的选择，考生的实际水平无法和试题指标建立相应的函数关系。（2）项目反应理论项目反应理论和经典测量理论大相经庭，经典测量理论是在测试者完成一定数量的情况下，再对被试者进行评价；项目反应理论假定测试者有能力，然后定量估计其能力。项目反应理论克服了经典测量理论的缺点，但对测试者的能力认评估还需要更精确。项目反应理论把测试者的能力称为“潜在特质”，潜在特质是在观察分析测验反应基础上提出的一种统计构想。项目反应理论是根据考生回答题目的情况，估算考生的能力。项目反应理论是能力测试的理论，它主要包括几种重要的假设：能力的单维性假设、局部独立性假设、题目特征曲线假设、完成

43、测试时间的充分性假设等。3.2.2试题库建设的特性一个科学合理的试题库在保证试题质量的同时，组卷速度快、区分度好、难度适中、试卷的分析科学合理以及减少系统的负担。由此试题库建设是非常必要和重要的，试题库中的试题是按照考试大纲、考试目标、试题约束和考试结果进行筛选和校准的。本系统的试题库应该具有以下几个特性：（1）试题库的容量要适中，题量太小，生成的试卷不科学，不合理；题量太大，抽取试题时间太长，题目的录入和选取也比较耗时。（2）为了便于组卷，试题库中的题目按照题型分类。（3）试题库中的试题除了能反应题目本身之外，还要能识别题目的属性，这样能区别于库中的其他题目。3.2.3组卷系统成卷步骤组卷系

44、统要实现其功能必须经过四个过程，即获取用户需求、建立试卷模式、建立组卷算法的数学模型和试卷模型的求解。其中，前一步的操作时下一步实现的基础。好的组卷数学模型使得求解相对容易，整个算法实现的比较快。不好的组卷数学模型不仅使得算法的实现比较困难，还有可能导致系统的瘫痪。成卷模式是对用户需求一种定量的反应，它是建立组卷数学模型的基础，它的好坏决定了组卷数学模型的好坏。3.3传统组卷算法的分析自动组卷就是按照测验目的和组卷要求在试题库中抽取满足条件的试题，从而组合成一套或多套试卷。试卷的质量直接影响着考试的考核尺度。然而，目前现有的组卷算法在一定程度上还存在着一些问题。比如，随机组卷算法具有很大的随机

45、性和不确定性回；溯试探法对内存的占有量较大，结构复杂，组卷时间长；误差补偿策略中的误差难以掌握；优先权策略的操作过程中需要对优先权反复进行排序和比较，算法比较复杂等等。因此，寻求一种更加合理、有效的组卷算法。3.3.1随机抽取策略随机抽取策略就是根据组卷指标，从试题库中随机抽取试题，不断重复搜索过程，直到试题生成、操作完成或不能再搜索到满足组卷指标的试题为止11。这种方法结构简单，但对试题量的要求较高，具有很大的不确定性和随机性，在题库中题量较少的情况下，效率很差。3.3.2回溯试探法回溯试探法是将随机抽取法产生的每一状态类型记录下来，当搜索失败时释放上次记录的状态类型进行试探，通过不断地回溯

46、试探直到试卷生成完毕或退回到出发点为止12。此方法适应于类型和出题量都比较小的题库系统，实际应用程序结构相对复杂，而且选取试题随机性差，组卷时间长。3.3.3误差补偿策略所谓误差补偿策略就是在试题生成过程中，当有些约束条件不能满足的时候，可以适当地放宽约束条件，让试题在允许的误差范围内生成试卷。这种组卷策略在试题的生成过程中确实可以减少失败的次数，提高了组卷的效率和成功率，但在生成试题时的误差区间是很难掌握的。3.3.4优先权策略在试题生成的开始阶段，由于各项属性都有较大的取值范围，各指标的牵制问题不会立即反映出来，但随着被选试题数的增加，取值范围逐步缩小，矛盾便会随之产生，为了避免这种情况，

47、可以考虑利用优先权策略，将难选的试题放在前面选出13。该方法在实际的操作过程中需要不断地对优先权重新进行计算与排序，这样会使算法很复杂，效果也有限。3.4遗传算法组卷原理自动组卷按照一定的算法自动地从试题库中抽取试题，组成试卷14。算法的好坏直接影响抽取试题的质量。利用好的算法组成的试卷既能满足教学要求又能满足用户要求。系统在对用户进行需求分析的基础上，将用户的要求转化成对试卷指标的具体要求，试卷指标主要包括考试时间、难度、区分度，可隐性地包含试卷总分100分；然后根遗传算法，在试题指标的约束下，从试题库中随机试题形成试卷初始群体，使用遗传算法作用在群体上进行进化，再得出近似的全局最优解，最后

48、对得出的解进行解码映射，生成试卷。相比传统的“先从试题库中抽取试题，然后验证试题是否符合试题指标”组卷方式，遗传算法组卷建立一个最接近用户要求的多目标的数学模型，然后对数学模型进行求解，求解的结果满足当前试卷模式下的具体指标要求值，最后在题库中查找与指标值相匹配的试题，完成组卷15。遗传算法组卷只需遍历一次试题库，经过遗传选择、交叉和变异算子的操作，就可以找到符合条件的试题，明显的避免了抽题的盲目性，节约了组卷时间。3.5遗传算法组卷设计本文是按分类编码的准遗传算法进行组卷设计，对参数映射、编码解码、遗传算子、适应值函数、停止准则进行设计，将问题变为遗传算法可操作对象，最后得出近似全局最优解，

49、再将解还原成问题对应的解。3.5.1问题参数映射设计本系统需要按题型分类将试题信息表中试题数量映射成二进制编码位串长度，解码后取出各试题的难度、区分度属性值，进行适应函数值的计算，然后进行遗传操作，最后将得出的全局近似最优解依旧按题型分类使用试题的主键字段映射到试卷信息表中。采用多表查询的方式，从试卷信息表和试题信息表得到所要的试题。这样保留了历次考试的试卷信息，提高了试题存储的效率，降低了试题库信息的改变对历次试卷的影响。3.5.2编码和解码的设计由问题空间向遗传算法编码空间的映射称作编码，而由编码空间向问题空间的映射称作译码。遗传算法编码一般需要满足以下三个条件：完备性：问题空间中的所有点

50、（可行解）都能成为遗传算法编码空间中的点（染色体位串）的表现性；健全性：遗传算法编码空间中的染色体位串必须对应问题空间中的某一潜在解；非冗余性：染色体和潜在解必须一一对应。基于自小字符集原则，考虑按试题分类编码，采用非定长二进制编码、解码的方式比较合适。编码字符集为0,1，0代表字符串中该位代表的试题不被选中，1则代表选中。编码位串空间：Bt=（A1，A2，A3，An），Ai（i=1，2，3，n）属于字符集0,1，n代表试题信息表中第t类试题的总量。由编码位串空间构成问题解空间的位串，即个体位串空间为：P=（B1，B2，Bm），Si（i=1，2，3，m）是第i类试题中被选中的试题，m代表试题库

51、中试题类型的总量。由于采用非定长二进制编码，首先对编码位串空间进行解码，再对编码问题空间进行解码，解码方式如下。解码位串空间函数：St=JM(string Bt)；函数JM(String)的设计如下：Protected String JM(string Bt) String arry=”;for( j=1; j L) tmpStr = str.Substring(0, L); return tmpStr;protected string right(string str, int L) string tmpStr; tmpStr = str; if (str.Length L) tmpStr

52、= str.Substring(str.Length - L, L); return tmpStr; 解码问题空间，便是根据解码的串位空间结果对题库试题信息表进行相应的数据操作，取得各试题难度、区分度的值，再利用适应值函数计算该解的适应值。3.5.3遗传算子的设计遗传算法中，选择算子的作用是在种群中选择优良个体的基因遗传给下一代，变异算子的作用是基因重组和群体更迭，变异算子的具有维持群体的多样性、提高遗传算法的局部搜索效率的。（1）选择算子选择算子采用排序选择，作用于整个群体，将其中个体按适应值由大到小的排成一个序列，再由头向尾小取出下一代种群的量，放入交配池，等待交叉操作。与英选择相比，排序

53、选择容易丢失全局最优解，但过程比较容易控制，可以动态调整选择概率，根据群体进化情况适时改变群体的选择压力；与的适应值比列选择相比，排序选择种群的多样性更高，后代的选择压力较小，进化能力更强；与模拟退火过程的Boltzmann选择相比，不必考虑如何选择退火温度的值和最大的进化代数。设置选择的概率为0.8。排序选择的流程图如图3-3所示。图3-3选择排序流程图（2）交叉算子交叉算子的作用是使个体间进行基因的交流，产生新的子代，从而使种群得到更新。交叉有多点交叉、两点交叉和单点交叉。多点交叉可以使基因快速交流，加快收敛的速度，但整个过程难以控制；两点交叉和单点交叉在整个基因交流过程中比较缓慢，但较容

54、易控制和实施。此外，交叉算子作用下，只进行基因的交流，并不在更新种群过程产生新的基因。本系统交叉算子采用单点交叉，一次作用在两个个体上，随机选中作用的题型，再作用在该题型位串上的某位，将作用域里的两个个体位串都按该位将位串分为两部分，开始相互交换对应的位串。与多点交叉和一致交叉相比较，单点交叉效率较低，位串头和尾部的位总是在不断的交换，不利于快速产生优良个体。但该方法容易理解，过程控制简单，便于学习和研究遗传算法。交叉算子流程图如图3-4所示。图3-4 交叉算子流程图变异算子是作用在个体位串的等位基因上的，变异概率大小决定了局部搜索的范围，太大了遗传算法容易蜕变为随机搜索算法，太小了种群的多样

55、性难以确保，本系统将变异概率设置为0.15。变异算子流程图如图3-5所示。图3-5变异算子流程图3.5.4适应值函数设计参与适应函数设计的两个要素，难度系数和区分度系数定义如下：试题难度系数：nd(Xi)= sum(Xi)( N*f(Xi)Xi为试卷中第i道题，nd(Xi)为第i题的难度，sum(Xi)为所有参与考试的考生在第i道题得分的总分，N为参加考试的人数，f(Xi)为第i道题对应的分值。试题难度系数越大，考生越容易分。试题区分度：qf(Xi)为(1/e)的t次方, qf(Xi)为第i题的区分度t=|G(Xi)g(Xi)(f(Xi)5)|，G(Xi)为考试成绩靠前的占考生总量20%的考生

56、对试卷中第i道题的平均的分，g(Xi)则为考试成绩靠后的占考生总量20%的考生对试卷中第i道题的平均的分，f(Xi)为第i道题的分值。区分度越高，对考生的区分能力就越强。试卷难度tnd取所有选中试题难度的平均值，试卷区分度tqfd取所有选中试题区分度的平均值。适应值函数S(y,z)为(1/e)的T次方。T=| 0.5*（ytnd）0.5*(ztqfd) |,y为教师组卷设置的试卷难度，z为教师组卷设置的试卷区分度。3.5.5停止准则的设计采用设定种群的最大代数的方法来停止遗传算法对对象的遗传操作，该方法需要根据试题库总量信息，来确定遗传操作所需的最大代数，容易实施。3.6本章小结本章系统的介绍

57、了遗传算法及其相关概念，对组卷理论做了简介，分析了传统组卷算法在组卷应用中的优劣，说明了遗传算法在组卷应用中的优势，并对应用遗传算法组卷进行了详细的设计和说明。4 系统设计4.1系统硬件平台设计由于本系统是分布式系统，若实施，其业务层需要Web服务器来支撑，数据逻辑层要数据库服务器来支持，当然业务层和数据逻辑层可以在同一台服务器上。服务器硬件基本要求为：主频3.OGHZ，内存容量4G，硬盘越大越好。客户机性能要求：主频1.7G以上，内存容量256M以上。由资料得知，该分布式系统发布后的网络拓扑图应如图4-1所示。图4-1网络拓扑图本校已有的服务器完全可以充当其中的Web服务器和数据库服务器，并

58、且微型系统由于用户量少，占用学校服务器系统资源较少，可以进行实施。4.2系统软件平台的选择本系统运行在Windows 2000/XP及以上操作系统平台之上，浏览器为IE5.0以上，以动态网页的方式呈现给用户。网站开发平台为Visual Studio 2010，开发语言以为主ASP.NET，辅以JavaScript、IIS、HTML、C#。数据库采用的是关系型数据库SQL Server2008。4.3系统总体功能设计根据用户需求分析和系统设计目标的要求，系统主要由三个部分组成学生子系统、教师子系统和管理员子系统。系统结构如图4-2所示。4-2系统结构简图学生子系统主要功能是考生登陆、在线考试、通

59、知浏览、成绩查询和信息维护；教师子系统主要功能是教师登陆、学生信息管理、试题信息管理、组卷管理、考试管理、通知信息管理和个人信息维护；管理员子系统的主要功能是学生信息管理、教师信息管理、通知信息管理、管理员信息维护、系统维护。4.4系统主要功能模块设计根据用户需求分析和系统设计目标的要求，系统总体结构主要由登陆界面、学生考试子系统、教师子系统和管理员子系统组成，下面将对各个子系统分别加以介绍：学生子系统，登陆后就进入显示考试规则页，若有考试，点击“同意，开始考试”才能考试，否则就不能进行考试。此外，可以查看自己考试的成绩，浏览教师或管理员发布的通知，修改密码功能。其功能结构如图4-3所示。图4

60、-3考生子系统功能结构（1）考生登录模块管理员为每一个考生分配一个用户名和密码，其中分配的密码可以为空或者为默认值，减少工作量并方便考生修改信息，而考生根据用户名和密码在考试系统的登陆界面进行登陆，进入考试系统的主界面。（2）在线考试模块考生进入考试系统的主界面以后，可以选择进行考试。系统按照遗传算法，从数据库中读取数据，生成试卷。考生在规定时间内进行考试，可提前交卷，也可在规定时间结束时自动提交试卷。（3）成绩查阅模块：考生可登陆主界面对考试的成绩进行查询。（4）个人信息维护模块图4-4教师子系统功能结构管理员为考生分配的密码一般是一致的，考生可以在密码修改模块里对密码进行修改。教师子系统共

61、包括五个模块，学生管理、试题管理、通知管理、信息维护和试卷管理，其中试卷管理是教师子系统所独有的，体现了教师在本系统的独特地位。教师子系统：其功能结构如图4-4所示。教师按照分配的用户名和密码进入系统后，通过试题管理信息模块对试题库进行维护，可以对试题进行增加、删除、修改和查询；通过组卷管理模块，按照一定区分度和难度的约束条件，利用遗传算法进行自动组卷；通过考试结果管理模块，教师可以查询学生的考试成绩，从而对试卷进行评价；通过个人信息维护模块，教师可以修改管理员分配的密码，保证个人信息和考试信息的安全性。管理员子系统：其功能结构如图4-5所示。图4-5理员子系统功能结构管理员在本系统中拥有最高的权限，管理员通过通知管理模块、学生信息管理模块、教师信息管理模块，实现对通知信息、学生信息、教师信息的增加、删除、修改和查询，通过系统维护模块进行维护。4.5系统数据库设计数据库的设计是根据对用户需求及系统功能要求分析的基础上的进行设计的，主要由一些常用的表组成。4.5.1用户信息表登陆系统的用户