论文网
计算机有关论文范例,与硕士学位文重复率武汉相关论文格式模板
本论文是一篇计算机有关论文格式模板,关于硕士学位文重复率武汉相关电大毕业论文范文。免费优秀的关于计算机及算法及试题方面论文范文资料,适合计算机论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。
;题作了确定的分配,然后按照这个分配到题库中查找,这样的静态分配对题库的要求非常高,一旦题库对该要求不能满足,就要重新修改分数分配模式,效率低且随机性差.而本算法中,每一道试题的选择都是根据已入选试题的情况以及题库中现有试题的使用情况灵活处理的,而且是从所有尽可能严格地满足用户要求的试题中随机抽取的,保证了良好的随机性和适应性.但为了实现动态制定试题模式的方法,系统必须多次在试题特征库中查找所有满足当前状态的试题,故该方法在速度上不能保证.
3.3倒塔式收缩成卷算法
在组卷过程中,由于试卷参数间的相互制约,它们很难同时得到满足,通常是先随机抽题组卷,再判断试卷参数是否满足要求,不满足时调换试题这种成卷方法.在顺利的时候成卷速度较快,但往往是经过多次更换仍得不到理想的试卷,不得不推倒重来.大体说来,这种成卷方法的速度是比较慢的.究其原因,主要是把问题留到了最后,也就是说等到问题成了堆才去解决.因此,文献[3]中采用了"倒塔式收缩"的成卷方式,先把各参数值放宽,以保证抽题的随机性,然后将各参数值逐步缩紧,最终收缩到允许的范围内.在组卷过程中,一旦参数值越界,立即强制返回.由于选题过程中先宽后严,并逐步收缩试卷数值范围,直至符合选题要求为止,故称为"倒塔式收缩法".按此种成卷模式,最后的试卷一定是一份合格的试卷,不会出现推倒重来的局面.
3.4回溯试探成卷算法
回溯法[4]是一种"通用的解题法",属于有条件的深度优先算法.该方法是将随机选取产生的每一状态记录下来,搜索失败时,释放上次记录的状态类型,然后再依据一定的规律,变换一种新的状态类型进行试探.通过不断地回溯试探直到组卷完毕或回到出发点为止.按照上面提到的三种方法选取试题,随着选题数的增加,指标间的约束增大,选出来的试题可能不是最优的,此时回溯法往往是有效的.该算法对于试题类型较少和题量较少的题库以及组卷指标简单的试卷而言,成功率较高.但当总题量较大时,组卷时间长,占用的空间复杂度大,程序结构较为复杂,选取试题也缺乏随机性.
综合考虑以上几种组卷算法,发现上述算法对于小规模的考试来说,能够比较好地完成组卷,但对于中,大规模的考试来说,组卷时间长,而且,不一定能够满足所有的约束条件,对于用户来说,是不能令人满意的.
因此,结合以上几种方法的优点,寻找一种新的改进算法,不仅要具有智能搜索技术,并且要具备收敛速度快的特点.遗传算法以其具有自适应全局寻优和智能搜索技术,并且收敛性好的特性能够很好地满足自动组卷的要求.
第4章遗传算法在组卷中的应用
通过上章对常用的组卷算法的分析可知,将遗传算法应用于组卷是具有实际意义的.因为通过遗传算法强大的搜索能力得到的组卷参数表,可以保证根据此表抽题组卷时,题库中不会找不到满足所有属性的试题,从而使试卷的总体指标得到满足.
作为本文的重点以及难点部分,本章将首先阐述遗传算法的思想以及基本步骤,接着分析传统遗传算法用于组卷的可行性,最后针对遗传算法在应用时的一些弊端,将遗传算法进行了改进,使之更符合组卷问题的实际需求.
4.1遗传算法
4.1.1遗传算法概述
遗传算法[11]简称GA(GeicAlgorithm)是一种模拟自然选择和自然遗传机制的随机优化算法,它对目标函数没有可微的要求,可以用于解决传统搜索方法难以解决的复杂问题和非线性问题,可广泛应用于规划设计,组合优化,自适应控制等领域.
遗传算法的起源可以追溯到上世纪50年代初,最初是几个生物学家用计算机来模拟生物系统.到60年代后期和70年代初期,密歇根大学的JohnHolland从试图解释自然系统中生物的复杂适应过程入手,模拟生物进化机制构造人工系统模型,形成了较为完整的遗传算法理论和方法.在接下来的几十年中,人们对遗传算法的兴趣日益升温,在该领域也取得了理论研究的进展和丰硕的成果.近些年,随着人工生命研究的兴起,遗传算法的应用和研究也渐渐成熟.
4.1.2遗传算法的基本思想
遗传算法的基本思想[13]是把问题的解表示成染色体,在算法中就是经过编码的字符串.在执行遗传算法之前,给出一群染色体,作为假设解.然后,把这些假设解置于问题的"环境"中,按照适者生存和优胜劣汰的原理,从中选出较适应环境的染色体进行复制,再通过交叉,变异产生更适应环境的新一代的染色体群.这样,一代代进化,最后就会收敛到最适应环境的一个染色体上,这就是问题的最优解.可是,生物物种的进化是很缓慢的,要得到满意的结果,通常要经过上千次甚至上万次交叉,变异.为加快种群的优化速度,需根据实际情况对算法进行改进.
4.1.3遗传算法的特点
遗传算法是从某一初始群体出发,遵循进化原则,不断迭代计算,逐步逼近最优解,作为一种搜索和优化方法,它具有以下特点[12]:
遗传算法是一种间接的优化方法.它的搜索过程不是直接作用在问题的变量上,而是作用在将变量编码后的字符串上.对给定问题,它可以产生许多潜在解,有较大的选择性.
遗传算法的搜索策略不是穷举式的全面搜索,而是利用适应度逐步逼近目标值的搜索,目的明确.
遗传算法的搜索过程不是单点搜索,而是按并行方式搜索一个种群数目的点,是从一个群体到另一个群体,减少了陷入局部最优解的风险.它适合大规模并行,可同时搜索解空间的多个区域.
遗传算法的搜索过程只依赖于个体的适应度函数,不需要其它辅助信息,适用范围广泛.
遗传算法对搜索空间没有特殊要求,不要求可行域是连通的或凸的,对求解问题的数学模型没有特殊要求,不要求目标函数可导,可应用于离散问题和函数关系不明确的问题.
在有限次遗传迭代时,一般只能得到满意解而难以得到全局最优解.
4.1.4构成遗传算法的基本要素
1,染色体编码
遗传算法不能直接处理问题空间的参数,它只能处理以基因链码形式表示的个体[10].因而,使用遗传算法来求解问题的时候,就必须把问题解的参数形式转换成由基因编码按一定结构组成的遗传染色体即个体,这一转换叫编码,也称为问题的表示.从生物学的角度来看,编码就相当于选择遗传物质,它是研究遗传的基础.常用的染色体编码方式有:二进制编码,自然数编码,实数编码等.
2,适应度函数
在遗传算法中,衡量个体优劣的尺度是适应度.由适应度大小来评价群体中每个个体对环境的适应能力,决定某些个体是繁殖还是消亡.因此,适应度是驱动遗传算法不断寻优的动力.从生物学角度讲,适应度相当于"生存竞争,适者生存"的生物生存能力,在遗传过程中有重要意义.
一般而言,适应度函数由目标函数变换而成.标准遗传算法采用赌轮选择机制,按个体适应度来决定当前群体中每个个体遗传到下一代群体中的概率大小.由于要计算每个个体被复制的概率,所以个体适应度必须为非负数.
3,遗传操作
在遗传算法中,遗传操作就是对群体中的个体,按照它们对环境的适应程度施加一定的操作,从而实现优胜劣汰的进化过程.从优化搜索的角度来说,遗传操作可以使问题的解一代又一代地优化,并逐渐逼近最优解.
选择算子
选择染色体的目的是为了强调群体中适应性强的个体,并希
计算机有关论文范例,与硕士学位文重复率武汉相关论文格式模板参考文献资料：