基于改进遗传算法的智能组卷系统设计∗

高凌洁

（宝鸡职业技术学院 宝鸡 721013）

基于改进遗传算法的智能组卷系统设计∗

高凌洁

（宝鸡职业技术学院 宝鸡 721013）

针对传统随机组卷模型在组卷速度和组卷质量方面存在的问题，对传统遗传算法进行改进，提出一种基于改进遗传算法的智能组卷系统。基于试题组卷约束，构建试题组卷数学模型，并通过遗传编码方法对试卷个体属性值进行保存，从而提高运算速率；针对组卷过程中知识点容易冲突问题，利用分段多点的变异策略和杂交策略进行优化；同时针对种群多样性问题，提出一种大比率杂交和变异策略，从而提高组卷速度。最后借助C#语言+Mysql数据库分别进行编程和试题库构建，通过仿真验证改进算法在收敛性和质量方面的优势。

遗传算法；智能组卷；遗传编码；适应度函数；组卷质量

1 引言

在智能组卷系统中，如何保障生成的试卷能最大限度地满足教学的需求，并提高试卷组卷的质量、难度、出题时间等问题，是当前的一个难点，也是一个重点。但是，传统的随机组卷算法带有很大的随机性，同时知识点、试题难度等也不能把握，大大减少了试卷的质量，不能发挥考试测验的效果。如当试题库规模和试卷指标设置越多的情况下，随机组卷算法在计算速度、组卷质量方面都很难达到满意效果。而遗传算法是一种模仿自然界生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化搜索算法，具有全局优化强、操作简单的特点。遗传算法的原理是通过在代与代之间维持由潜在解构成的种群来实现全局搜索和多样性，从而为多目标的优化提供了更好的解决方法。而近年来，遗传算法也被广泛的应用在智能组卷问题求解中，并取得丰硕成果。但后期收敛速度慢、多个约束条件下出现冲突等问题仍然不能得到有效满足。对此，文章给出一种改进遗传算法的组卷系统，并通过设计开发，得到满意效果。

2 组卷数学模型构建

假设试题库中的每道题可通过n项不同的指标来决定其是否可以被组卷，从而构成了一个n维度的向量（an1题型，an2分数，an3难度，an4章节，……），其中，ani表示第i道试题存在的全部指标。而在试题库之中包含p道试题，由此构成了一个m*n的矩阵。

在上述的目标矩阵X则为需要求解的目标矩阵，每一列之中表示了每一道题所包含的一个属性，而每一行则代表一道题的左右的属性值，apn表示第 p道题的第n个属性。从而得到试题构成的染色体模型：

对试题指标选择设置相应的约束条件。所谓的约束条件，通常被认为是能够提高组卷质量的方法。试卷指标很多，主要包括各题型包含的题数、试题分值、预计答题时间、每章节出题数量、每章节出题分值、试卷难易分布、试卷总题型数量及总分、试卷区分度、知识点覆盖、试卷认知程度。其中知识点覆盖的约束条件为

其中，y(j，i)=1表示第i题的第 j个知识点，否则为0，k则表示输入的知识点覆盖数。

试卷难易分布指标约束条件为

其中，b(j)表示第 j类试题难度的总分数；y(j，i)=1表示第i道题属第 j难度，否则值为0。

3 传统基于遗传算法的组卷

传统遗传算法被广泛用在试卷生成之中，其具体的思路为：对试题进行自然数编码，然后抽取出设定数量的初始试卷，从而作为遗传算法的交配池。利用遗传算法设计适应度函数，从而对每一道试题的适应度值进行计算，同时按照预先设置的交叉、变异操作进行运算，衡量适应度值是否满足要求。如果通过计算出来的适应度值满足，那么解码生成相应的试卷，如果不满足，那么继续进行交叉、变异运算，直到适应度值满足设定要求，即停止迭代。具体如图1所示。

图1 遗传算法

遗传算法的特点在于适合全局搜索，而不适合局部搜索。因此，在早期搜索中，这种算法在试卷生成占极大优势，但容易陷入“早熟”问题，从而得不到试卷组合最优解，达不到提高试卷质量的目的。同时其变异、交叉、选择等操作属于独立的，不能确保试卷中的实体知识点不重复问题。

4 基于改进遗传算法的试卷组卷

4.1 适应度函数设计

而入门的小学生和初中低年级学生，处境就比较尴尬。从国外引进的童书绘本中，以外研出版社引进的偏文字英语故事书为主，对英语入门级学生而言难度偏高；其他出版社，更多为直接出中文译作。而承载着认知启蒙、培养语言兴趣使命的入门级英语原版绘本，市面上实在是少之又少（漆秋香，2015），视听资源更是缺乏。偶尔出现，价格还偏高。正版资源少，盗版也是无源之水。

为有效地设计试卷组卷的适应度函数，本文则提出一种基于线性关系的适应度函数，具体思路为通过对不同目标属性 fi赋予不同的权值，从而得到组合的目标函数 f，最终计算目标函数的适应度。

其中，∑wp=1。

4.2 初始种群改进

为提高组卷收敛速度，改变传统的随机搜索方法，在对初始种群进行筛选过程中引入知识点分布、题型约束等参数。具体算法设计如图2所示。

图2 初始种群改进流程

4.3 遗传算子改进

4.3.1 选择操作改进

对选择算子来讲，物竞天择、适者生存是其构建的基本思路。而根据这样的选择方式，最后可能会因为种群数量不多，形成过早收敛的问题。对此，在遗传算法改进中，引入轮盘赌方式，从而增加适应度值小的个体概率，增加种群数量。具体思路为：

对于给定的种群 XP，其中的某个个体apn适应度值可以用 fi表示，由此先计算出种群所有个体的适应度总和SUM，然后计算出每个个体的选择概率XPi=fi/SUM ，找出其中的最大概率max，按照随机原则产生一个0～max的随机数a，如果a＜XPi那么这个个体被选中，如果a＞XPi，则淘汰。由此，对于一些适应度较小的试题，也有可能被选中。然后，利用精英选择思想，通过适应度函数计算出其中是适应度最大和最小的个体，保留适应度较大，淘汰适应度较小的试题。

4.3.2 杂交操作改进

杂交是一种重要的工具，可获得更加优秀的个体。为避免选题知识点的冲突，提出一种改进的分段多点杂交方法，具体策略如图3所示。

图3 杂交操作改进

在图3的杂交操作中，杂交知识点相同的试题，从而得到新的后代，对新产生的后代进行适应度计算，适应度较低的直接淘汰，保留适应度较高的后代。

4.3.3 变异操作改进

为进一步防止在试卷组卷过程中陷入局部最优的问题，对传统的变异操作进行改进，提出一种分段多点变异策略，即在保证题型和知识点不变的前提下，从试题库中抽取新的具有相同难度、知识点的题型来替代旧的题型，从而保持试题的实时性更新。具体操作如图4所示。

图4 变异操作策略

4.4 改进遗传算法

根据上述的改进，可以将传统的图1用于试卷组卷的遗传算法改进为如图5所示。

图5 基于改进遗传算法的组卷策略

5 算法验证

5.1 仿真部署及工具

为验证算法的正确性和效率，采用C#进行编程开发，采用Mysql对试题库进行构建。试题库数量总共为10万条，题型总共分为5种：选择、填空、判断、计算、简答，编码01～05；难度设计为较易、易、中、难、较难，分别编号为01～05；区分度编码设计为9种，分别从01～09；知识点总共为100个，编码设计为00～99；答题时间设计为1-30个单位，1个单位30s。

5.2 仿真编程

以改进变异策略的编程为例，其具体实现代码为：

//从数据库中选择相同知识点和同类型与同分数的试题题号

var other DΒ=from a in problem List

where a.Points.Intersect(problem.Points).Count()＞0

select a;

List＜Problem＞small DΒ =other DΒ.Where(p=＞Is Contain

(paper， p)).Where(o=＞ o.Score==temp.Score o.Type==temp

.Type o.ID!=temp.ID).To List();

//从符合要求的试题中随机选一题替换

if(small DΒ.Count＞0)

{

int change Index=rand.Next(0，small DΒ.Count);

u.Problem List[index]=small DΒ[change Index];

}

5.3 仿真结果

设置最大迭代数为1000，迭代初始种群规模10、20、50、100、150。根据编程仿真，可以得到在不同初始种群规模下的迭代时间。具体见图6所示。

图6 不同种群规模下的迭代时间统计

同时以100次试验为例，分别对改进遗传算法、遗传算法和传统随机抽取算法进行比较，可以得到表1的结果。

表1 不同组卷算法比较

由此可以看出，随着规模的扩大，其迭代时间越来越长，并呈现出线性的变变化关系，从而说明该算法性能好、收敛速度快的优势。

6 结语

本文通过对遗传算法中的选择操作、交叉算子、变异算子进行改进，对基于实数编码的智能组卷矩阵模型进行求解，从而得到不同指标参数下的试题组卷最优求解，从而大大提高了组卷质量，并克服了传统组卷时间较长的问题，大大提高组卷效率。

［1］周显春，刘东山.无纸化考试智能生成试卷技术的综述［J］.电脑知识与技术，2011，36：9501-9502，9508.ZHOU Xianchun，LIU Dongshan.An overview of the intelligent generation of test paper in the paperless examination［J］.Computer Knowledge and Technology，2011，36：9501-9502，9508.

［2］宫磊，赵方.基于改进自适应遗传算法的智能组卷算法［J］.计算机与现代化，2012（5）：152-156.GONG Lei，ZHAO Fang.Intelligent generating test paper algorithm based on improved adaptive genetic algorithm［J］.computer and modernization，2012（5）：152-156.

［3］李欣然，靳雁霞.一种求解组卷问题的量子粒子群算法［J］.计算机系统应用，2012（7）：244-248.LI Xinran，JIN Yanxia.A quantum behaved particle swarm optimization algorithm for solving the problem of generating test paper［J］.Computer System Application，2012（7）：244-248.

［4］李书全，孙雪，孙德辉，等.遗传算法中的交叉算子的述评［J］.计算机工程与应用，2012（1）：36-39.LI Shuquan，SUN Xue，SUN Dehui，et al.Review of crossover operator in genetic algorithm［J］.Computer Engineering and Application，2012（1）：36-39.

［5］马永杰，云文霞.遗传算法研究进展［J］.计算机应用研究，2012（4）：1201-1206，1210.MA Yongjie，WEN Xia.Study on cloud genetic algorithm in［J］.Application Research of computers，2012（4）：1201-1206，1210.

［6］张超群，郑建国，钱洁.遗传算法编码方案比较［J］.计算机应用研究，2011（3）：819-822.ZHANG Chaoqun，ZHENG Jianguo，QIAN Jie.Comparison of genetic algorithm coding scheme［J］.Computer Application Research，2011（3）：819-822.

［7］金弟，刘杰，杨博，等.局部搜索与遗传算法结合的大规模复杂网络社区探测［J］.自动化学报，2011（7）：873-882.JIN Di，LIU Jie，YANG Bo，et al.The large-scale complex network community detection［J］.automation of combining local search and genetic algorithm，2011（7）：873-882.

［8］曹道友，程家兴.基于改进的选择算子和交叉算子的遗传算法［J］.计算机技术与发展，2010（2）：44-47，51.CAO Daoyou，CHENG Jiaxing.Genetic algorithm［J］.computer technology and development to improve the selection operator and crossover operator based on 2010（2）：44-47，51.

［9］赵鑫宁，喻歆，吴锡.一种基于混合概率选择算子的改进遗传算法［J］.成都信息工程大学学报，2016（3）：247-254.ZHAO Xinning，YU Xin，WU Tin.A hybrid genetic algorithm［J］.Journal of probability selection operator based on Chengdu Information Engineering University，2016（3）：247-254.

［10］董妍汝.基于选择算子的遗传算法改进［J］.办公自动化，2015（16）：59-61，42.DONG Yanru.Genetic algorithm based on selection operator to improve［J］.Office Automation，2015（16）：59-61，42.

Design of Intelligent Test Paper System Based on Improved Genetic Algorithm

GAO Lingjie
（Baoji Vocational Technology College，Baoji 721013）

Aiming at the problems existing in the test paper speed and quality of the traditional random test paper model，this paper improves the traditional genetic algorithm，and proposes a new intelligent test paper system based on improved genetic algorithm.Based on the constraint of the test paper，test paper build mathematical model，and to test individual attribute values are preserved by genetic encoding method，so as to improve the operation rate，for the test process of knowledge points to the conflict，the variation strategy and cross sectional multi point strategy for optimization，at the same time to solve the problem of population diversity，a large the ratio of crossover and mutation strategy，so as to improve the test speed.Finally with the C#language and Mysql database to achieve the test paper system，greatly improve the quality and speed of the test paper.

genetic algorithm，intelligent generating test paper，genetic coding，fitness function，test paper quality

TP391

10.3969/j.issn.1672-9722.2017.10.005

Class Number TP391

2017年4月10日，

2017年5月13日

高凌洁，女，讲师，硕士，研究方向：计算机技术。