有关硕士学位论文重复率武汉毕业论文写作资料-论文写作网

简介:关于本文可作为相关专业算法试题论文写作研究的大学硕士与本科毕业论文算法试题论文开题报告范文和职称论文参考文献资料。

算法试题论文范文

　　 1,本论文的目的,意义: 随着当今教育的发展,现代考试对试卷的测量学特性要求越来越严格,不仅要在考核的内容范围,能力层次方面符合事先指定的要求,而且平均分,考试时间,区分度等方面也要符合要求.同时,如何做到高效,经济,灵活,及时编出需要的试卷也显得尤为重要.在试题编制过程中,组卷算法起着举足轻重的作用.它的优劣直接影响组卷的质量和成功率.从题库建设和组卷算法的发展来看,目前还没有一种比较完美的试题生成办法.设计一个算法从试题库既快又好地抽出一组最符合考试要求的试题,一直是有关科研工作者不断探索的课题.

　　本文应在详细分析组卷评价体系的基础上,拟提出一个智能组卷的数学模型,并结合当前存在的组卷算法,拟组建一个改进算法用于组卷问题.拟考虑以遗传算法所涉及的初始种群的优化,适应度函数的设计,个体编码的改进以及交叉算子和变异算子的自适应性等方面予以改进,缓解全局优化中容易出现早熟和收敛速度慢的问题,设计一种较优的算法用于组卷过程,提高组卷的成功率.

　　 2,学生应完成的任务 (1)掌握测量学相关知识;(2)学习组卷的相关知识,弄清组卷流程;(3)总结目前常用的组卷算法,了解它们的实现过程,归纳它们的优缺点;(4)解决组卷问题的建模方法,在此过程中,提高分析解决问题的能力;(5)学习遗传算法,熟悉算法的具体步骤和实现过程,详细说明对算法的改进方法;(6)查找相应的资料文献,完成论文.

　　 3,论文各部分内容及时间分配:(共 16 周)

　　第一部分查阅资料及相关文献 ,进行整理. (2周)

　　第二部分学习测量学和组卷的相关知识. (3周)

　　第三部分构建组卷的评价体系和数学模型,学习遗传算法 . (4周)

　　第四部分根据遗传算法的实现过程对它的几个步骤进行改进 . (2周)

　　第五部分修改论文和制作答辩时文档. (3周)

　　评阅及答辩 (2 周)

　　备注毕业论文的内容可有所变动,但论文的主要方面应与本论文题目相关 .

　　指导教师: 年月日

　　审批人: ____ 年月日

　　摘要

　　组卷问题是一个在一定约束条件下的多目标参数优化问题,采用传统的数学方法求解十分困难,自动组卷的效率和质量完全取决于试题库的设计以及抽题算法的设计.如何设计一个算法从试题库既快又好地抽出一组最符合考试要求的试题,是本文研究的目的.

　　目前已出现多种算法用于自动组卷,如随机抽取策略,回溯试探策略,遗传算法等.这些算法在大的解空间,多峰值的问题上往往容易陷入局部最优或算法复杂度过高.由于自动组卷要求生成的试卷能最大程度地满足用户的不同需要并具有随机性,合理性.因此,必须寻找更加行之有效的算法.在对国内外大量相关文献分析研究的基础上,本文研究了一种改进的遗传算法及其在组卷中的应用.

　　本文首先对试题生成策略的研究背景进行了比较系统的总结,详细分析了试题生成过程中试卷的各项约束条件.文中重点分析了试卷的评价指标,各项指标的作用及几个重要指标间的关系.在这些知识的基础上采用各个评价指标的分布构建了成卷模式,并根据成卷模式定义了评价试卷质量的偏好关系,建立组卷数学模型,并对模型进行简化处理.

　　其次,详细介绍了改进遗传算法应用于组卷问题的解决步骤,涵盖了其中的各项关键技术:包括组卷策略,编码方案,适应度函数的确定,选择交叉变异算子,遗传算法的实现等.

　　最后,依据自动组卷问题的特点,本文采用分组自然数编码,减少了染色体长度空间,编码直接采用试题编号,省去了编码和解码的繁琐.利用这种方式,在编码时就可以解决在试题生成问题中题型及各题题量大小这两个约束条件,简化了求解的问题.将初始化的试卷随机抽取两份进行配对,采用有条件的"顺序交叉",在染色体交叉和变异改进中采用相同题型组内的单点交叉变异.

　　关键词:试题库组卷适应度函数改进遗传算法

　　 ABSTRACT

　　 The test paper generating is an optimized problem to multi-objective parameter with certain restriction. The optimization is implemented very difficultly by traditional method. The quality and efficiency of auto-generating test paper is all determined by the test questions-database designs and get problems-terms algorithm. The aim of the research is to design an algorithm that can get a group of test problem terms quickly, which fit the restriction of test requirement.

　　 Several algorithms h论文范文e been applied in test paper auto-generation, such as randomization strategy, trace and trial strategy, geic algorithm and so on . When encountering with big solution space, multimodal problems, these algorithms are usually inclined to run into local extremi论文范文 or difficult to solve. Since generated test paper needs to fulfill variable demand with great randomness and rationality, a more effective algorithm is in great demand. A great deal of articles from inside and outside analyzed, the thesis is to develop an improved geic algorithm, and apply the algorithm in the test paper auto-generation problem.

　　 Above all, this thesis systemically summarizes the research background of auto-generating test paper strategy, detailedly analyzes all kinds of constraint conditions during the process of auto-generating test paper .This thesis focuses on the analysis of the papers of evaluation criteria, indicators and the role of several important indicators of the relationship between them. In the knowledge base on the use of indicators constructed distribution model into volumes. According volume and pattern definition into the evaluation of the quality of the papers preferences, we establish a mathematic model to generate test paper and simplify it.

　　 Secondly, this thesis details on the improved geic algorithm used in geic test paper steps to solve the problem, covering one of the key technologies, including the establishment of test paper strategy, coding programs, fitness function identification, choice of crossover and mutation operator, geic algorithm realization.

　　 Finally, aiming at the characteristic of automatic generating test paper system, this thesis makes use of the national code which is used in the geic algorithm in order to decrease space of chromosomes. This coding style can resolve two constraint conditions of question sorts and question quantities during coding and simplify the problem of drawing the results. The initialization test paper will be selected two to match randomization, using the condition "order crossover", and one-point crossover mutation of the same 论文范文ic group in the chromosome crossover and mutation improved.

　　 Keywords: item bank, paper-design, fitness function, improved geic algorithm

　　第一章绪论 1

　　 1.1 研究的背景和意义 1

　　 1.2 计算机智能组卷中要解决的重要问题 2

　　 1.3 本文的主要工作 3

　　第二章组卷的评价体系与建模 5

　　 2.1 组卷的基本原则 5

　　 2.1.1 试卷信度和效度 5

　　 2.1.2 组卷的基本原则 7

　　 2.2 组卷策略 7

　　 2.3 组卷步骤 8

　　 2.4试题参数及其说明 9

　　 2.5组卷的数学模型 12

　　 2.6组卷过程的难点及其解决办法 18

　　第三章常用组卷算法介绍 20

　　 3.1 随机抽题成卷算法 20

　　 3.2 自动成卷算法 20

　　 3.3 倒塔式收缩成卷算法 21

　　 3.4 回溯试探成卷算法 21

　　第四章遗传算法在组卷中的应用 22

　　 4.1 遗传算法 22

　　 4.1.1 遗传算法概述 22

　　 4.1.2 遗传算法的基本思想 22

　　 4.1.3 遗传算法的特点 23

　　 4.1.4 构成遗传算法的基本要素 23

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

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

　　 4.3.1 个体编码的改进 27

　　 4.3.2 优化初始种群 28

　　 4.3.3个体适应度函数的自适应改进 30

　　 4.3.4选择方法的改进 31

　　 4.3.5交叉算子的自适应改进 31

　　 4.3.6变异算子的改进 33

　　总结与展望 35

　　致谢 37

　　参考文献 38

　　附录 40

　　第一章绪论

　　随着计算机技术的发展,如何有效地利用计算机从已有的标准试题库中自动,成功,高效地组合满足考试目的的试题,形成具有专业教师水准的试卷是一项非常有意义的课题.在过去的近三十年中,关于组卷技术的研究,结合教育测量学的发展,已产生众多的理论知识.但各种组卷方法在实际应用中仍存在不成熟之处,因此,组卷算法的研究仍是一项具有深远意义的课题.本章将从组卷技术研究的背景和意义出发,提出组卷中的几个重要问题,确定本文要完成的几项工作.

　　 1.1研究的背景和意义

　　当前,许多学校采用的都是传统的考试方式,通常由任课老师出几道题目,然后按主观制定的评分标准打分.这种考试方式的不科学性表现在:1)从命题到评分都有主观性,不能做到授课教师和命题教师的分离,影响了考试的准确性和可靠性.2)难以满足现代考试对知识点,认知层次,平均分,考试时间,区分度,难度系数等测量学的要求.3)若考试规模大,教师的工作量变得相当繁重.针对传统考试这些弊端,广大教学科研工作者开始探索能高效,经济,灵活,保密,及时编制试卷的方法,以使现代考试更科学化,标准化.

　　随着计算机与数据库技术的飞速发展,计算机应用已经深入到人们生活的各个方面.科研部门利用计算机高效的管理数据能力,进行了题库组建,将适合一定考核目标,具有必要参数的大量优质测验项目集合在一起.实践证明,题库的构建在一定程度上推动了考试的大规模发展.目前,国内研制的较有影响的题库系统有清华大学研制的高等学校工科高等数学课程试题库系统,南京大学计算机技术系研发的PASCAL题库系统,山东省高教自考办公室等联合编制的高等数学财经类题库系统等[1].但这些系统大多没有自动组卷功能,因此,组卷系统的研究逐渐成为题库建设的热点.组卷即先组建一个比较完整的题库,然后计算机根据用户给定的约束条件从题库中搜索满足要求的试题,自动组合成一套比较完整的试卷.

　　近几年,国内外许多科研单位和学校机构都对组卷系统进行了研究,但至今还没有一个很好的组卷方案.自动组卷的效率与质量取决于组卷算法的设计.如何设计一个算法从题库中既快又好地抽出一组最符合用户要求的试题,涉及到一个全局寻优和收敛速度快慢的问题.

　　目前,常用的组卷算法有随机抽题成卷算法,自动成卷算法[2],倒塔式收缩成卷算法[3],回溯试探成卷算法[4].对于随机抽题成卷算法,在随机抽取试题的过程中,可能发现抽出来的试题不符合某种要求,如整体难度系数超出预定的难度值,或者考试过程中预计学生所花费的考试时间超过给定的考试时间等原因,从而导致本次组卷过程失败.由于随机抽取的试卷存在过多的无效试卷,而导致组卷效率比较低,因此许多研究者基于随机抽取算法的基础上,提出了自动成卷算法与倒塔式收缩成卷算法.算法在组卷过程中采用随机的方法抽取试题,但在抽取过程中通过验证所选择的试题是否满足系统给定的目标条件来决定该试题是否抽取.当发现目前没有任何试题满足要求而组卷过程又没有完成时,则采用回溯试探方法,通过废弃前一段时间所做的组卷操作来重新进行组卷.由于这种方法在组卷过程中通过废弃部分工作而不是废弃本次组卷过程中的全部操作,从而有效降低了无效组卷的次数,使自动组卷算法的性能得到提高.但这种算法缺乏专家知识的启发式搜索,耗费时间也难以估量.许多研究者开始利用人工智能的方法试图改进自动组卷的性能,并提高组卷的质量.由于组卷算法的目的是从试题库中对各试题单位进行组合,使组合出来的试卷能够基本满足用户给定的各项指标,对应这种问题存在多个可行解,对于用户来说,无所谓最优解,这一点恰好可以结合遗传算法适合大规模并行,可同时搜索解空间的多个区域的特点.将遗传算法改进为一种快速有效的组卷算法因此而成为了一项具有一定实际意义的课题.

　　 1.2计算机智能组卷中要解决的重要问题

　　试卷是教师用来在规定时间范围内对某一个群体在某一知识领域的理解程度所进行的检验与评估的重要手段.学生经测试后,会在各个知识点的掌握上显示出差异,老师便能通过差异对学生采取针对性的指导,同时调整教学方式,使之适应学生的实际要求.试卷质量的好坏直接影响对考生真实情况的反映,因此,试卷难度以及对知识点的覆盖程度是组卷过程中非常重要的问题[16].此外,如何利用专家的组卷经验对题库中的试题进行有效组卷也不容忽视.

　　概括而言,应用计算机进行组卷过程中,必须注意的几个重要问题[4]是:

　　 1)试卷使用对象

　　在组卷之前,首先应对本次出题的对象进行全面了解.了解考生的整体水平,对相关知识点的掌握情况,知识点的认知层次要求等.

　　 2)试卷属性

　　为使试卷满足教学和教师要求,应合理定义试卷属性,常用与组卷相关的属性有:知识点,题型,题量,认知层次,难度等.

　　 3)试题各项指标的衡量

　　由于题库中的试题是由不同老师提供的,每位老师对各个知识点的要求也不尽相同,这必然导致对题库中每道试题的各项指标的衡量缺乏统一标准,从而导致组卷系统的客观性受教师主观能动性的影响,使得计算机智能组卷的性能受到干扰.因此,应通过考生的考试结果调整试题各项指标,使之更接近考生的真实水平.

　　 4)试卷的评估

　　在组卷过程中,系统按照预定的指标信息从试题库中挑选单元试题,以在满足组卷要求的情况下组成试卷,实现计算机自动组卷的目的.在组卷完成后对于组卷程度是怎样的情况,许多系统并没有对这个问题进行考虑,只是简单地从试题库中抽取试题就完成了任务,并没有考虑在组卷过程中由于算法的输入可能导致组卷的试卷质量比较差.在这种情况下,应考虑将试卷的组卷效果的真实情况反馈给计算机,以便计算机能够自动地对组卷算法中的各项参数进行适当地调整,以便在下次进行组卷的时候能够提高组卷的性能.

　　 1.3本文的主要工作

　　本文的主要工作是鉴于组卷中待解决的几个问题,根据教育测量学理论,制定符合教育测量学理论的试题属性,首先提出组卷的评价体系,对组卷过程进行建模,接着针对现有的计算机智能组卷技术进行了深入,系统地研究,最后综合现有算法的特点,提出了改进遗传算法的组卷算法,并对其实用性进行详细地分析.本文的具体章节安排如下:

　　第1章介绍了计算机组卷的背景与意义,简单说明了组卷过程中面临的重要问题.

　　第2章对组卷的评价体系与建模进行介绍,分别阐述了组卷基本原则,组卷策略,组卷步骤,详细对试题参数进行了说明,提出了组卷的数学模型.

　　第3章对常用的智能组卷算法进行介绍,并分析了它们各自的应用技巧与实现过程,指出了它们的优缺点.

　　第4章基于现有算法的基础上,提出了改进遗传算法的智能组卷算法,算法思想是把组卷问题的解表示成染色体,通过遗传算法的几个步骤,寻求问题最优解,即符合用户要求的试卷.

　　结束语部分对文章进行了总结,提出了智能组卷过程中还存在的其他问题,并对论文下一步的工作进行了展望.

　　第二章组卷的评价体系与建模

　　组卷是题库建设的核心环节,它的成功率直接影响试题的质量,从而影响考试质量.所以,组卷工作的科学性建设尤为重要.组卷的科学性主要体现在代表性和针对性.代表性是指试题取样能足够反映考试内容.针对性是指试题本身编制要合理,对不同的考试对象有不同的体现.本章目标是:先根据组卷的基本原则,提出组卷策略和组卷步骤,然后详细设计了试题参数,使之易于组卷算法的操作,最后提出了组卷的数学模型.

　　 2.1组卷的基本原则

　　 2.1.1试卷信度和效度

　　 1,试卷信度

　　信度[1]指的是测量结果的稳定性程度,简单地说就是测量结果的可信程度.如果用同一测量工具反复测量同一特质对象,则多次测量结果间的一致性程度就叫信度.各种类型的测量,无论是物理测量还是教育测量,先后向同一对象施测后,所得数值很难做到绝对一致.每次测量结果实际上包含了被测量特质对象的实际水平和测量误差两部分.如果每次测量结果中误差部分都很小,那么测量结果必然是稳定的.由于考试中测试对象的特殊性,出现测量误差的可能性更大,如考试环境,完成时限,主被试的关系,被试的动机和情绪都可能影响到考试的结果.信度在这里就是指对这种随机误差的控制.

　　 2,影响试卷信度的因素及提高试卷信度的方法

　　信度是测量过程中随机误差大小的反映.随机误差大,信度就低;随机误差小,信度就高.测量过程会引起随机误差的因素,例如被试,主试,测试内容,实测情景等都会影响测量信度.这些因素有些是难以改善的,如被试者个体差异的程度,试卷内容的同质性等因素;但有些因素却是可以通过被试,主试的努力,采取相应的对策而得以改善的.

　　被试个体差异的程度.

　　被试之间的差异是指被试水平的高低程度,它在每次测量中都是难以避免的.

　　试卷的长度.

　　试卷的长度主要指试卷所包含题目的多少.题目越少,则考试得分就越容易受试题抽样偶然性的影响,因而考试信度也越低.一般情况下,加大试卷的长度就能提高考试的信度.

　　试卷内容的同质性程度.

　　一般地,内容性质相同或相近的试卷,和内容性质不同或相差较远的试卷比,前者信度往往较高,后者信度往往偏低.

　　试卷的难度.

　　试卷难度对考试的分数分布状态发生直接的影响,当考试难度过高或过低时,分数呈偏态分布.此时得分大部分集中在低分段或高分段.分数分布的范围和分数之间的差异较小,信度也就小.大量实践表明,当试题难度取值在0.3至0.7区间时,使试题难度接近正态分布,较有利于提高考试信度.

　　 5)考试中出现的各种偶然性因素.

　　考试中出现的各种偶然因素也是影响信度的一个方面.可提高考试的标准化程度,减少无关因素的干扰.

　　 3,试卷效度

　　效度[1],就是一次测量的有效程度,是指一个测验或量表实际能测出其所要测量的特性的程度.测验或量表是测量使用的工具,如果测量能测出其所要测的特性,我们就认为这个测验或量表是有效的.效度指标是测量质量的一个重要方面,测量工具效度太低,就失去了存在的价值.效度是反映一项考试实现其既定目标的成功程度的指标.考试效度指的是根据考试分数做出推论或预测的准确性程度,是程度上的概念.评价试卷效度的高低,主要看它达到既定目标的程度.一般来说,影响效度的因素主要是系统误差,考试内容的同质程度,应考者差异程度,试卷的长度.

　　 4,提高试卷效度的方法

　　 1)精心编制试卷,题目样本要能较好地代表欲测内容或结构.题目的难易程度,区分度要适当,数量适中,避免系统误差.

　　 2)严格控制随机误差.测验实施者一定要严格按要求进行操作,指导语要清楚,尽量减少无关因素的干扰.

　　 3)提供标准的测试环境.让被试能正常发挥水平.

　　 4)适当增长考试的长度.

　　 5)适当控制试题的同质程度.提高考试内容的同质程度有助于提高考试的信度,但却使效度降低了.这就要求我们"彼此兼顾",妥善处理好信度与效度的关系.Tucher研究表明,当试题取中等相关时(0.1—0.6)时,可求得相对满意的效度(0.3—0.8)和信度(小于0.9).

　　 2.1.2组卷的基本原则

　　根据对试卷信度和效度的分析,可总结出组卷过程的几个基本原则:

　　 1)组卷必须全面反映大纲的广度和深度,既要反映考生对基本知识和技能的掌握程度,又要考核考生灵活运用所学理论去分析,解决问题的能力.

　　 2)确定好一份试卷出多少道题才符合大纲要求.由于每门课程都有重点章节和非重点章节,在决定成卷时,重点章节应多出题,反之,应少出题.同时,要避免试题重复出现.

　　 3)在组卷时,应考虑试题类型的多样化,以考查考生的综合能力.

　　 4)试卷难度分配要恰当.难度太大或太小会降低试题的区分度.若试题太容易,难以激发考生的积极性;若太难,超出考生的能力,易使考生失去信心.对于不同类型的学生,试卷的难度也应有所不同.

　　总之,要按照用户指定的考试目的,考试范围,考试时间,考试期望平均分组卷.

　　 2.2组卷策略

　　题库建成后,系统根据用户输入的参数抽出最适合参数要求的试题,组成试卷,定义这种查询参数以及对这些参数进行变换算法,称为组卷策略[15].组卷策略的实质是将直观明了的组卷参数变换成计算机能直接操作的试题属性项,然后根据这些属性项,在题库中抽题组卷.

　　组卷问题就是从题库中选择满足所有组卷要求的试题子集.从题库中组出满足要求的试卷,取决于题库的结构,组卷策略,成卷算法的优劣.组卷策略的优劣取决于所选取的抽题算法及相关的约束条件,前者是提高组卷速率的保证,后者是确保组卷符合用户要求的重要因素.

　　在组卷策略中,并不是随意输入参数,参数必须符合用户组卷目标中各个约束条件的要求.

　　 2.3组卷步骤

　　组卷就是按照给定的组卷策略,从题库中抽取适当的题目组成一份符合要求的试卷.在一般的考试中,组卷的过程应遵循以下几个步骤来组成一份有效的试卷.

　　 (图2-1)组卷步骤

　　根据上图组卷分为以下几步:

　　 1)确定考试知识点的范围,即考的章节范围.分清哪些知识点是重点,哪些是只要求了解就可以的.

　　 2)确定试卷包含哪几个题型.

　　 3)确定各题型的题量和完成整个考试的时间.

　　 4)确定试卷的结构,就是按章节的重要程度确定各章节在试卷中的比重,即各知识点在试卷中的分值比例.

　　 5)确定试卷难度和区分度,这一步骤很关键,它们的选取会影响到整个考试的信度和效度.

　　 6)确定与调整各题的分值,是指在试卷组卷允许的误差范围内进行调整,以使分数趋于合理化,以便于对学生的分数进行统计并做出合理的评价,同时满足用户的要求.

　　 2.4试题参数及其说明

　　试题参数是对试题属性及其在考试中的功能进行的定性或定量的描述.它的设计应符合以下要求:(a)易于抽题算法的操作.(b)利于提高组卷效率.(c)全面反映试题的特征.题库用于存放各试题的参数,各字段为试题编号,题型,难度系数,所属知识点,区分度,论文范文度,分值,估计时间,选中时间,试题内容,试题答案,标志位.

　　 (表2-1)试题参数结构

　　字段名类型说明试题编号整型每一道试题有唯一编号题型整型该题属于的类型难度系数浮点型该题的难度所属知识点字符型该题的具体考核内容区分度浮点型区分各水平的考生论文范文度整型试题被选中的次数分值整型该题的分值估计答题时间整型该题的答题时间选中时间日期型该题组卷时被选中年份试题内容指针型题目内容试题答案指针型题目答案标志位整型标记题目是否被选中

　　试题内容类型文字内容字符型图形内容指针型(指向图形文件)

　　试题答案类型答案内容字符型答案图形内容指针型(指向图形文件) 下面分别予以说明:

　　 1)题型

　　将试题类型划分为五种题型:①填空题.②判断题.③选择题.④简答题.⑤综合题.用0～4分别代替这五种类型的题型,在组卷初始化时,根据知识点的约束条件,从总题库中选出符合知识点条件的试题,并对不同的题型建立各自的成卷试题数据库表.这样在进行组卷时,每种题型的试题就会定位在自己的符合出题要求的库表中搜索,减小了搜索范围,加快了搜索速度.

　　 2)试题编号

　　试题编号分为总库编号和成卷分库编号.在组卷初始化前,试题有一个编号,我们称之为总库编号.总库编号不参与运算,只作为试题标记,初始化时,在内存中生成DataSet数据库,并形成5个DataTable数据表,分别表示5种题型.试题在DataTable数据表中按顺序重新编号,我们称之为分库编号.分库编号具有与每一道试题一一对应的性质,在遗传算法中直接作为基因编码参与运算.

　　 (表2-2)从总库中选出的填空题的数据表

　　分库编号题型难度系数知识点区分度论文范文度分值估计时间选中时间标志位 0 0 0.6 AAA 0.8 1 2 1 2017-4-23 1 1 0 0.5 ABA 0.5 2 2 2 2017-3-20 0 2 0 0.2 BBA 0.4 0 2 3 Null 0 等等等等等等等等等等等等等等等等等等等等 3)所属知识点

　　知识点即试题的具体考核内容.知识点的划分按章节和内容从上到下分为3个层次,每一层最多可划分为26个知识点,用字母A到Z表示.例如:AAB表示第一章第一节第二个知识点.BBC表示第二章第二节第三个知识点.当知识点编码不足3层时,后面用X表示.知识点数据以字符型存放在试题记录中.

　　 4)难度系数

　　在试卷命题过程中,针对不同的考试对象,不同教学阶段的考试,命题难度也不同,根据成卷要求,对难度系数进行搜索,得到符合考核难度要求的试卷.试题难度是指全体被试者对该题的失分率,计算公式[1]:

　　 (2-1)

　　其中,为试题的难度系数, 为全体被试者在该题上得分的平均数,为该题题分.越大,越小;当等于,等于0;越小,值越大;当等于0时等于1.的取值范围是:.

　　由于难度系数对不同层次的考生及在不同的教学阶段相差很大(例如学习完立即测试和两个月后测试),为了使难度系数更客观反映考生的情况,可以设计出一种试题难度调整算法.该算法的思想是:题目入库时,由教师的教学经验预估试题的难度系数,以后,根据每次考试的反馈,及时调整试题的难度系数,使其更接近试题的真实难度[6].预估难度系数的四个层次:A类,容易,答对率在70%以上,难度系数小于0.3.B类,中等偏易,答对率50%~70%,难度系数处于0.3~0.5之间.C类,中等偏难的试题,答对率为30%~50%,难度系数处于0.5~0.7之间.D类,难题,答对率在30%以下,难度系数大于0.7.对于难度过高或过低的题,组成的试卷区分度低,所以一般考试试题平均难度应控制在0.5左右,这样的试卷成绩分布才能符合正态分布.而竞赛试题却适合抽取平均难度较高的试题.

　　 5)试题区分度

　　题目的区分度也叫题目的鉴别力,它是由被试者在该题上的得分与被试者的实际能力水平之间的关系来确定的,是衡量题目对不同水平被试者的心理特质的区分程度的指标.试题的区分度一般是由该题的成绩与整个测验成绩之间的相关程度来表示.相关程度高,表明区分度高;相关程度低,表明区分度低.一般来说,求取试题区分度的方法,是计算被试在该题上的得分跟试卷总分的相关系数.其计算公式[1]为:

　　等于 (2-2)

　　为试题i的区分度,为试题的答对率,为答错率,.为答对第i题的被试者总分的平均数,为答错第i题的被试者总分的平均数,为全体被试者总分的标准差.

　　为了给区分度的高低确定一个评定标准,经过大量研究,伊贝尔(R.L.Ebel)提出了试题区分度评价表:(表2-3)

　　区分度值对试卷的评价 0.4以上优良 0.3~0.39 合格 0.2~0.29 勉强可以使用 0.2以下应该淘汰 6)论文范文度

　　论文范文度即试题被选中使用的次数.在题库中,它指该题最后一次被使用的试卷流水号.论文范文度值越大,下次该题再次被选中的概率就要越小.相反,论文范文度值越小的试题下次再次被选中的概率越大.我们还可通过试题难度的变化程度控制试题的论文范文度,如果题目难度明显向容易的方向变化,就会考虑停止使用该题.以一道题的论文范文率与总组卷数比较来决定是否选用该题.

　　 7)最近出题时间

　　为避免相同试题在规定的时间内多次使用,抽取试题时,需要考虑题目最近使用日期.

　　 8)估计答题时间

　　完成该题所需的时间.在该时间内大多数学生能完成并有时间检查该题,数据类型为整型,单位为分钟.该项数据可通过客观测试后由教师根据教学经验加以调整.

　　 9)试题内容

　　表示试题的内容,它不参与组卷的运算.

　　 10)试题答案

　　表示该试题的标准答案,不参与组卷运算.

　　 11)标志位

　　用于组卷过程中区分可选与不可选试题,0表示可选,1表示不可选.

　　以上参数应在题库运行时自动生成.

　　 2.5组卷的数学模型

　　组卷问题实际上是一个多条件的约束优化问题,这种问题通常被定义为一个目标函数和多个约束条件的组合.

　　为考核学生对所学内容的掌握情况,为每道试题定义如下指标:试题编号,题型,分值,难度系数,所属知识点,认知分类,估计答题时间,区分度.组卷中生成一份试卷,就是得到一个m×8的矩阵(m是试卷中试题总数).矩阵的每一行代表一道选中试题的相关信息,每一列是试题的某一控制指标的全部取值.

　　试题编号难度区分度知识点题型认知估时分值

　　 S等于 (2-3)

　　这就是问题求解中的目标状态矩阵.

　　由于计算机组卷是根据试题指标一道道试题进行处理的,教师一般都不可能对所有试题指标进行设置.因此,需要设置一些教师易于理解,容易操作,同时又能很好体现教师考试意图的组卷目标.设置组卷目标的主要依据是一套完整试卷的属性,具体有:试卷难度,试卷区分度,知识点,题型,认知层次,考试时间,试卷总分.

　　下面根据试题属性和组卷目标设计目标函数.

　　在文献[7]中,给出了试卷中各种难度试题的分配方法,运用该方法,可以根据用户期望的试卷难度计算出各种难度值的试题在所有试题中所占的比例及分数.同时,借鉴该方法,我们也可根据用户期望的区分度算出各种区分度值的试题的分数.在文献[8]中,提出了根据题型表,计算某知识点某类题型所出试题数的方法.借鉴该方法,我们可以计算出各认知层次所出的试题数.通过对这几种方法的分析,可以发现,组卷模式其实是一些分数分布.组卷的过程就是从试题库中选择出适当的试题去实现这些分布的过程.每一个分布可以看作是一个需要实现的约束,组卷过程就是一个实现多个约束的过程.

　　设试卷难度-分数分布,试卷区分度-分数分布,知识点-分数分布,题型-分数分布,认知层次-分数分布,考试时间,试卷总分的期望值分别为:, ,,,,.

　　对于一套试卷,为试卷的总题数,为试卷中的第道试题,为试题的分数.

　　设为试题的难度级别,为试卷的第个难度级别的分数,为第个难度级别,为难度级别的个数,用表示试卷难度-分数分布的预估值,有:

　　其中,

　　 (2-4)

　　设为试题的区分度,为试卷的第个区分度级别的分数,为第个区分度,为区分度级别的个数,用表示试卷区分度-分数分布的预估值,有:

　　其中,

　　 (2-5)

　　设为试题的知识点,为试卷的第个知识点的分数,为第个知识点,为知识点个数,用表示知识点-分数分布的预估值,有:

　　其中,

　　 (2-6)

　　设为试题的题型,为试卷中第种题型的分数,为第种题型,为题型数,用表示题型-分数分布的预估值,有:

　　其中,

　　 (2-7)

　　设为试题的认知层次,为试卷第个认知层次的分数,为第个认知层次,为认知层次的个数,用表示认知层次-分数分布的预估值,有:

　　其中,

　　 (2-8)

　　设完成试卷所需的预估时间为,预留检查时间为;则完成试卷所需的实际时间为:

　　 (2-9)

　　其中,为试卷的试题的预估时间.

　　设组成试卷的总分数为,则:

　　 (2-10)

　　其中,为试卷的试题的分值.

　　下面计算试卷各项期望值与预估值的偏差.

　　由于以上各项分布的期望值与预估值都不是一维向量,所以采用欧式距离来度量偏差,偏差越小则试卷越接近期望值.

　　设试卷难度-分数分布,试卷区分度-分数分布,知识点-分数分布,题型-分数分布,认知层次-分数分布,考试时间,试卷总分的偏差分别为.则有:

　　 (2-11)

　　 (2-12)

　　 (2-13)

　　 (2-14)

　　 (2-15)

　　 (2-16)

　　 (2-17)

　　组卷目标就是从一个试题库中,寻找一个子集使得这个子集满足上面所述的成卷模式中的各个约束分布.其中,是试题库的总题量,为一套试卷中的总题量.

　　因此,目标函数就是要使实际得到的试卷中的各指标分布与理论要求分布的偏差最小.这里采用对各分布的所有偏差加权求和,取该和的最小的方法来定义组卷问题的目标函数.

　　令:

　　 (2-18)

　　其中,为各指标的权重,且.

　　作为一个多目标优化问题,对各指标分布与理论要求分布的偏差的优化往往是矛盾的,不能期望它们的极小点重叠,即不能同时达到最优,甚至还产生对立,即对一目标是优点,对另一目标却是劣点,这就要在各目标的最优解之间协调,以取得整体最优.根据对组卷的7个目标的内在含义以及它们对组卷的重要程度的分析,可以发现,若使用式(2-18)的线性加权和法,若子目标数量级不一样,则次要目标会掩盖主要目标,影响优化效果,为解决此问题,可采用规范化加权平方和法[22].即在原来线性加权和法的基础上,找到各目标绝对值的最大值,将其与各目标相比,得到的各目标值将在[-1,1]间变化,为减小各目标差值较大对目标函数的影响,将各项平方后分权相加,目标函数改为:

　　 (2-19)

　　我们可以将7个组卷目标按重要程度分成3类:1)难度,区分度.2)知识点,认知层次.3)题型,总时间,总分数.这样,组卷问题的目标函数就可以简化为:

　　 (2-20)

　　其中,为各类指标的权重,,根据各类指标的重要程度,规定,这样可以加重第三类指标对组卷的影响,根据各类指标重要程度的大小将各类指标的偏差限定在1%—5% 之间.

　　同时,为保证每道试题在连续份试卷中不重复出现,可增加一个约束来控制论文范文率[9].设试卷中任意试题上一次在试卷中出现,本次组卷中试卷的流水编号为.则得到求解组卷问题的目标函数:

　　 (2-21)

　　至此,由上式的约束条件和目标函数已经建立了组卷的数学模型.

　　对组卷目标的分析,还有几点说明如下:

　　 1)试卷难度和考试分数的关系

　　试卷的难度指一份试卷的总体难易程度,显然试卷的难度是由试卷中每道题目的难度来决定的.试卷的难度中等时,考生的分数呈正态分布.试卷难度较大时,考生的分数较低,低分区出现高峰,呈负偏态分布.试卷难度较小时,考生的分数较高,高分区出现高峰,呈偏态分布.试卷难度与平均分的关系:

　　 (2-22)

　　其中,为所有考生的平均分,为试卷的满分,为试卷难度.

　　 (图2-2)试卷难度与分数的关系

　　 2)试卷区分度与试题难度的关系

　　试题难度和区分度有密切的关系[5],当难度过高或过低时,区分度将会很低;当难度在0.5左右时,试题的区分度将会很高,可接近最大值.

　　它们之间的关系式为: (2-23)

　　 2.6组卷过程的难点及其解决办法

　　在组卷过程中,如何保证生成的试卷能充分满足用户的需要,并具有合理性,随机性,科学性是组卷系统实现的难点.

　　 1,为保证随机性,使组卷过程不出现重复的题目,可以采用下面的方法[17]:(1)在试卷参数设计时,为每一道试题添加了标志位,数据类型为整型.在插入试题前标志位的值全部设置为0,然后每插入一个题目,就把该字段的值设置为1,若为1,则不进行任何操作,这样就保证了插入的试题不重复.当组卷结束之后,将标志位的值全部恢复为0.(2)在编制试题编号时,用7位代码表示一道题.其中最高位表示题目类型(如:1填空题,2选择题,3判断题,4简答题,5综合题),第2,3位表示题目所在的章,第4,5位表示题目所在的节,6,7位表示平行题的题号,即同一类型,同一章节,同等难度的第一题,第二题.(例如:1040302,1表示此题为填空题,04表示它在第四章,03表示第三节,02表示同类,同章节,同等难度的第二题).由于编码的唯一确定性,可确保在生成的同一份试卷中,不会抽到相同的试题.本文采用的是第一种方法.

　　 2,为保证试题的合理性和科学性,试题分值根据试题难度,答题时间在试卷中所占的比例与试卷的满分值来确定,试卷的满分值可由出题人根据情况任意设定,满分值不受试题个数的约束.使试卷的试题个数摆脱试卷满分值约束,从而可通过增加试卷试题个数来增加测试效度和信度.

　　第3章常用组卷算法介绍

　　计算机自动组卷是按照教师和教学要求,由计算机自动从题库中选择试题,组成一份符合用户设置的知识点分布,题型,认知层次,难度系数,区分度,时间,分数等要求的试卷.组卷中的难点是:如何保证生成的试卷能最大程度地满足用户的不同需要并具有随机性,科学性,合理性.

　　组卷问题是一个结合了计算理论,算法分析,优化控制等知识的多目标优化问题.国内外的教育研究者针对此问题提出了许多算法,本章将简单介绍其中的几种.

　　 3.1随机抽题成卷算法

　　该方法根据组卷状态空间的控制,由计算机抽取一道符合控制指标的试题放入组卷库,不断重复,直到组卷完毕或无法从题库中抽取满足要求的试题为止.该方法结构简单,对于单道题的抽取运行速度较快,但是对于整个组卷过程来说,组卷成功率较低,且要求试题库题量大,分布良好.

　　 3.2自动成卷算法

　　该方法[2]采用动态地制定试题模式的方式,在组卷过程中,考虑到已产生试题的情况,采用某种推理算法逐题产生下一题.每当在题库中寻找到一道符合当前要求的试题并选中后,将其记入已入选试题题号组,从各指标限定的总分中减去该题分数,并且标记该题以防止它再次入选.当按某一模式找不到试题时,可按照题目控制指标需优先保证的顺序来逐个放宽条件.放宽条件的顺序是:题分,难度系数,章节,题型.该方法方便灵活,适应性好,随机性强.许多组卷算法都是将全卷分数分别分配到各章节中,这实际已将各章节在某题型,某难度系数上出几分的题作了确定的分配,然后按照这个分配到题库中查找,这样的静态分配对题库的要求非常高,一旦题库对该要求不能满足,就要重新修论文范文数分配模式,效率低且随机性差.

　　而本算法中,每一道试题的选择都是根据已入选试题的情况以及题库中现有试题的使用情况灵活处理的,而且是从所有尽可能严格地满足用户要求的试题中随机抽取的,保证了良好的随机性和适应性.但为了实现动态制定试题模式的方法,系统必须多次在试题特征库中查找所有满足当前状态的试题,故该方法在速度上不能保证.

　　 3.3倒塔式收缩成卷算法

　　在组卷过程中,由于试卷参数间的相互制约,它们很难同时得到满足,通常是先随机抽题组卷,再判断试卷参数是否满足要求,不满足时调换试题这种成卷方法.在顺利的时候成卷速度较快,但往往是经过多次更换仍得不到理想的试卷,不得不论文范文重来.大体说来,这种成卷方法的速度是比较慢的.究其原因,主要是把问题留到了最后,也就是说等到问题成了堆才去解决.因此,文献[3]中采用了"倒塔式收缩"的成卷方式,先把各参数值放宽,以保证抽题的随机性,然后将各参数值逐步缩紧,最终收缩到允许的范围内.在组卷过程中,一旦参数值越界,立即强制返回.由于选题过程中先宽后严,并逐步收缩试卷数值范围,直至符合选题要求为止,故称为"倒塔式收缩法".按此种成卷模式,最后的试卷一定是一份合格的试卷,不会出现论文范文重来的局面.

　　 3.4回溯试探成卷算法

　　回溯法[4]是一种"通用的解题法",属于有条件的深度优先算法.该方法是将随机选取产生的每一状态记录下来,搜索失败时,释放上次记录的状态类型,然后再依据一定的规律,变换一种新的状态类型进行试探.通过不断地回溯试探直到组卷完毕或回到出发点为止.按照上面提到的三种方法选取试题,随着选题数的增加,指标间的约束增大,选出来的试题可能不是最优的,此时回溯法往往是有效的.该算法对于试题类型较少和题量较少的题库以及组卷指标简单的试卷而言,成功率较高.但当总题量较大时,组卷时间长,占用的空间复杂度大,程序结构较为复杂,选取试题也缺乏随机性.

　　综合考虑以上几种组卷算法,发现上述算法对于小规模的考试来说,能够比较好地完成组卷,但对于中,大规模的考试来说,组卷时间长,而且,不一定能够满足所有的约束条件,对于用户来说,是不能令人满意的.

　　因此,结合以上几种方法的优点,寻找一种新的改进算法,不仅要具有智能搜索技术,并且要具备收敛速度快的特点.遗传算法以其具有自适应全局寻优和智能搜索技术,并且收敛性好的特性能够很好地满足自动组卷的要求.

　　第4章遗传算法在组卷中的应用

　　通过上章对常用的组卷算法的分析可知,将遗传算法应用于组卷是具有实际意义的.因为通过遗传算法强大的搜索能力得到的组卷参数表,可以保证根据此表抽题组卷时,题库中不会找不到满足所有属性的试题,从而使试卷的总体指标得到满足.

　　作为本文的重点以及难点部分,本章将首先阐述遗传算法的思想以及基本步骤,接着分析传统遗传算法用于组卷的可行性,最后针对遗传算法在应用时的一些弊端,将遗传算法进行了改进,使之更符合组卷问题的实际需求.

　　 4.1遗传算法

　　 4.1.1遗传算法概述

　　遗传算法[11]简称GA(Geic Algorithm)是一种模拟自然选择和自然遗传机制的随机优化算法,它对目标函数没有可微的要求,可以用于解决传统搜索方法难以解决的复杂问题和非线性问题,可广泛应用于规划设计,组合优化,自适应控制等领域.

　　遗传算法的起源可以追溯到上世纪50年代初,最初是几个生物学家用计算机来模拟生物系统.到60年代后期和70年代初期,密歇根大学的John Holland从试图解释自然系统中生物的复杂适应过程入手,模拟生物进化机制构造人工系统模型,形成了较为完整的遗传算法理论和方法.在接下来的几十年中,人们对遗传算法的兴趣日益升温,在该领域也取得了理论研究的进展和丰硕的成果.近些年,随着人工生命研究的兴起,遗传算法的应用和研究也渐渐成熟.

　　 4.1.2遗传算法的基本思想

　　遗传算法的基本思想[13]是把问题的解表示成染色体,在算法中就是经过编码的字符串.在执行遗传算法之前,给出一群染色体,作为假设解.然后,把这些假设解置于问题的"环境"中,按照适者生存和优胜劣汰的原理,从中选出较适应环境的染色体进行复制,再通过交叉,变异产生更适应环境的论文范文的染色体群.这样,一代代进化,最后就会收敛到最适应环境的一个染色体上,这就是问题的最优解.可是,生物物种的进化是很缓慢的,要得到满意的结果,通常要经过上千次甚至上万次交叉,变异.为加快种群的优化速度,需根据实际情况对算法进行改进.

　　 4.1.3遗传算法的特点

　　遗传算法是从某一初始群体出发,遵循进化原则,不断迭代计算,逐步逼近最优解,作为一种搜索和优化方法,它具有以下特点[12]:

　　遗传算法是一种间接的优化方法.它的搜索过程不是直接作用在问题的变量上,而是作用在将变量编码后的字符串上.对给定问题,它可以产生许多潜在解,有较大的选择性.

　　遗传算法的搜索策略不是穷举式的全面搜索,而是利用适应度逐步逼近目标值的搜索,目的明确.

　　遗传算法的搜索过程不是单点搜索,而是按并行方式搜索一个种群数目的点,是从一个群体到另一个群体,减少了陷入局部最优解的风险.它适合大规模并行,可同时搜索解空间的多个区域.

　　遗传算法的搜索过程只依赖于个体的适应度函数,不需要其它辅助信息,适用范围广泛.

　　遗传算法对搜索空间没有特殊要求,不要求可行域是连通的或凸的,对求解问题的数学模型没有特殊要求,不要求目标函数可导,可应用于离散问题和函数关系不明确的问题.

　　在有限次遗传迭代时,一般只能得到满意解而难以得到全局最优解.

　　 4.1.4构成遗传算法的基本要素

　　 1,染色体编码

　　遗传算法不能直接处理问题空间的参数,它只能处理以基因链码形式表示的个体[10].因而,使用遗传算法来求解问题的时候,就必须把问题解的参数形式转换成由基因编码按一定结构组成的遗传染色体即个体,这一转换叫编码,也称为问题的表示.从生物学的角度来看,编码就相当于选择遗传物质,它是研究遗传的基础.常用的染色体编码方式有:二进制编码,自然数编码,实数编码等.

　　 2,适应度函数

　　在遗传算法中,衡量个体优劣的尺度是适应度.由适应度大小来评价群体中每个个体对环境的适应能力,决定某些个体是繁殖还是消亡.因此,适应度是驱动遗传算法不断寻优的动力.从生物学角度讲,适应度相当于"生存竞争,适者生存"的生物生存能力,在遗传过程中有重要意义.

　　一般而言,适应度函数由目标函数变换而成.标准遗传算法采用赌轮选择机制,按个体适应度来决定当前群体中每个个体遗传到下一代群体中的概率大小.由于要计算每个个体被复制的概率,所以个体适应度必须为非负数.

　　 3,遗传操作

　　在遗传算法中,遗传操作就是对群体中的个体,按照它们对环境的适应程度施加一定的操作,从而实现优胜劣汰的进化过程.从优化搜索的角度来说,遗传操作可以使问题的解一代又一代地优化,并逐渐逼近最优解.

　　选择算子

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

　　交叉算子

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

　　变异算子

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

　　 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 ++语言描述为:

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

　　 { int t等于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]的策略.独立编码就是将合成编码分解成几个相对独立的组,按各个题型分组编码,每一组编码反映一种题型,每组长度由题库内该题型题数决定.采用自然数编码就是用自然数编码策略,直接利用试题编号编码.为了加快遗传算法的收敛并减少迭代次数,试卷初始种群是根据各题型的题量要求,从初始化后的具有知识点约束属性的试题分库中随机产生,保证了初始种群既满足知识点约束又满足题型和题量的要求,并且染色体中的题目不会过多,为以后的染色体运算减少复杂度.因为编码长度由题库中的试题数决定,若题库中有种题型,每种题型的试题数分别为,而每一组编码的长度就是由题型数决定的.所以有:

　　 ,,等 (4-2)

　　其中,是试卷所含的题目数,分别为试卷中各个题型所出的题目数.

　　假设各代表一种题型,分别表示对应题型的题目数,,,表示对应题型中选中试题的题号,这样每个染色体就可以表示为:.

　　由于采用了自然数编码,可以克服采用二进制编码搜索空间过大和编码长度过长的特点.同时,按题型分段编码,在随后的交叉和变异操作时也按段进行,保证了每种题型的题目总数不变.以题号编码所表达的意义清楚,明确,不需解码,能有效改善遗传算法的复杂性,提高运算效率.

　　 (表4-1)两张试卷的染色体编码

　　填空题选择题计算题综合题 12 3 6 15 26 45 56 1 5 19 21 52 58 3 11 18 22 5 18 29 3 6 21 25 33 39 66 1 9 11 21 41 59 11 19 21 29 9 16 31 4.3.2优化初始种群

　　初始种群的特性对遗传算法的计算效率有很大影响,要实现全局最优,初始种群在解空间中中应该尽量分散.而传统遗传算法中,随机产生的初始种群可能在解空间中分布不均匀,从而影响算法的性能.所以,应设法在产生初始种群时,使它们尽量均匀分布在整个解空间中.

　　一种方法[19]是,为初始种群中的个体之间设置一个距离限制,要求入选初始种群的各个体之间的距离必须大于这个限制距离,这样就能保证初始种群的个体之间有较明显的差别,使它们能较均匀地分布在解空间中,保证了初始种群含有较丰富的模式,从而增加搜索收敛于全局最优解的可能.

　　另一种方法是,首先将解空间分割成若干个子空间,对每个子空间进行初始种群选择,然后将每个子空间的初始种群进行合并,生成总的初始种群,那么这个种群中至少包含了来自不同子空间的个体.本文采用的是第二种方法.

　　根据本文前面部分对组卷步骤的分析,组卷要先确定知识点章节范围和试题类型,这一步就是试题的初始化操作,根据知识点的约束条件,从总题库中选出符合知识点条件的试题,然后对不同的题型建立各自的成卷试题数据库表.

　　 (图4-1)具体实现过程

　　下一步,为了组卷方便,我们可以设置题型表[18],用于表示各题型出题数量和考核的知识点.(表4-2)

　　题型填空题判断题

　　选择题

　　简答题

　　综合题

　　出题数量 20 10 20 5 2 题分 20 15 40 15 10 考核知识点 1,3,25,7 2,3,6 8,5,9 3,6,11 16,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)

　　填空题选择题计算题综合题 12 3 6 15 26 45 56 1 5 19 21 52 58 3 11 18 22 5 18 29

　　 3 6 21 25 33 39 66 1 9 11 21 41 59 11 19 21 29 9 16 31 交叉前两张试卷的染色体

　　 12 3 6 25 33 39 66 1 5 11 21 52 58 3 11 21 29 5 18 31

　　 3 6 21 15 26 45 56 1 9 19 21 41 59 11 19 18 22 9 16 29 交叉后两张试卷的染色体

　　 4.3.6变异算子的改进

　　由于普通的变异操作可能会使用户指定范围外的题目出现在染色体中,也会使各题型的题目数难以保证.本文采用有条件的变异算子,即每个个体的每一个基因座上的基因都按设定的变异概率在一定范围内(考试范围内与该基因题型相同且知识点与本个体其他题的知识点不重复)变异.大量的随机试验表明[10]变异概率在0.001~0.01的范围内取值是比较合理的.对每一个个体的每一个基因(试卷中的每一道试题),在0~1之间产生随机数与比较,若不大于,则发生变异操作.

　　最后,针对试题组卷的具体情况,我们将2.2所述组卷策略和4.3所述改进遗传算法的组卷算法应用于试题组卷中,并在具体的应用环境中对环境变量进行改造,使得组卷算法更为高效.

　　 (图4-4)改进遗传算法的组卷算法流程图

　　总结与展望

　　总结:

　　针对文章开头提出的组卷相关课题,本文做了以下主要工作:

　　 1,对组卷算法的研究背景进行了比较系统的总结.

　　 2,对计算机自动组卷算法进行初步归纳总结,在基于教育测量理论基础上,探讨了影响试题质量的因素,并从分析组卷策略入手,介绍了组卷的一些基本原则,接着分析了试卷各项评价指标的作用以及关系,建立了组卷的数学模型,最终得出了组卷的目标函数.

　　 3,研究组卷算法时,由于对算法不熟悉,作者陷入了困惑.通过几周的比较学习,参考大量论文资料,分析了几种常用的组卷算法的优缺点后,从自动组卷的基本思想出发,选定遗传算法作为组卷算法,因其智能性,并行性比较适合组卷流程.文中对基本遗传算法理论以及改进方面详细进行了介绍,目标是将改进的遗传算法应用于组卷.针对试题生成系统的自身特征,本文采用自然数编码的遗传算法,并采用基因分段独立编码的方式,利用该方法,在编码时就可以解决试题生成问题中题型以及各题型题量大小这两个约束条件,简化了求解的问题.提出了交叉算子和变异算子的自适应性改进,在保持试卷群体多样性的同时,保证遗传算法的收敛性并防止遗传算法陷入局部最优.运用自适应的选择方法,能很好地抑制非成熟收敛.

　　 4,要验证本文提出的组卷算法,必须要建立一个题库,以便在此基础上考察组卷算法的有效性.但一个题库的建立需投入大量的时间和人力资源.即便设计一个模拟的试题库,要设计足够数量的试题,并对每道试题的属性进行精确划分,其中涉及的数据量之庞大在短期内难以由个人单独完成.所以本文只是对组卷算法进行了理论上的描述,并对其合理性进行了分析,而没有给出具体的算法程序,这些可以在实际操作时进行具体分析.

　　展望:

　　组卷系统是当前各类学校和科研机构在积极研究的系统,它涉及到教育学,心理测量学,人工智能技术等多个领域,目前还没有一种比较完美的试题生成方法,因此,它具有比较高的研究价值和广泛的应用前景.本文的研究主要在理论上对其进行了验证,具体到实际应用中,还需要在以下几个方面进一步深入:

　　 (1)智能试题库的构建问题.

　　 (2)组卷算法中控制参数的选择,以及组卷算法在计算机上的实现问题.

　　 (3)试题生成中题型,分值,答题时间等多种因素对整个试题生成指标的影响度的问题.

　　 (4)应用误差理论研究如何使计算机组卷和用户要求之间差距最小的问题.

　　 (5)利用考生的真实考试情况来修正组卷过程存在的主观性带来的偏差的问题.由专家确定的组卷参数带有很大的主观性,缺乏科学性和客观性.因此,可考虑建立一个精细的模型,由程序自动根据以往的答题情况对试卷的参数进行调整,以便下次组卷过程中能提高计算机组卷的效果.模型要建立得比较符合教育学,心理测量学,人工智能等相关学科的原理,需要各个学科的专家参与组卷标准的制定.同时,还需要计算机方面的专家进行相关算法的开发以实现组卷算法的程序化.

　　 (6)本文组卷问题的目标函数为,见式(2-20):

　　这是一个约束优化问题,处理比较麻烦.可以从原来的试题库中直接剔除不满足论文范文度要求的试题,将满足要求的试题构成一个新的题库.即原来的约束优化问题简化为了无约束优化问题:.这样既避开了约束条件,又缩小了寻优的范围,可提高算法效率.

　　本文的研究具有重要的实际意义.作者相信,随着信息技术的发展以及学科建设的不断深入,本文的科研工作将会在推进教学改革进程方面起到一定的积极作用.

　　致谢

　　论文竟笔,不禁感慨万千.作者通过努力得到的成果与所选科研论题本身的期待相比,仍存在较大的差距.但即使如此有限的阶段性成果,也是与诸多师长,朋友和家人的关心和支持分不开的.

　　首先,特别感谢我的指导老师赵海良教授的悉心指导和谆谆教诲.赵老师凭借丰富的教学经验,从论文的选题,研究思路的确定,论文撰写直到论文修改的整个过程中,都给了我很多的指导和启迪.赵老师渊博的学识和严谨的治学态度,为学生开阔了研究视野,丰富了专业知识.赵老师朴实真诚的做人原则和一丝不苟,勤奋进取的敬业精神,为我们今后的工作和学习树立了很好的典范.

　　感谢数学系的培养,感谢数学系所有给予我莫大帮助的老师们,从他们那里我不仅学到了专业知识,更重要的是我在学术上的修养也得到了进一步的提高.

　　在本科学习期间,得到许多同学,朋友在学习和生活上的帮助,在此表示感谢.此外,我还要衷心感谢所有对我的论文提出宝贵意见和建议以及即将评阅本论文的老师.

　　感谢我的父母和亲友,多年来在我的求学道路中给予我的关心,支持;感谢父母温暖的鼓励.

　　参考文献

　　 [1] 漆树青,戴海崎,丁树良,现代教育与心理测量学原理,高等教育出版社,2002

　　 [2] 顾永跟,开放型试题库系统的设计与实现,湖州师范学院学报,1999.12

　　 [3] 李东亮,张银菊,高等学校无机化学试题库研制,西安建筑科技大学学报,1999.2

　　 [4] 龚完全,基于最小回溯代价的智能组卷算法,湖南大学工程硕士学位论文,2005

　　 [5] 王力发,杨丽敏,教育统计与测量,哈尔滨工程大学出版社,1994

　　 [6] 刘文,刘艳伟,刘秋梅,关于试题难度系数调整算法和组卷算法的研究,燕山大学学报,2007.3

　　 [7] 朱黎明,基于单亲遗传算法的试题生成及其应用研究,湖南大学工程硕士学位论文,2005

　　 [8] 李香英,高校题库建设与试卷生成系统,山东大学硕士学位论文,2007

　　 [9] 陈锋,基于遗传算法的智能组卷研究与应用,北方工业大学硕士学位论文,2007

　　 [10] [美]Z.米凯利维茨,演化程序—遗传算法和数据编码的结合,科学出版社,2000

　　 [11] 董聪,广义遗传算法,大自然探索,1998

　　 [12] 张文修,梁怡,遗传算法的数学基础(第二版),西安交通大学出版社,2003

　　 [13] 唐朝霞,基于遗传算法的智能题库的设计

　　 [14] 周文举,基于遗传算法的自动组卷系统研究与实现,山东师范大学硕士学位论文,2006

　　 [15] 张延华,吴华武,朱杰,毛锐,网络教学试题库与智能组卷系统的设计与实现,企业技术开发,2007.2

　　 [16] B.S.布鲁姆等着,邱渊译,教育评价,华东师范大学出版社,1987

　　 [17] 梁苏妍,崔希民,测量学试题库的设计与开发,矿山测量,2007.3

　　 [18] 杨秀梅,基于遗传算法的组卷系统研究,上海交通大学硕士学位论文,2007

　　 [19] 周芬,改进遗传算法在题库系统中的应用,高校理科研究,2006

　　 [20] 阳明盛,罗长童,最优化原理,方法及求解软件,科学出版社,2006

　　 [21] 王淑佩,基于改进的遗传算法组卷系统应用研究,湖南大学工程硕士学位论文,2005

　　 [22] 孟卓,卜贺,规范化加权平方和法多目标优化设计,哈尔滨科学技术大学学报,1995

　　附录

　　附录1 外文原文选自 rennard.org/alife/english/g论文范文intrgb.html#evolga

　　 Introduction to Geic Algorithms

　　 ? Physics, Biology, Economy or Sociology often h论文范文e to deal with the classical problem of optimization. Economy particularly has bee specialist of that field. Generally speaking, a large part of mathematical development during the XVIIIth century dealt with that 论文范文ic (remember those always repeated problems where you had to obtain the derivative of a function to find its extremes).

　　 ?????Purely analytical methods widely proved their efficiency. They nevertheless suffer from a insurmountable weakness : Reality rarely obeys to those wonderful differentiable functions your professors used to show you.

　　 ?????Other methods, bining mathematical analysis and random search h论文范文e appeared. Imagine you scatter 论文范文all robots in a Mountainous landscape. Those robots can follow the steepest path they found. When a robot reaches a peak, it claims that it has found the optimum. This method is very efficient, but there's no proof that the optimum has been found, each robot can be blocked in a local optimum. This type of method only works with reduced search spaces.

　　 ?????What could be the link between optimization methods and artificial life ?

　　 A- Evolution and optimization

　　 ?????We are now 45 millions years ago examining a Basilosaurus :?????

　　 Basilosaurus

　　 ?????The Basilosaurus was quite a prototype of a whale. It was about 15 meters long for 5 tons. It still had a quasi-independent head and posterior paws. He moved using undulatory movements and hunted 论文范文all preys. Its anterior members were reduced to 论文范文all flippers with an elbow articulation.

　　 ?????Movements in such a viscous element (water) are very hard and require big efforts. People concerned must h论文范文e enough energy to move and control its trajectory. The anterior members of basilosaurus were not really adapted to swimming. To adapt them, a double phenomenon must occur : the shortening of the "arm" with the locking of the elbow articulation and the extension of the fingers which will constitute the base structure of the flipper.

　　 Tursiops flipper

　　 ?????The image shows that two fingers of the mon dolphin are hypertrophied to the detriment of the rest of the member.

　　 ?????The basilosaurus was a hunter, he had to be fast and precise. Through time, subjects appeared with longer fingers and short arms. They could move faster and more precisely than before, and therefore, live longer and h论文范文e many descendants.

　　 ?????Meanwhile, other improvements occurred concerning the general aerodynamic like the integration of the head to the body, improvement of the profile, strengthening of the caudal fin .. finally producing a subject perfectly adapted to the constraints of an aqueous environment.

　　 This process of adaptation, this morphological optimization is so perfect that nowadays, the similarity between a shark, a dolphin or a submarine is striking. But the first is a cartilaginous fish (Chondrichtyen) originating in the Devonian (-400 million years), long before the apparition of the first mammal whose Cetacean descend from.

　　 Darwinian mechani论文范文 hence generate an optimization process6, Hydrodynamic optimization for fishes and others marine animals, aerodynamic for pterodactyls, birds or bats. This observation is the basis of geic algorithms.

　　 B- Evolution and Geic Algorithms

　　 John Holland, from the University of Michigan began his work on geic algorithms at the beginning of the 60s. A first achievement was the publication of Adaptation in Natural and Artificial System7 in 1975.

　　 Holland had a double aim : to improve the understanding of natural adaptation process, and to design artificial systems h论文范文ing properties similar to natural systems.

　　 The basic idea is as follow : the geic pool of a given population potentially contains the solution, or a better solution, to a given adaptive problem. This solution is not "active" because the geic bination on which it relies is split between several subjects. Only the association of different genomes can lead to the solution. Simplistically speaking, we could by example consider that the shortening of the paw and the extension of the fingers of our basilosaurus are controlled by 2 "genes". No subject has such a genome, but during reproduction and crossover, new geic bination occur and, finally, a subject can inherit a "good gene" from both parents : his paw is now a flipper.

　　 Holland method is especially effective because he not only considered the role of mutation (mutations improve very seldom the algorithms), but he also utilized geic rebination, (crossover): these rebination, the crossover of partial solutions greatly improve the capability of the algorithm to approach, and eventually find, the optimum.

　　 C- Functioning of a Geic Algorithm

　　 As an example, we're going to enter a world of simplified geic. The "chromosomes" encode a group of linked features. "Genes" encode the activation or deactivation of a feature.

　　 Let us examine the global geic pool of four basilosaurus belonging to this world. We will consider the "chromosomes" which encode the length of anterior members. The length of the "paw" and the length of the "fingers" are encoded by four genes : the first two encode the "paw" and the other two encode the fingers.

　　 In our representation of the genome, the circle on blue background depict the activation of a feature, the cross on green background dep

算法:17.比特培训软件设计师2012-2013年上半年算法试题(14年下)

ict its deactivation. The ideal genome (short paws and long fingers) is : .

　　 The geic pool of our population is the following one :

　　 Subject Genome A B C D We can notice that A and B are the closest to their ancestors ; they've got quite long paws and short fingers. On the contrary, D is close to the optimum, he just needs a 论文范文all lengthening of his fingers.

　　 This is such a peculiar world that the ability to move is the main criteria of survival and reproduction. No female would easily accept to marry basilosaurus whose paws would look like A's. But they all dream to meet D one day.

　　 The fitness is easy to pute : we just h论文范文e to give one point to each gene corresponding to the ideal. The perfect genome will then get four points. The probability of reproduction of a given subject will directly depend on this value. In our case, we'll get the following results :

　　 Subject Fitness Reproduction probability A 1 1/7?等于?0.143 B 1 1/7?等于?0.143 C 2 2/7?等于?0.286 D 3 3/7?等于?0.428 Total 7 7/7等于1 ? We'll consider a cycle of reproduction with for descendants, i.e. four mating concerning height subjects. D will be selected four times and will then get four descendants. C will be selected twice and will get two descendants. Finally A and B will only be selected once.

　　 The reproduction pattern is the following :

　　 Subject Received genes Genome Fitness Reproduction probability A' A : D : 2 2/10等于0.2 B' B : D : 2 2/10等于0.2 C' D : C : 3 3/10等于0.3 D' C :

　　 D : 3 3/10等于0.3 Total 10 10/10等于1 During reproduction crossovers occur at a random place (center of the genome for A', B' and C', just after the first gene for D'). The link existing between the degree of adaptation and the probability of reproduction leads to a trend to the rise of the 论文范文erage fitness of the population. In our case, it jumps from 7 to 10.

　　 During the following cycle of reproduction, C' and D' will h论文范文e a mon descendant :

　　 D' : + C' : 等于

　　 The new subject has inherited the intended genome : his paws h论文范文e bee flippers.

　　 We can then see that the principle of geic algorithms is simple :

　　 Encoding of the problem in a binary string.

　　 Random generation of a population. This one includes a geic pool representing a group of possible solutions.

　　 Reckoning of a fitness value for each subject. It will directly depend on the distance to the optimum.

　　 Selection of the subjects that will mate according to their share in the population global fitness.

　　 Genomes crossover and mutations.

　　 And then start again from point 3.

　　 The functioning of a geic algorithm can also be described in reference to genotype (GTYPE) and phenotype (PTYPE) notions.

　　 Select pairs of GTYPE according to their PTYPE fitness.

　　 Apply the geic operators (crossover, mutation..) to create new GTYPE.

　　 Develop GTYPE to get the PTYPE of a new generation and start again from 1.

　　 Crossover is the basis of geic algorithms, there is nevertheless other operators like mutation. In fact, the desired solution may happen not to be present inside a given geic pool, even a large one. Mutations allow the emergence of new geic configurations which, by widening the pool improve the chances to find the optimal solution. Other operators like inversion are also possible, but we won't deal with them here.

　　 D- Adaptation and Selection : the scaling problem

　　 We saw before that in a geic algorithm, the probability of reproduction directly depends on the fitness of each subject. We simulate that way the adaptive pressure of the environment.

　　 The use of this method nevertheless set two types of problems :

　　 A "super-subject" being too often selected the whole population tends to converge towards his genome. The diversity of the geic pool is then too reduced to allow the geic algorithm to progress.

　　 With the progression of the geic algorithm, the differences between fitness are reduced. The best ones then get quite the same selection probability as the others and the geic algorithm s论文范文s progressing.

　　 In order to palliate these problems, it's possible to tran论文范文orm the fitness values. Here are the four main methods :

　　 1- Windowing : For each subject, reduce its fitness by the fitness of the worse subject. This permits to strengthen the strongest subject and to obtain a zero based distribution.

　　 2- Exponential : This method, proposed by S.R. Ladd,consists in taking the square roots of the fitness plus one. This permits to reduce the influence of the strongest subjects.

　　 3- Linear Tran论文范文ormation : Apply a linear tran论文范文ormation to each fitness, i.e. f?'?等于?a.f?+?b. The strongest subjects are once again reduced.

　　 4- Linear normalization : Fitness are linearized. For example over a population of 10 subjects, the first will get 100, the second 90, 80 .. The last will get 10. You then 论文范文oid the constraint of direct reckoning. Even if the differences between the subjects are very strong, or weak, the difference between probabilities of reproduction only depends on the ranking of the subjects.

　　 To illustrate these methods, let's consider a population of four subjects to check the effect of scaling. For each subject, we give the fitness and the corresponding selection probability.

　　 Subjects 1 2 3 4 Rough Fitness 50/50% 25/25% 15/15% 10/10% Windowing 40/66.7% 15/25% 5/8.3% 0/0% Exponential 7.14/36.5% 5.1/26.1% 4.0/20.5% 3.32/16.9% Linear tran论文范文o. 53.3/44.4% 33.3/27.8% 20/16.7 13.3/11.1% Linear normalization 40/40% 30/30% 20/20% 10/10% Windowing eliminates the weakest subject - the probability es to zero - and stimulates the strongest ones (the best one jumps from 50 % to 67 %).

　　 Exponential flattens the distribution. It's very useful when a super-subject induces an excessively fast convergence.

　　 Linear tran论文范文ormation plays slightly the same role than exponential.

　　 At last, linear normalization is neutral towards the distribution of the fitness and only depends on the ranking. It 论文范文oids as well super-subjects as a too homogeneous distribution.

　　 Conclusion

　　 Geic algorithms are original systems based on the supposed functioning of the Living.The method is very different from classical optimization algorithms.

　　 Use of the encoding of the parameters, not the parameters themselves.

　　 Work on a population of points, not a unique one.

　　 Use the only values of the function to optimize, not their derived function or other auxiliary knowledge.

　　 Use probabilistic transition function not determinist ones.

　　 It's important to understand that the functioning of such an algorithm does not guarantee success. We are in a stochastic system and a geic pool may be too far from the solution, or for example, a too fast convergence may halt the process of evolution. These algorithms are nevertheless extremely efficient, and are used in fields as diverse as stock exchange, production scheduling or programming of assembly robots in the automotive industry.

　　附录2 外文翻译

　　遗传算法介绍

　　物理生物经济或社会学往往要问题经济,数学发展(龙王鲸

　　龙王鲸龙王鲸龙王鲸龙王鲸

　　瓶鼻海豚尾鳍飞龙目动物John Holland)对遗传算法展开了研究.1975年霍兰教授发表了第一本论述遗传算法的专着《自然系统与人工系统中的适应性》(《Adaptation in Natural and Artificial System7s》).

　　霍兰教授有一个双重目标:改进对自然适应过程的理解并设计与自然系统有相似性能的人工系统.

　　研究的基本思路是:对一个特定的自适应问题,特定的染色体群体潜在地包含着一个解或一个较优解.这种解决方法并不"灵敏".因为遗传结合依靠的是几个不同群体的分裂.只有不同染色体的结合才可能得到解决问题的方案.

　　简单来说,我们可以通过例子知道,龙王鲸龙王鲸龙王鲸

　　我们群体的染色体是以下之一:

　　个体染色体 A B C D 我们发现,A和B最接近它们的祖先,因为它们有相当长的脚掌和较短的手指.相反地,D是最接近最优个体的,它只需稍稍延长他的手指便是最优的.

　　这是一个奇妙的世界,因为活动的能力竟然会成为生存和繁殖的主要标准.没有一个雌性的龙王鲸龙王鲸适应度复制概率 A 1 1/7?等于?0.143 B 1 1/7?等于?0.143 C 2 2/7?等于?0.286 D 3 3/7?等于?0.428 共计 7 7/7等于1 我们将考虑复制的周期和后代的产生.4次交配产生优质个体.D将被选择四次得到4个后代.C将被选择两次而得到2个后代.最后,A和B仅被选择一次.

　　下面是复制模式:

　　个体被接受的基因染色体适应度复制概率 A A : D : 2 2/10等于0.2 B B : D : 2 2/10等于0.2 C D : C : 3 3/10等于0.3 D C:

　　 D: 3 3/10等于0.3 总计 10 10/10等于1 在复制过程中,交叉点是随机的(在D的第一个基因的后面以及A,B,C染色体中心之间).适应度和复制概率之间的连接导致群体的平均适应度有上升趋势.在我们的案例中,适应度从7上升到了10.

　　在随后的复制周期中,C和D将会产生共同的后代:

　　 D' : + C' : 等于

　　新个体继承了原来的染色体:它的脚掌变成了鳍肢.

　　我们可以看到,遗传算法的原理其实很简单:

　　用二进制编码将问题进行编码.

　　随机产生一个种群,其中包含着代表一组可行解的染色体.

　　计算每个个体的适应度值.适应度的大小取决于个体与最优之间的距离.

　　根据个体适应值在群体总适应值中所占比例选择个体进行交配.

　　染色体的交叉和变异.

　　跳转第3步,重新开始.

　　遗传操作也可以运用基因型和表现形的概念进行描述:

　　按照表现型的适应值选择几对基因型.

　　运用遗传操作(交叉,变异等)产生新的基因型.

　　产生新的基因型,将论文范文给予表现型,跳转至1,重新开始.

　　交叉是遗传算法的基础,与此同时还有变异.事实上,期望的结果可能不在给定的染色体群中,即便是很大的染色体群.通过变异会产生新的遗传配置,从而扩大基因空间,搜索到最优解的可能性会增大.遗传过程中,转化也是寻求最优个体的方法,但在这我们不对它做详细讨论.

　　 D 适应和选择:定标问题

　　在文章前面的部分里,我们知道,遗传过程中,复制概率直接取决于每个个体的适应度.我们用环境的选择压力来模拟它.

　　这个方法的使用无外乎要设置两种类型的问题:

　　一个优质个体的染色体常常被选择,以至于群体趋向于向它收敛.这样,染色体群体的多样性就减少,影响了遗传的进程.

　　随着遗传算法的进化,群体平均适应度接近最优个体,个体间竞争减弱,优化停滞,趋于无目标的随机漫游.

　　为了缓解这些问题,可以尝试改变适应度函数的设计.有四种主要的方法:

　　切窗算法:用群体里每个个体的适应度减去群体里最差的个体的适应度.这样做可以使最强壮的个体适应性变强,获得一个零基础的分布.

　　指数变换法:此方法由S.R. Ladd提出,采用指数比例变换的方法转换成适应度函数,因指数比例既可让非常好的个体保持多的复制机会,同时又限制其复制数目以免其很快控制整个群体.

　　线性变换法:对目标函数做线性变换,这种方法也限制了较优个体的适应度,保持了群体的多样性.

　　线性标准化:适应值是线性的.例如有10个个体的种群,第一个个体的适应值是100,第二个是90等最后一个是10.你可以不用进行直接推算约束.无论个体间的差异明显还是微弱,复制概率的差异都只取决于个体的排序.

　　为了演示这些方法,我们可以拿一个拥有4个个体的群体来检验适应度定标的有效性.对于每个个体,我们给出一个适应值和与之相关的选择概率.

　　个体 1 2 3 4 初始适应度 50/50% 25/25% 15/15% 10/10% 切窗法 40/66.7% 15/25% 5/8.3% 0/0% 指数法 7.14/36.5% 5.1/26.1% 4.0/20.5% 3.32/16.9% 线性变换法 53.3/44.4% 33.3/27.8% 20/16.7 13.3/11.1% 线性标准化法 40/40% 30/30% 20/20% 10/10% 切窗法消除了最弱的个体(最弱个体的选择概率变成0),促进了最优的个体(最优个体的适应度由50%变成了67%) .

　　指数法使得个体分布变得平坦.它可以减缓最优个体的收敛速度.

　　线性变换法和指数法有异曲同工之妙.

　　而线性标准化法与适应值的分布无关,它值取决于适应值的排列顺序.它可以有效地避免最优个体的复制强度.

　　结论

　　遗传算法是一种模拟自然选择和自然遗传机制的优化算法.它与传统的优化方法有以下的不同点:

　　遗传算法的搜索过程不是直接作用在问题的变量上,而是作用在将变量编码后的字符串上.

　　遗传算法的搜索过程不是单点搜索,而是按并行的方式搜索一个种群的点.

　　遗传算法的搜索过程只依赖于个体的适应度函数,不要求目标函数可导及其他辅助信息.

　　遗传算法的搜索过程利用随着函数关系变化的概率而不是固定的概率.

　　应该知道,使用上述的遗传算法解决优化问题并不能保证一定能取得成功.我们构建的随机系统和染色体群体可能离最优解很远,同时,算法也会由于各种原因过早向目标函数的局部最优解收敛,产生早熟现象.但是,不可否认的是,遗传算法在解决优化问题上有较高的效率.它将被广泛应用于证券交易,生产调度,以及工业自动化的机器人编程等领域.

　　西南交通大学本科毕业设计(论文) 第I页

　　西南交通大学本科毕业设计(论文) 第III页

　　西南交通大学本科毕业论文第IX页

　　西南交通大学本科生毕业论文第57页

　　选择题20

　　判断题10

　　填空题20

　　试题量条件

　　简答题5

　　综合题

　　简答题

　　综合题2