遗传算法大学计算机基础的自动组卷方法的毕业论文.doc

遗传算法大学计算机基础的自动组卷方法的毕业论文 摘要：针对传统组卷方法效率、成功率低等难题，设计基于遗传算法的大学计算机基础自动组卷方法。首先设计大学计算机基础自动成卷适应度函数，采用编码对组卷过程中题型及与其数量分布相关的约束条件进行处理，然后设计选择算子、交叉算子以及变异算子，将适应度作为评价群体多样性的指标，求出交叉概率与变异概率，给出遗传算法终止条件。实验结果表明，该方法提高了大学计算机基础自动组卷方法的效率和成功率。 关键词：遗传算法；计算机基础；自动组卷；适应度函数；约束条件；编码 0引言 大学计算机基础自动组卷是实现在线考试系统的核心技术，当前很多学校机构都对自动组卷进行了大量研究，尽可能使最终形成的试卷达到用户要求，同时保证科学性1。在大学计算机基础题库试题质量要求高的情况下，自动组卷的效率和质量只和组卷方法有关。因此，设计一种科学有效的自动组卷方法非常关键，其涉及全局寻优问题，具有重要研究价值23。当前常用的自动组卷方法有随机生成方法和回溯试探方法。随机生成方法通过随机抽取的方式从试题库中抽取试题，对其是否满足试卷要求进行判断，该方法有很高的不确定性，在试题数量多的情况下，效率极低4。回溯试探方法按照某一准则对当前组卷状态进行转换，试探性的选择试题破坏了选择试题的随机性，同时组卷所需时间长。为此，提出一种新的基于遗传算法的大学计算机基础自动组卷方法。 1遗传算法的大学计算机基础自动组卷方法 1.1大学计算机基础自动组卷模型 组卷问题可描述为：采用相应软件程序把成卷要求与资料库中试题特征参数匹配，得到符合成卷条件的试卷。组卷的目标为寻找最优解，确定最符合输入要求的组卷策略5。在大学计算机基础自动组卷过程中，命题人会事先输入多个限制条件，主要含有以下几个方面：1）试卷总分：试卷的总分数，通过命题人设定；2）考试时间：学生参与试卷解答时间，通过命题人设定；3）试卷难易程度：通过难度系数体现，是学生关于试题失分状况的体现；4）试卷区分度：区分度为试卷对考生情况的辨识能力，通常大小为-1，1，该值越大表示区分效果越好。一般情况下，当试题区分度高于0.39时，则认为试卷存在较好的区分度；当试题区分度低于0.2时，则认为试卷区分度很差。计算区分度采用的方法为：对分数进行排列，Q1=27%dh，dh表示高分组的难度，Q2=27%dl，dl表示低分组的难度，则区分度为=(Q)1-Q2总分数；5）试卷涵盖度：试卷中涉及知识点占所学课本的比重，是根据教学大纲与考试大纲设定的；6）试卷试题结构：试卷中包含的题型通常包括单选题、填空题、计算题、简答题等。对上述组卷限制条件进行分析。试卷的涵盖度为最关键条件，在确定试题过程中，依据试题的知识点属性，通过考试大纲决定知识点在试卷中出现的形式和比重；试卷难易程度通过各考生分数情况确定，依据以往的测试结果对题库内各试题的难度级别进行划分，并赋予相应的难度系数值6。通常要求全部考生的成绩服从正态分布，由于二项分布在一定条件下与正态分布类似，因此，本节通过离散型随机变量的二项分布体现试卷难度与分数的关系，公式描述为：Ws(g)=Fgswg()1-ws-g（1）式中：s为正整数，表示最大难度级别；Ws(g)表示难度级别为g的试题总分数占整个试卷总分数的比例；Fgs表示难度级别为g的试题总分数；wg表示各难度级别的难度比例；w表示难度系数。 1.2目标函数 设k为试卷试题数量，Fz为试卷总分数，按照二项分布试卷难度与分数的映射关系，通过难度系数求出每个难度级别的难度比例wg，T为考试时间，Tj为各试题作答时间。设PFN为大纲内第N章知识点占试卷的比率，M为总章节数，FN为相应章节试题的分数，j为试题的区分度，则大学计算机基础自动成卷的初始目标函数如下：f=g=0s|wg-FgNFz+()N=1M|gFNFz-PFNs.t.|T-j=1kTjT0.15()j=1kjFNFz0.3（2）把考试时间与试卷区分度当成目标函数的约束条件，以减少运行时间。 1.3遗传算法适应度函数的确定 依据上述目标函数确定适应度函数。适应度函数的复杂度为遗传算法复杂度的重要构成部分7，因此，当设计适应度函数时需确保计算时间复杂度最低，把目标函数描述成计算最大值形式，保证适应度函数为非负函数。上述成卷的目标函数为求最小值函数，依据各函数特点，确定两函数间的映射关系为：f*=1(1+f)（3）式中：f*表示适应度函数；f表示目标函数。针对任意个体，判断考试时间和试卷区分度是否符合约束条件，如果两者符合约束条件，则进行适应度计算；反之，停止计算。 1.4遗传算法编码 通过基因分段式编码实现问题解的编码描述，采用编码对组卷过程中的题型及其数量分布相关的约束条件进行处理，由此实现问题的简化。详细编码过程为：先对每种题型进行独立编码，组成相应基因段，基因段的个数取决于题型的种数，这里用K描述；基因段中基因数取决于题库中此种题型的试题数量。若题库中存在道试题，则编码为a1,a2,a，其中：ai=1,第i道试题被选中0,第i道试题未被选中（4）对于被选中的全部试题需满足i=1ai=k，k为试卷中的试题数量；被选中的每种题型试题需满足i=1u1ai=b1,i=1u2ai=b2,i=1uKai=bK。其中，u1,u2,uK表示题库内相应题型的试题数量；b1,b2,bK表示试卷中每种题型试题需要的数量。 1.5遗传算子设计 遗传算子包括选择算子、交叉算子以及变异算子，下面对其进行设计。1）选择算子。在进行遗传选择时，通过最佳个体保存法与适应度比例选择法获取算子8。具体过程为：先挑出最好的个体，并将其复制至下一代中，然后根据每个个体被选择概率与其适应度间的函数关系实现剩余个体的挑选。求出被选择概率，其计算公式如下：P*i=Eii=1ZEi（5）式中：Z用于描述种群大小；Ei用于描述适应度。2）交叉算子。在进行交叉时，结合编码方案进行分析，选用单点交叉方式，交叉主要在同种题型组卷时进行。3）变异算子。变异算子能够实现局部检索，为辅助型算子，在初始种群形成时已符合各项约束条件。为了不改变约束条件，在同种题型中进行两点变异，也就是每种题型在自身编码段中进行变异。1.6自适应交叉与变异概率交叉概率po与变异概率pv对遗传算法有极大影响，本节将适应度作为评价群体多样性的指标，使po与pv随适应度的变化而变化。依次求出交叉概率po与变异概率pv：po=1(E)max-Eo(E)max-E,EoE2,EoE4,Ev 2自动组卷实验结果分析 为了验证本文提出遗传算法的可行性与有效性，针对大学计算机基础课程，通过ASP+SQLServer2000，依据遗传思想编写程序，进行自动组卷实验。假设题库共存在五种题型、六个章节、七个难度系数与四个认知层次。题库中有700题，其题型题量分布、章节题量分布、假设组卷要求为：试卷总分为120分，选题需达到题型与题量要求，不同题型分数已给出。所有章节的分值误差、难度分值误差及不同认知层次分值误差都在2分以内.自动组卷结果分析：1）在交叉概率为0.8，变异概率为0.1的情况下，令群体规模依次取20，30，40，50，60，运行代数在20100范围内变化。群体规模对遗传算法收敛性有很大的影响。在群体规模较小的情况下（20和30），参与遗传算法的试题较少，搜索空间受到限制，适应度值小，得到有效试卷的机会很小。在群体规模达到40的情况下，适应度值明显升高，而当群体规模为50和60时，适应度值无显著区别，基本不增长，说明群体规模达到40时，即可达到收敛，而群体规模越大，则程序运行速度越低，所以本文实验设定群体规模为40。除此之外，还可以看出，在运行代数为60代的情况下适应度值已实现收敛，所以将运行代数设置为60代。2）令最大迭代数为60代，交叉概率为0.8，变异概率为0.1，群体规模为40。经50次调试运行，获取大学计算机基础自动组卷结果。为了验证本文方法的有效性，将随机生成方法和回溯试探方法作为对比，在题库量是700题的情况下，对三种方法的组卷时间、组卷成功率进行比较.本文方法成功概率为100%，且所需时间明显低于随机生成方法和回溯试探方法，性能优于其他两种方法，验证了本文基于改进遗传算法的大学计算机基础自动组卷设计与实现方法的优越性。 3结论 本文提出基于遗传算法的大学计算机基础自动组卷方法。介绍了大学计算机基础自动组卷模型，给出通过遗传算法实现大学计算机基础自动组卷的详细过程。经实验验证，所提方法效率和成功率较高。 参考文献 1陈国彬，张广泉.基于改进遗传算法的快速自动组卷算法研究J.计算机应用研究，xx，32（10）：29962998.CHENGuobin，ZHANGGuangquan.NewalgorithmforintelligenttestpaperpositionbasedonimprovedgeicalgorithmJ.Applicationresearchofputers，xx，32（10）：29962998. 2吴爱婷，官伯然.一种基于遗传算法的超宽带天线自动设计方法J.微波学报，xx，31（3）：2226.WUAiting，GUANBoran.AnautomationdesignmethodoftheultrawidebandantennabasedonthegeicalgorithmJ.Journalofmicrowaves，xx，31（3）：2226. 3李瑞森，张树有，伊国栋，等.可拓集成模式的工程图学试题库组卷方法研究J.图学学报，xx，37（6）：851856.LIRuisen，ZHANGShuyou，YINGuodong，etal.ResearchonthetestpapergeneratingmethodofengineeringgraphicsbasedontheextensionandintegrationmodeJ.Journalofgraphics，xx，37（6）：851856. 4王宁，蔡顺燕.基于随机相位重构的智能组卷混叠均衡算法J.科技通报，xx，32（5）：236239.WANGNing，CAIShunyan.SmartgroupaliasingequalizationalgorithmbasedontherandomphasereconstructionJ.Bulletinofscienceandtechnology，xx，32（5）：236239. 5席卫文，张春辉，王飞，等.一种基于改进遗传算法的医学题库自动组卷设计与实现J.中国医学物理学杂志，xx，33（8）：861864.XIWeiwen，ZHANGChunhui，WANGFei，etal.DesignandimplementationofimprovedgeicalgorithmforautomatictestpapergenerationJ.Chinesejournalofmedicalphysics，xx，33（8）：861864. 6徐海东.基于遗传算法的自动组卷算法的研究J.微型电脑应用，xx，32（3）：6062.XUHaidong.ResearchonautomatictestpaperbasedongeicalgorithmJ.Microputerapplications，xx，32（3）：6062. 7吕海燕，周立军，宦婧，等.通用在线考试系统智能组卷遗传算法设计J.计算技术与自动化，xx，35（4）：8590.LHaiyan，ZHOULijun，HUANJing，etal.DesignofintelligenttestpapergeneratinggeicalgorithmformononlineexaminationsystemJ.Computingtechnologyandautomation，xx，35（4）：8590. 8潘刚，杨清平，蒲国林，等.遗传算法在智能组卷系统中的应用研究J.云南民族大学学报（自然科学版），xx，25（6）：579584.PANGang，YANGQingping，PUGuolin，etal.ApplicationofthegeicalgorithmintheintelligenttestpapergenerationsystemJ.JournalofYunnanUniversityofNationalities（natural