刘学丰

(渤海大学，辽宁 锦州 121013)

基于差分进化算法的英语考试智能组卷

刘学丰

(渤海大学，辽宁 锦州 121013)

为保证英语大规模标准化考试质量要求和信息化建设的需要，针对传统组卷算法存在的问题，基于差分进化算法展开研究。首先，在阐明影响试卷质量指标的基础上，构建了组卷算法数学模型；然后，研究差分进化算法模型，主要针对变异、交叉和选择三种操作；最后，以组卷算法和差分进化算法模型为基础，绘制了差分进化算法智能组卷程序流程图，并对主要步骤进行了说明。差分进化算法具有原理简单、受控参数少、鲁棒性强、收敛性和稳定性好等特点，依据文中研究内容可以快速构建适合于大学英语教学和考试的智能组卷系统。

差分进化算法；英语考试；智能组卷；程序流程

0 引 言

目前的大学英语教学是以《大学英语教学大纲》为基础，考试内容及题型主要围绕《大学英语四级考试大纲》进行。大学英语考试是大学英语教育的重要组成部分，目的是对大学生实际英语能力进行客观、准确的测量，为大学英语教学提供服务。大学英语考试也是一项大规模标准化考试，为了提高考试成绩，必须保证试卷质量，在设计上必须满足教育测量理论对大规模标准化考试的质量要求。生成试卷速度慢、质量不高是传统组卷算法的主要缺点，已越来越不适应教育信息化的需要[1-2]。

智能组卷是利用人工智能技术，由计算机自动从试题库中选择试题，组成符合要求的试卷，是考试系统智能化或半智能化操作的核心目标之一，是计算机辅助教学的重要组成部分[3]。智能组卷的效率与质量主要取决于组卷算法。如何设计算法从题库中既快又好地抽出一组最符合考试要求的试题，是全局寻优和快速收敛问题。差分进化算法(Differential Evolution，DE)是基于群体智能的随机并行优化算法，遵循达尔文的“适者生存、优胜劣汰”的进化原则[4-5]。特有的记忆能力使其可以动态跟踪当前的搜索情况，以调整搜索策略，实现自适应寻优，因此具有较强的全局收敛性和鲁棒性，能够求解利用常规的数学规划方法所无法求解的复杂环境中的优化问题，非常适宜处理试题库智能组卷[6]。文中基于差分进化算法研究英语考试智能组卷问题，为软件系统开发提供支持。

1 组卷算法数学模型

智能组卷的过程就是通过辨识问题中变量之间的关系而把实际问题转化为由数学模型并运用计算机求解的过程，组卷质量依赖于数学模型。因此，建立数学模型是智能组卷的基础性工作。

1.1 影响试卷质量的指标

根据经典测量理论(Classical Test Theory，CTT)，题库是按照一定的教育测量理论并利用计算机技术构成的某种学科题目的集合。智能组卷系统的试题来源于题库，题库中题目的质量直接影响组卷的质量，参照CTT的题目量化指标，将影响试卷质量的属性指标归纳为如下4个[7]：

(1)信度：反映考试结果的稳定程度，即考试结果的可信度。信度高说明考生分数不易受偶然性因素影响，考生分数可以比较真实地反映出考生的实际水平。影响信度的因素包括试题难度、题目数量、题目用语准确性等。

(2)效度：反映试卷的有效程度，即考试结果与预期要达到的考试目标相符合的程度。效度高的试卷，能够准确地测试出考生掌握或运用所学知识和技能的真实情况。提高效度要注意试题与考试目标以及课程标准的一致性。

(3)难度：反映试题或试卷考查学生知识和能力水平适合的程度。难度中等时分数呈正态分布；难度较大时呈负偏态分布；难度较小时呈正偏态分布。因为难度值要在考试结束后通过统计得到，因此，组卷时必须对难度做出比较准确的估计。

(4)区分度：反映试题对于不同层次考生的鉴别能力。区分度高的试卷能对不同知识水平和能力的学生加以区分，使能力强的学生得高分，能力弱的学生得低分。区分度和难度有着密切的关系，只有合适的难度才会有很好的区分度。

1.2 组卷数学模型描述

组织一份试卷时，要确定试卷的满分值、试题难度、试题数量、知识点分布以及考查的能力层次等参数指标。结合英语考试的实际情况，建立由9项核心属性的智能组卷数学模型，一份试卷的参数指标变成了一个9维空间向量，即：试题(试题编号，分值，难度系数，能力层次，知识点，题型，区分度，答题时间，使用频率)。一道试题由9个参数指标(属性)决定，即由一个9维向量空间(a1,a2,a3,a4,a5,a6,a7,a8,a9)的特征决定。

设一套有n道试题的试卷，可以用(n×9)的矩阵表示：

S=

(1)

式中各属性描述如下：

(1)试题编号。试题编号(a11,a21,…,an1)是试题的唯一标识，对计算机处理极为重要。根据四级试卷结构，试题编号由四位数字和代码构成[8]。第1位分别用“Ⅰ、Ⅱ、Ⅲ、Ⅳ”表示试卷的“PartⅠ、PartⅡ、PartⅢ、PartⅣ”部分；第2位分别用“A、B、C”表示PartⅡ和PartⅢ的“SectionA、SectionB、SectionC”部分，PartⅠ和PartⅣ部分用“N”补位；第3位和第4位用“01，02，03，…”等数字表示小题号，无小题号时用“00”补位。

(4)能力层次。《大学英语课程教学要求》将大学阶段的英语教学要求分为三个能力层次，即一般要求、较高要求和更高要求，每个能力层次有其对应的编码。ai4表示第i道试题的能力层次编码，所选择的试题应满足指定的能力层次要求。

(9)使用频率。ai9表示第i道试题单位时间内使用的次数，这里的单位时间可以是年，也可以是学期。如果使用频率较高，表明学生考过该题的可能性就大。因此，组卷初步完成后，要考察使用频率，将使用频率较高的试题替换掉。

2 差分进化算法模型

DE是基于实数编码的进化算法，与遗传算法的主要区别在变异操作，DE变异操作基于染色体的差异向量进行，其余操作则和遗传算法类似。差分进化算法主要是变异、交叉和选择三种操作，因此数学模型围绕三种操作构建[9]。

2.1 变异操作

变异操作是DE算法的重要操作，通过差分方式实现。基本方法是在当前种群中随机选取两个相异个体，将它们的差向量缩放后与另外的待变异个体进行向量运算，生成新个体[10-11]。

定义差分向量：

(2)

将差分向量加权后再加到第三个随机选取的个体向量上就形成了变异向量：

(3)

式中，F为缩放因子，是[0,2]区间上的一个实常数，用于控制差分向量的缩放程度。

2.2 交叉操作

(4)

2.3 选择操作

(5)

从式(5)可以看出，变异操作实际是将两个不同父代个体的差值加权后加到第三父代个体，从而得到一个新个体。因此，DE具有很好的几何意义。

3 智能组卷程序流程

组卷问题实质是多重约束条件的最优求解问题，满足条件的最优解不惟一。计算机智能组卷是以数学模型为基础进行软件开发。

基于差分进化算法的英语考试智能组卷程序流程如图1所示[13-14]。

图1 智能组卷程序流程图

对图1的各步骤描述如下[15-16]：

(1)初始化组卷参数。包括组卷算法数学模型的参数和DE算法参数。组卷算法数学模型的参数包括等难度系数、能力层次、知识点、题型、区分度、答题时间、使用频率等；DE算法参数包括种群的大小、最大迭代次数、变异算子、交叉算子等。

(6)

式中，rand[0,1]为[0,1]区间的均匀随机数。

(7)

式中，ck表示试题k；k表示试题编号。

(4)计算个体适应度值。适应度是以数值的方式来评估个体向量相对于整个群体的优劣程度的指标。适应度值的计算需要适应度函数，也称评价函数。DE算法的适应度函数不受连续可微的约束，可以任意设定区域，为了保证适应性能好的个体被选择的机会大，适应度函数的取值必须非负，设计尽可能简单，使计算的时间复杂度最小。

(5)判断是否满足算法终止条件。最大进化代数可作为DE的终止条件，还需要其他判定准则。一般当目标函数值小于阈值时程序终止，阈值常选为10-6；或者通过判断种群中的最优值连续若干代并没有明显变化时，也可以作为终止条件。

(6)差分进化操作。依据差分进化算法模型进行变异、交叉、选择操作。

4 结束语

智能组卷是大学英语考试自动化的核心工作，如何保证生成的试卷最大程度地满足考试需要，并具有随机性、科学性、合理性等特点是实现过程中的难点。DE算法通过变异算子来探索新解，利用交叉算子进行局部开发，利用贪婪选择策略进行保优，使种群向最优区域靠拢。与其他算法相比，具有基本原理简单、受控参数少、鲁棒性强、收敛性和稳定性好等特点。依据文中的研究内容可以快速构建适合于大学英语教学和考试的智能组卷系统。同时也必须注意，DE算法的理论基础还比较贫乏，为了使智能组卷系统更科学合理，扩展DE算法和其他算法相结合，是未来智能组卷算法的发展方向。

[1] 唐启涛.基于改进的遗传算法的智能组卷算法研究[J].计算机技术与发展,2014,24(12):241-244.

[2] 雷 茜，刘淳安．智能优化的英语试题库组卷策略研究[J]．科学技术与工程，2009，9(24):7500-7502.

[3]ZhangYJ,LiHB.Cluster-basedpopulationinitializationfordifferentialevolutionframeworks[J].ProcediaEnvironmentalSciences,2011,10(1):517-522.

[4] 郭 鹏.差分进化算法改进研究[D].天津:天津大学,2012.

[5] 张贵军，何洋军，郭海锋，等.基于广义凸下界估计的多模态差分进化算法[J].软件学报,2013,24(6):1177-1195.

[6] 百度文库.差分进化算法[EB/OL].2015-03-01.http://wenku.baidu.com/link?url=k9NS6nEw09MKfwhh5WhPd5VnFoLzkEqjJwxDsM67w2INu3VwhzmrhcfjEs3IM3F3R_fTXTTPoLTBiLNBZccE3l3MdP4QvdO_s7dRyVXgp9a.

[7] 衡量试卷的标准.衡量试卷质量的四大指标[EB/OL].2015-03-01.http://www.jxteacher.com/lcez/column72487/a2a4fff0-00bc-454c-baf9-005932658190.html.

[8] 马 宁.大学英语四级题型改革后英语学习策略探讨[J].读与写:教育教学刊,2012,9(1):21-22.

[9]PoikolainenI,NeriF,CaraffiniF.Cluster-basedpopulationinitializationfordifferentialevolutionframeworks[J].InformationSciences,2015,297(10):216-235.

[10] 王凤蕊，王文宏，潘全科.基于差分进化算法的智能组卷研究[J].计算机工程与设计,2009,30(8):1974-1976.

[11]AyalaHVH,dosSantosFM,MarianiVC,etal.Imagethresholdingsegmentationbasedonanovelbetadifferentialevolutionapproach[J].ExpertSystemswithApplications,2015,42(4):2136-2142.

[12] 刘淳安，赵天绪，黄梅娟.基于差分进化算法的智能组卷方法[J].计算机与数宇工程,2011,39(1):1-3.

[13]ZamudaA,BrestJ.Vectorizedproceduralmodelsforanimatedtreesreconstructionusingdifferentialevolution[J].InformationSciences,2014,278(10):1-21.

[14] 魏玉霞.差分进化算法的改进及其应用[D].广州：华南理工大学,2013.

[15]LuXiaofen,TangKe,SendhoffB.Anewself-adaptationschemefordifferentialevolution[J].Neurocomputing,2014,146(25):2-16.

[16]SharmaH,BansalJC,AryaKV.Selfbalanceddifferentialevolution[J].JournalofComputationalScience,2014,5(2):312-323.

[17] 孙成富，赵建洋，陈剑洪.差分进化算法马尔可夫链模型及收敛性分析[J].计算机技术与发展,2013,23(8):62-65.

Intelligent Test Paper Composition on English Examination Based on Differential Evolution Algorithm

LIU Xue-feng

(Bohai University,Jinzhou 121013,China)

In order to ensure the quality requirements of large-scale standardized tests in English and the needs of information construction,study is carried on based on differential evolution in the light of the problems in traditional test paper algorithm.First,a mathematical model of test paper algorithm was constructed after illustrating indicators effected papers’ quality.Then,the model of differential evolution was studied,especially for mutation,crossover and choice.Finally,the program flowchart of intelligent test paper composition based on differential evolution was drawn according to test paper algorithm and model of differential evolution algorithm,and the main steps were described.Differential evolution algorithm has many characteristics,such as simple in principle,less controlled parameters,strong robustness,good convergence and stability and so on.Intelligent test paper composition system for college English learning and test can be quickly built based on the content studied.

differential evolution;English examination;intelligent test paper composition;program flow

2015-03-08

2015-06-11

时间：2016-01-04

辽宁省教育科学“十二五”规划项目(JG12DB243)

刘学丰(1970-)，女，副教授，硕士，研究方向为英语教育信息化。

http://www.cnki.net/kcms/detail/61.1450.TP.20160104.1608.072.html

TP311

A

1673-629X(2016)01-0181-04

10.3969/j.issn.1673-629X.2016.01.039