论文部分内容阅读
摘 要：互联网已经成为21世纪最重要的信息交互平台，更多的终端设备如计算机、智能手机、平板电脑等都可入网，传统以纸质试卷为主的考试手段费时耗力，其劣势逐渐显现，那么就需要新的考试平台来分享互联网平台高速发展带来的成果。随着教育信息化的不断普及，利用先进的网络和计算机技术，网络考试系统自然得到长足发展。而网络考试系统中最重要的环节就是利用遗传算法进行自动组卷。网络考试系统中数据库平台的设计是否适合遗传算法的实际需要，并且同时要保证数据的独立性、完整性和高共享性，值得我们去探讨。
关键词：网络考试系统；组卷；遗传算法（GA）；数据库设计
中图分类号：TP311.52
1 遗传算法的简单介绍
遗传算法（Genetic Algorithm，缩写为GA）是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它能够模拟生命进化机制进行并行、智能全局随机搜索。遗传算法可以使用简明的代码和“繁殖机制”进行说明繁杂的情况，不会影响对具体问题的阐述，比较适合使用到那些其它搜索方法难于解决的繁杂及优化组合问题。遗传算法的主要应用领域如下图1：
图1
2 遗传算法的进化过程
在自然界中，经过染色体间的交叉和变异，促进了生物进化，与之相类似，遗传编程算法是通过遗传算子间的选择、交叉和变异操作来达到实现最优解的搜索过程。经过实际操作，一个新群体G（t+1）就会通过遗传从老群体G（t）继承相关属性优化生成。具体步骤如下：
2.1 编码。解决遗传算法组卷的首要问题是编码，利用编码将问题的解空间映射到GA算法的编码空间。说简单点，是对遗传算法的搜索目标的表示。遗传算法的特长就是，可对问题可行解的个体编码进行选择、交叉、变异的遗传运算。最终达到最优化结果。编码的不同形式对遗传动作的操作效率有着直接的影响。现在用的比较多的是分段整数编码方案，也就是说，把一类相似题归为一个段，每类型段的编码是独立的，每种题型只能在本编码段进行遗传操作，这样就形成了以题号作为基因组成染色体用于分段整数编码的遗传算法，没有编码和解码的情况，可以很大程度上降低了搜索的复杂度，提高了目标卷的生成效率。另一种是采用传统的二进制编码，虽然存在时间复杂度大，编码和编码过程复杂，并容易出现早熟等问题，但它有操作简单、易于实现的等优点。具体来说，一份试卷看作一个染色体，该染色体由多个试题基因组成。试题的数量就是该试卷的染色体的长度。
2.2 初始化种群。要求从试题库中选出符合条件的试题组成的种群的过程就是种群初始化，亦即染色体初始化。种群的大小一般是靠经验和估值来定，合理设置种群规模的大小，能够充分体现遗传算法的优点所在。如果种群过少，表示的样本就越少，就不能搜索到很精确的解，很可能就不能满足实际需求。所以，种群规模也要合理设置，找到一个平衡点。
2.3 染色体适应值计算。染色体初始化后，要进行评估和计算，即看看这些染色体是否达到目标要求。我们可以先利用计算公式2-1得到个体的适应度 （适应度大小可以区分群体中个体的优劣），最终得到终卷指标 。
（式2-1）
对于我们组卷过程来说，选用合适的适应度函数来判断某试卷染色体是否已经满足用户的需求，具体参数一般为：总分值，难易度，知识点覆盖率等，如果试卷个体的适应度函数值较大，表示试卷个体接近组卷目标。
2.4 选择（selection）操作。根据个体适应度值，按照要求，把迭代多次的优良个体向下一代群体遗传。
2.5 交叉（crossover）操作。為了得到更多优质的遗传个体，就把每个个体随机组合，以一定的交叉概率进行交换部分染色体，会形成新的优良个体。
2.6 变异（mutation）操作。同样为了得到更多优质的遗传个体，以一定的变异概率改变某个体的部分基因位的值就完成了变异。
总的来说，遗传算法的过程是先对群体初始化；然后，迭代未结束前对染色体进行适应值得评估和计算、选择、交叉以及变异，最后生成新的高质量的染色体群体，完成遗传操作过程。
3 数据库设计
自动组卷过程中，遗传算法的首要任务是对染色体编码，试题就是基因，当题库的试题越多，组卷操作时间和空间复杂度就越高。试题库的属性越多，组卷难度更高，运行效率就相对低。所以数据库的最终设计是否满足和适应遗传算法的需要，就要充分考虑到平衡度的把握，尽量精简试题记录数量，合理控制试题属性个数。具体设计准则如下：
3.1 数据库设计说明书和命名规范。精细制作数据库设计说明书，进一步强化命名规范。在数据字典设计中反映出数据库相关的各种标识。
3.2 数据库建模。实体关系中，建模中数据的整合方式一般有三种，即以属性聚集的方式、面向对象抽象属性和贴源方式。在考试系统中建议采用以属性聚集方式来建模，其优点为稳定性好、减少大量的数据冗余。
（1）实体关系的建立。如果题库由多种题型组成，在建立关系的时候，一类试题就对应一个关系，并且主、客试题分开。这样可以避免出现大量重复的属性。提炼核心属性，一般的考试系统常见核心属性有：题号、题目内容、所属课程编号、知识点、难度系数、分值等。（2）试题库的建立。建议按照试题类型独立建立试卷题库，在生成试卷过程中，采用分步完成，如依次生成单选题T1、多选题T2、程序改错题T3、简单题T4和综合题T5，最后进行组合T=T1+T2+T3+T4+T5。这样一份完整的目标卷就可以得到。
4 结束语
经过实践经验和跟踪测试，按照此原则设计的数据库，在遗传算法的操作过程中表现稳定，生成目标卷的成功率和时间效率大大提高。
参考文献：
[1]贾兆红.一种基于混合遗传算法的聚类方法[J].计算机应用软件，2008，25（4）：82-85.
[2]William A shay.Understanding Data Communications and Networks[M].Physician Law Weekly，2005，5（3）：226-228.
[3]贾海龙.智能组卷考试系统的研究与实现[D].北京工业大学，2010.
[4]陆亿红，柳红.基于整数编码和自适应遗传算法的自动组卷[J].计算机工程，2005（12）：1-3.
作者简介：程开固（1975.11-），男，实验师，硕士，从事计算机方面实践实习教学多年；潘慧（1979.1-），女，实验师，硕士，从事计算机方面实践实习教学多年。
作者单位：武昌理工学院，武汉 430223
关键词：网络考试系统；组卷；遗传算法（GA）；数据库设计
中图分类号：TP311.52
1 遗传算法的简单介绍
遗传算法（Genetic Algorithm，缩写为GA）是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它能够模拟生命进化机制进行并行、智能全局随机搜索。遗传算法可以使用简明的代码和“繁殖机制”进行说明繁杂的情况，不会影响对具体问题的阐述，比较适合使用到那些其它搜索方法难于解决的繁杂及优化组合问题。遗传算法的主要应用领域如下图1：
图1
2 遗传算法的进化过程
在自然界中，经过染色体间的交叉和变异，促进了生物进化，与之相类似，遗传编程算法是通过遗传算子间的选择、交叉和变异操作来达到实现最优解的搜索过程。经过实际操作，一个新群体G（t+1）就会通过遗传从老群体G（t）继承相关属性优化生成。具体步骤如下：
2.1 编码。解决遗传算法组卷的首要问题是编码，利用编码将问题的解空间映射到GA算法的编码空间。说简单点，是对遗传算法的搜索目标的表示。遗传算法的特长就是，可对问题可行解的个体编码进行选择、交叉、变异的遗传运算。最终达到最优化结果。编码的不同形式对遗传动作的操作效率有着直接的影响。现在用的比较多的是分段整数编码方案，也就是说，把一类相似题归为一个段，每类型段的编码是独立的，每种题型只能在本编码段进行遗传操作，这样就形成了以题号作为基因组成染色体用于分段整数编码的遗传算法，没有编码和解码的情况，可以很大程度上降低了搜索的复杂度，提高了目标卷的生成效率。另一种是采用传统的二进制编码，虽然存在时间复杂度大，编码和编码过程复杂，并容易出现早熟等问题，但它有操作简单、易于实现的等优点。具体来说，一份试卷看作一个染色体，该染色体由多个试题基因组成。试题的数量就是该试卷的染色体的长度。
2.2 初始化种群。要求从试题库中选出符合条件的试题组成的种群的过程就是种群初始化，亦即染色体初始化。种群的大小一般是靠经验和估值来定，合理设置种群规模的大小，能够充分体现遗传算法的优点所在。如果种群过少，表示的样本就越少，就不能搜索到很精确的解，很可能就不能满足实际需求。所以，种群规模也要合理设置，找到一个平衡点。
2.3 染色体适应值计算。染色体初始化后，要进行评估和计算，即看看这些染色体是否达到目标要求。我们可以先利用计算公式2-1得到个体的适应度 （适应度大小可以区分群体中个体的优劣），最终得到终卷指标 。
（式2-1）
对于我们组卷过程来说，选用合适的适应度函数来判断某试卷染色体是否已经满足用户的需求，具体参数一般为：总分值，难易度，知识点覆盖率等，如果试卷个体的适应度函数值较大，表示试卷个体接近组卷目标。
2.4 选择（selection）操作。根据个体适应度值，按照要求，把迭代多次的优良个体向下一代群体遗传。
2.5 交叉（crossover）操作。為了得到更多优质的遗传个体，就把每个个体随机组合，以一定的交叉概率进行交换部分染色体，会形成新的优良个体。
2.6 变异（mutation）操作。同样为了得到更多优质的遗传个体，以一定的变异概率改变某个体的部分基因位的值就完成了变异。
总的来说，遗传算法的过程是先对群体初始化；然后，迭代未结束前对染色体进行适应值得评估和计算、选择、交叉以及变异，最后生成新的高质量的染色体群体，完成遗传操作过程。
3 数据库设计
自动组卷过程中，遗传算法的首要任务是对染色体编码，试题就是基因，当题库的试题越多，组卷操作时间和空间复杂度就越高。试题库的属性越多，组卷难度更高，运行效率就相对低。所以数据库的最终设计是否满足和适应遗传算法的需要，就要充分考虑到平衡度的把握，尽量精简试题记录数量，合理控制试题属性个数。具体设计准则如下：
3.1 数据库设计说明书和命名规范。精细制作数据库设计说明书，进一步强化命名规范。在数据字典设计中反映出数据库相关的各种标识。
3.2 数据库建模。实体关系中，建模中数据的整合方式一般有三种，即以属性聚集的方式、面向对象抽象属性和贴源方式。在考试系统中建议采用以属性聚集方式来建模，其优点为稳定性好、减少大量的数据冗余。
（1）实体关系的建立。如果题库由多种题型组成，在建立关系的时候，一类试题就对应一个关系，并且主、客试题分开。这样可以避免出现大量重复的属性。提炼核心属性，一般的考试系统常见核心属性有：题号、题目内容、所属课程编号、知识点、难度系数、分值等。（2）试题库的建立。建议按照试题类型独立建立试卷题库，在生成试卷过程中，采用分步完成，如依次生成单选题T1、多选题T2、程序改错题T3、简单题T4和综合题T5，最后进行组合T=T1+T2+T3+T4+T5。这样一份完整的目标卷就可以得到。
4 结束语
经过实践经验和跟踪测试，按照此原则设计的数据库，在遗传算法的操作过程中表现稳定，生成目标卷的成功率和时间效率大大提高。
参考文献：
[1]贾兆红.一种基于混合遗传算法的聚类方法[J].计算机应用软件，2008，25（4）：82-85.
[2]William A shay.Understanding Data Communications and Networks[M].Physician Law Weekly，2005，5（3）：226-228.
[3]贾海龙.智能组卷考试系统的研究与实现[D].北京工业大学，2010.
[4]陆亿红，柳红.基于整数编码和自适应遗传算法的自动组卷[J].计算机工程，2005（12）：1-3.
作者简介：程开固（1975.11-），男，实验师，硕士，从事计算机方面实践实习教学多年；潘慧（1979.1-），女，实验师，硕士，从事计算机方面实践实习教学多年。
作者单位：武昌理工学院，武汉 430223