当前位置 —论文—写论文— 范文

计算机有关论文范例,与硕士学位文重复率武汉相关论文格式模板

本论文是一篇计算机有关论文格式模板,关于硕士学位文重复率武汉相关电大毕业论文范文。免费优秀的关于计算机及算法及试题方面论文范文资料,适合计算机论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。

望其后代也能具有较强的适应性.选择算子选择强度应该适中,选择强度太大将会使局部最优个体在群体中占优势,从而使群体的多样性减少,使群体陷入局部最优,影响群体进化.反之,选择算子选择强度太小,将极大地缓解群体进化过程.常用选择方法有:次序选择,竞争选择,适应度成比例选择.

交叉算子

遗传算法的主要特点就是使用交叉算子.一方面,它使得在原始群体中的优良个体的特性能够在一定程度上保持.另一方面,它使得算法能够探索新的基因空间,从而使新的群体中的个体具有多样性.常用的交叉算子有:单点交叉,多点交叉,均匀交叉等.

变异算子

变异算子的基本内容是,对群体中的个体串的某些基因位置上的基因值做变动.遗传算法中使用变异算子使得遗传算法具有局部的随机搜索能力,可使遗传算法维持群体的多样性.常用的变异算子有:自适应变异,均匀变异等.

4.2采用传统遗传算法的组卷算法

传统的遗传算法中,采用{0,1}k上的定长二进制串编码方式[13],将一群二进制串作为种群.问题的一个解对应一个长度为k的二进制串.从初始种群出发,采用基于适应值大小的选择策略,在当前种群中选择个体,使用杂交和变异来产生下一代种群.如此一代代演化下去,直到满足期望的终止条件.具体步骤如下:

染色体的编码和定义适应度函数

试题库由m道试题组成,则编码就用m位长的二进制编码表示:x1x2x3等xm,若xi为1,表示该题被选中,若xi为0,则表示该题未被选中.一份试卷有n道试题,x1x2x3等xm中就有n个1.

个体的适应度函数应能保证任何个体的适应度值都是非负的,且能反映个体的优劣,或能反映个体对环境的适应能力.在组卷算法中,选取的是各约束条件与目标值的误差值,见式(2-20):

(4-1)

所以越小的个体对环境的适应能力越强,被选择用来繁殖后代的机会越大.

产生初始群体

随机产生N份试卷个体构成初始群体.N为群体规模,它影响遗传算法的最终结果及其执行效率.若N取得太小,每一代处理的染色体数量不多,搜索效率不高,且易陷入局部最优解.若N取得太大,每一代的适应度值计算量太大,计算效率不高.

个体评价

计算群体中每个个体的适应度值,用组卷的目标函数作为适应度函数.

停机条件的判断

若群体中存在最优个体,或已经满足预先设定的停机条件则输出最优解后停机,否则转下一步.

选择

按照某种选择策略,从群体中选择出若干个体进入交配池.交配池中的个体通过遗传算子的作用产生新一代群体.选择策略应遵循的基本原则是:适应度值越小的个体被选中的概率应该越大.

交叉和变异

定义适当的交叉和变异算子.通过交叉,变异算子的作用,交配池中的个体产生新的个体,构成新一代群体.

跳转第(3)步

遗传算法就是这样不断进行个体评价,选择,交叉,变异,如此循环往复,使群体中的个体朝着最优解的方向不断移动,直到获得在误差允许范围内的试卷.

以上步骤可以简单表示为:

{GA等于(B,Q(0),N,S,C,P,f,T)

B:试卷个体的编码方法Q(0):试卷初始群体的大小

N:种群数S:选择算子C:交叉算子P:变异概率f:适应度函数T:终止原则

初始化种群Q(t):t等于0//t为当前种群代数

计算群中各个体的适应值

执行选择操作

while(不满足终止准则)do

{执行选择生成父代个体

执行交叉,变异

产生新一代种群

计算新一代种群中个体适应度值

保留最好解

执行选择产生新的种群Q(t+1):t等于t+1}

输出结果}

主要算法段用VC++语言描述为:

voidGA()//智能组卷的遗传算法

{intt等于0,

initialize(p(t)),//初始化,产生初始试题号集合

calcufit(t),//计算适应度

do{if(r<,等于Pm){select_parent,//选择父体

mutation,//变异}

else{select_parent,

crossover,//交叉}

}while(满足迭代终止条件)

cout等//输出最终的题号}

这种传统遗传算法解决组卷问题时,结构较为简单,遗传操作方便,具有较高的专家水平.但当题库比较大时,容易导致编码过长,解码繁琐,难以在遗传操作过程中处理约束条件,搜索耗时,而对于小规模的题库,有可能导致组出的试卷中试题重复率较高.

4.3改进遗传算法的组卷算法

设计遗传算法的一个原则[20]就是要在保持群体多样性以不断拓展搜索空间的同时,对群体施加一定的选择压力,以保证搜素过程是进化的.但这两者又是矛盾的,当增大选择压力时,就会使遗传搜索倾向于群体中的较好个体,从而降低群体的多样性,并使算法较快地收敛到局部最优解.反过来,为保持群体的多样性,就必须降低选择压力以拓展搜索空间,从而不得不进行大量的计算,使算法的搜索效率变低,这也是遗传算法计算量巨大的原因.因此,如此在这两者之间取得平衡,是改进遗传算法时必须考虑的问题.

根据前面部分的叙述以及实际过程中的操作,采用传统的遗传算法会出现以下问题:1)在传统遗传算法中,初始种群的每个字符串中"1"的数目等于试题的数目n,进行遗传操作后,字符串中"1"的数目可能大于或小于n,从而变成非法解,此时,必须对解进行修正,而修正过程很复杂,运算量大.2)组卷对生成试卷的各个属性指标要求不一样,对于考试分数,我们希望没有误差,而对于题型,章节,难度系数,区分度,认知层次等只要在误差允许的范围内就可以了,换言之,组卷工作仅仅为了组成一份误差在可接受范围内的试卷,并非要求试卷的整体指标一定是全局最优的.3)使用遗传算法求解多条件约束优化问题,初始种群可以随机生成.但若能使用已经满足一定条件的种群作为初始种群,定能极大加快遗传算法的计算速度.基于以上问题,我们可对传统遗传算法的个体编码,初始种群,杂交运算进行改进.

4.3.1个体编码的改进

使用二进制编码,虽然在组卷上取得过成功,但随着题库试题量的增多,染色体长度不断增长,计算复杂,导致组卷时间变长.针对这一弊端,同时利用标准化试卷中每种题型所占分数和题数相同的特点,采用分组自然数独立编码[14]的策略.独立编码就是将合成编码分解成几个相对独立的组,按各个题型分组编码,每一组编码反映一种题型,每组长度由题库内该题型题数决定.采用自然数编码就是用自然数编码策略,直接利用试题编号编码.为了加快遗传算法的收敛并减少迭代次数,试卷初始种群是根据各题型的题量要求,从初始化后的具有知识点约束属性的试题分库中随机产生,保证了初始种群既满足知识点约束又满足题型和题量的要求,并且染色体中的题目不会过多,为以后的染色体运算减少复杂度.因为编码长度由题库中的试题数决定,若题库中有种题型,每种题型的试题数分别为,而每一组编码的长度就是由题型数决定的.所以有:

大学生怎么写计算机论文
播放:24569次评论:5379人