组卷算法（共9篇）
组卷算法 篇1
0 引言
随着计算机技术的发展及计算机的日益普及,无纸化考试系统的自动组卷、自动评阅、计分、成绩存档与考试统计分析等功能将有效地避免资源的浪费,如何合理地利用试题库中的试题组成一份科学的试卷,是网上考试系统设计中的重要环节,也是一大难题,本文介绍了一种改良后的遗传算法来解决这一问题。
1 组卷算法分析
组卷算法是针对考试系统中的组卷问题所提出的一种解决问题的算法,该算法会根据考试系统对组卷问题所提出的要求,采用遗传算法思想,合理和快速地生成相应的试卷,因此,研究组卷算法的关键在于研究相关的试题参数和组卷目标,再结合遗传算法来解决问题。
1.1 试题参数说明
在组卷问题中,每一道试题都有若干个属性来描述其基本特征,被选择的试题的特征值将直接参与试题适应度的计算。下面分别介绍几个重要的参数[1,2,3]。
(1)难度:即答题的难易程度,难度越大,得分越少;难度越小,得分越多,定义为公式(1)。
式(1)中,Dqp为难度系数;Sqa为该试题所得的平均分;Sqf为该试题分值。
试卷的难度可以利用试题的难度求得,试卷难度计算公式如下:
式(2)中,Ded是试卷难度;Dqdi是第i道试题的难度系数;Sqfi是第i道试题的分值;Sef是试卷的总分;n表示该试卷有n道试题。
(2)鉴别度:是最大限度区分被试者的特性和能力的指标,区分度好的试卷,不仅对学生的特性、能力和学业水平有较高的鉴别能力,而且可以说明试题难易搭配合理,能区分学生的等级。为了估计区分度,将考生分成高分组和低分组两个组,分别统计高分组和低分组的得分率,把区分度定义为:
式(3)中,Dqp是试题的鉴别度;Rhs是高分组的得分率;Rls为低分组的得分率。
试卷的鉴别定义如下:
式(4)中,De{为试卷的鉴别度;Depi为第i道题的鉴别度;Sqfi为第i道题的分值;Sef是试卷的总分;n表示试卷有n道试题;
(3)被组卷的次数:在组卷的时候,若某一试题被抽取参与组卷,则该参数加1,该参数是控制试卷之间差异性的重要标准。也即是说,在试题个体的选取中,将则重于被组卷次数少的试题。
1.2 组卷问题分析
组卷问题是属于多目标组合优化问题,主要考虑以下几个方面[4,5]:
(1)考试的难度和平均分须尽量满足试卷参数所设定的要求。
(2)考试成绩的分布图大致成正态分布。
(3)试卷中各章节所占的比例须尽量满足试卷参数所设定的要求。
以上三个方面是组卷时需要重点考虑的对象,也即是组卷生成后的试卷必须符合以上三个条件,下文的适应度函数章节将会解决这个问题。
2 组卷算法设计
本组卷算法基本上采用了遗传算法的运算步骤,不同之处在于补充了算法的预处理过程,该过程为算法的优化提供了基础,组卷算法流程图如图一所示。
2.1 算法预处理
预处理主要是对试题的搜索空间进行筛选和排序,需要考虑的因素有:排除一部分被指定课程和章节以外的试题、排除一部分被指定题型以外的试题、排除一部分鉴别度太低的试题和排除一部分被组卷次数太高的试题。试题的搜索空间大小可以定义为:
式(5)中,SI是搜索空间的大小;Ne是试卷的试题总数。Ndb是试题库中的试题总数;k为系数,用来控制搜索空间和试卷题目数之间的关系。
2.2 编码方法
二进制编码方法是遗传真法中最常用的一种编码方法,试题库中的每一道试题都会对应着二进制串中的每一位,而二进制串的长度即是试题库所有试题的总数目,若第i位二进制位为0的时候,即说明它所对应的试题库中第i道试题没被选中,若第位二进制位为1的时候,即说明它所对应的试题库中第i道试题被选中,因此,二进制串中1的总数即代表着试卷的试题总数。这种编码方法结构清晰,容易操作,变异操作也不会出现非法解。
2.3 初始化群体
初始群体的设计主要讨论两个问题,一个是如何产生初始化群体,另一个是初始群体的规模。为了体现所生成试卷的差异性,需要考虑采用试题被组卷次数这个参数,也就是说,试题被抽取组卷的命中率与这个参数有关,试题的命中率为:
式(6)中,Rsci是第i道题根据试题被组卷次数计算出来的试题被抽取组卷的命中率;Cqsmax是试题搜索空间中最高的被组卷次数;Cqsi是第i道题的被组卷次数。
初始群体可以按试题的命中率随机抽取试题组成第一代试卷,命中率高的试题,被抽取的概率就大。接着,还要考虑初始群体的规模问题,也就是说初始群体由多少个个体组成才比较合适?考虑到具体情况,可以把群体的默认规模Sc赋值为10。
2.4 适应度函数
根据组卷问题分析,可以将组卷的三个条件转换成目标函数,也即是适应度函数。
(1)解决难度和平均分约束条件问题,其实两者是同一个问题,只要考虑试卷的难度一个条件就可以了。试卷的难度计算公式在前面公式给出,因此试卷的难度适应度函数可以表示为:
式(7)中,fda是试卷难度的适应度;Ded是试卷的难度;Dc是组卷时手工预计指定的难度;δda是试卷难度适应度的控制参数,其默认值可以设置为0.1。
(2)解决成绩分布图成正态分布约束条件问题,最关键的是要防止成绩分布图出现驼峰的形状,为了防止出现这种现状,判断所抽取的试题中,某一难度的试题的分值的和占试卷总分的比例大于某一指定比例就可以近似地达到要求。因此,该条件的适应度函数可以表示为:
式(8)中,fsa是成绩正态分布的适应度;Sqfη表示难度为η的试题的分值;Sef表示试卷的总分;n是试卷的试题数;δsa是控制参数,用来控制被指定的某一难度的试题的总分占试卷总分的比例的大小δsa的默认值可以赋值为50%。
(3)解决各章节所占的比例问题,首先得求出试卷中各章节试题分值占试卷总分的比例,公式如下:
式(9)中,Pei是第i章试题的总分占试卷总分的比例;Sqfi是第i章试题的分值;Sef是试卷总分;
根据上述计算公式,便可以求得该目标条件的适应度函数,该条件的适应度函数可以表示为:
式(10)中,fca是章节比例的适应度;Pei是第i章试题的总分占试卷总分的比例;Pci是第i章手工预设置的比例;δca是控制参数,用来控制章节比例设置差异程度,该参数的默认值赋值为20%。
通过上述三个目标函数适应度的计算公式,便可以求得试卷群体的适应度函数了,计算方式采用将以上三个适应度加权相加的方法,计算公式如下:
式(11)中,λda是fda的权重系数;λsa是fsa的权重系数;λca是fca的权重系数。这三个权重系数决定了这三个适应度的重要程度,根据实际情况,难度适应度是最重要的,因此,它大小会很大程度上影响到试卷整体的适应度,默认取值为0.5,而其它两个适应度相对次要,它们的默认取值都为0.25。试卷适应度的值越小,说明试卷的适应度越强,也就是说当试卷的适应度的计算结果大于等于0,小于等于0.1的时候,试卷可以达到比较理想的状态,这时可以继续繁殖优化,也可以结束繁殖,输出试卷。
2.5 选择算子
根据组卷问题的实际情况,采用排序选择组合和最优保存策略相结合的思想进行选择算子的设计,具体的操作过程如下:
(1)对群体中的每份试卷的适应度按由好到差进行排序。
(2)淘汰适应度最差的若干份试卷个体。
(3)计算迄今为止最好适应度的试卷,复制该试卷,即生成新的试卷个体。
(4)从试题的搜索空间中,随机产生生成新的试卷个体。
2.6 交叉算子
采用多点交叉算子的设计思想,详细的交叉算子的操作步骤如下:
(1)确定试卷个体的配对方式,由适应度最高的试卷与适应度第2高的试卷进行配对,适应度第3高的试卷与适应度第4高的试卷进行配对,以此类推,在选择算子中,新产生的试卷也相互进行配对。
(2)设置各试卷的交叉点,以题型为划分标准,分别计算试卷中各题型段中试题的适应度。
(3)在配对的两份试卷中,把各对应的题型段中适应度高的抽取出来重组一份试卷,各对应的题型段中适应度低的抽取出来重组另一份试卷。
2.7 变异算子
采用基本位变异算子,操作步骤如下:
(1)按相关的统计建议,变异算子的变异概率一般不会取值大于0.1,考虑到试卷的试题数量有限,变异算子的变异概率默认取值为0.05。
(2)对于组卷问题来说,要保证题目数的固定不变,变异的位数必定是偶数,因此要保证二进制编码串中1的个数不变,假如二进制编码串中有一位0变成1,肯定会有另一位从1变成0,而且它们都属于同一个题型段里面的,这样才能保证每一种题型的题目数也是一定的。
3 组卷算法实验
采用本算法和随机抽取算法分别组5份试卷,并将实验结果作比较,如表一所示。
实验结果表明,随机抽取算法的组卷时间比较短,可是在试卷的难度、成绩分布、试卷差异度和章节比例几个方面分析,远远比不上遗传算法。特别是试卷的难度和章节比例这两个重要的条件更是无法估算,严格上说,比较正式的考试一般都不会采取该方法来组卷,因为它不科学,也不合理。
4 结束语
现有的标准化试题库和网上考试系统的研究才刚起步,没有统一的标准,各地和各学校的具体情况不大相同,一般考试系统的设计都是结合各自的情况而研究的,因而参差不齐。同样,组卷算法更是多种多样,就算采用同一种理论来解决组卷问题,它们的详细方式和步骤也不大相同,实现的效果也是不一样的。本文充分考虑了这些差异性,并力求研究和设计出符合一般情况下的网上考试系统和组卷算法,同时对算法优化做了充分的考虑,取得了比较理想的结果。
参考文献
[1]杨青.基于遗传算法的试题库自动组卷问题的研究[J].济南大学学报(自然科学版),2004,3(18).
[2]孙勇,柏云.基于遗传算法的试题组卷策略[J].淄博学院学报(自然科学版),2002,(3):27-28.
[3]全惠云,范国闯等.基于遗传算法的试题库智能组卷系统研究[J].武汉大学学报(自然科学版),1999,(5):758-760.
[4]于晓强,刘柏等,谢益武.基于改进遗传算法的组卷策略与实现[J].微电子学与计算机,2006,23(12).
[5]焦翠珍,戴文华.基于遗传算法的智能组卷方案研究[J].微电子学与计算机,2006,23(6).
组卷算法 篇2
关于 第 批次建设用地组卷说明书
依据土地管理法律法规，我市（县）第 批次建设用地应呈报省政府审批。我局组织了相关申报材料，现说明如下：
一、土地基本情况
该批次用地涉及我市（县）的 个乡镇 个村和 个国有单位，已全部进行土地登记发证，土地产权明晰，界址清楚，没有争议。申请用地总面积 公顷，其中农用地 公顷（耕地 公顷、园地 公顷、林地 公顷、草地 公顷、其他农用地 公顷）、建设用地 公顷、未利用地 公顷；国有农用地 公顷(耕地 公顷、园地 公顷、林地 公顷、草地 公顷、其他农用地 公顷)、未利用地 公顷，地类和面积准确。
该批次涉及 个地块。其中1号地块拟用征收 村集体土地 公顷、村集体土地 公顷，拟开发用途为（按《土地利用现状分类》细分到二级地类）；2号地块……（逐地块描述）。
二、用地规划计划情况
该批次用地符合土地利用总体规划，使用 下达我市（县）的用地计划指标，其中农用地 公顷（耕地 公顷）、未利用地 公顷。
三、征地补偿安置情况
该批次征地补偿标准按照《河北省人民政府关于实行征地区片价的通知》（冀政[2008]132号）规定执行，共涉及 县（市、区）个区片。其中 区片，区片价为 万元/公顷，面积 公顷； 区片，区片价为 万元/公顷…….。加上青苗补偿费 万元、地上附着物补偿费 万元，征地补偿费用共 万元。
征收土地需安置农业人口 人（其中劳动力 人），征地前村人均耕地 亩--亩，征地后人均耕地 亩--亩（涉及村较多的附征地前后人均耕地变化情况表）。我市（县）计划通过货币安置 人、用地单位安置 人、……（其他安置途径与人员）。本次征地后人均耕地少于0.5亩的涉及 个村，我市（县）采取 等措施，可以妥善安排被征地农民的生产和生活。
四、社会保障费用落实情况
根据《河北省人民政府关于实行征地区片价的通知》（冀政[2008]132号）规定，我市（县）征收农用地，已按照征地区片价的 %，落实了社会保障费用 万元，已缴入当地社保资金专户。用地批准后，按有关规定要求将符合条件的被征地农民纳入社会保障体系，可以做到被征地农民原有生活水平不降低，长远生计有保障。
（不涉及社保费用的，表述为：该批次用地，并涉及征收集体农用地，根据《河北省人民政府关于实行征地区片价的通知》（冀政[2008]132号）规定，不需落实社保费用。）
五、征地程序履行情况
我局按规定履行了征地报批前告知、确认程序，被征地村集体经济组织和农户对征地方案中的征地位置、土地权属、地类和面积以及补偿标准、安置途径等无异议，没有提出听证申请。
（被征地村组和农民提出听证申请并组织了听证会的，表述为：我局按规定履行了征地报批前告知、确认程序、被征地村集体经济组织和农户提出听证申请。按照《国土资源听证规定》要求，我局于 年 月 日在（地点）组织听证会。被申请人提出的 等合理要求已采取 等措施妥善解决。）
六、补充耕地落实情况
该批次占用耕地 公顷，申报用地前，落实了补充耕地。补充耕地位于 县 乡，挂钩的土地整治项目为 项目、项目，均已经省国土资源厅核实合格，并在农村土地整治监测监管系统中备案，对应项目编号分别为、……。
（不需要补充耕地的，表述为：该批次用地不占用耕地，不需补充耕地。）
七、新增建设用地土地有偿使用费落实情况
该批次用地涉及城市（含建制镇）建设用地范围内新增建设用地 公顷，其中： 等别 公顷、等别 公顷，共需缴纳新增建设用地土地有偿使用费 万元。我市（县）人民政府承诺在批准用地后按有关规定及时足额缴纳。
（不涉及缴纳新增建设用地土地有偿使用费的，表述为：该批次不涉及城市（含建制镇）建设用地范围内新增建设用地，按规定不需缴纳新增建设用地有偿使用费。）
八、信访与违法用地处理情况
年 月，（信访人）来信（访）反应该批次用地（信访具体内容）。我局进行了认真调查处理，（处理具体措施）。目前，信访群众反映的问题已得到妥善解决，信访人表示不再上访。
年 月，（违法主体）未经批准，非法占用土地 公顷，其中耕地 公顷，含基本农田 公顷。我局于 年 月 日，对该违法用地行为作出处罚决定：。年 月 日，我局向 机关提出对 的 处分建议。年 月 日，我局向 法院提出了强制执行申请书。截止 年 月 日，各项处罚、追究均已到位。
（不涉及信访与违法用地的，表述为：经我局调查核实，该批次用地不涉及信访与违法用地。）
综上所述，该批次用地报批资料齐全，申报内容真实，符合土地管理法律法规和政策规定。请予审查。联系人：（电话）
组卷算法 篇3
关键词:试题库;组卷;遗传算法;伪并行;精英个体
中图分类号:TP18文献标识码:A文章编号:1000-8136(2009)17-0091-03
在国内,近年来题库的建设受到高度重视。目前,题库系统有3类:基于单机、基于局域网和基于WEB。基于单机的系统已经逐渐被淘汰,其缺点是题库的建立和维护非常困难;基于局域网的系统通常用于比较严格的考试,基本上都是由某一重要的大机关封闭运行,缺乏开放性,无法真正在教学过程中发挥其应有的作用。基于WEB的系统具有集中管理、共享使用、简单易用、开放性强的特点,可提供考试、自测、联机评卷等多项功能,还能提供强大的统计与分析功能,揭示全方位的教学过程信息。相对来说,现在的开发主流为基于WEB的系统。而作为该系统的组卷策略因其在整个系统中的核心地位成为研究的热点。
遗传算法是一种模拟自然选择和遗传机制的全局概率寻优算法,它的寻优过程是一个迭代过程,通过基因遗传机制将每一代的基本特征遗传到下一代。该方法能解决随机算法的盲目随机性,能从群体中选择更满足条件的个体,具有很强的智能性。同时,由于遗传算法具有内在的并行性,不会出现像回溯试探法一样计算量大的问题。许多研究人员对基于遗传算法的试题生成方法作了深入的研究,取得了比较好的效果。本文对标准的遗传算法进行了改进,提高了试卷生成的效率。
1 组卷问题分析
1.1 试题命题的基本原则
1.1.1 目的性原则
考试的功能是多方面的,目的不同,试卷编制的结构和试题的难度就不同。前面提到,平常的检测主要是诊断教学内容的掌握情况,期中、期末考试则主要是考查考生的学习水平。
1.1.2 科学性原则
编写的试题不但要求其本身没有科学性和知识性错误,而且试题表述要规范,尽可能采用学科术语。
1.1.3 简洁性原则
试题的语言表达要简洁、精练,每道试题应该清楚地提出一个或几个独立而明确的问题,学生阅读题干后能够明确他们要解答的内容,不存在理解题意的障碍。
1.1.4 层次性原则
层次性原则就是根据学生认知结构的差异性、教材内容的难易度、教学大纲要求,编制的试卷必须具有一定的梯度。
1.1.5 创新性原则
创新性主要体现在试题的新颖性上,而试题的新颖性则主要反映在取材的新颖性、创设情境的新颖性、设问的创新性以及考查角度的独到性等方面。严格来讲,在一份试卷中,至少应有20%~
30%的试题是新命题才算较好地体现了创新性原则。
1.2 试题分析
在智能教学系统的研究中,一个非常重要的课题是怎样在已生成的题库中自动生成满足教学和教师要求的试卷。通常,全部试题按内容分为若干篇章、题类和多个细目,每一道试题又包含多个属性,但过多的约束条件会增加实际自动组卷的难度、降低效率。由于多约束条件的重要性是不一样的,且它们之间存在内在的联系,有必要选择一些核心属性作为组卷的约束条件(总时间、试卷分数、试卷难度系数、题型比例、能力层次、知识点、区分度、已被选择次数、最近被选时间等),具体属性定义如下:
(1)题型:用正整数1～6分别代表选择题、填空题、判断题、简答题、作图题和计算题。
(2)难度系数:设P为试卷的难度系数,x为试卷平均分,w为试卷满分,则试卷的难度为: p=1-(1)
试题的难易程度分五级,难:0.8～1.0,较难:0.6～0.8,中等:0.4～0.6,较易:0.2～0.4,易:0.0～0.2。
(3)区分度:取值1～3,分别表示优秀、良、差3种状态。
(4)知识点:某道题属于某门课程的哪个知识点。用1～20代表学科的20个知识点。
(5)分值:某题的分数。
(6)答题时间,估计该题所需的时间。
(7)已被选择次数:某题被选重的次数。
(8)最近被选时间:某题最近被选的时间。
1.3 组卷模型的建立
组卷主要是根据给定的约束条件(总时间、试卷分数、试卷难度系数、题型比例、能力层次、知识点、区分度等)从大量的试题库中抽取出最优的试题组合,由此可见,组卷问题是一个具有多重约束的组合优化问题。因此,组一份m道试题的试卷,并且每道试题有n项属性,就相当于构建了一个m×n的目标矩阵。(本论文n=6)。
目标矩阵应满足以下的约束条件
(由用户给定,即试卷分数的约束);
(由用户给定,即试卷难度约束);
(由用户给定,即试卷区分度的约束);
我们设定整套试卷综合指标f来反映与用户要求的误差,实际试题生成工作中,上述各项指标的重要程度是不相同的,因此,整卷指标f就是各项指标与用户要求之间误差的加权和,为了避免各个误差的相互抵消,各指标与用户要求的误差都取绝对值,可以用如下方式表示:f=wi(e1+e3+e4)+w2e2+w3e5。(9)
在公式中wi表示第i个指标的权值,ei表示第i种约束条件与目标值的偏差(取绝对值)。
1.4 遗传算法求解
1.4.1 编码
采用分组实数编码策略,试卷初始种群也不是随机产生,而是根据题型比例、总分的要求随机产生,使得初始种群已经满足了题型和总分的要求。
1.4.2 选择操作
选择操作的目的是为了从当前群体中选择优良的个体,使它们有机会作为父代为下一代繁殖子孙。本文采用赌轮选择。
1.4.3 交叉操作
由于分段实数编码,结合单点交叉和一致交叉,我们采用段内/段间两种交叉方式实现种群中个体的交叉操作,具体操作方法如下:
(1)仿照单点交叉操作的一、二步,对种群中个体进行配对,并对每一对配对个体随机设置一个交叉点。
(2)根据交叉点所在的位置进行段间/段内交叉操作。
1.4.4 变异操作
本文将采用自适应变焦变异,以加强变异算子的局部搜索能力。
1.4.5 精英保留策略
在遗传算法搜索的过程中,对其所发现的最佳个体作适时“记录”,则全局最优个体总能被找到。在遗传算法中耦合这种最佳个体记录的策略,被称之为精英保留策略。
1.4.6 算法的基本流程
步骤1分段实数编码。
步骤2复制:为了避免最优基因丢失,提高全局收敛性和计算效率,将适应值最优的m条染色体复制到精英个体序列库中。
步骤3选择、分组:随机将种群按比例分组,并行进行改进的遗传算法和标准遗传算法的遗传操作(选择、交叉、变异);各组的最优值通过迁移算子传给下一代。
步骤4交叉。
步骤5变异。子代中,两种遗传算法伪并行运算,相互之间通过迁移算子进行信息交换,得出子代个体,选出同样数目的最优染色体与精英个体序列库进行比较,取50%高适应值的个体保留在库中,其余留给子代。
步骤6判断是否满足收敛准则,满足,输出搜索结果;否则,执行第二步。
改进的遗传算法的基本流程图见图1。
2 结论
我们通过模拟题库在MATLAB平台上对算法性能进行测试,以课程《电路基础》试卷为例。在测试中,题库中共设置4种题型,整个试题库根据题型分为4部分,每个题型对应的试题表中的试题数分别为100、100、50、50。各题的属性已经事先设定好。
取群体规模为50,对比标准遗传算法与改进的伪并行遗传算法在生成满足要求的组卷系统中的应用,见表1。
从实验结果可以看出,改进的伪并行遗传算法能更有效地解决试题库智能组卷问题,与其他方法相比,它能较早地找到满足条件的群体。同时,本文也为解决类似于该问题的多重约束目标的问题提供一种新的、有效的途径。
Research on an Intelligent Generating Papers based on the
Improved Pseudo-Parallel Genetic Algorithm
Guo Lixin,Xie Keming
Abstract:The traditional way of test paper composition has many flaws, for example the time test paper composition needed is long and the efficiency is low. This paper proposed a improved Pseudo-Parallel Genetic Algorithms, it needs short time in test papers composition and has a high success ratio, and has fine function and usability. Simultaneously it improved the test papers’ quality and the test becomes more scientific and objective, has a vital practical significance to implement the work smoothly.
运用遗传算法进行智能组卷 篇4
智能组卷是一个典型的多条件约束优化问题, 组卷时通常考虑的约束有试卷分数、试卷题型、试卷难度系数、能力层次、教学要求、区分度等约束。因此, 组卷中的一道试题应由n项指标决定, 要生成一份试卷, 就应决定一个m×n的矩阵。假设从题库中抽取n道试题, 每道试题由五个属性 (题分a1, 题型a2, 所需时间a3, 难度a4, 知识点a5) 决定, 则可生成这样的矩阵:
以上问题求解中的目标状态矩阵为例, 目标矩阵应满足如下约束条件:
1. 试卷总分:一般由用户给定, 设试卷总分为M, M满足公式 (1) :
2. 题型分数:
组卷过程中的题型主要包括单选题, 多选题, 填空题, 断判题, 简答题等, 设T为第m种题型要求的分数, T满足公式 (2) , 当试题题型编号ai2属于第m种题型时, tm为1, 否则为0;
3. 平均难度:
平均难度一般由用户给出, 本文取容易、较容易、中等、较难、难5个难度级别, 难度系数, 设D为平均难度, 则D满足公式 (3) :
4. 知识点分数:
设S为第m个一级知识点的要求分数, S满足公式4.4, 当知识点ai5属于第m知识点时, sm为1, 否则为0;
5. 答题时间:
设T为答题时间, 则T满足公式 (5) :
可以看出, 组卷问题是一个多目标的最优求解问题。在组卷过程中, 并不是约束条件越多就越好, 过多的约束条件反而会增加组卷难度并降低组卷效率, 因此在系统试题库的初期阶段选取了以上五个约束条件, 随着系统的不断完善与用户量的增加, 可以再考虑其它约束条件。
(二) 组卷算法设计
自动组卷是根据用户给定的约束条件搜索试题库中与特征参数相匹配的试题, 从而抽取最优的试题组合。目前常用的组卷方法有随机抽取组卷算法、回溯试探组卷算法、遗传组卷算法。随机选取法是根据组卷状态空间的控制参数, 由计算机提供的随机函数随机的从试题库中抽取一道试题进行组卷, 之后不断重复此过程, 直到组卷完毕, 或者无法从试题库中抽取满足参数的试题为止。这种算法结构简单, 但具有很大的随机性和不确定性, 易于陷入局部最优解和求解速度慢的情况;回溯试探组卷法是将随机选取法产生的每一状态类型纪录下来, 当搜索失败时释放上次纪录的状态类型, 然后再依据一定的规律变换一种新的状态类型进行试探, 通过不断的回溯试探直到试卷生成完毕或退回出发点为止。这种算法对于题量较少的试题库组卷成功率较高, 但却不能很好地在全局范围内搜索, 同时也存在组卷时间很长, 程序结构相对比较复杂的特点。
从以上分析可以看出, 随机抽取组卷算法和回溯试探组卷算法并不能很好地实现组卷要求, 遗传算法是一种新发展起来的并行优化算法, 它很适合解决自动组卷问题。
1. 遗传算法原理
遗传算法起源于60年代对自然和人工自适应系统的研究, 最早由美国密执安大学的Holland教授提出, 遗传算法把问题的解表示成“染色体”, 在算法中以二进制编码表示, 在执行遗传算法之前, 先给出一群“染色体”的假设解, 再将这些假设解置于问题的“环境”中, 通过评价函数从中选择出较适应环境的“染色体”进行复制, 再通过交叉, 变异过程产生更适应环境的新一代“染体”群。如此反复, 经过一代又一代地进化, 最后收敛到最适应环境的一个“染色体”, 它就是问题的最优解, 遗传算法基本原理图如图1所示。
2. 遗传算法基本操作
遗传算法有三个基本操作:选择、交叉、变异。这些操作又有不同的方法来实现
(1) 选择
又称为再生操作, 可以加强群体中个体的适应性, 它的作用是根据每个个体的优劣程度 (如适应度函数值) 来决定其是被留下还是被淘汰。一般来说, 适应度高的个体存在的机会较大, 而适应度低的个体存在的机会较小。
常用的选择算子比例选择方法, 它首先根据个体的适应度值与当前种群中所有个体的适应度值总和的比值, 计算出每个个体的相对适应度, 该值反映了个体的适应度值占整个群体个体适应度值总和的比例, 值越大, 个体被选择复制到下一代的可能性就越大。
目前遗传算法中最经典的选择方法是轮盘赌选择法, 它是是根据比例选择方法来设计的, 其基本思想是:每个个体被选中的概率与其适应度大小成正比。
(2) 交叉
遗传算法中由于交叉算子具有全局搜索能力, 因而作为主要的操作算子。交叉算子是在基因交换的基础上加入基因对之间的算术运算而构造出来的, 能够使优良个体的特性在一定程度上保持。常用的交叉算子有单点交叉、二点交叉、多点交叉、均匀交叉等等。单点交叉是最简单的交叉, 它首先对染色体群中的个体进行随机配对, 在配对个体中随机设定交叉处, 再配对个体彼此交换部分信息。对于实数编码的遗传算法, 算术交叉操作算子多采用传统的中间重组的方法。
例如有个体S1=100100, S2=110111, 选择它们的左边4位进行交叉操作, 则有S1=110100, S2=100111
(3) 变异
在遗传算法的应用中, 变异操作可以维持遗传算法中群体的多样性。由于选择和交叉操作基本上已经完成了大部分的搜索功能, 所以变异操作主要用来增加找到接近最优解的能力, 它的存在对避免遗传算法的搜索过程陷入局部最优解和保证算法的全局收敛性至关重要。
主要的变异算子有基本变异算子、均匀变异、正态变异、自适应变异。变异操作是按位进行的, 即把某一位的内容进行变异, 如在二进制串的每一位中, 原先为1时, 产生变异就是把它变成0, 反之亦然。
如有个体S=101010。对其的第1, 3位置的基因进行变异, 则有S=000010。
执行变异算子操作可维持种群的多样性, 使算法更好地在全局范围内搜索, 防止“早熟”现象发生。在执行完交叉操作后, 由于题型中的每一题号己确定, 所以产生的随机数不会超过该题型的题号范围, 如果该随机数己被个体选中过, 则应重新产生随机数, 直到产生的题号与该个体包含的题号不相同。
(三) 遗传算法在组卷中的应用
基本遗传算法可定义为一个8元组:SGA= (C, E, P0, M, Φ, Γ, Ψ, T) 其中C为个体的编码方法;E为个体适应度函数;P0为初始群体;M为群体大小;Φ为选择算子;Γ为交叉算子;Ψ为变异算子;T为算法终止条件。
1. 染色体编码
用遗传算法求解问题, 首先要将问题的解空间映射成一组代码串。一般采用二进制编码方案, 该方案中用1表示被选中的题, 用0表示未被选中的题, 这种编码简单明了, 但是这样的二进制位串较长, 在进行交叉和变异遗传算子操作时, 各种题型的题目数量不好控制, 而且随着试题库题量的增多, 使得染色体长度不断增加、复杂化, 降低了算法的运行速度。因此可将二进制编码方案改成十进制分段编码方案, 每一份试卷对应一个由题号, 每种题型的题号放在一起, 按题型分段, 在随后的遗传算子操作时也按段进行, 保证了每种题型的题目总数不变。
如果试题库中含有200道选择题、500道填空题、200道判断题, 则它的编码方式如表所示:
2. 初始化群体
初始化群体指选择一个串或个体的集合作为问题假设解的集合, 试卷初始种群根据题型比例、总分的要求随机产生, 群规模的大小可以决定组卷速度, 当种群规模较大时组卷收敛速度较慢, 但易搜索到全局最优解, 而种群规模较小时组卷收敛速度快, 却不易搜索到全局最优解, 因而一般取种群规模为30~160, 并且初始种群在解空间中应尽量分散。
另外, 为了比较初始个体与最优个体的适应度值, 即试卷的质量, 在初始种群产生后需计算每个个体的适应度值, 然后将该值显示出来。
3. 确定适应度函数
适应度函数是用来评判试卷群体中个体的优劣程序的指标, 它要求应能反映待求解问题的特征。遗传算法利用种群中每个个体的适应度值进行搜索。一般情况下, 适应度函数是由目标函数转换而成的, 适应度值越大的个体越好。实际应用中, 通过设定整卷指标F来综合反映生成试卷的5个指标与用户要求的误差, 由于它们的重要程度不同, 所以整卷的指标F就是5个指标的加权和, 同时为了避免各个误差相互抵消, 这5个指标与用户要求的误差都取绝对值, 可以表示为:
其中fi表示第i个指标与用户要求的误差的绝对值, wi表示第i个指标的权值, 组卷就是从题库中抽取试题, 使得整卷指标F最小。
4. 遗传算子的确定
选择算子是从群体中按某一概率成对选择个体, 某个体bi被选择的概率P与其适应度值成正比。
设目标函数为f, f (bi) 称为个体bi的适应度, P为选中bi为下一代个体的次数。可知, 适应度较高的个体, 繁殖下一代的数目较多, 适应度较小的个体, 繁殖下一代的数目较少, 甚至被淘汰。
交叉算子将被选中的两个个体的基因按概率Pc进行交叉, 生成两个新的个体, 交叉概率Pc如选取过大, 可能使算法变成随机搜索, 如果过小会使组卷收敛速度变慢, 一般取值在0.25~0.75之间。
变异算子是按变异概率Pm对执行变异串的对应位求反, Pm如选取过大, 同样可能使算法变成随机搜索, 而Pm过小时不易产生新的个体, 可能使算法早熟收敛, 陷入局部最优, Pm值一般取0.01~0.2。
5. 算法的终止条件
遗传算法终止条件不同于其他传统算法终止条件, 原因在于它没有利用目标函数的梯度等信息, 无法确定演化过程中个体解空间的位置, 因而无法用传统的方法来判定算法收敛与否来终止算法。常用的终止条件有三个:当搜索到最优解时;当运行次数达到最大的演化代时;当最新最大适应度值与上代的最大适应度值没有明显改进时。
在实际组卷系统中, 采取固定最大遗传代数MAX, 最大遗传代数MAX由题库中题目的个数与模型中约束条件的个数共同决定, 当算法进行MAX代遗传后停止。
(四) 结束语
大量的研究和实践表明, 遗传算法在解决复杂的带约束的优化问题时具有良好的性能。但是, 智能组卷的遗传算法的设计与实现也比较复杂, 还需进一步研究实践。
参考文献
[1]毛秉毅.基于遗传算法的智能组卷系统数据库结构的研究[J].计算机工程与应用, 2003 (6) :230-232.
[2]李海兵.智能组卷系统的研究与实现[J], 中国优秀硕士学位论文全文数据库, 2008 (5) .
[3]GOLDBERG D E.Genetic algorithm in search, optimization and machine learning[J].Adison-Wesley, 1989 (2) :97-99.
[4]BERTONI A, DORIGO M.Implicit parallelism in genetic algorithms[J].Artificial Intelligence, 1993, 61:307-314.
基于EDPSO算法实现智能组卷 篇5
1 分布估计的离散粒子群优化算法 (EDPSO)
1.1 基本的PSO算法
粒子群优化 (Particle Swarm Optimization-PSO) 是一种基于群体智能的进化计算技术, 是1995年Eberhart和kennedy博士提出的, 其思想来源于对鸟群、鱼群等群集行为的模拟[2]。PSO源于对鸟群捕食的行为研究, 设想这样一个场景:一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。它通过追随当前搜索到的最优值来寻找全局最优, PSO从这种模型中得到启示并用于解决优化问题。PSO中, 每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。粒子i在N维空间里的位置表示为矢量Xi=[x1, x2, …, xn]所有的粒子都有一个由被优化的函数决定的适应值, 每个粒子还有一个速度Vi=[v1, v2, …, vn], 决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子 (随机解) 。然后通过叠代找到最优解。在每一次叠代中, 粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pid。另一个极值是整个种群目前找到的最优解。这个极值是全局极值pgd。粒子根据这两个最优值来更新自己的速度和位置:
k是迭代次数, vundefined是粒子的速度, xundefined是当前粒子的位置。rand () 是介于 (0, 1) 之间的随机数。c1, c2是学习因子。通常c1=c2=2。
上述PSO主要适用于求解连续优化问题。Kennedy和Eberbart也提出了一个离散版本的PSO (DPSO) [3], DPSO把标准PSO的第2个方程替换为:
其中undefined为Sigmoid函数。
1.2 分布估计算法
分布估计算法的基本思想是在每一次迭代中, 依据当前优质解信息的概率分布模型来产生新解。具有概率分析的理论基础[4,5]。EDAs的基本框架可描述如下:
第一步:t=0, 随机产生初始种群Xbase (t) ;
第二步:选择, 从当前种群Xbase (t) 中根据某种选择机制选择若干粒子构成父代种群Xparent (t) ;
第三步:建模, 采用某种概率模型评估Xparent (t) 构建一个概率分布模型p (t) ;
第四步:抽样, 依据概率p (t) 分布模型抽样产生新解Xoffspring (t) ;
第五步:判断是否满足终止条件, 若满足则转到第六步;否则t=t+1, 转到第二步;
第六步:种群Xbase (t+1) 为所求解。
EDAs的核心部分是选择、建模和抽样, 它首先随机生成初始种群, 然后根据某种机制选择拥有较好目标函数值的若干个体组成父代种群, 再建立一个能反映父代种群的概率分布模型, 根据概率分布模型抽样产生新种群。EDAs的实质是抽取优质解的整体信息, 然后评估它们的分布, 再利用这种分布产生新种群。
1.3 分布估计的离散粒子群优化算法
在标准PSO的 (E) 中, ω, pid和pgd三项可以解释为随机——局部搜索项、个体历史最优信息项和全局最优项[6]。在这里选择所有个体的历史最优信息, 建立一个反映优质解分布的概率模型, 这个概率模型标识解空间中最具潜力解的区域分布信息。对于新的种群, 随机从概率模型和全局最优信息项中获取解信息, 相应的随机——局部搜索项功能, 通过变异或者通用的局部搜索算法实现。
EDAs中采用一阶统计量的UMD (Univariate marginal distribution) , 单变量边缘分布概率模型来建模[5], 评估整个解空间中优质解的分布情况。
完全按文献[7]的设计, 在EDPSO中, 第t次迭代时粒子i的位置xid (t) ∈{0, 1}。首先统计个体历史极值的每一维出现1的个体数量, 要概率模型计算出一个实值概率向量, 表示为P= (p1, p2, …, pd, …, pD) , Pd表示粒子的第d维取值为1的概率。然后, 这个概率向量P引导粒子在0-1的解空间进行。在产生下一代种群时, 以大概率β从概率向量抽样产生新解, 以小概率1-β直接复制种群全局最优解作为新解。即个体粒子的部分维值由概率向量来决定, 部分维值直接来源于群体最优个体。
EDPSO产生新个体粒子的机制是:
概率向量用下列方程 (1) 进行初始化:
在每一次迭代中, 按照PBIL (Population Based Incremental Learning, 基于人口增量学习的进化算法) 的概率更新规则更新概率向量P:
其中λ∈[0, 1]是学习率, 式中右边的pd代表上一代概率向量信息, undefined是在当代优质解估计出的新的概率信息。为了避免算法的早熟, 在抽样产生的新解上以一定的变异概率α实施按位变异来保持种群的多样性:
2 基于EDPSO的组卷方案
智能组卷是根据用户输入的组卷要求, 搜索试题库中与特征参数相匹配的试题, 生成满足用户要求的试卷。自动组卷系统理论基础涉及试卷评价指标与组卷要求、数学模型、智能组卷算法、试题库中试题属性及编码方法。本文用于测试的题库结构和组卷目标模型采用文献[1]的描述方案。
2.1 算法实现过程设计
采用文献[1]的编码方案, 按题型进行分段编码, 以缩小解的搜索空间。
第一步:初始化种群, 按组卷目标中各种题型的分值要求, 对每个独立代码段采用随机抽题的方法, 并保存所有题的个体历史极值和全局最优[7]。
第二步:用 (1) 式初始化概率向量P, 即标识题库中最具潜力解的区域分布信息。
第三步:根据文献[7]中产生新个体粒子的机制, 以大概率β从概率微量抽样产生新解, 以小概率1-β直接复制种群全局最优解作为新解。
第四步:按 (3) 式进行变异, 产生新的种群, 即新的题库。
第五步:评价新库中所有题的适应度。
第六步:比较适应度值更新当前的全体历史极值和全局最优值。
第七步:使用PBIL的概率更新规则更新概率向量P, 即 (2) 式。
第八步:同化检验处理。
第九步:判断是否满足终止条件, 若满足则结束进行过程, 完成;否则转到第三步继续迭代抽题的过程。
2.2 适应度函数
利用试题的历史信息对试题进行筛选, 历史信息控制函数[8]作为适应度函数:
f (x) =F/ (γA·λg (B) ) , 其中F表示试题的抽取标志、A表示抽取次数、B表示最近选用时间日期, g (B) 为时间转换函数, 它是B与当前组卷时间的差, γ, λ为A, B的权重系数, 反映A, B对组卷的影响程度。
2.3 避免或降低同化率
在文献[9]的组题算法实现过程中, 先将各级难度系数的试题从试题库中抽出, 并分别建立临时试题库, 然后从中抽掉知识点与其他题型重复的那些试题, 再从临时库中抽取给定的题量, 每抽一题, 删掉临时库中知识点相同的试题, 然后反复抽取试题, 直至组卷完成[9]。
这个方法可以有效避免或降低同化率 (知识点重复) 问题, 同时也可减少余下粒子的搜索范围, 提高收敛速度。所以文本也借鉴文献[9]的这种建立临时库、边抽边删的思想, 在算法的实现过程的第八步上比较检验同化的处理过程, 以避免知识点的重复。在处理同化检验过程中要考虑题库的健壮程度, 避免缺题现象, 有效控制鲁棒性。
3 组卷实验
本文以铁路《车辆检车员鉴定系统》为例, 对本文所提出的系统方案分三个阶段进行了实验:第一阶段在原始题不变, 编码方案及参数不进行完善改造的情况应用EDPSO组卷;第二阶段对题库先按专家系统和文献[9]提出的方法改进后应用EDPSO组卷;第三阶段在第二阶段基础上, 再按文献[10]对组卷目标进行满足目标检查, 然后应用EDPSO。题库规模600道题, 其中单选260题, 多选题80题, 填空100题, 判断120题, 问答题40题, 难度5级。每一阶段所用的各项参数一致:种群规模60 (试卷题量) 、每一阶段抽取试卷10套, 最大迭代次数50、题型要求及分数标准默认, 其他参数按惯例;EDPSO用到的参数:β控制产生新粒子的方式, 为了让算法具有更好的学习能力, 取β=0.9;λ学习率均衡算法的全局探索能力和局部开采能力, 为了让算法具有较好的搜索性能, 设λ=0.7;α变异率是粒子发生变异的概率, 变异的目的是为了防止算法陷入局部极小值, 变异太大会变成随机搜索, 取α=0.001。
4 结束语
实验结果表明, 将分布估计的离散粒子群算法应用于智能组卷, 可通过分布概率的调整, 较好地达到目标要求, 在组卷效率上能达到满意的效果。
参考文献
[1]Xiaoying SUN.Study on algorithm of intelligent test paper[C].2008Intermational conference on multimedia and information technology (MMIT 2008) .Published by IEEE computer society, 2008:86-89.
[2]Kennedy J, Eberhart R C.Particle Swam Optimization[C].Procee-dings of IEEE International Conference on Neural Networks.Pisca-taway, NJ:IEEE Press, 1995:1942-1948.
[3]Kennedy J, Eberhart R C.A discrete binary version of the particleswarm slgorithm[C].Proceedings of the World Multiconference on Sys-temics, Cybemetics and Informatics.Bscataway.NJ, 1997:4104-4109.
[4]Baluja S.Population-based incremental learning:A method for inte-gratin genetic search based function optimization and competieive lear-ning[J].School of Comput.Sci, Carnegie Mellon Univ, Pittsburgh, PA, Tech Rep CMU-SC-94-163, 1994.
[5]M uehlenbein H.The equation for response to selection and its use forprediction[J].Evolutionary Computation, 1997, 5 (3) :303-346.
[6]周驰, 高亮, 高海兵.基于PSO的转换流水车间调度算法[J].电子学报, 2006, 34 (11) :2008-2011.
[7]周雅兰, 王甲海, 印鉴.一种基于分布估计的离散粒子群优化算法[J].电子学报, 2008, 36 (6) .
[8]郝彦, 陈丽燕.基于题库信息的智能组卷算法[J].浙江海洋学院学报:自然科学版, 2006, 25 (2) .
[9]林雪明, 张钧良, 蒋伟.基于知识占的试题库组卷算法的建立[J].微机发展, 2001 (2) .
试题库智能组卷算法研究 篇6
1、智能组卷的数学模型
智能组卷实质上是一个多目标和多约束的组合优化问题, 通常可根据某效用函数将多个目标依照各自权重组合成单一目标来优化处理以期找到问题的近似最优解。
组卷的目标是生成多份有差别的能准确考核学生对知识的掌握情况的高质量等效试卷, 基于组卷的实际需要与问题的复杂性, 精选试题的属性定义试卷;在组卷策略中, 采用的试题相关属性定义如下: (1) 题目编号:试题的唯一标识; (2) 题型编号:主要包括单项选择题、多项选择题、填空题、判断题、名词解释题、简答题、综合题等题型; (3) 题分:试题的分值; (4) 知识点编号:试题所考核的知识点, 与科目的章节有关; (5) 难度:试题的困难程度, 分为:难, 较难, 一般, 较易, 易; (6) 考核要求编号:试题在教学内容上的要求层次, 一般分为:了解、理解、掌握、熟练掌握与综合; (7) 估时:完成该试题所需的时间, 以分钟为单位; (8) 区分度:试题对学生学习水平的鉴别能力, 分为:好, 较好, 一般, 差; (9) 选用次数:该题曾被选中的次数, 表示使用频度。
假设生成的一份试卷的试题数目为n, 试卷则由以下矩阵S决定, 其中每道试题上述的9个属性决定矩阵S某一行元素的值, 其定义如下:矩阵S=[aij], 其中aij表示试卷中第i题中第j个属性值, 且1≤i≤n, 1≤j≤9。上述矩阵S的列元素的分布分别体现了以上9种用户指定的试卷要求或者误差最小。组卷问题即可转化为一个多目标多约束的组合优化问题。
在实际应用中, 我们设定整卷指标f来综合反映这9个指标与用户要求的误差, 由于它们的重要程度不同, 所以整卷的指标f就是9个指标的加权和, 同时为了不至于各个误差相互抵消, 这9个指标与用户要求的误差都取绝对值。可以用下式表示:
其中fi表示第i个指标 (即所有第i列) 与用户要求的误差的绝对值, wi表示第i个指标的权值。组卷的目标就是使整卷指标最小, 或者尽可能小。[1]
2、试题库结构设计
在试题库系统的建设中, 试题库的结构设计是至关重要的, 良好的试题库结构往往会收到事半功倍的效果。本文建立了一个能使用遗传算法智能组卷的试题库管理系统, 建立了以下试题库数据模型:
(1) 题目内容表 (试题编号、题目内容、答案、备注) ;
(2) 题目属性表 (试题编号、所属课程、题型编号、难度系数、认知层次、知识点、区分度、答题时间、抽题标记、备注) ;
(3) 题型表 (题型编号、试题类型) ;
(4) 题目其他情况表 (试题编号、出题人、出题时间、有效期) ;
(5) 题目反馈情况表 (试题编号、答对率、良好率) ;
(6) 组卷方案表 (方案编号、课程名称、编制教师、目标难易程度、目标区分度、题目数量) ;
(7) 组卷方案明细表 (方案编号、试题类型、题目数、分值、总体顺序) ;
(8) 组卷方案章节分布表 (方案编号、所属章节、所占比例) 。
另外, 还可建立一些诸如知识点设置情况表、大纲设置情况表等辅助支持数据库, 以方便组卷算法的实现。
3、遗传算法组卷
3.1 遗传算法原理
遗传算法GA (Genetic Algorithms) 由美国学者J.H.Holland于1975年首先提出, 它是一种模拟自然界生物进化过程的计算模型。它的求解问题是从多个可行解开始, 然后通过一定的法则进行迭代以产生新解, 直到得到最优结果。就实质而言, 遗传算法是一种具有自适应调节能力的搜索寻优技术。遗传算法同时具有简单通用、鲁棒性强、内在的并行性以及应用范围广等显著特点, 能有效地解决计算量大的问题, 这些都适宜于处理试题库组卷的问题。
简单遗传算法的主要步骤可描述如下:
(1) 基因编码;
(2) 初始群体生成;
(3) 群体中个体适应度函数值的计算;
(4) 对群体中个体进行遗传操作 (即选择、交叉和变异) ;
(5) 适应度函数值的再次计算;
(6) 如果满足停止搜索判据, 迭代停止, 输出问题的最优解;否则, 转向步骤4。
3.2 基于遗传算法组卷
3.2.1 确定编码方案
用遗传算法求解问题, 一般不是直接在问题的解空间上, 而是利用解的某种编码来表示的。在智能型试卷自动生成系统中, 由于在建库时为每种题型建立了一个库文件, 故每种题型可各自独立编码。因此, 编码方案可采用分组实数编码策略, 就是根据各个题型各自进行实数编码, 然后对每一个题型再采用传统二进制编码策略进行处理, 但题型组之间的编码是独立的, 每组编码反映一种题型。这样, 可以克服以往采用二进制编码搜索空间过大和编码长度过长的缺点。
3.2.2 生成初始群体
为了加快遗传算法的收敛并减少迭代次数, 试卷初始种群不是完全随机的方法产生, 而是根据题型 (或各篇章内容或各考查点) 所占分数比例、总分的要求随机产生, 使得初始种群已经满足了题型 (或篇章或考查点) 和总分的要求。
3.2.3 适应度函数的确定[2]
适应度函数的选择是影响智能组卷算法性能好坏的关键。在一般情况下, 适应度函数是由目标函数变换而成的, 在遗传算法中是以适应度大小来区分群体中个体的优劣, 其值越大个体越好。依据组卷原则, 目标函数是越小越好, 而适应度函数则是越大越好, 所以要将目标函数转换成适应度函数。因指数比例既可让非常好的个体保持多的复制机会, 同时又限制其复制数目, 以免其很快控制整个群体, 提高了相近个体间的竞争, 故采用指数比例变换方法将其转换为适应度函数。采用指数变换法:f=e-af, 这种变换法的基本思想来源于模拟退火过程, 其中的系数a决定了复制的强制性, 其值越小, 复制的强度就越趋向于那些具有最大适应度的个体。
3.2.4 遗传算子的改进
3.2.4. 1 选择算子
本文采用轮盘方式复制对象。轮盘算法可以简单地描述如下:[3]
(1) 依次累计群体内各个体的适应度, 得到相应的累计值S, 最后一个累计值为Sn;
(2) 在[0, Sn]区间内产生均匀分布的随机数R;
(3) 依次用Si与R进行比较, 第一个出现Si大于或等于R的个体i被选为复制对象;
(4) 重复 (2) , (3) , 直至满足所需要的个体数目。
3.2.4. 2 交叉算子
通过在群体中随机挑选两个染色体, 并随机在染色体中央某一点进行点交换从而得到下一代的新个体, 完成交叉的工作。在分段遗传算法的组卷过程中, 考虑到组卷最终必须满足题型题量的要求, 本文按照题型的变化采用分段进行操作, 每种题型对应染色体中的一个独立分段, 在段间进行交叉。
3.2.4. 3 变异算子
变异算子也改进为在同一题型组内进行有条件的单点变异, 即个体的每一个基因座上的基因都按设定的变异概率Pm, 在一定范围内 (与该基因题型相同且考查点与本个体其他基因的考查点不重复) 变异。通过变异算子可以达到局部搜索的目的。
3.2.5 遗传算法控制参数[4]
遗传算法中的交叉概率Pc和变异概率Pm的选取对算法的性能有重要的影响, 如果Pc和pm过大, 可能使算法变为随机搜索;而Pc过小, 会使搜索过程缓慢, Pm过小, 则不易产生新的个体结构, 可能使算法早熟收敛, 陷入局部最优。为了加快遗传算法的搜索效率和有效地防止其陷入局部最优, 同时保护优良试卷个体, 根据种群的进化情况来动态地调整交叉概率Pc和变异概率Pm, 这种遗传算法在保持试卷群体多样性的同时, 保证遗传算法的收敛性并防止遗传算法陷入局部最优。在试题组卷中采用了如下公式进行自适应调整:
其中, Pc是交叉概率, Pm是变异概率, fmax为群体适应函数最大值, favg为群体适应函数的平均值, f为两个交叉个体中的适应函数值较大的一个, f'为变异个体的适应函数值, a、b为概率系数a≤1, b≤1。
3.2.6 最优个体保存策略
进行选择、交叉、变异操作后, 比较新一代最好个体与上一代最好个体适应度值, 如下降, 则用上一代最好的换新一代最差个体, 此策略可保证最优个体不被选择、交叉、变异操作所破坏, 它是遗传算法收敛性的一个重要保证条件。
3.2.7 终止条件
(1) 出现种群满足组卷约束要求时 (个体的适应度值达到预先设定值) ; (2) 进化中连续若干代中的最优个体不被替换所持续的代数超过某一设定值, 则迭代停止; (3) 达到设定的最大迭代数时, 则迭代强制停止;
4、仿真实验
在本实验中, 将1000道试题按要求分别赋予各项特征值存于试题库中, 给出要生成的试卷的要求, 分别用传统的遗传算法和本文提出的改进式遗传算法对我们开发的多媒体医学影像在线考试系统进行实验。实验环境是:CPU主频2.4 GHz, .NET平台, 1G内存。由于组卷是组成一份误差在可接受范围内的试卷, 并非要求此试卷的整体指标一定是全局最优, 因此在实验中试卷总分、试卷题型分布及各题型试题量分布这两个约束要求没有误差, 而在试卷难度系数、区分度等上的一定范围内的误差是可以接受的。设交叉概率Pc=0.6, 变异概率Pm=0.07, 实验了100次, 得到结果如下:对于传统遗传算法:成功组卷次数64, 平均迭代次数389, 平均组卷时间 (s) 62;对于本文改进的遗传算法, 成功组卷次数85, 平均迭代次数57, 平均组卷时间 (s) 35。
5、总结
本文采用改进的遗传算法实现了组卷系统, 已应用到我们开发的医学影像在线考试系统。下一步研究的方向是融合教育测量理论更好的遴选好的组卷因素, 应用到无纸化网络自动考试中, 实现一个完整的网络化教学系统。
摘要：本文讨论了适合于智能组卷的数学模型、数据库结构、并将遗传算法应用于在线医学影像试题库系统的智能组卷中。
关键词：智能组卷,数据库,遗传算法,试题库,在线考试
参考文献
[1].刘艺.自动组卷算法的研究[J].渤海大学学报, 2005, 26 (2) :124-127
[2].荆霞.网上考试系统自动组卷功能实现[J].南京审计学院学报, 2009, 6 (1) :90-92
[3].陈宇.启发式遗传算法组卷模型研究[J].计算技术与自动化, 2006, 25 (1) :50-52
基于遗传算法的自动组卷设计 篇7
1 遗传算法原理
遗传算法GA[1](Genetic Algorithm)是一种群体型操作，它以群体中的所有个体为对象，选择、交叉和变异构成的遗传操作，使遗传算法有了其余传统方法所没有的特征。遗传操作的设计、参数编码、初始群体的生成、适应度函数的设计、控制参数设定一起构成了遗传算法的核心内容，一般将其称之为遗传算法的五大要素。遗传算法的基本步骤：
(1)在一定编码方案下，随机产生一个初始种群。
(2)用相应的解码方法，将编码后的个体转换成问题空间的决策变量，并求得个体的适应值。
(3)按照个体适应值的大小，从种群中选出适应值较大的个体构成交配池。
(4)由交叉和变异这两个遗传算子对交配池中的个体进行操作，并形成新一代的种群。
(5)反复执行步骤(2)-(4)，直至满足收敛判据为止。试题库组卷方法研究遗传算法的处理流程[2]如图1所示。
2 自动组卷模型
组卷系统最基本的目的是根据用户的要求，组出一份符合要求的、高质量的试卷。一般而言，出卷首先要确定考试时间KSSJ、试卷的满分值MFZ和所用的题型以及各种题型的题目和分数，而且对一种考试而言，这种题型一一分数分布曲线LT常保持相对稳定。然后获取难度一一分数分布曲线LD、内容一一分数分布曲线LC，教学要求度一一分数分布曲线LR及其各自允许的误差。曲线LC,LR及其允许的误差均由用户给出，后者采用专家默认曲线(根据各课程的教学大纲给出的)。曲线LD在很大程度上决定了考试成绩的分布，是很重要的一条曲线，高等数学试题库系统Math lab中，将其称为中心曲线，系统的默认曲线不一定满足用户要求，但是要用户用难度分布曲线LD表示对试卷的难度要求又比较困难，为此，借用专家模型[3]。下面根据试题参数和组卷要求设计建立目标函数。
设yi,hi,ji(j=1,2,3……k，),k为教学难度的档数，(本文中k=5)分别表示用户要求的试题难度为i档的题应占的分数、实际生成试卷中试卷难度为i档的题应占的分数、用户允许试卷难度要求度为i档的题的分数误差。生成的试卷满足用户关于难度分数分布要求的程度可以用公式(1)值的大小来评价：
由式(1)可以看出f的值越小，则生成的试卷越接近于用户关于各教学要求度应占分数要求。因此，只要题库题量充裕，这一要求很容易满足。综上所述，得到求解组卷问题的目标函数：min(f)=f1。
3 自动组卷的遗传算法设计与实现
3.1 染色体编码及群体的初始化
用遗传算法求解问题，首先要将问题的解空间映射成一组代码串。经典遗传算法采用二进制编码，用1表示此题被选中，0表示此题未被选中，这种编码简单明了，但是进行交换等遗传操作时，各题型的题目数难以精确控制，而且，当题库中题量很大时，编码很长。在解决数值优化问题时，采用实数编码的遗传算法的效率要好得多。注意编码时应将同一题型的题目放在一起，并且为保证一份试卷中知识点不重复，每条染色体中，各基因的知识点编码必须各不相同。
3.2 适应度函数
一般情况下适应值越大的个体越好，适应值越小的个体越差。本文提出的组卷模型是最小化问题，采用公式(2)将目标函数f转换为适应度函数F'：
因为指数比例既可以让非常好的个体保持多的复制机会，又限制了其复制数目以免其很快控制整个群体，所以对L述适应度函数F'采取公式(3)指数比例变换方法转换为适应度函数[4]：(其中β取值为0.03)
3.3 遗传算子设计
(1)选择算子。采用期望值模型选择机制，即先用公式(4)计算群体中各个个体期望被选中的次数：
其中M为种群规模，Fi为第i个个体适应值。用Nim的整数部份[Ni]安排个体i被选种的次数，这样其选出个个体，然后对Ni的小数部分作为概率进行贝努利试验，若试验成功，则此个体被选中，不断重复，直至选满为止。
(2)交叉算子。将以上选出的个体进行两两随机配对，对每一对相互配对的个体采用有条件的“均匀交叉”，即两个配对个体的每一个基因座上的基因都按设定的交叉概率Pc和一定的条件(确保交换后个体仍是有意义的组合)进行交换，产生两个新个体。具体的操作是：对两个配对个体的每一个基因座上的基因，先随机产生一个0～1的实数r1，如果r1
(3)变异算子。每个个体的每一个基因座上的基因都按设定的变异概率Pm在一定范围内(考试范围内与此基因题型相同且知识点与本个体其余题的知识点不重复)变异。对经以上交换操作后产生的每一个个体的每一个基因座上的基因，具体的变异操作是：
(1)确定搜索新题的最大次数S，令当前搜索新题的次数S=0;
(2)随机产生一个0～1的实数r2，如果r2>Pm，则保持此基因不变;否则，根据此基因的值(题号)，判断所属题型;
(3)搜索次数S加1，若S>S，则结束搜索新题，保持此基因不变，否则，在此题型的题号范围内随机产生一个与此基因值不同的整数作为新题的题号;
(4)判断新题的知识点是否在考试范围内，若否，转(3);
(5)判断新题的知识点是否与本个体其余题的知识点重复，若是，转(3);
(6)用新题的题号替换此基因的值。
(4)最优保存策略。进行了选择、交叉、变异操作后，比较新一代的最好个体与上一代的最好个体的适应值，如下降，则以上一代最好个体替换新一代的最差个体。
3.4 算法实现
确定参数：最大代数MaxGene，群体规模Pop Size，交叉概率Pc，变异概率Pm;接收用户的组卷要求：
程序执行输出最好个体的编码，计算各难度级别的分数等指标，输出这些指标的值并与用户的要求值相比较，通过VB程序实现上述自动组卷，组卷的具体要求：试卷总分100，用时120min，试卷难度系数0.7。组卷结果表明，在进化到100代左右即可生成一份满意的试卷且误差比较小，改进的遗传算法降低了组卷问题的求解难度，组卷效率高、成功率高。
4 结束语
遗传算法的自动组卷具有成功率高、时间复杂度和空间复杂度小的优势，但是，其实用性也是建立合理的题库基础之上，要组出合理的试题，不要忽视合理性题库的建立。
参考文献
[1]李敏强,等著.遗传算法的基本理论与应用[M].北京:科学出版社,2003-03.
[2]赵跃新,许军林.基于遗传算法自动组卷的实现[J].合肥:计算机与信息技术,2009(3):46-47.
[3]洪潮兴,陈凤平,等.试题库通用软件成卷系统中的数学模型[J].广州:华南理工大学学报(自然科学版),1995,9(9):87-92.
遗传算法在自动组卷中的应用 篇8
关键词：遗传算法,自动组卷,成卷技术指标
1 概述
考试是用来考查人们学习程度的一种常见方式,传统的出试题的方式让老师有很大的负担,由于每个老师的理解不同,使其对学生的学习掌握程度的认识也有所不一样,这样就使得知识的覆盖面和试题难度难以被控制。为了达到考查的目的,提高老师的工作效率,避免不必要的重复劳动,我们有必要采用一种科学的组卷方式实现科学,高效,快速组卷。该文主要探讨遗传算法在自动组卷中的应用,研究遗传算法解决自动选题成卷的问题。
2 遗传算法
遗传算法起源于达尔文的进化理论与孟德尔的遗传学理论,它是一种新型的,模拟自然界生物进化过程的随机搜索方法。借鉴生物遗传学的方法,经过选择、遗传、变异等生物过程,提高个体的适应性,从而达到优胜劣汰的淘汰机制。遗传算法已经在搜索、优化、机器学习、图像识别等领域得到了广泛的应用,已经成为智能计算的重要技术。与传统的优化算法相比较,遗传算法具有如下优势:1)遗传算法从解集中的串集开始搜索,不同于传统优化算法从单个初始值开始迭代得到最优解的方法。遗传算法搜索覆盖面大,容易搜索到全局最优解。2)遗传算法通过适应度函数值来评价个体的优劣从而得到最优解,不涉及搜索空间的知识和其它辅助信息。由于适应度函数可以取任意的定义域,并且不受连续可微的约束。这样大大扩展了遗传算法的应用范围。3)遗传算法根据概率的改变来确定搜索方向,经过比较得到最优解集,其概率并不是确定的。有效地防止了组卷失败的状况。4)遗传算法遗传算法在进化过程中利用获得的信息进行自主搜索,使得优质个体能够以更高的概率被选中,从而得到更优质的基因结构。遗传算法的主要工作流程,如图1所示。
3 自动组卷
3.1 自动组卷的发展
在自动组卷试题库的创建方面,我们可以不断的更新与完善试题库的内容,在组卷时,对每题的内容进行分析,对出现过的缺点与不规范可以进一步修改,从而避免了传统出试卷时,考试结束后没有时间来进行总结与记录的缺点。自动组卷的产生,使得试题的内容具有了继承性,规范性,可以不断地积累出试卷的经验,并做好相应的记录与分析,丰富与规范试题库的内容,达到了开放性,实用性与交流性的特点。回溯试探法与随机抽取法是自动组卷中最常用的算法,回溯试探法记录每次操作的状态类型,然后分别与设定的条件进行对比,抽取满足条件的类型,一直循环到自动生成试卷或者重新开始组卷,它是基于随机抽取法基础上的。随机抽取法不考虑最优化,自动组卷生成的试卷只需要满足预先提出的各种约束条件,此试卷就为可用的了。随机抽取法算法结构简单,选取单一的试题时有较快的运行速度,但是应用于组卷的整个过程中,其抽取空间较大,会使得组卷时间很长,或者最后选取的试题不能满足要求,组卷失败。
3.2 自动组卷的技术指标与系统分析
试卷的评比中,会通过有几种曲线来考核试卷的好坏,如获取难度分数分布曲线LD,教学要求度分数分布曲线LR,题型分数分布曲线LT,内容分数分布曲线LC及其各自允许的误差,其中LR,LC及允许的误差都是用户给出的。曲线LD是很重要的曲线,大大地决定了最终成绩的分布。成卷的技术指标有难度,区分度,信度,效度这些方面,我们通常是用试卷的考试结果进行分析,但是在组卷时,我们了解这些指标的计算方法,然后进行科学合理地组卷。组卷系统中的试题库需要进行难度控制,能够生成符合测试要求,达到真正考查学生目的的试卷。
3.3 自动组卷试题属性
为了保证试题的质量,更好地考查学生对知识的掌握情况,我们通过控制以下属性来让试题规范化,科学化,最优化。
1)难度系数D:学生掌握试题内容的难易程度,D公式1确定
其中,Di是指第i道题的难易系数值;Si是指所有考生在第i题的平均分数;Fi是i题的满分值。只有当Di适中,才能使得试卷达到检测学生对知识的真实掌握情况,当Di为0,则意味着,没有一个学生可以答对第i题,则该题的难度太大;当Di为1时,则意味着所有的学生都能答对第i题,则该题难度太低,这样的题目不能达到检测学生的目的。一份理想的试卷的难度系数应该在0.4—0.6之间,这样考试的成绩分布能够满足正态分布,也具有实际的参考价值。
2)区分度Q:为了区分考生的水平与能力,更好地考查考生各方面,试题需要设定一个区分度标准。区分度是根据考生的前35%高分组与后35%低分组计算出来的。如公式2
其中,Qi为第i题的区分度;Hi是前35%高分组在第i题的平均分数;Li是后35%高分组在第i题的平均分数;Fi是i题的满分值。当Qi=0,表明低分组和高分组的平均分数相等,从而本试卷不能区分考生能力;当Qi<0;则说明此试卷太难,考生都是胡乱猜测做题的;Qi>0,才是正常的,但最好要大于0.3,这样才能有效区分考生能力。
3)时间T:是确定所有考生做完整套题所需要的平均时间。
4)分数S:确定此试卷的满分值。
5)曝光度E:曝光度是用来描述一道试题在前后两份试卷中出现的时间间隔。通过对曝光度值的大小来决定是否选用该题。
其中,Ei为第i题的曝光度;Sa为第i道题在最近的那份试卷的出卷时间;Sb为第i道题在此次试卷的出卷时间;G为用户允许前后两份试卷出卷时间的最小间隔值。
4 基于遗传算法自动组卷的设计与实现
遗传算法应用于自动组卷中,首先要生成初始群体然后按照各约束条件对其中的个体进行选择与复制,再对其以一定的概率进行交叉与变异的操作,从而实现个体结构之间新的重组,不断迭代,知道搜索到符合条件的全局最优解。遗传算法应用于自动组卷中的算法如下:
1)确定编码方案
自动组卷最终需要得到一份满足各约束条件的可行试卷,根据生物遗传学,我们可以将一份试卷对应一个染色体,而试卷中的每个试题对应染色体中的每个基因,我们可以用试题的题号来表示标记基因的值。染色体中的每个基因编码可以表示为:(R1,R2,R3,……Rn),其中Ri(n为试卷中的总题型数目,i=n-1)是试题的题号。
2)建立适应度函数
在遗传算法中,群体中个体的优劣是通过适应值的大小来区分的。通常来说,适应值越大,就判断该个体越优秀,反之,则判断该个体越差劲。适应度函数就相当于是求解一个问题的评价标准函数。我们设某个体的适应度函数为f(x),在建立函数之前,我们要保证目标函数与适应度函数建立映射后,使得f(x)是非负的,并使其越大越好。
3)设计遗传算子
Step 1选择算子。选择算子是用来确定进行交叉的个体,本身并不具有产生个体的能力,主要是为了达到提高群体平均适应度值的目的。通过选择算子,我们选择优异的个体,使其直接遗传给下一代或者让其通过交配产生新个体然后再遗传下一代,从而就淘汰了适应度值低的个体,也就是劣质个体被淘汰了。个体i在初始群体为n的情况下,其被选中的概率为
其中n为初始群体的大小,fi为第i个个体的适应值。
Step 2交叉算子。交叉算子能够产生新个体,它主要操作是将父代个体的部分结构进行两两替换重组,从而产生新个体,这主要是在相同题型段内操作的。基本的遗传算法中,交叉概率是固定的。自适应的交叉概率是可以自己调整的,交叉概率越大,则搜索过程中更加容易保证群体的多样性。所以,在粗略搜索时,其交叉概率越大越好,最后细搜时,其交叉概率越小越好,这样能够加快其收敛速度。
Step 3变异算子。变异算子也能够产生新个体,是产生新个体的一种辅助方法。它决定遗传算法在局部的搜索能力。采取最小的概率对满足约束条件的相同题型段的单点进行变异操作,并且先进行交叉操作再以变异概率Pm来进行操作。在确定每个题型的题号范围后,需要考虑该个体基因与其他基因是否被多次选中,有没有重复,如果被选中,就要重新开始产生,直到没有被选中的随机数,用它来代替此题型段中的任意一个题号。变异算子可以保证种群的多样性,防止出现早熟现象。
Step 4选择算法的控制参数指标。遗传算法中需要考虑的参数有,群体规模n,交叉概率为Pe,变异概率为Pm。当群体规模过小时,能够提高运算速度,但是降低了种群的多样性,比较难得到最优解。但是当群体规模过大时,运算速度会下降,n的取值范围一般大于30且小于150。交叉概率决定了个体的更新与算法的全局搜索能力,当Pe取值过大时,容易导致群体的高适应度值得到破坏,取值过小时,其退化为简单的随机搜索,所以其取值范围为0.35~0.85之间。变异概率Pm过小时,会使产生的新个体较少,若过大,则会使其退化为简单的随机搜索,所以其取值范围为0.01~0.2之间较合适。P的值是经过多次的实验确定的。
Step 5确定算法的终止条件。我们通过限制最大的迭代次数与既定的目标适应度值来判断是否终止算法,分别将个体的最大适应度值与目标适应度值进行比较,当期望值不大于最大适应度值时就停止迭代,否则对上述遗传操作进行反复循环,直到达到期望适应度值时,组卷才成功。
Step 6算法的实现
参数的确定,群体规模n,交叉概率为Pe,变异概率为Pm,最大迭代次数为MaxGene,实际迭代次数Gene;
确定用户的约束条件;
建立初始群体;
初始迭代的次数Gene=0;
确定群体中每个个体的适应度值;
While(最好个体的适应度值大于期望值&&Gene
确定最好个体的编号,输出的指标值分别与用户的约束条件值进行比较。
5 结束语
随着计算机的普及,信息知识的发展,使得自动组卷技术被大家追捧。自动组卷技术能够减轻老师的负担,使老师们将更多的时间投入到科学研究中;使试题的形式更加规范化,能够更好地进行总结与分析,使试题更加科学化,更好地考查学生各方面的素质。该文主要是基于遗传算法在自动组卷中的应用,设置了几个变量,设计了遗传算法自动组卷的基本步骤,实现了简单的自动组卷功能。由于时间与能力有限,其运行过程中的细节问题还需得到完善。
参考文献
[1]王明川.基于遗传算法的组卷方法研究[J].基础科学,2011,35(2):65-81.
[2]朱大茗,马绍汉.算法设计与分析[M].北京:高等教育出版社,2009.
[3]李敏强.遗传算法的基本理论与应用[M].北京:科学出版社,2003.
[4]宋芝兰.基于遗传算法自动组卷问题的设计研究[J].商业科技,2011,2(上):9-10.
[5]王栋.自适应遗传算法的研究[J].科技前沿,2011,2(646):175.
[6]王小平,曹立明.遗传算法理论应用与软件实现[M].西安:西安交通大学出版社,2002.
[7]钟宁,刘连浩.遗传算法在在线考试系统中自动组卷的优化设计[J].电脑知识与科技,2010,7(2):397-398.
[8]谢兴,秦前清.遗传算法在医学图像自适应融合中的应用[J].计算机工程与应用,2011,47(3):181-183.
[9]Xiao Han-peng.Research of Test Paper System Base on Genetic Al-gorithm[J].Computer Knowledge and Technology,2010,27(056):65-81.
基于遗传算法的自动组卷问题研究 篇9
在目前高等教育中,考试仍然是评价教学效果的重要方式,也是给提高教学质量提供反馈信息的重要手段。因而试卷的设计就尤为重要,不仅要涉及知识的覆盖面。而且试题的难易程度要控制在一定的标准中,这样才起到真正的评价和反馈作用。利用计算机开发新的组卷系统已成当代教育研究的热点问题之一,而如何保证试卷的随机性、公平性、合理性,是实现自动组卷系统的一个难点。
1.1 控制试题的难易度
试卷是老师对学生进行所学知识掌握程度检测的重要手段,然而同一门课对不同专业的学生要求掌握的程度会有所不同,如《计算机应用基础》这门课对理科学生要求掌握的程度相对文科学生要高,因此针对不同专业学生试卷的难度会有所不同;对同一专业学生,要根据学生已有的基础,以及学生的年龄和接受能力,试题的难易程度也要不同;同时根据考试的级别和及格率的要求,试题的难易程度也要有所调整。
1.2 保证试题的公平性
为了保证考试的公平性,在组卷过程中要保证考生前后左右的试题都不一样,但试题的难易程度一样,这就要求在组卷中要灵活多样,同等难易程度的试题要有足够的数量。而且试题的形式要保持一致,不然很难保持同一场考试的公平性。
1.3 发挥组卷系统的智能性
计算机在组卷的过程中往往按照命题人给出的指令从试题库中挑选试题完成组卷工作,可是系统对所生成试卷的难易程度、有效性很难有效地控制。于是如何有效地提高计算机的组卷性能,使计算机能够自动调整组卷算法实现其组卷的智能性,是组卷成功的重要因素之一。
2 算法分析
遗传算法是来源于达尔文生物进化论中适者生存、优胜劣汰遗传机制的自然选择和遗传学机理生物进化过程的计算模式,是一种模拟自然进化过程搜索最优解的方法[1]。遗传算法从代表问题潜在解集的一个种群出发,一个种群由经过基因编码的一定数目的个体组成。每个个体是染色体带有特征的实体。染色体作为遗传物质的主要载体,其内部表现(即基因型)是某种基因组合,它决定了个体形状的外部表现[2]。因此,在一开始需要实现从表现型到基因型的映射即编码工作。初始种群产生后,按照适者生存和优胜劣汰的原则,逐代演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度大小选择个体,并借助于自然遗传学的遗传算子进行交叉和变异,产生出代表新的解集的种群,最后一代种群中的最优个体经过解码,可以作为问题近似最优解。
本文基于对遗传算法的仔细研究,并从四个方面进行了改进,分别是编码方式、适应度函数设计、初始种群生成方法以及遗传算子的基础上,提出一种基于改进遗传算法的组卷模式。在此基础上,对该算法的实现过程进行仿真分析,分别研究在不同的迭代次数的基础上的进化情况,进而可以看出改进遗传算法的有效性。
3 基于遗传算法的自动组卷系统设计
B/S架构模式的用户界面是通过WWW浏览器来实现,极少部分逻辑事务在前端(Browser)实现,逻辑事务在服务器端(Server)实现,即形成所谓三层3-tier结构。B/S结构的系统不需要安装客户端软件,它运行在客户端的浏览器上,系统升级或维护时只需更新服务器端软件即可,这样就简化了客户端电脑负荷,减轻了系统维护与升级的成本和工作量,降低了用户的总体成本。通常在组卷系统建成后,在应用中为与软件的变化相配,题库中的数据会不断变化、升级更新。本系统采用B/S(Browser/Server)模式开发系统,这就使系统的升级和维护更为便捷,完全解决了系统维护和升级客户端无关这一难题,使所有的操作都可以在服务器端完成。B/S三层框架结构如图1所示:
本系统主要使用Visual Studio 2010的C#、ASP.NET语言进行编程,用Microsoft SQL Server 2008 数据库实现多个数据库,采用改进遗传算法求解自动组卷问题,分析设计出基于B/S结构的组卷设计方案,实现一个较为实用的智能组卷系统。界面友好,智能、高效。组卷系统功能模块如图2。
4 结论
在计算机辅助教学中,自动组卷系统是其重要的构成部分,它是把测量学、教育统计学等多门科学知识与人工智能技术相结合,借鉴专家命题的智能经验,并合理利用计算机的先进科学技术,最终实现计算机完全能智能生成试卷。本文主要研究了利用遗传算法开发的自动组卷系统。
参考文献
[1]张晓博.基于云遗传算法实现自动组卷问题[J].电脑知识与技术,2011(3).
[2]崔艳.基于通用试卷库组卷算法的研究和实现[D].郑州大学硕士论文,2010.
[3]陈锋.试题库系统中随机抽题算法的设计与实现[J].现代计算机,2010(3).