肖衡 龙草芳 潘玉霞
(三亚学院,海南三亚 572022)
遗传算法在智能组卷中的实现
肖衡 龙草芳 潘玉霞
(三亚学院,海南三亚 572022)
遗传算法是智能化考试系统的最常用的一种组卷算法。本文介绍了遗传算法的特点及操作过程,依据组卷时各种约束建立了数学模型,提出使用改进的遗传算法解决组卷中一些问题。最后以实验证明,使用动态调整交叉概率和变异概率可避免遗传算法的一些弊端。
智能组卷 遗传算法 交叉算子 变异算子 适应度
1 引言
随着人工智能的发展和网络的普及,无纸化考试系统已成为各种教育平台的一大热点。实现智能组卷,可以避免大量的重复劳力,提高工作效率。而要实现智能组卷主要在于组卷算法的研究。在组卷算法的设计中,试题库系统的建设是非常重要的一个环节,要想生成的试卷具有高质量,在对题库设计中对难度,总分,区分度,章节百分比,题型百分比,层次百分比等参数的设定非常重要。智能组卷是从题库中随机抽取题实现组合,其本质是典型的多约束问题求解的过程。而想让每次组卷的效率与质量都尽量接近用户的期望值,模拟自然进化过程群体搜索自适应调整策略的遗传算法能为多目标优化提供非常合适的解决方案。
2 遗传算法简述
遗传算法是一种并行的、能够有效优化的算法,以Morgan的基因理论及Eldridge与Gould间断平衡理论为依据,同时融合了Mayr的边缘物种形成理论和Bertalanffv一般系统理论的一些思想,模拟达尔文的自然界遗传学:继承(基因遗传)、进化(基因突变)优胜劣汰(优的基因大量被遗传复制,劣的基因较少被遗传复制)。其实质就是一种把自然界有机体的优胜劣汰的自然选择、适者生存的进化机制与同一群体中个体与个体间的随机信息交换机制相结合的搜索算法。运用遗传算法求解问题首先需将所要求解的问题表示成二进制编码,然后根据环境进行基本的操作:选择selection,交叉或重组基因crossover,变异mutation,适应度函数fitness operation……这样进行不断的所谓“生存选择”,最后收敛到一个最适应环境条件的个体上,得到问题的最优解。
遗传算法求解过程的主要操作如下:
2.1 编码
遗传算法在求解过程,先将问题进行二进制编码,形成基因型串结构数据,体现种群的多样性,提高算法的搜索能力。该过程需要两大问题,一是编码的长短对数据精度和搜索空间的影响;二是选择性的随机特,造成局部搜索能力弱小的问题。
2.2 选择
选择是根据个体的相对适应值,计算个体的再生次数,确定系统重组或系统的交叉个体,选择父代个体,产生子代个体。常用的系统选择算法有轮盘赌选择、随机遍历抽样、局部选择等。
2.3 交叉或重组基因
交叉操作是种群之间的交叉,随机选择两个群体,随机确定交叉处,按一定概率进行基因交换,再互换形成新的种群。
交叉有二进制交叉、单点交叉、多点交叉、洗牌交叉等
基因重组是结合继承父代交配信息产生个体,常有离散重组、扩展性重组、中间重组、线性重组等。
2.4 变异
变异是随机选择种群中一个染色体,按一定概率进行基因变异。
2.5 适应度函数
可以直接引用目标函数或是变异后的目标函数作为适应度函数,利用适应度函数搜索空间内的解,并计算个体的适应度。
3 智能组卷算法研究
在智能组卷中,抽题样本希望能合理全面考察学生的综合能力,题型应涉及几个方面:题目、题型、章节覆盖、区分度、难度系数、分值、时间。而要得出期望效果,事先需给出理想试卷的评估标准,以评估标准组成一个MxN的矩阵,将组卷问题变成求解空间的过程。在实践证明中发现,约束条件越多,要求越严格,组卷的难度就越大,而且过多的约束条件会降低组卷的成功率。一般情况组卷约束有:
K约束,知识点约束,涉及章节覆盖和分值比例。
TP约束,题型约束,指明试卷中的题型,如选择题、简答题、判断题等。
M约束,题数约束,表示该试卷中各题型的数量总和。
D约束,难度约束,针对考试对象选择不同的难度。
Q约束,区分度约束,体现考生对知识掌握的水平的高低。
B约束,曝光度结束,控制试题反复出现的次数。
T约束,考试时间约束,一般与题量成正比。
4 组卷数学模型型
将以上七种约束结合起来构建数学模型,在这些约束中找出若干个可行性解的过程就是组卷的过程。如果用n表示一套试卷的题数,则mx7的矩阵表示一套试卷
多个解中的某个候选解可以如下
章节 题型 分值 难度 区分度次数 时间
0001 选择 2 容易 差 1 2
…… …… … …… …… … …
0012 计算10 难 良 1 10
组卷是一个多目标规划求解问题,如果将所有约束都考虑进去是不切实际的,约束过多,会影响遗传算法的组卷效率,还可能找不到可行解。要尽量减少约束,缩小模型的维数。
5 遗传算法设计
5.1 确定编码方案
在遗传算法中任何一种编码方案都是为了更好地得到优良种群。若采用二进制编码,会使遗传算法算子的操作简单易用。但试题库信息量较大时,染色体会过长,则会产生许多不利因素,需要改进编码方案,采用十进制编码。因而要根据种群的大小和多样性来确定最优的编码方案。
5.2 确定适应度函数
遗传算法中评价个体的优劣,是由适应度值决定的。设计适应度函数对各约束条件所产生的偏差进行记录,适应度值最高,种群越优。通常在遗传算法中引用权重对各约束条件进行不同侧重点的定理分配,然后将各约束条件产生的实际偏差与各权重之积进行累加,来设计适应度函数。
5.3 确定遗传算子
遗传算法选择算子有许多种,选择依据都是适应度值,选择适应度值高的个体进入下一代。目前最经典的是轮盘方式,轮盘任意旋转后停下来时,指针所指区域则被选中。这种选择算子中个体适应度值越高,被选中的概率越高,能很好地保护优良个体,将适应度大的种群进行复制。
5.3.1 交叉算子
本文采用了段间交叉算子,也称为群体内交叉,表现为整个染色体多点交叉。由编码方案中确定了每一种题型的染色体都是独立的,假设A表示选择题,则A11、A12、A13都是单选题,B、C、D分别表示填空题、判断题、计算题。交叉之前随机产生两个父代个体,两个父代个体进行段间交叉。假设两个父代个体如下:
F1＝A11A12A13A14A15A16|B11B12B13B14B15|C11C12C13|D11D12
F2＝A21A22A23A24A25A16|B21B22B23B24B25|C21C22C23|D21D22
再随机产生一个0到1之间的数字,当这个数字小于等于交叉概率时,确定交叉点。假设四种题型的交叉点分别是4、2、2、1,产生的子代则是:
S1＝A11A12A13A14A25A26|B11B12B23B24B25|C11C12C23|D11D22
S2＝A21A22A23A24A15A16|B21B22B13B14B15|C21C22C13|D21D12
为了保证种群数量不变,F1与S1,F2与S2分别进行比较,适应度值高的保留,值低淘汰。
5.3.2 变异算子
变异操作是在种群中随机选中一个变异位,将该位置的编码取反,使算法具有局部随杨搜索功能,增加群体多样性。本文采用单个染色体单点变异。选随机产生随机数,与变异概率进行比较,若小于等于变异概率则变异。假如该题是选中状态,变异后则变成未被选中,再随机选取一个未被选中的置为选中状态。
通常为避免遗传算法中“早熟收敛”现象,加快搜索效率和防止局部最优,需要根据种群的遗传进化情况来动态地调整交叉概率和变异概率。
6 实验数据
将5个章节的500道题分别赋予各种特征值,给出生成试卷的要求,分别使用遗传算法进行实验。成批生成10套试卷,要求任两套间的重复率不超过5%,每题被抽的最大次数是3次。总分100分,用时90分钟,种群大小50,试卷区分度为0.5,难度0.5,最大迭代次数100,交叉率为0.6。(如表1)
表1 变异率对算法的影响
从实现结果看出变异率在0.002－0.004时,能产生适量的新个体,适当地扩大解空间,得到的适应度值最低,当变异率过小,不易产生新个体,过大,产生过多新个体,适应度值偏大,容易丢失优良个体。
7 结语
使用动态地调整交叉概率和变异概率,不仅能避免遗传算法的“早熟早收敛”现象,在收敛速度、算法成功率和算法效率方面也具有一定的优势。
[1]贺荣,陈爽.在线组卷策略的研究与设计.计算机工程与设计,2011,32(6).
[2]虞耀君,等.基于遗传算法的网络考试系统.计算机仿真,2010.
[3]杨秀梅.基于遗传算法的组卷系统的研究[硕士学位论文].上海:上海交通大学,2007.
[4]张超群,等.遗传算法编码方案比较.计算机应用研究,2011年28卷3期.
[5]葛宇,梁静.基于免疫遗传算法的智能组卷系统设计.计算机应用与软件,2011,28(1).
专业智能性试题库建设—以三亚学院为例(项目编号:Syxyjy120404)。三亚市院地科技合作项目(2012YD42)。
肖衡(1979－),女,硕士,三亚学院,讲师,研究方向为计算机网络与安全。龙草芳(1983－),女,硕士,三亚学院,助教,研究方向为计算机网络与数据库应用。潘玉霞(1983－),硕士,三亚学院,讲师,研究方向智能计算与应用。
