基于遗传算法的题库自动组卷问题的研究(ASP.NET2.0)

摘  要
伴随着科技的发展和进步，网络已经渐渐地走进了大众生活，远程教育、在线考试等词汇也成了人们日常生活的口头禅。和传统的教育相比，考试成了网络教育者们最头疼的一件事。于是，如何能在考试时间、难度等考试要求相同的情况下，在短时间内，得出大量差别较大的等效试卷，便成了一项迫在眉睫的任务。
本文分析了考试及其作业练习中自动组卷的作用、方法，并利用SQL SERVER 2000建立安全、有效、小冗余、访问方便的数据库，实现了按照一定的自动组卷算法能够自动的生成平时作业。从试题库的组成及随机选题自动组卷数学模型的方向,详细论述了试题库自动组卷系统的研制方法、主要内容和关键技术的实现。在比较了比较普遍的3种组卷算法基础上，针对平时作业组卷生成这一具体任务，选择了随机组卷算法。
 此系统预期包含题库管理，组卷管理两个功能模块。在题库管理模块，我们会实现对题库的管理功能，包括添加新的试题、修改已有的试题、删除某道试题、以及题型分数的修改等等。在组卷管理模块，当用户输入试卷的相关信息例如试题的数目、覆盖得内容、分数、试卷难度和试卷的表头等信息后，根据用户的输入，利用遗传算法从题库里选择出对应的一套最符合用户需求的试卷，并将此试卷显示在屏幕上。

关键词：遗传算法，多目标优化，智能组卷，自动组卷，试题库  

The study of the automatic Test paper generation of the examination data system based on Genetic algorithms
Abstract
Along with the development of technology, the Internet has come into the life of general people. Remote education, test online and some other new words always appear when people talking with each other. Compared with traditional education, the test has become the hardest thing to the educators. So in case of the time of test, the difficulty of test paper and other conditions are the same, how to make a lot of different test papers has become an important thing.
In this paper, the usages and the methods of automatic test paper generation in examination and exercises were analyzed. Furthermore, this paper applied SQL SERVER 2000 to establish safely, effective, minor redundant and efficient access of the databases, which made automatically creation of the assignment by certain automatic test paper generation. What's more, this paper disgusted the realization of the manufacture method, main content and key technology of automatic test paper generation system. The discussion was made from the aspects of the organization of the examination database system and the randomized automatic test paper generation of mathematical models. Based on the comparison of the three common test paper generation methods, we chose randomized algorithms.
 This system will include two functional modules: the question bank management and the Test paper auto-generation management. In the first module, we will implement question bank management including adding a new question to the bank, changing the question, deleting a question and changing the score of the type of questions. In the second module, we will implement the test paper auto-generation management. After the user input the relating information about the test paper, including the account of questions, the content covered, the total score of the test, the difficulty distribution of the test paper and the name of the paper and some other information about the test paper, according to the input of the user, a test paper will come out which get questions from the question bank with genetic algorithms, and it will show on the screen

Key words: genetic algorithms, Multi-objective optimizations, Test paper auto-generation,   automatic test paper generation, the examination database system

遗传算法的基本思想
 遗传算法是从代表问题可能潜在解集的一个种群开始的。而一个种群则由经过基因编码的一定数目的个体组成，每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的组合，其内部表现是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征时候染色体中控制这一特征的某个基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更适应于环境，末代种群中的最优个体经过解码，可以作为近似最优解。
遗传算法采纳了自然计划模型，如选择、交叉、变异、迁移、局域和邻域等。计算开始时，一定数目N个个体（父个体1，……父个体N）即种群随机的初始化，并计算每个个体的适应度函数，第一代也即初始代就产生了，如果不满足优化准则，开始产生新一代的计算。为了产生下一代，按照适应度选择个体，父代要求基因重组（交叉）而产生子代。所有的子代按一定的概率变异。然后子代的适应度又被重新计算，子代被插入到种群众将父代取而代之，构成新的一代（子个体1，子个体2，…子个体N），这一过程循环执行，直到满足优化准则为止。

系统架构设计
本系统采用vision studio 2005 和sql server 2000进行开发。使用asp.net技术构筑了B/S架构构建三层浏览器/服务器体系结构。
在B/S三层体系结构下，表示层、功能层、数据层被分割成三个独立的单元。
第一层表示层:Web浏览器。在表示层中包含系统的显示逻辑。Web浏览器向网络上的某一Web服务器提出服务请求，Web服务器对用户身份进行验证后用HTTP（超文本传输协议）协议把所需的主页传递给客户端，客户端接收传送的数据，并把它显示在Web浏览器上。
第二层功能层:具有应用程序扩展功能的Web服务器。在功能层中包含系统的事务处理逻辑，位于 Web服务器端。它的任务是响应用户的请求，首先需要执行相应的扩展应用程序与数据库进行连接，向数据库服务器提出数据处理申请，而后数据库将数据处理的结果提交给Web服务器后，再由Web服务器传送回客户端。
 第三层数据层:数据库服务器。在数据层中包含系统的数据处理逻辑，它的任务是接受Web服务器对数据库操纵的请求，实现对数据库查询、修改、更新等功能并把运行结果提交给Web服务器。
 由此可见，原来两层的C/S结构转变成三层的B/S结构后，客户机的压力大大减轻了，把负荷均衡地分配给了Web服务器。这种结构不仅把客户机从沉重的负担和不断地提高性能的要求中解放出来，而且把技术维护人员从繁重地升级维护工作中释放出来。由于客户机把事务处理逻辑部分分给了功能服务器，不再负责处理复杂计算和数据访问等关键事务，只负责显示部分，使客户机一下子“苗条”了许多，所以维护人员不再为程序的维护工作奔波于每个客户机之间，而把主要精力放在功能服务器上程序的更新工作。这种三层体系结构层与层之间相互独立，任何一层的改变不影响其他层的功能。它从根本上改变了传统的两层C/S体系结构的缺陷，它是应用系统体系结构中一次深刻的变革。

系统模块设计
本系统采用模块化程序设计思想。模块化程序设计是进行大规模程序设计的有效措施，其基本思想是将一个程序按功能分割成一些模块，使每一个模块都成为功能单一、结构清晰、接口简单、容易理解的小程序。主要包含题库管理和组卷管理两个模块。
1、题库管理模块：此模块主要用来对题库进行管理。主要包括对新题目的添加，原有题目的修改、删除以及题型分数的修改。当添加新题目时，添加试题描述，选择题型、平均答题时间、所考察的考查点的能力层次要求（主要包括理解、掌握、会用和了解）以及难易程度（容易、中等、较难和很难四类）进行添加。其他功能在此不再赘述。
2、组卷管理模块：此模块是此系统的核心，主要是根据遗传算法从题库里选择出满足用户需求的试卷。系统组卷时要求用户输入考试时间、试卷头、试卷分数、各种类型的试题的数目、各个能力层次的试题所占的百分比和各个难度的试题所占的百分比等组卷条件进行组卷。