一种基于改进差分算法的智能组卷方法

（云南电网公司教育培训评价中心昆明650000）

一种基于改进差分算法的智能组卷方法

江龙曹俊豪陈祖恩张德刚

（云南电网公司教育培训评价中心昆明650000）

智能组卷是典型的多约束组合优化问题，用户设定针对试卷的多个限定条件，系统给出满足约束的最优试题组合。符合实际的组卷模型与高效的算法是保证组卷质量的关键。结合南方电网的实际考试需求，对于差分算法收敛过早，且易收敛于局部最优等不足，提出了通过均匀搜索题库生成初始种群，根据种群适应度的取值情况对变异率和交叉率进行动态微调。实验表明，经过改进的差分算法在面对海量试题时仍具有较好的全局寻优能力，具有较高的组卷质量与组卷效率。

智能组卷；差分进化；智能优化

Class NumberTP391

1 引言

随着计算机技术的发展，以组合优化算法为基础，按照用户要求无需人工参与自动构建一份符合考试约束的试卷已成为众多学者研究的课题［1～2］。智能组卷大大降低了组织考试的工作量，节约了考试成本。符合实际需求的高质量试卷也为企业的人才测评工作提供了更为科学合理的工具。

目前用于计算机智能组卷的方法主要有以下两类：一类是以随机生成法［3］为代表，包括分段随机抽取、集合随机抽取、回溯试探法，此类方法实现简单但具有较大的不确定性，难以生成高质量试卷；另一类是以进化算法为代表的组合优化算法，该类方法具有较好的鲁棒性，组卷的质量相对较高，但搜索时间长、参数控制复杂。目前的研究主要是针对其不足进行改进，包括：蚁群组卷算法［4］、粒子群组卷算法［5］、遗传算法［6］等。相较于其他算法，差分进化具有收敛速度快，稳定性好等优异性能，但标准的差分进化易于陷入局部最优和收敛过早［7］。本文针对差分进化算法的不足，结合南方电网实际的考试需求，提出了改进措施，并建立了基于该算法的智能组卷模型，实验结果表明，经过优化的差分进化算法在性能上具有明显的优越性。

2 智能组卷的数学描述

本文经过对南方电网考试需求的深入调研，确定试题属性的定性指标为能力层次、素质维度、知识点、题型；定量指标为分值、难度、区分度、曝光度；试卷的评价指标为：试卷总分、试卷难度、试卷区分度、试卷曝光度［8］。其中，能力层次取值为基本能力、专业能力、管理能力；素质维度取值分别为：知识、技能、潜能。知识点、题型、分值等指标为传统组卷指标。定量指标描述如下：试卷总分P为该试卷题目i的分值pi之和，其中n为试题总数；试卷难度为

其中，fi是试题i的区分度，W是该试卷考生考试成绩的标准差。它可用于验证区分度取值的正确性，a，b是由经验确定的常数。试卷曝光度

其中P为试卷满分值，di为第i道试题难度值，pi是第i道试题的分值，Yˉ是该试卷全部考生的平均得分，该值用于验证试题难度的准确性。试卷的区分度为取值为0表示试题i在以往试卷中从未出现，gi取值为1表示试题i在以往的试卷中已出现过。基于以上约束定义，对于具有m道试题的题库，组卷过程即是算法从迭代中选择n道试题（m≫n）。且满足用户设定的8个约束属性。组卷算法的目标状态矩阵如式（3）：

显然，组卷问题的目标状态并不唯一，S的每个行向量为满足所有约束的一道试题，其列向量满足组卷约束的整体要求，即8个指标满足用户指定或与用户设定的误差最小。

为了便于组卷算法的迭代，更好地衡量试卷指

其中，∂i(i=1，2，3，4)为指标权重，且满足标与用户给定约束的误差，需定义目标函数（适应度函数）F(x)。本文将定性指标作为初始选题边界，将关键的定量指标作为目标函数的设计因素，这样做在一定程度上简化了组卷算法的复杂度。因此：分别为用户给定的试卷分数、试卷难度、试卷区分度和试卷曝光度。

3 基于改进差分算法的组卷过程

3.1 差分进化算法改进

差分进化算法可解决具有多个约束条件的极值优化问题，是一种控制参数较少具有较高收敛速率的算法［9～10］。基于标准的DE算法，本文提出一种经过优化的的DE算法—SDE算法，首先按题型分布，在试题库中均匀随机产生初始种群，相较于传统的直接随机抽取，其初始种群覆盖面更广分布更均匀使得算法搜索空间更加合理，大大提高了全局寻优能力。另外，根据适应度变化，对算法参数变异率F和交叉率Cr进行反馈自适应调节，从而实现了根据上一代的搜索信息对下一代种群个体的变异方向进行微调，保证了搜索过程的效率与高精度。

3.2 组卷过程

按照改进的差分进化算法步骤，首先应产生一定规模的初始种群。题库中共m道试题，按照题型划分为若干区域，然后根据组卷的定性指标约束在每个区域随机产生一个原始解构成初始种群。规则如下

其中，xi，j表示初始种群个体xi的第j个分量，N为种群个体数量，d为每个区间的长度。xi，max，xi，min分别为其取值上下界。种群矩阵如下式：

其中t取0，表示第0代即初始种群。P(0)的每一行均为组卷问题的一个可行解，可表示为xi(0)=(xi1(0)，xi2(0)，…，xin(0))T(i=1，2，…，N)，因此组卷的最终目标就是经过t代的进化，使得P(t)中产生满足终止条件的行向量。

第二步，需进行变异操作。根据改进措施，按式（4）计算适应度，令Ft为当前变异率，fi_max，fi_avg分别是种群中最大适应度、平均适应度，则变异率F的更新计算公式为

每代种群的变异率均按上式计算，其取值范围为F∈[0.5，1]。以更新的变异率对第t代种群P(t)中的可行解xi(0)=(xi1(0)，xi2(0)，…，xin(0))T(i=1，2，…，N)执行变异操作，所生成的新个体为

其中，i，r，s∈{1，2，…，N};i≠r≠s，xrj(t)与xsj(t)为进化种群中不同于xi(t)的两个个体的第j个分量。

第三步，进行交叉操作。交叉率Cr的更新计算公式如下，其中fi_max，fi_avg分别为种群中最大适应度和平均适应度，Cr的取值范围为Cr∈[0.8，1]。

对于父代个体xi(t)=(xi1(t)，xi2(t)，…，xin(t))，(i=1，2，…，N)的每个分量xij(t)产生[0，1]区间内的随机数βi，然后根据βi与Cr的关系决定是否将变异步骤中的第j个分量代替xij(t)。具体规则如下式：

第四步，需根据适应度对种群中的个体进行选择。先对种群中每个个体进行排序，然后采用轮盘赌法进行选择，对于适应度较高的个体有更大的概率被选中参与进化。

第五步，达到终止条件，设定固定的进化代数或适应度满足要求，当达到该条件时，算法终止，

4 实验结果与分析

为验证所提出改进差分进化算法的性能，本文以南方电网企业考试为背景，分别以不同题库规模的《安规考试》为算例进行实验，并与遗传算法（GA）、标准的差分进化算法（DE）进行对比。本文算法SDE与标准差分算法初始参数为：种群规模N=100，变异率F为0.6，交叉率Cr为0.9，对DE算法来说上述参数均为定值。实验中对两个规模分别为2000、10000的安规考试题库分别进行组卷。设定约束如下：能力层次为基本能力与专业能力；素质维度为知识与技能；知识点为全部知识点；题型为选择、分析、论述；试卷总分为100分；试卷难度为0.52；试卷区分度为0.48；试卷曝光度为0.1。

在两种不同的题库规模下，按照上述设定进行三种算法的组卷对比试验，每种算法各独立运行50次，运行结果如表1所示。

表1 不同题库规模下三种组卷算法运行结果比较

表中的成功率是指算法运行50次生成符合要求的试卷概率，最优值、最差值和标准差分别表示各个算法组卷过程中最优和最差的适应度函数值及对应的标准差。分析表1的结果可知，本文提出的SDE算法性能优异，在中等题库规模时具有较好的寻优能力，组卷成功率高。在面对大规模题库时，遗传算法收敛速度慢且组卷成功率略低，标准的差分算法存在陷入局部最优，组卷成功率不够理想等问题，相比之下，SDE在保证组卷速度的同时，提高了组卷成功率。

5 结语

本文结合南方电网的实际考试需求，建立了智能组卷数学模型，在此基础上提出了差分进化算法的改进算法—SDE，实现了高质量高效率的智能组卷。实验表明，该算法即便是面对大规模题库仍具有较高的性能，这对于大型考试系统的设计具有重要的参考价值。

［1］Chen X.A Fast and Efficient Algorithm for Intelligent Test Paper Generating：Practical Applications of Intelligent Systems［M］.Berlin Heidelberg：Springer，2011：231-236.

［2］Jiang L，Zhang F.Research and Implementation of Intelligent Paper Generating System［C］//International Conference on Computer Science and Service System.Nanjing，China，2011.

［3］Li J，Wang M.Research on Intelligent Generating Test Pa-per Basedon Parallel Genetic Algorithm［C］//KESE.Shenzhen，China，2009.

［4］Hu X M，Zhang J，Chung S H，et al.An intelligent testingsystemembeddedwithanant-colony-optimization-based test composition method［J］.Systems Man& Cybernetics Part C Applications&Reviews IEEE Transactions on，2009，39（6）：659-669.

［5］Jian L V.Application of Improved PSO in Intelligent Test Paper Auto-Generation System［J］.Modern Computer，2008.

［6］Liu D，Zheng L，Wang X，et al.Research on Intelligent Test Paper Generation Based on Improved Genetic Algorithm［C］//Second Wri Global Congress on Intelligent Systems.2010：363-365.

［7］Ali M，Siarry P，Pant M.An efficient Differential Evolution based algorithm for solving multi-objective optimization problems［J］.European Journal of Operational Research，2012，217（2）：404-416.

［8］Luo J，Zhang R，Jin Y.Implementation Strategy of Several Key Issues in Intelligent Testing Paper Generation System［C］//Computational Intelligence and Software Engineering，2009.CiSE 2009.International Conference on. IEEE，2009：1-4.

［9］Shi Y，Gao H，Wu D.An improved differential evolution algorithm with novel mutation strategy［C］//Symposium on Differential Evolution，Orlando，FL，2014：20-25.

［10］Cheng S L，Hwang C.Optimal approximation of linear systems by a differential evolution algorithm［J］.Systems Man&Cybernetics Part A Systems&Humans IEEE Transactions on，2001，31（6）：698-707.

An Intelligent Test Paper Generation Method Based on Improved Differential Algorithm

JIANG LongCAO JunhaoCHEN Zu'enZHANG Degang
（The Education and Training Evaluation Center of Yunnan Power Grid Co.，Ltd，Kunming650000）

Intelligent generating test paper is a typical multi constrained combinatorial optimization problem.The user sets a number of qualified conditions for the paper.The system gives the optimal combination of test questions to meet the constraints.In line with the actual test paper model and efficient algorithm is the key to ensure the quality of the test paper.According to the actual demand of China Southern Power Grid test，for the differential algorithm premature convergence，and easy convergence to the local optimum problem，proposes a search database to generate the initial population by uniform，according to the value of the population to adapt to the dynamic fine-tuning of the mutation rate and crossover rate.Experiments show that the improved differential algorithm still has a good global optimization ability in the face of massive test questions，which has a high quality of the test paper and the efficiency.

intelligent generating test paper，differential evolution，intelligent optimization

TP391

10.3969/j.issn.1672-9722.2017.06.009

2016年12月24日，

2017年1月30日

江龙，男，博士，政工师，研究方向：电网教育培训评价。曹俊豪，男，硕士，工程师，研究方向：电网教育培训评价。陈祖恩，男，高级经济师，研究方向：电网教育培训评价。张德刚，男，博士，工程师，研究方向：电网教育培训评价。