基于遗传算法实现自动组卷的数据库设计思路

1 遗传算法的起源

遗传算法 (Genetic Algorithm, 缩写为GA) 是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holland教授提出, 起源于60年代对自然和人工自适应系统的研究。在一系列研究工作的基础上, 80年代Goldberg归纳总结, 形成了遗传算法的基本框架。

2 遗传算法的实现步骤

生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。与此相对应, 遗传算法中最优解的搜索过程也模仿生物的这个进化过程, 使用所谓的遗传算子作用于群体P (t) 中进行选择、交叉和变异三种遗传操作, 从而得到新一代群体P (t+1) 。具体地, 算法的实现步骤有如下几点。

2.1 编码

在遗传算法中如何描述问题的可行解, 即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。遗传算法最重要的特点就在于它对表示可行解的个体编码施加选择、交叉、变异等遗传运算, 通过这种遗传操作来达到优化的目的。

基本遗传算法使用固定长度的二进制符号串来表示群体中的个体, 其等位基因是由二进值符号集{0, 1}所组成的。对于电子考试系统而言, 某份试卷可以被视为一个染色体, 该染色体由一个个的试题基因组成。对于任何一个试题而言, 它与某份试卷的关系只有两种状态:其一, 被包含在其中 (记为“1”) ;其二, 未被包含在其中 (记为“0”) 。所以解码时只要看题目对应的标记值即可判定一份试卷包含了哪些题目。同时我们也可以看出, 每份试卷染色体的长度均为试题库中试题记录的数量。

2.2 初始化

在算法执行的过程中, 首次根据组卷要求从试题库中选出试题组成试卷染色体的过程被称为染色体初始化。试卷初始种群往往是采用随机的方法产生。

2.3 评估染色体

任何一个染色体个体诞生后, 我们都要看其对环境的适应度是否已经达到拟定的目标值, 或者判断二者之间的差距是否已经达到最小, 这个过程被称为评估。对于组卷问题而言, 我们要选用合适的适应度函数来判断某试卷染色体是否已经满足用户的需求, 如总分值是否达到要求, 难易度是否合适, 知识点覆盖率如何等。如果试卷个体的适应度函数值较大, 就表示试卷个体接近组卷目标。

2.4 选择 (selection)

选择指的是根据各个个体的适应度按照一定的规则或方法, 从第n代群体中选择出一些优良的个体遗传到下一代群体中。

2.5 交叉 (crossover)

将群体内的各个体随机成对组合, 对每一对个体, 以某个概率 (称为交叉概率crossover rate) 交换它们之间的部分染色体的过程即是交叉。

2.6 变异 (mutation)

对群体中的每一个个体, 以某一概率 (称为变异概率, mutation rate) 改变某一个或某一些基因座上的基因值为其他的等位基因的过程即是变异。

综上所述, 遗传算法运算流程即是首先初始化染色体群体;其次, 在不满足迭代结束条件的前提下对染色体进行评估、选择、交叉以及变异进而生成新的优良的染色体群体。

3 数据库设计思路

据前所述, 在基于遗传算法实现自动组卷的过程中, 第一步也是最重要最基本的一步就是对染色体进行编码。在编码时, 由于试题充当生物学当中基因的角色, 致使试题库中试题记录越多, 在自动组卷时其时间复杂度就越高。试题库中的属性越多, 组卷的难度越高, 以致效率就越低。基于这一考虑, 在设计数据库时, 要一方面尽可能减少试题库中对应的试题记录的数量;另一方面, 在满足科学组卷的需要的前提下, 以教育学理论为指导, 合理地控制试题属性的数量。具体思路有如下几点。

3.1 按试题类型分解题库, 一类试题对应一张表

主观试题与客观试题分开, 这样可以避免一张表中存放所有试题。另外, 如果所有类型的试题都存储在一个表中, 还需要增加“试题类型”属性, 分开处理有利于减少属性, 进而提高算法的执行效率。

3.2 提炼试题中最重要的核心属性

根据经验, 最重要的核心属性可以归纳为如下几个。

(1) 题号。用来唯一标识试题。

(2) 题目内容。试题的问题描述。

(3) 所属课程编号。该试题属于哪门课程。

(4) 知识点。某道题属于某门课程的哪个知识点。

(5) 难度系数。用未通过率来表示。

(6) 分值。某题分数。

3.3 按照试题类型分别设计试卷库

试卷库指的是由相关试题组合而成的一系列试卷。由于试题已经过分类处理, 所以在组卷时, 必然要根据试题类型分步实现试卷的生成。比如, 在生成一份完整的试卷时, 要首先从主观试题中选择合适的题目生成对应的主观试卷P1, 然后再从客观试题中选择相应的题目生成对应的客观试卷P2, 最后再由P1和P2组合成一份完整的试卷P。

4 结语

根据分析, 该思路设计下的数据库与不经过任何处理的试题数据库相比, 在用遗传算法实现自动组卷时效率可以提高大约一倍, 达到了数据存储与算法有效结合的设计目的。

摘要：当前为了减轻阅卷人员的工作量, 提高其工作效率, 许多考试都在使用电子考试系统。而电子考试系统中大部分都涉及到了由计算机自动组卷的操作。所谓自动组卷, 就是根据用户的要求, 采用一定的算法自动地从试题库中抽取一定数量的试题组成试卷。遗传算法是一种并行优化算法, 它很适合解决自动组卷问题。同时, 为了保持系统数据的整体性、完整性和共享性, 考试系统毫无例外地得依靠数据库平台的支持。那么如何使得数据库尽可能地适应算法的需要就成了一个值得考虑的问题。

关键词：遗传算法 (GA) ,组卷,数据库,试题

参考文献

[1] 王珊, 陈红.数据库系统原理教程[M].北京:清华大学出版社, 2003.

[2] 文海英.智能型试卷自动生成系统中试卷难度控制技术的研究[J].湖南科技学院学报, 2005, 26 (5) :153～156.

[3] 常振江.学生成绩分布与一种简便的评估试卷命题质量的方法[J].辽宁师范大学学报 (自然科学版) , 2003, 26 (1) :109～112.

[4] 魏平, 张元.一种求解组卷问题的遗传算法[J].宁波大学学报 (理工版) , 2002, l5 (2) :47～50.

[5] 王淑佩, 易叶青.基于改进自适应遗传算法的组卷研究[J].科学技术与工程, 2006, 6 (4) :468～473.