论文网
计算机有关论文范例,与硕士学位文重复率武汉相关论文格式模板
本论文是一篇计算机有关论文格式模板,关于硕士学位文重复率武汉相关电大毕业论文范文。免费优秀的关于计算机及算法及试题方面论文范文资料,适合计算机论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。
0;染色体编码填空题选择题计算题综合题1236152645561519215258311182251829362125333966191121415911192129916314.3.2优化初始种群
初始种群的特性对遗传算法的计算效率有很大影响,要实现全局最优,初始种群在解空间中中应该尽量分散.而传统遗传算法中,随机产生的初始种群可能在解空间中分布不均匀,从而影响算法的性能.所以,应设法在产生初始种群时,使它们尽量均匀分布在整个解空间中.
一种方法[19]是,为初始种群中的个体之间设置一个距离限制,要求入选初始种群的各个体之间的距离必须大于这个限制距离,这样就能保证初始种群的个体之间有较明显的差别,使它们能较均匀地分布在解空间中,保证了初始种群含有较丰富的模式,从而增加搜索收敛于全局最优解的可能.
另一种方法是,首先将解空间分割成若干个子空间,对每个子空间进行初始种群选择,然后将每个子空间的初始种群进行合并,生成总的初始种群,那么这个种群中至少包含了来自不同子空间的个体.本文采用的是第二种方法.
根据本文前面部分对组卷步骤的分析,组卷要先确定知识点章节范围和试题类型,这一步就是试题的初始化操作,根据知识点的约束条件,从总题库中选出符合知识点条件的试题,然后对不同的题型建立各自的成卷试题数据库表.
(图4-1)具体实现过程
下一步,为了组卷方便,我们可以设置题型表[18],用于表示各题型出题数量和考核的知识点.(表4-2)
题型填空题判断题
选择题
简答题
综合题
出题数量20102052题分2015401510考核知识点1,3,25,72,3,68,5,93,6,1116,22,31根据从题型表中得到的各题型包含的题量,在各自的题型数据库表中抽题,抽题时采用随机函数法.这样抽取的一组题目,为一个个体样本,满足题型,题量与知识点的要求.按照这种方法选取多个样本,便可作为遗传算法的初始种群.
(图4-2)个体样本的抽取过程
4.3.3个体适应度函数的自适应改进
算法对适应值的调整是通过适当控制群体适应值的分布,进而控制个体的被选择概率[21].为此,引入一个自适应常数,算法运行过程中根据群体中各个个体的适应值分布情况加以启发,进行自适应调整,改变群体适应值的分布,从而有效地对算法加以引导,使算法快速向全局最优解靠拢.具体方法是,令适应度函数为:
(4-3)
(对于函数极小值问题,只需要一个简单的变换:,在起始时刻,可以给定一个较大的正数.在计算过程中,可以根据群体适应值的分布来自适应调整).
传统遗传算法解决组卷问题时,用组卷目标函数作为适应度函数,很好地反映了染色体与成卷要求之间的差别.但在遗传算法中,一般是适应值越大的个体越好.组卷问题是最小化问题,可取等于100,将目标函数转换为适应度函数:
(4-4)
依据组卷原则,目标函数是越小越好,而适应度函数是越大越好.指数比例既可让非常好的个体保持多的复制机会,同时又限制其复制数目以免其很快控制整个群体,提高相近个体间的竞争,采用指数比例变换方法将转换为:
(4-5)
其中取0.03,它决定了复制的强制性,它越小,复制的强度就越趋向于那些具有最大适应度的个体.
4.3.4选择方法的改进
使用传统的赌轮选择时,在遗传迭代早期,群体中个体适应度差别很大,适应度低的个体生存机会很少,低适应度个体淘汰太快容易使算法收敛于局部最优解.在遗传迭代的晚期,群体中个体适应度差别不大,"优胜劣汰"的作用不明显.本文选择自适应的选择方法.
先计算种群中所有个体的适应度总和,每个个体都有自己的选择概率(为第个个体的适应度).找出种群中所有个体的最大选择概率,对每个个体产生一个的随机数,如果则表示该个体被选中.显然,个体适应值越高,被选中的概率越大.但是,适应值小的个体也有可能被选中,这样有助于增加下一代群体的多样性.
4.3.5交叉算子的自适应性改进
遗传算法的交叉概率影响着算法的收敛性.越大,新个体产生的速度就越快,而遗传模式被破坏的可能性也越大,使得具有高适应度的个体结构可能被破坏,过小,会使搜索过程缓慢,以致停滞不前.为了加快遗传算法的搜索效率,保护优良试卷个体,在本组卷系统中根据种群的进化情况采用自适应函数来动态地调整交叉概率Pc:
(4-6)
其中,是交叉概率,为群体适应度的最大值,为群体适应度的平均值,为两个交叉个体中的适应函数值较大的一个,为概率系数,.从公式可以看出,越大时,越小,越小,小于群体适应度的平均值时,则趋于相同的概率系数.即对于适应函数值大于平均值的个体,其受破坏的可能性较小,而对于小于平均适应函数值的个体,其受破坏的可能性较大.这样便达到了好的个体尽量被保留,差的个体尽量被替代而淘汰.
在进化之初,各染色体之间的适应度差别较大,种群的多样性较强,取较大值,以加快进化速度,随着进化的发展,各染色体之间的适应度差别变小,此时,取较小值,减缓进化速度,避免陷入局部最优.因此,自适应函数能够为每个试卷个体提供一个较为合适的值.这种自适应交叉算子在保持试卷群体多样性的同时,保证遗传算法的收敛性并防止遗传算法陷入局部最优.
为保护优良的试卷个体,自动组卷染色体交叉改进为在相同题型组内进行单点交叉,各种题型在各自的编码组中独立进行交叉操作,交叉点随机选取.
随机选取两个双亲染色体,计算交叉概率,并产生0~1的随机数,将随机数与交叉概率相比较确定是否进行交叉操作.若随机数小于交叉概率,则进行交叉操作.随机选定交叉点,进行交叉运算得到两个新的个体.例如,选择两个双亲,双亲的染色体如下,组卷中交叉操作生成子代的形式如图:(图4-3)
填空题选择题计算题综合题1236152645561519215258311182251829
36212533396619112141591119212991631交叉前两张试卷的染色体
1236253339661511215258311212951831
36211526455619192141591119182291629交叉后两张试卷的染色体
4.3.6变异算子的改进
由于普通的变异操作可能会使用户指定范围外的题目出现在染色体中,也会使各题型的题目数难以保证.本文采用有条件的变异算子,即每个个体的每一个基因座上的基因都按设定的变异概率在一定范围内(考试范围内与该基因题型相同且知识点与本个体其他题的知识点不重复)变异.大量的随机试验表明[10]变异概率在0.001~0.01的范围内取值是比较合理的.对每一个个体的每一个基因(试卷中的每一道试题),在0~1之间产生随机数与比较,若不大于,则发生变异操作.
最后,针对试题组卷的具体情况,我们将2.2所述组卷策略和4.3所述改进遗传算法的组卷算法应用于试题组卷中,并在具体的应用环境中对环境变量进行改造,使得组卷算法更为高效.
(图4-4)改进遗传算法的组卷算法流程图
总结与展望
总结:
针对文章开头提出的组卷相关课题,本文做了以下主要工作:
1,对组卷算法的研究背景进行了比较系统的总结.
2,对计算机自动组卷算法进行初步归纳总结,在基于教育测量理论基础上,探讨了影响试题质量的因素,并从分析组卷策略入手,介绍了组卷的一些基本原则,接着分析了试卷各项评价指标的作用以及关系,建立了组卷的数学模型,最终得出了组卷的目标函数.
3,研究组卷算法时,由于对算法不熟悉,作者陷入了困惑.通过几周的比较学习,参考大量论文资料,分析了几种常用的组卷算法的优缺点后,从自动组卷的基本思想出发,选定遗传算法作为组卷算法,因其智能性,并行性比较适合组卷流程.文中对基本遗传算法理论以及改进方面详细进行了介绍,目标是将改进的遗传算法应用于组卷.针对试题生成系统的自身特征,本文采用自然数编码的遗传算法,并采用基因分段独立编码的方式,利用
计算机有关论文范例,与硕士学位文重复率武汉相关论文格式模板参考文献资料：