基于线性递减系数粒子群优化算法的组卷实现

白雁

摘  要： 为了避免目前常用的组卷算法组卷时间长、程序结构复杂、收敛速度慢等缺陷，提出基于线性递减系数粒子群优化算法的组卷策略。通过调整惯性系数，使得步长较小，惯性权系数的变化幅度小，这种减小趋势较为缓慢的方法能够避免陷入局部最优。并对数学模型以及线性递减惯性权系数进行了理论设计，同时通过编程实现了该算法。测试结果表明加入线性递减系数后运算迭代次数明显减少，证明加入线性递减系数后的组卷策略收敛性好，能够高效准确地按照一定的预期条件进行组卷，符合预期要求。

关键词： 组卷; 粒子群优化算法; 线性递减惯性权系数; 适应度函数

中图分类号： TN911?34                    文献标识码： A                            文章编号： 1004?373X（2014）24?0041?04

Implementation of test paper generation based on particle swarm optimization algorithm with linear decreasing inertia weight

BAI Yan

（The Distance Education School， Xian Jiaotong University， Xian 710048， China）

Abstract：In order to avoid defects in the commonly used test paper generation algorithm， such as too much time taking， complicated program structure and low velocity of convergence， a test paper generation strategy of  particle swarm optimization algorithm based on linear decreasing inertia weight is proposed. The step size becomes smaller and the inertia weight changes less by adjusting the inertia coefficient. The relatively slow decreasing trend method can avoid falling into local optimum. The theoretical design for mathematical model， linear decreasing inertia weight was carried out. The algorithm was realized by programming. Test results show that the addition of linear decreasing coefficient can greatly reduce the iteration times， can make the convergence characteristic better， and can efficiently and accurately generate test paper according to the expected conditions.

Keywords： test paper generation; particle swarm optimization algorithm; linear decreasing inertia weight; fitness function

0  引  言

教育信息化促进了教育领域的全面变革，其中传统的考试方式也慢慢开始逐步被在线考试这一形式所取代。如何快捷、有效、科学地组卷是在线考试系统的技术核心。合理的组卷策略不仅仅是完成一份考题，而是要像人工考试那样能够按照总分，题型，章节，难度等信息筛选相应的试题组成具有一定难度和区分度的试卷，这样能够更加客观，公平，真实地反映出学生对知识点掌握的情况。

组卷算法实际上是多目标约束优化问题，合理选择组卷算法是解决问题的关键。目前常用的组卷算法有随机组卷法、回溯法、遗传算法、鱼群算法、粒子群优化算法等。但这些算法存在着组卷时间长，程序结构复杂，收敛速度慢，计算复杂等缺陷[1]。针对这些问题，本文提出的基于线性递减系数粒子群优化算法的组卷策略，其具有粒子群优化算法的原理简单、参数少、收敛性好、容易实现等特点，同时又加入了线性递减的惯性权重系数，在避免陷入局部最优的同时使得搜索后期加速收敛，克服了粒子群优化算法的缺点，较好地解决了组卷的优化问题。

1  组卷策略的理论设计

1.1  粒子群优化算法概述

粒子群优化算法是基于鸟群觅食行为的一种迭代优化算法，由Eberhart博士和Kennedy博士提出的。他们发现鸟群在觅食的过程中，在不清楚食物具体位置的情况下能够不断调整速度和飞行的位置以接近食物，最终聚到一起找到食物[2]。

经过模拟社会模型将其概括成以下公式：

[vidt+1=w*vidt+c1rand*pidt-xidt+                     c2rand*Pgdt-xidt] （1）

[xidt+1=xidt+vidt+1] （2）

式中：[c1，c2]为正的常数，一般均取值为2;rand（）和rand（）为[0，1]之间的随机数，可以用随机数生成函数生成;w为惯性权重。

式（1）表示鸟群速度矢量的更新由以下三部分决定：首先是当前的状态，这个是其惯性的表现。其次是自身经验，在以往过程中距食物最近的位置往往起着导向作用。最后一部分通过与其他鸟儿进行信息交流，了解整个鸟群的社会经验，即整个迭代过程中其他鸟儿距离食物最近的位置，来获得的最佳位置。同时每次迭代都要使用位置矢量根据预设的适应度函数计算出适应度值来判断位置的远近[3]。

1.2  数学模型

试题数据库中的题目具有以下几个属性：

（1） 总分。一份试卷中所有试题的分数总和，一般为100分，120分，150分。

（2） 题型。题库中的题目可分为主观题，客观题两种类型，主观题是人工改卷的题型，主要有问答题，论述题等。客观题是计算机自动改卷的题型，主要有单选题，多选题，判断题，填空题，复合题（阅读理解，完形填空）等。将每种题型进行编号，比如单选题为1，多选题为2，判断题为3，填空题为4，阅读理解为5，完形填空为6，问答题为7，论述题为8。按照要求设定各个题型的比例，比如{b1，b2，…，b8}为每种题型所占分数的比例。

（3） 章节比例。每道题目都有其所属的章节属性，科学的组卷是在考试中每章的知识点按照权重出题，重要的章节要多出并且兼顾每章的知识点都要有所涉及，以本院《计算机科学与技术》题库为例，一共有8章内容，分别用数字1～8表示，所占分数比例{c1，c2，…，c8}。

（4） 难易程度。试题难度分为1，2，3等级，1表示简单题，2表示中等难度，3表示难题。

据上述分析可知，一份由n道试题组成的试卷实际上可以转化为一个具有多重约束的寻优问题，这份试卷就是一个目标矩阵：

[Z=a11a12a13a14a15a21a22a23a24a25??…??an1an2an3an4an5]

式中每一行是一道题目，包含5个属性向量;其中ai1表示题目编号（1≤i≤n），ai2表示题型编号，ai3表示所属章节，ai4表示难度编号，ai5表示分数值[4?6]。其应该满足的约束条件如下：

（1） bm为每个题型所占分数，则有[bm=i=1nc1ai2]，当ai2为m时，c1为1，其余为0。其中1≤m≤8。

（2） Cj为每个章节所占分数，则有[cj=i=1nc2ai3]，当ai3为j时，c2为1，其余为0。其中1≤j≤8。

（3） dz每道题目的难易程度和，则有[dz=i=1nc3ai4]，当ai4为z时，c3为1，其余为0。其中1≤z≤3。

（4） Ts为试卷总分值，ai5为每道题目的分数，则有[Ts=i=1nai5] 。

适应度函数由这四个基本条件以及其他的复杂条件，比如题型分布条件、难度方差约束，区分度约束条件等组成，本系统进行了简化使用这四个条件作为适应度函数。

1.3  线性递减惯性权系数

在粒子群优化算法中，惯性权系数是最重要的参数。根据上面的公式可以知道，w大，速度V大， 这样粒子可以搜索更大的范围空间。而w小， 则速度V就小，有利于提高局部搜索能力在当前的空间里搜索最优解，但是容易陷入局部最优。因此对于参数的选择，实际就是要在全局搜索和局部搜索取得最佳的比例关系[7?8]。

本文在Yuhui Shi研究的基础上调整了惯性系数的策略，选用了[9?10]：

[wk=wini-wini-wend2kmax·k] （3）

式中：k是目前的进化次数;kmax 为最大进化次数;wini 为初始惯性权重值;wend为进化至最大次数时的惯性权重值，wini=0.9，wend=0.4。分母乘以2，使得步长较小，w的变化幅度小，这种减小趋势较为缓慢的方法能够避免陷入局部最优。在本程序中可以简化为以下形式：w（k）=0.9-0.25[kkmax]，其中k为程序循环迭代的次数，kmax为最大迭代次数。

2  算法流程

首先确定试卷的组卷参数，比如总分，每个题型的分数比例，每章所占分数比例，题目难易程度分布等，并且确定适应度函数的几个参数。设定条件后题目的数目也是固定的，用随机数生成器随机生成固定数目的若干题号，组成一份试卷，每份试卷就是一个初始群体，一共产生5个初始群体，代入适应度函数公式计算出个体适应度，作为初始pbest和gbest。根据循环的次数计算出w的值，并且计算出速度适量和位置矢量，粒子的速度和位置决定了粒子移动的方向，组卷模型中和其他模型不同的地方在于：题目的编号相当于位置矢量，而题目的递增不会出现小数类型，故速度矢量和位置均为整型。之后进行下一步迭代，计算个体适应度，并且与初始pbest，gbest进行比较，并同时更新这两个值。直到满足适应度函数的取值，找出其速度矢量和位置矢量。如果收敛则取得的结果就是最终成卷结果，如果不收敛则重新抽题。

3  数据库结构设计

系统前台为ASP，后台为VB.Net+SQL Server 2005数据库，学生端考试是B/S架构，方便快捷。教师改卷以及管理员端是C/S架构，安全性高。

试题库数据表储存每道题目的详细信息，试题是按照不同的题库录入的。其关键字段如1所示。

表1 试题库数据表的关键字段

考试试卷数据库表用于存放考试试卷，其关键字段如表2所示。

对于选定题库并根据组卷算法生成的试卷的所有题目将会存放在一个数据表中，每次显示某个试卷的试题就是根据试卷编号从这个数据库和试题数据库提取，其中表3中的题目编号也就是试题库中的题目编号，根据这个外键联合查询可以取得试题的具体信息在前台网站上显示。其关键字段如表3所示。

表2 考试试卷信息数据表的关键字段

表3 试卷包含试题编号表的关键字段

4  组卷测试结果及数据分析

为了验证算法及其函数取值的可行性和有效性，利用上述网上考试的组卷系统，以《计算机科学与技术》课程为例进行组卷实验。

系统题库共有4种题型、8个章节、3个难度系数的326道题目。组卷时设置满分为 100分，将粒子群规模设为5，最大迭代次数为 500次，并且根据下面的约束条件设置题目：

（1） 试卷总分为100分。

（2） 题型分数比例为：{30，30，20，20，0，0，0，0}.单选题30分，多选题30分，判断题20分，填空题20分，其他题型没有选择到，均为0。

（3） 章节分数比例为：{10，10，20，10，10，10，20，10}。

（4） 试题难易程度均为2。

加入线性递减系数的运行结果为由以下题号的题目组成一份试卷：13， 16，23，27，28，31，35，47，68，72，74 ，76，80，91，95，103，111，136，138，149，169，179，183，185，191，210，258，279，287，289，293，302，323，325。

上述题号13试题在程序运行中的数据为：[13，1，1，2，3]，往数据库中增加题目的同时自动运行存储过程将每道题目信息转化成矩阵形式，依次类推。基于线性递减系数粒子群优化算法就是基于这些元数据进行反复迭代运算。上例中单选题 10道 ，多选题10 道 ，判断题 10道 ，填空题 4 道，单选题一道3分，多选题一道3分，判断题一道2分，填空题一道5分。

表5 运行结果比较

分别使用粒子群优化算法和加入线性递减系数的粒子群优化算法进行组卷实验，总共运行10次，可以看出总体上基于线性递减粒子群优化算法效率高，全部成功，而粒子群优化算法速度较慢，成功率较低。

5  结  语

本文设计了基于线性递减系数粒子群优化算法的组卷策略和算法流程，并且用题库中的数据进行测试，结果表明加入线性递减系数后的组卷策略更能高效准确的组卷，成卷效果良好，但是本系统还需要进一步的完善以满足实际需要。

参考文献

[1] 潘莉.遗传算法在自动组卷中的应用方法研究[D].长春：东北师范大学，2010.

[2] KENNEDY J， EBERHART R C.Particle swarm optimization [J]. Institute of Electrical and Electronics Engineers， 1995 （11）： 1942?1946.

[3] 刘波.粒子群优化算法及其工业应用[M].北京：电子工业出版社，2010.

[4] 骆睿，周宁，赵舵.带惯性权重的粒子群优化算法性能仿真[J].信息技术，2008（8）：94?99.

[5] 胡建秀，曾建潮.微粒群算法中惯性权重的调整策略[J].计算机工程，2007（11）：199?201.

[6] 马跃亮.基于改进粒子群算法的组卷策略研究[D].保定：河北农业大学，2011.

[7] SHI Y， EBERHART R C. Parameter selection in particle swarm optimization [C]// Proceedings of the IEEE International Conference on Evolutionary Computation. Piscataway， NJ： IEEE Press， 1998： 69?75.

[8] 阎峰，安晓东.基于粒子群优化算法的智能抽题策略研究[J].中北大学学报：自然科学版，2008（4）：46?50.

[9] 田民格.改进的粒子群优化算法实现多目标智能组卷[J].三明学院学报，2009（4）：49?52.

[10] 丁瑾.基于粒子群优化算法组卷的研究[J].软件导刊，2010（11）：81?83.

表2 考试试卷信息数据表的关键字段

表3 试卷包含试题编号表的关键字段

4  组卷测试结果及数据分析

为了验证算法及其函数取值的可行性和有效性，利用上述网上考试的组卷系统，以《计算机科学与技术》课程为例进行组卷实验。

系统题库共有4种题型、8个章节、3个难度系数的326道题目。组卷时设置满分为 100分，将粒子群规模设为5，最大迭代次数为 500次，并且根据下面的约束条件设置题目：

（1） 试卷总分为100分。

（2） 题型分数比例为：{30，30，20，20，0，0，0，0}.单选题30分，多选题30分，判断题20分，填空题20分，其他题型没有选择到，均为0。

（3） 章节分数比例为：{10，10，20，10，10，10，20，10}。

（4） 试题难易程度均为2。

加入线性递减系数的运行结果为由以下题号的题目组成一份试卷：13， 16，23，27，28，31，35，47，68，72，74 ，76，80，91，95，103，111，136，138，149，169，179，183，185，191，210，258，279，287，289，293，302，323，325。

上述题号13试题在程序运行中的数据为：[13，1，1，2，3]，往数据库中增加题目的同时自动运行存储过程将每道题目信息转化成矩阵形式，依次类推。基于线性递减系数粒子群优化算法就是基于这些元数据进行反复迭代运算。上例中单选题 10道 ，多选题10 道 ，判断题 10道 ，填空题 4 道，单选题一道3分，多选题一道3分，判断题一道2分，填空题一道5分。

表5 运行结果比较

分别使用粒子群优化算法和加入线性递减系数的粒子群优化算法进行组卷实验，总共运行10次，可以看出总体上基于线性递减粒子群优化算法效率高，全部成功，而粒子群优化算法速度较慢，成功率较低。

5  结  语

本文设计了基于线性递减系数粒子群优化算法的组卷策略和算法流程，并且用题库中的数据进行测试，结果表明加入线性递减系数后的组卷策略更能高效准确的组卷，成卷效果良好，但是本系统还需要进一步的完善以满足实际需要。

参考文献

[1] 潘莉.遗传算法在自动组卷中的应用方法研究[D].长春：东北师范大学，2010.

[2] KENNEDY J， EBERHART R C.Particle swarm optimization [J]. Institute of Electrical and Electronics Engineers， 1995 （11）： 1942?1946.

[3] 刘波.粒子群优化算法及其工业应用[M].北京：电子工业出版社，2010.

[4] 骆睿，周宁，赵舵.带惯性权重的粒子群优化算法性能仿真[J].信息技术，2008（8）：94?99.

[5] 胡建秀，曾建潮.微粒群算法中惯性权重的调整策略[J].计算机工程，2007（11）：199?201.

[6] 马跃亮.基于改进粒子群算法的组卷策略研究[D].保定：河北农业大学，2011.

[7] SHI Y， EBERHART R C. Parameter selection in particle swarm optimization [C]// Proceedings of the IEEE International Conference on Evolutionary Computation. Piscataway， NJ： IEEE Press， 1998： 69?75.

[8] 阎峰，安晓东.基于粒子群优化算法的智能抽题策略研究[J].中北大学学报：自然科学版，2008（4）：46?50.

[9] 田民格.改进的粒子群优化算法实现多目标智能组卷[J].三明学院学报，2009（4）：49?52.

[10] 丁瑾.基于粒子群优化算法组卷的研究[J].软件导刊，2010（11）：81?83.

表2 考试试卷信息数据表的关键字段

表3 试卷包含试题编号表的关键字段

4  组卷测试结果及数据分析

为了验证算法及其函数取值的可行性和有效性，利用上述网上考试的组卷系统，以《计算机科学与技术》课程为例进行组卷实验。

系统题库共有4种题型、8个章节、3个难度系数的326道题目。组卷时设置满分为 100分，将粒子群规模设为5，最大迭代次数为 500次，并且根据下面的约束条件设置题目：

（1） 试卷总分为100分。

（2） 题型分数比例为：{30，30，20，20，0，0，0，0}.单选题30分，多选题30分，判断题20分，填空题20分，其他题型没有选择到，均为0。

（3） 章节分数比例为：{10，10，20，10，10，10，20，10}。

（4） 试题难易程度均为2。

加入线性递减系数的运行结果为由以下题号的题目组成一份试卷：13， 16，23，27，28，31，35，47，68，72，74 ，76，80，91，95，103，111，136，138，149，169，179，183，185，191，210，258，279，287，289，293，302，323，325。

上述题号13试题在程序运行中的数据为：[13，1，1，2，3]，往数据库中增加题目的同时自动运行存储过程将每道题目信息转化成矩阵形式，依次类推。基于线性递减系数粒子群优化算法就是基于这些元数据进行反复迭代运算。上例中单选题 10道 ，多选题10 道 ，判断题 10道 ，填空题 4 道，单选题一道3分，多选题一道3分，判断题一道2分，填空题一道5分。

表5 运行结果比较

分别使用粒子群优化算法和加入线性递减系数的粒子群优化算法进行组卷实验，总共运行10次，可以看出总体上基于线性递减粒子群优化算法效率高，全部成功，而粒子群优化算法速度较慢，成功率较低。

5  结  语

本文设计了基于线性递减系数粒子群优化算法的组卷策略和算法流程，并且用题库中的数据进行测试，结果表明加入线性递减系数后的组卷策略更能高效准确的组卷，成卷效果良好，但是本系统还需要进一步的完善以满足实际需要。

参考文献

[1] 潘莉.遗传算法在自动组卷中的应用方法研究[D].长春：东北师范大学，2010.

[2] KENNEDY J， EBERHART R C.Particle swarm optimization [J]. Institute of Electrical and Electronics Engineers， 1995 （11）： 1942?1946.

[3] 刘波.粒子群优化算法及其工业应用[M].北京：电子工业出版社，2010.

[4] 骆睿，周宁，赵舵.带惯性权重的粒子群优化算法性能仿真[J].信息技术，2008（8）：94?99.

[5] 胡建秀，曾建潮.微粒群算法中惯性权重的调整策略[J].计算机工程，2007（11）：199?201.

[6] 马跃亮.基于改进粒子群算法的组卷策略研究[D].保定：河北农业大学，2011.

[7] SHI Y， EBERHART R C. Parameter selection in particle swarm optimization [C]// Proceedings of the IEEE International Conference on Evolutionary Computation. Piscataway， NJ： IEEE Press， 1998： 69?75.

[8] 阎峰，安晓东.基于粒子群优化算法的智能抽题策略研究[J].中北大学学报：自然科学版，2008（4）：46?50.

[9] 田民格.改进的粒子群优化算法实现多目标智能组卷[J].三明学院学报，2009（4）：49?52.

[10] 丁瑾.基于粒子群优化算法组卷的研究[J].软件导刊，2010（11）：81?83.