PBIL进化算法在考试系统中的应用

高 俊

（江西冶金职业技术学院 江西 新余 338000）

0 引言

随着计算机应用的迅猛发展，人们迫切要求利用现代信息技术来进行在线考试。在线考试系统极大地提高了教学的灵活性，它在许多领域已经有了广泛的应用。现阶段在线考试系统种类繁多，但目前已有的网上考试系统题型单一，没有真正通用的集自动组卷、在线答卷、自动评卷、成绩管理与统计分析、题库管理、用户管理、记录查询、在线审批于一体的综合考试系统，为了积极适应新形势的发展和信息网络化的发展趋势，科学有效地利用信息网络的资源和技术优势，开发一个在线考试系统是非常必要和可行的。

1 国内外研究现状

目前大多数考试系统的系统结构：比较流行的是C/S结构和B/S结构。

C/S结构，即Client/Server(客户机/服务器)结构。它通过将任务合理分配到Client端和Server端，降低了系统的通讯开销。这种结构的考试系统要求在服务器和客户端单机上都安装考试应用软件，客户端软件具有考题的显示，考试计时及与服务器通信联络等功能。服务器端软件则负责维护题库、抽取试题及考后的阅卷、成绩的收取、统计、汇总等工作。考生在单机上参加考试，考试结果被系统收集到服务器中的指定目录下。

B/S结构，即Browser/Server(浏览器／服务器)结构。该结构的核心是WEB服务器，它负责接收浏览器的WEB页请求和数据请求，并处理WEB页请求，同时将数据请求通过数据库接口程序转换成数据库服务器能够接受的形式，之后送到数据库服务器，数据库服务器执行相应的数据库操作，并将结果通过数据库接口程序的转换送回WEB服务器，WEB服务器将结果处理成浏览器能够接受的形式后，送回发出请求的浏览器，显示结果。

2 基于PBIL进化算法组卷

2.1 算法的原理

PBIL算法基本原理[2]：设定S代表解的二进制编码，其长度为N，第 i个基因位 si(1≤i≤N)的取值为 0 或 1，P＝(p1,p2,p3,……,pn)代表一个N维的概率向量(Probability Victor)，向量中各元素表示当前种群中的个体在对应基因位上不同取值时的学习概率；对于二进制编码的情况，pi(1≤i≤N)代表第i个基因位取值为1时的学习概率；r是算法的学习速率(Learning Rate)，M是种群规模。初始概率Pini中学习概率pi，大小都为0.5，即各基因位上取值为0或1的机会均等。

为了防止学习概率过早地收敛到0或1附近而产生早熟现象，在每一代对学习概率修正后，再按变异率P随机地选择部分学习概率pi进行调整，rm是变异速率(Mutate shift)。算法的处理流程[2]如下：

1）初始化学习概率 P：pi=0.5(1≤i≤N)；

2）由学习概率P指导随机产生M个个体；

3）计算机由2）产生的M个个体的目标函数值；

4）根据3）计算的目标函数值找出其中一个最优解：fitness；

5）用4）找到的最优解fitness修正学习概率P，修正方法如下：

pi=pi+(fitnessi-pi)×δ(δ 为修正常数，1≤i≤N)；

6）对P进行变异操作；

7）返回2），直到满足结束条件为止。

2.2 试卷结构分析

一份试卷一般涉及到总分、试题类型、试题类型分值、难度系数、各知识点分数分布等因素。以《C语言程序设计》为例，试题类型可分为填空题、选择题、程序填空题、写出程序运行结果和编程题。一般将难度划分为个4个等级(1,2,3,4级)。组卷算法就在以下几个方面尽可能接近目标值：

（1）试卷的总分应等于用户设定的总分，即：

其中n为试卷的题目总数，yi为第i个题目的分数，M为用户设定的试卷总分。

（2）各题型的总分之和应等于试卷的总分，即：

其中n为题型的总数，fi为第i个题型的分值，F为用户设定的试卷总分。

（3）试卷中同类知识点分数之和应等于用户要求的分数，即：

其中n为第k个知识点在试卷中的题目数量，zi为第k个知识点第i个题目的分数，Zk为用户设定的第k个知识点的分数，m为知识点的个数。

（4）各题型的分数应等于用户设定的分数，即：

其中n为第j个题型的题目总数，li为第j个题型中第i个题目的分数，Lk为用户设定的第k个题型的分数，m为题型总数。

（5）各题型的难度系数应等于用户设定的难度系数，即：

其中n为第j个题型的题目总数，si为第j个题型中第i个题目的难度系数，fi为对应的分值，Sk为用户设定的第k个题型的难度，m为题型总数。

2.3 目标函数

现用指标x1,x2,x3,x4,x5分别表示上述5项目标值。则可知，当x1,x2,x3,x4,x5越大时，说明目标值与用户要求的值相差越大；当x1,x2,x3,x4,x5越小时，说明目标值与用户要求的值相差越小；当x1,x2,x3,x4,x5等于0时，说明目标值与用户要求的值相等。再设各项指标的权重为：d1,d2,d3,d4,d5，它们反映对上述各项指示的重要程度。所以 f=x1×d1+x2×d2+x3×d3+x4×d4+x5×d5表示整份试卷所有指示与用户要求的指示的相差程度。

下面定义各项指示的目标函数：

其中n为题目总分，yi为第i个题目的分数，M为用户设定的试卷总分a表示算法生成的最大误差。

其中n为题型的道数，fi为第i个题型的分值，F为用户设定的试卷总分，b表示算法生成题型的最大误差。

其中m为知识点的个数，n为第k个知识点在试卷中的题目数量，zi为第k个知识点在第i个题目的分数，Zk为设定的第k个知识点的分数，c表示算法生成的每个知识点分数的最大误差之和。

其中m为总题型数，n为第j个题型的题目总数，li为第j个题型中第i个题目的分数，Lj为设定的第j个题型的分数，d表示算法生成的每个题型分数的最大误差之和。

其中m为总题型数，n为第j个题型的题目总数，si为第j个题型中第i个题目的难度系数，fi为对应的分值，Sj为设定的第j个题型的难度，e表示算法生成的每个题型难度系数的最大误差之和。综上所述，对于一个有M个个体，则总体目标函数表示为：

其中，i∈[1,M]，M为种群规模，x1,x2,x3,x4,x5由以上目标函数决定，d1,d2,d3,d4,d5为该项指标的权重因子。

2.4 组卷实现

题库中可以选取的试题的数量作为基因链的长度L，编码方式采用二进制编码方式。现假设题库中有N道各种题型的试题，则L的长度就等于N，Li等于0时表示题库中第i题未选中，Li等于1时表示题库中第i题选中，其中1≤i≤N。

算法实现如下：

3 结束语

本设计是以《C语言程序设计》为例，介绍了PBIL进化算法在考试系统中的应用。实现的考试可以加强规范性，提高质量，减少组织考试工作的工作量，简化工作手续。

［1］张小艳,龚尚福.ASP技术在网上考试系统中的应用[J].西安科技学院学报,2002,22(l):53-55.

［2］Baluja S.Genetic Algorithms and Explicit Search Statistics.In:IEEE.Advances in Neural Information Processing System.MA:MIT Press.

［3］曹丽文,杨静.“基础工程与施工”网上考试系统的开发与实现[J].中国地质教育,2005（2）:32-34.

［4］吉根林,崔海源.ASP.NET程序设计教程[M].北京:电子工业出版福,2004.

［5］胡勇辉,扶玉坤,张阳戬.ASP.NET基础教程与上机指导[M].北京:清华大学出版社,2005.

［5］周红晓.遗传算法在试题库智能组卷中的应用[J].浙江师范大学学报：自然科版,2003,26(4):374-378.

［6］楼玉萍,金炳尧,骆红波.PBIL进化算法在自动组卷系统中的应用[J].计算机技术与发展,2006,16(6):81-82.

［7］袁锋.遗传算法在自动组卷系统中的应用[J].山东师范大学学报：自然科学版,2006,21(1):53-56.

［8］刘卫忠,徐重阳,蔷薇.多层客户机/服务器结构分析[J].华中理工大学学报：自然科学版,2000,1.