《一种基于遗传算法的智能组卷方法的研究.ppt》由会员分享，可在线阅读，更多相关《一种基于遗传算法的智能组卷方法的研究.ppt（29页珍藏版）》请在三一办公上搜索。
1、一种基于遗传算法的智能组卷方法的研究,国内外研究现状与主要问题研究定位与目标研究意义主要研究内容、创新点本文的组卷算法软件展示,提纲,国内外研究成果：国外的研究生入学考试(GRE)、TOFEL等 清华大学等联合编制“高等学校工科高等数学课程试题库系统”山东省高教自考办公室等联合编制“高等数学题库系统 全国计算机等级考试系统等等,国内外研究现状,组卷算法发展现状：将试题库看做题集，组卷时由教师逐题筛选抽取-计算机作为工具，但实质上仍然是人工组卷 将试题库看做试卷集，将已经出好的试卷存储起来，考试时 随机抽取一份试卷-试卷数量有限，组卷缺乏灵活性 应用某种组卷算法自动抽题组卷-虽然灵活性大，但组卷
2、效果不太理想,国内外研究现状,智能组卷算法发展现状：误差补偿法-成功率低随机抽取算法-成功率低深度与广度搜索算（回溯算法）-如果题库规模太大，效率很低基于遗传算法的组卷算法-比较优秀，但有很多不足,国内外研究现状,一般的组卷算法只能在非常简单的约束条件下完成试题的选 择抽取，基本不能满足目前的考试需要。传统的遗传算法成功率低和效率差、容易产生局部最优解和 早熟等问题。各种改进的遗传算法在选择，编码，交叉，变异等环节做出 了局部改善，而且在一定程度上缓解了早熟和局部最优解等 问题，但是仍然需要改进。,主要问题,在前人工作的基础上，对各种遗传算法的改进方法进行分析比较，寻找一种基于遗传算法的智能组
3、卷方法，提高算法的效率和成功率，进一步缓解了早熟和局部最优解等问题。并应用到东师理想网络题库管理系统中。,研究定位与目标,研究意义,理论意义 提供一种新的组卷方法 对于软件设计方法的研究也有一定的促进作用 现实意义 使老师从组卷工作中解脱出来 提高了组卷的质量和效率,深入研究遗传算法理论和考试理论比较各种算法之间的优点及其不足 探索遗传算法的各种改进措施对算法的影响 总结早熟成因和应对措施从多方面对遗传算法进行改进，如：初始种群的选取遗传算法的编码和适应度函数的设计遗传算子的自适应设计小生境技术的应用,研究内容,应用创新：应用到 东师理想网络题库管理系统算法创新：对遗传算法的一种多方面改进。即
4、比较几种成熟的而且效率较高、成功率较大的改进方 法，分析其改进原理及对算法的影响，并引入到本文。在损 失尽可能小的性能的前提下提高遗传算法的成功率。,创新点,遗传算法是求解满足多个约束条件的最优解的方法。也就是搜索解空间内的一个符合要求的模式。选择算子：复制优秀模式 交叉算子：模式重组（搜索解空间）变异算子：增加新模式（保持模式的多样性）模式在进化中的变化 因此早熟现象发生的根本原因是种群多样性的过早丧失。,用模式理论分析早熟原因,算法介绍-数学模型,假设每个试题为一个8维向量（题分-a1，题型-a2，难度等级-a3，章节-a4，时间-a5，知识点-a6，区分度-a7，认知程度-a8），那么一
5、套试卷就是一个n*8的目标矩阵。n是一套试卷的试题数。例如：aij 就是第i题的第j个属性值（1=i=n,1=j=8）。矩阵如下：,适应度函数为：F=1-f，(0 F 1)目标函数为:,算法介绍-适应度函数设计,gi(00,0=w1+w2+wn=1)是赋予第 i约束条件的权重。例如：,P是约束条件，试卷要达到的总分，g1是约束分数与试卷实际分数的相差程度。,本文采用的策略是：始种群的创建可以通过例如总分、题型和答题时间的要求对题库进行初步过滤,达到加快算法收敛并减少迭代次数的目的。群体规模既决定了多样性的多少，同时也影响算法的效率。那么规模控制在 n,2n的范围内本文认为比较合适。(n为个体长
6、度或试卷所含试题数量)。最大进化代数设置为：500,算法介绍-初始种群,十进制分段实数编码方法（与传统的二进制编码方式相比）：省略了编码和解码的过程，使编码更有实际意义，缩短求解时间减少了个体编码的长度便于分段进行交叉和变异等操作分段编码也有利于种群的初始化,算法介绍-编码方式,选择算子 选择既要符合物竞天择、适者生存的客观规律，还要有足够的随机性，那么本文选择轮盘赌选择机制。避免了种群中适应度比较大的个体流失或者被破坏掉。本文还有应用精英选择策略，就是要对适应度比较大的个体保护起来，使其能够保留到下一代。,算法介绍-遗传算子,交叉算子 交叉概率:,算法介绍-遗传算子,其中，fmax为最大适应
7、值，f为个体适应值，favg为平均适应值。K1=0.8,K2=0.5，当fmax f 越趋近于 0，那么Pc越趋近于 k1；反正Pc 将很小。交叉方式:,变异算子 变异概率：,算法介绍-遗传算子,其中，fmax为最大适应值，f为个体适应值，favg为平均适应值。k3=0.1，k4=0.005，当 fmax-f 越趋近于 0，那么 Pm 就越趋近于 k3；反之 Pm 很小。变异方式：,海明距离：在信息编码中，两个合法代码对应位上编码不同的位数称为码距，称海明距离。例如：10110101 异或 10101010=00011111那么 hamming distance=5 应用小生境技术的思想是：惩
8、罚函数为：,算法介绍-应用小生境技术,最大染色体适应度满足要求（如大于0.95），算法终止，返回最大染色体适应度的个体。进化到规定的最大代数（500），算法终止，返回最大染色体适应度的个体。若此时最大个体适应度值不满足要求（如小于0.85）则认为本次问题求解失败。连续5代的平均适应度的比值在1.000，1.005时，算法终止，返回最大染色体适应度的个体。若此时最大个体适应度值不满足要求（如0.85）则认为本次问题求解失败。,算法介绍-终止条件,算法介绍-算法流程图,算法介绍-算法类图,硬件环境:服务器为PC机，CPU为因特尔酷睿双核，主频2.0，内存2G，硬盘250G操作系统:Microsof
9、t Windows XP数据库:SqlServer2000技术平台：java EE技术（jsp，servlet），eclipse 开发环境，JDK1.5 tomcat5.0,软件演示-开发和运行环境,软件演示-启动数据库,软件演示-启动tomcat,软件演示-组卷条件页面,软件演示-组卷结果页面,总结,经反复验证，新算法生成的试卷质量基本符合实际考试需求，虽然在运行效率上没有明显提高，但是组卷成功率高，算法稳定性较好，而且收敛速度更快。因此，本文的提出的算法确实比其他的算法要好一些。但是，目前代码实现的比较简单，考虑的还不够全面，还有很多其他问题，还需要改进和优化。,感谢导师对我的指导！感谢学院对我的培养！感谢各位老师批评指正！,致谢,
