简介:关于对写作算法遗传论文范文与课题研究的大学硕士、相关本科毕业论文算法遗传论文开题报告范文和相关文献综述及职称论文参考文献资料下载有帮助。
潘晓辉Pan Xiaohui
（上海政法学院,上海201701）
( Institute of Political&,Law of Shanghai,Shanghai 201701 ,China)
摘 要：组卷模块能否高效率地生成符合系统要求的试卷是评估考试系统的重要因素.遗传算法（GA算法）近年来在解决多重约束问题的求解中应用非常广泛.把遗传算法应用于自动组卷,在标准遗传算法的基础上进行了改进,采用分段编码,基于误差的适应度函数和动态交叉及变异概率.采用遗传算法的智能组卷系统既能很好的满足组卷的约束,且效率远高于传统的回溯算法.
Abstract:II is one of the major factors to evaluate a examination system that whether its testpaper generation module can produce the testpapers asthe system requirements effectivelv. Cenetic algorithms has been widely used in solving the multi-constrains problems recently. Apply genetic algorithmsin auto-generating testpaper and make imporvement to the standard genetic algorithms by using segmental encoding,adaptation funcion based on error and dynamic probability of cross&,variaLion operations. The intelligent testpaper generation system incorporating genetic algorithms not only can sati论文范文y the required constrains but also manifest far more better efficiency over testpaper generation systems which adopt craditional Lrace algorithms.
关键词：遗传算法；考试系统；自动组卷
Key words: genetic algorithms, examination system, aum-generating testpaper
中图分类号：TP273
文献标识码：A
文章编号：1006-4311( 2010 )14-0159-03
1.课题背景
考试作为检验学生对知识的掌握程度的重要手段,是高校教学活动中不可缺少的一个环节.通过考试,教师可以了解学生的学习情况,并借此了解教学效果,改进教学方法,提高教学质量,学生则可以通过考试了解自己对内容的掌握情况,有目的地进行学习.但是,随着网络技术的发展,特别是网络技术在现代教育领域应用的普及,以纸和笔为主要工具的传统考试方式的诸多弊端显露得越来越突出.传统的考试在命制试题、组织考试、统计分数的过程中,要花费大量的时间、人力和物力.其中不可避免地存在大量的重复劳动,工作效率比较低,而且很难避免人为因素对考试造成的影响.而组织一次计算机考试至少要经过五个步骤,即人工出题、学生考试、人工阅卷、成绩评估和试卷分析.显然,随着计算机考试类型的不断增加以及考试要求的不断提高,教师的工作量将会越来越大,并且其工作将是一件十分烦琐和非常容易出错的事情.此外,由于传统的卷面考试从出题印刷到下发试卷等环节需要较长的时间,接触的人员相对较多,因而在保密方面具有一定的困难.网络在线考试从根本上解决了传统考试过程中的工作量大、效率低、反馈周期长、反馈能力弱、资源浪费等缺陷,成为现代教育技术发展与研究的方向.网络无纸化考试系统以其较高的公平公正性正受到各界的一致推崇.
在线考试系统中的组卷子系统用于根据某种算法生成所需试卷.在已见诸文献的试卷自动生成算法,大都基于经验的积累,有一些任意性.本文以实现面向网络的在线考试系统的自动组卷算法为目标,在分析传统试卷自动生成算法的基础上实现了一种常规遗传算法的改进试卷生成算法.
利用计算机自动生成试卷是在线考试系统的一项重要任务,而生成试卷质量的高低,则取决于它的生成算法.智能组卷实际是一个典型的多约束目标的求解问题.本文所研究的采用分段编码、基于误差的适应度函数和动态调整交叉和变异概率的改进遗传算法,有效解决了智能组卷中的约束优化问题,具有很好的性能和实用性.
2.试卷组卷算法研究
2.1传统组卷方式传统的组卷算法大多采用随机选取和回溯试探法.随机选取法根据状态空间的控制指标,由计算机随机地抽取一道试题放入试题库,此过程不断重复,直到组卷完毕,或已无法从试题库中抽取满足控制指标的试题为止.这种算法虽然简单,但是要完整地组成一张试卷,其时间复杂度很大.回溯试探法则是将随机选取产生地每一种状态记录下来,搜索失败时,回归到上次记录的状态类型,然后再根据一定的规律变换一种新的状态进行试探,通过不断的回溯试探直到试题生成完毕或回到出发点为止.对于出题量较少的题库系统而言,回溯法组卷成功率较好.当数据库很大且题量较多时,其组卷时间长,占用的空间复杂度也很大.
2.2基于遗传算法的组卷方式在众多的优化搜索方法中,遗传算法（GA算法）是后起之秀.它是20世纪60年代末期到70年代初期由美国Michigan大学的J.H.Holland教授及其学生和同事发展起来的.遗传算法被广泛应用于各种复杂系统的自适应控制及复杂优化问题中,取得了良好的效果.我国有关遗传算法的研究,从20世纪90年代以来一直处于上升时期,特别是近年来,遗传算法的应用在许多领域取得了令人瞩目的成果,并且在算法改进及理论研究方面也作出了成功的探索.
遗传算法是模拟生物界自然选择和遗传变异机制来求解复杂问题的随机化搜索和优化算法.对于约束优化问题,由于遗传算法能以较大概率在有限时间内求得整体最优解,同时对目标函数和约束条件不作更多要求,因此已成为求解一般约束优化问题的强有力工具.
遗传算法主要由编码、个体适应度评价、遗传操作、新旧个体替换等步骤组成,基本的遗传操作有选择、交叉、变异三种.GA的每个步骤都有遗传算法多种解决方法,比如编码方式可以根据实际问题的需要采用二进制编码、格雷编码、实数编码等；选择操作可以采用论文范文赌选择、锦标赛选择、最优保留选择等；交叉操作有单点交叉操作数、多点交叉操作数、均匀交叉操作数和算数交叉操作数等等.
应用遗传算法解决具体问题的关键是确定五个问题：①问题解的染色体表示；②创建解的初始种群的方法；③用来判断个体优差的适应度函数④用于遗传操作的遗传算子；⑤遗传算法的参数值,包括群体规模(n)、交叉概率(Pc）、变异概率(Pm)、目标函数的变换方式和选择策略.
3.组卷的数学模型
3.1试卷的约束条件一份试卷有多个属性,每个属性实际是试题的一个约束条件.实践证明过多的约束条件只能造成组卷成功率低.通过归纳总结后拟采用这些属性：题目ID、题型ID、知识点ID、难度系数、区分度（普通、掌握、分类、选拔）、用时、分值.
因此智能组卷可以描述如下：在解空间中决定一个MxN的矩阵,M为试题中总题数,N为试题参数.设试卷总分为S,试卷总用时为T,试卷难度为D,知识点数量为Q,题型数量为R,区分度为L,试卷的标准差为,则目标矩阵满足以下约束条件.
4.遗传算法设计
4.1制定染色体编码编码就是用一种数字排列来表示问题的方法.利用编码将问题的解空间映射到GA算法的编码空间.编码方案的选择依赖于问题的性质,并影响到算法内操作的问题,是影响算法性能的重要因素.常见的编码方案有二进制编码、十进制编码、实数编码等.
标准Holland编码方案是若题库中有S条数据记录即试题,用1表示该题选中,用0表示该题未被选中.编码的结果是一个长度为S的串,串中有N个1表示被选中的试题,(S-N)个0表示未选中的试题.此方法表示自然清晰并易于进行各种选择交叉和突变方案.但在实际考试系统中,题库中有多种题型的试题,往往总数会很大.采用这个方法包含了所有试题基因,导致染色体长度太长,并且不利于进行遗传操作.我们研究并进行了改进.改进后只对组卷要求中需要的题型试题进行编码,并且将各种题型分开进行编码,每种题型的编码做为一段组合在一起成为最后的编码.每种题型的题数即为该题型的编码段长度.改进后的编码缩短了染色体长度,提升了系统的效率.
遗传算法matlab程序:遗传算法教学视频2
4.2适应度函数设计常规采用的误差加权函数比较简单,但在晚期容易随机徘徊而不收敛.本系统的适应度函数的目标是使试卷的各个题目的属性尽可能接近用户所定义的参数之间的误差,如下：
其中F：(x)为每个约束条件相对于用户所设定的标准值的误差.x代表每套试卷,即个体.m为这套试题中总的题数.d( i等于1.6)为每种约束条件的强度.在众多的约束条件内,各种约束条件的重要性是不一样的.为此,可以将这些约束条件分为以下四类：①强约束：试题的各类题型比例；②亚约束：试卷的总分,估计用时；③柔性约束：试题的难度、区分度；④弱约束：知识点限制.
在满足强约束和亚约束的前提下,可以适当的调整后两种约束指标,提高组卷成功率.本系统采用a的向量为
5.实验数据
5.1本模拟组卷系统支持多种课程,其中计算机及应用技术课程的试题库如下：
判断题：380题 单选题．512题 多选题：340题
填空题：447题 多空题：274题
每条记录均包含题型,难度,知识点代号,区分度,用时等组卷需要的字段.
5.2组卷参数
总题数：l00.
题型为判断题20道,单选题30道,多选题20道,填空题20道,多项填空题10道.
考试用时120分钟.
全卷总分100分.
难度系数5.5.
区分度l级30道,2级30道,3级30道,4级10道.
知识点40个.
5.3实验结果比较测试平台为．Pentium 4 2.4G512M SDRam,Win 2000 Server,SQL Server 2001,考试系统代码使用ASP．net 2.0+C#开发.分别用本文所述改进的遗传算法和标准回溯算法进行组卷实验,测试生成满足组卷要求的试卷所用的时间.在遗传算法的运行过程中对交叉概率p和变异概率P1按照前文所述的公式动态调整.下图为两种算法的性能比较：
其中第1 -5次实验遗传算法的遗传代数分别为314,295,288,274,2320从上图可以看出本文所述的改进遗传算法求解速度明显优于常规回溯法,一般遗传小于300代就能生成符合要求的解,从而较好的解决了智能组卷问题.
总结：这篇算法遗传论文范文为免费优秀学术论文范文,可用于相关写作参考。
遗传算法matlab程序引用文献:
[1] 遗传算法论文范文 关于遗传算法毕业论文模板范文2万字
[2] 遗传算法论文范文 遗传算法毕业论文的格式范文2万字
[3] 支持向量机和遗传算法论文写作资料范文 支持向量机和遗传算法论文范文资料2500字
