基于混合粒子群算法的智能组卷研究
摘 要
针对解决智能组卷这一组合优化问题进行有效研究，提出一种简化的数学模型，为改善单纯粒子群算法存在的早熟收敛和后期收敛速度慢的问题，提出一种混合粒子群算法，提高算法寻优初期的搜索效率，改变粒子的更新方式，提高算法收敛精度与速度。在几种算法的智能组卷的对比中，验证了HPSO算法的优势。
【关键词】智能组卷 数学模型 粒子群算法 遗传算法
智能组卷问题就是根据用户的组卷要求，按照一定的算法自动地从试题库中抽取试题，组成最优试卷，这是一个典型的约束组合优化问题。目前国内学者针对智能组卷做了大量的研究工作：文献[1]提出了一种自适应遗传算法来提高组卷效率。文献[2]提出了将差分进化算法与传统遗传算法相结合的一种混合智能算法求解最优组卷问题。文献[3]提出了遗传算法与粒子群算法相组合的改进遗传算法的精英策略，有效克服了未成熟收敛问题。文献[4]提出了将遗传因子引入到类电磁算法中的局部搜索中，取得好的组卷效果。文献[5]提出了一种遗传算法与模拟退火算法相结合的混合遗传算法克服早熟现象，提高局部寻优能力。
粒子群算法PSO（Particle Swarm Optimization）是Kennedy和Eberhart于1995年提出的一种基于群智能的共生合作优化算法，其思想源于人工生命和进化理论。由于PSO算法其收敛速度快，具有并行计算等优点，已经成功应用在很多领域的组合优化问题中。但POS算法适合求解连续优化问题但容易早熟收敛，本文通过引入遗传算法中的选择机制和交叉机制，利用其全局搜索的优点，提出一种混合粒子群算法求解组合优化组卷问题，较好地解决了POS算法易陷入局部极值的问题，提高收敛速度，求出优化问题的最优解。
1 组卷问题数学模型
智能组卷过程就是分析出题老师的要求，从试题库中抽取一定量的试题，对每个题进行组合，生成一份满足用户需求的试卷，是一个多条件约束优化问题。本文算法设计的试题属性包括1）章节知识点，试题属于哪一章的哪个知识点，如3.7；2）题型，如选择题，填空题，操作题等；3）难度系数，分为难、较难、中等和易4个等级，其对应的系数为1.0、0.7、0.5、0.3；4）区分度，试题对考生能知识水平鉴别以及区分程度的指标；5）题分，每道题的满分值；6）完成时间，估计完成一道题所需时间；7）曝光度，试题被选中使用的次数。
从试题库中的抽取的试题集应满足试题指标的多个约束，约束条件有以下几个方面：
（1）试卷总分约束
（2）题型分值约束
（3）考试时间约束
（4）试卷难度约束
（5）试卷区分度约束
（6）知识点覆盖度约束
（7）偏差计算
组卷过程就是从试题库中随机选择试题集，使其属性变量在作用域集内取值，并且满足约束集的约束。由此可以把组卷过程描述为最大限度满足用户的多目标优化的数学问题。组卷数学模型是对用户需求的一种定量反应，多目标优化的数学模型为：
（Vp）minF（x）
式中，F（x） = （f1 （x）， f2（x），…fp（x））T ，fi（x）（i=1，2， …，p）为第i个目标
G（x）=（g1（x），g2（x），…gm（x））T，gj（x）（j=1，2， …，m）为第j个约束函数
D ={x| gj（x）≥ 0， j =1，2， …，m}
（Vp）minF（x）表示向量极小化，即向量F（x）=（f1（x）， f2（x），…fp（x）） 中的各个子目标函
数fi（x）（i=1，2， …，p）尽可能极小化。
2 混合粒子群算法
2.1 基本粒子群算法
粒子群算法是一种并行的共生合作优化算法，其从一群随机初始化产生的粒子而组成的一个问题解的集合中以迭代的方式进行优化搜索，根据对环境的适应度将群体中的个体移动到好的区域。每个优化问题的潜在解都可以想象成M维搜索空间上的一个没有体积的粒子，以一定的速度飞行，这个速度依据它自身的飞行经验和粒子群整体的飞行经验来动态调整。
设M维的搜索空间中有N个粒子组成一个初始粒子群，其中第i个粒子表示为Xi=（xi1，xi2，…，xim），用Vi=（vi1，vi2，…，vim）表示第i个粒子飞行的速度向量，将Xi带入适应度函数f（x）计算出其适应值f（Xi），根据适应值的大小衡量Xi的优劣。其中粒子经过的历史最优位置个体极值为Pi=（pi1，pi2，…，pim），整个粒子群经历过的最好位置全局极值Pg=（pg1，pg2， …，pgm）。对每一代，其第M维根据如下方程迭代：
Vim（k+1）= vim（k）+c1r1（pim（k）-xim（k））+c2r2（pgm（k）-xgm（k））
Xim（k+1）=xim（k）+vim（k+1）
其中，i=1，2，…，N；m=1，2， …，M； 为惯性因子， vim（k）表示第i个粒子在第k次迭代中第m维的惯性速度；c1和c2为加速度系数；r1和r2是介于[0，1]之间的随机数。
2.2 基于GA的PSO混合算法
粒子群算法的实质在于粒子根据自己同伴的飞行经验不断调整位置和速度，从而向最优位置飞行。粒子的新位置是粒子的速度、个体极值和全局极值相互作用的结果。在PSO算法改进过程中，本文提出必须对粒子的最初飞行速度进行有效控制，提高算法寻优初期的搜索效率，进而影响算法的全局收敛性，将遗传算法GA（Genetic Algorithm）思想引入到PSO中，利用遗传算法的交叉操作在寻优早期对粒子群进行前期调和，使得初始种群能够快速地均匀分布整个搜索空间；粒子的更新方式采用将粒子的当前位置分别与全局极值和个体极值交叉、变异并通过适应度的判析确定更新粒子位置，使得种群更快地向目标移动靠拢，利于粒子群优化得出结果。改进后的混合粒子群算法对单纯粒子群算法存在的早熟收敛和后期收敛速度慢的问题在一定程度上得到解决，优化效率高。
2.3 混合粒子群算法实现流程
（1）粒子表示。
在组卷问题中，每个粒子Xi=（xi1，xi2， …，xim）表示一个可行解，即表示一套试卷。
（2）计算粒子群的适应度。
（3）个体极值Pi和全局极值Pg计算。
（4）对粒子前期调和。
将粒子按照适应度排序，对适应度排位靠后的一半与其内部进行交叉和变异操作，然后再按适应度排序，取前一半放入原始种群，保持种群规模不变。
（5）粒子更新。
粒子分别与全局极值和个体极值交叉，然后按随机产生变异，进行粒子位置更新。
随机产生两个交叉点，将两个交叉点之间的试题与极值交叉交换，保留交叉点之外的试题，产生新粒子。如：
Prt1：9，12，7，65，16，70，23，96，303，102，6，331
Prt2：48，25，30，2，4，169，256，379，26，123，37，79
随机交叉点选在3和10，两个父体交叉后得到，如：
Son1：9，12，7，2，4，169，256，379，26，123，6，331
Son2：48，25，30，65，16，70，23，96，303，102，37，79
再随机产生若干个变异点，然后在相应的位置随机选取一道试题。如：
变异前的个体：9，12，7，2，4，169，256，379，26，123，6，331
随机产生3个变异点，分别为3，7，11，
变异后的个体：9，12，216，2，4，169，95，379，26，123，152，331
若新粒子的适应度优于Pi，则设为Pi，在Pi中选择适应度最优的个体设为Pg，满足条件或其它终止条件，则退出。
（6）生成下一代群体。
由Vim（k+1）和Xim（k+1）生成下一代群体，循环次数加1。
（7）确定终止条件。
若找到最优解或者达到最大迭代次数，则退出循环，否则返回（2）。
3 组卷结果分析
为验证混合粒子群算法（HPSO）组卷的上优势，现对遗传算法、基本粒子群算法、混合粒子群算法在相同条件下组卷，试题库总题量600道，其中单选题 200 道，填空题 130道，多选题 120道，改错题70道，简答题50道，论述题30道。
在相同环境下，几种算法组卷的结果如表1：
如表1的数据可知，在组卷过程中，PSO和HPSO较GA更为有效，这是因为遗传算法是一种随机搜索算法，搜索过程中方向性不强，而粒子群算法的进化过程中，种群朝着全局极值和个体极值飞行，有较强的方向性和目标性。改进后的粒子群算法在数据上也表现出较优的特性，迭代次数少，组卷耗时低，最佳适应值高，从收敛率来看，HPSO由于结合了GA的交叉变异操作，提高算法寻优初期的搜索效率和加快种群的进化速度，进而提高算法的收敛精度与速度。
4 结束语
组卷问题是一个典型的约束组合优化问题，利用PSO这一智能高效的算法是有效解决这一问题的途径。本文针对PSO算法的优化原理，引入了遗传算法的交叉选择和遗传变异思想，改进后的混合粒子群算法求解组卷问题，避免了单纯粒子群算法存在的早熟收敛和后期收敛速度慢的问题，提高了算法的搜索速度和准确性，通过仿真实验证明该算法具有很好的性能和实用性。
参考文献
[1]黄宝玲.自适应遗传算法在智能组卷中的研究[J].计算机工程，37（14）：161-163.
[2]王凤蕊，王文宏，潘全科.基于差分进化算法的智能组卷研究[J].2009，30（8），1974-1976.
[3]肖理庆，徐晓菊.改进遗传算法智能组卷研究[J].计算机工程与设计，2012，33（10）：3970-3974.
[4]管宝云.基于混合智能算法的高校时间表及自动组卷问题研究[D].天津大学，博士论文，2005.
[5]王亚敏，冀俊忠.基于粒子群优化的考试时间安排问题的求解算法[J].计算机应用，2009（06）：137-140.
[6]陈泽琳，张庆彪.基于JAVA的考试系统中题库设计与组卷算法[J].重庆理工大学学报（自然科学），2010，24（3）：48-55.
[7]赵忠平，杨浩.智能组卷系统的设计与实现，山西师范大学学报（自然科学版），2008，22（2）：28-32.
作者单位
广东司法警官职业学院信息管理系 广东省广州市 510520
