一种基于遗传算法智能组卷方法研究

1、一种基于遗传算法智能组卷方法研究国内外研究现状与主要问题国内外研究现状与主要问题研究研究定位与目标定位与目标研究意义研究意义主要研究内容、主要研究内容、创新点创新点本文的组卷算法本文的组卷算法软件展示软件展示提纲提纲国内外研究成果：国内外研究成果： 国外的研究生入学考试(GRE) 、TOFEL等 清华大学等联合编制“高等学校工科高等数学课程试题库系统” 山东省高教自考办公室等联合编制“高等数学题库系统 全国计算机等级考试系统等等 国内外研究现状国内外研究现状组卷算法发展现状：组卷算法发展现状：将试题库看做题集，组卷时由教师逐题筛选抽取 -计算机作为工具，但实质上仍然是人工组卷 将试题库看做试卷

2、集，将已经出好的试卷存储起来，考试时 随机抽取一份试卷 -试卷数量有限，组卷缺乏灵活性 应用某种组卷算法自动抽题组卷 -虽然灵活性大，但组卷效果不太理想国内外研究现状国内外研究现状智能组卷算法发展现状：智能组卷算法发展现状：误差补偿法 -成功率低随机抽取算法 -成功率低深度与广度搜索算 （回溯算法）-如果题库规模太大，效率很低基于遗传算法的组卷算法 -比较优秀，但有很多不足国内外研究现状国内外研究现状一般的组卷算法只能在非常简单的约束条件下完成试题的选 择抽取，基本不能满足目前的考试需要。传统的遗传算法成功率低和效率差、容易产生局部最优解和 早熟等问题。各种改进的遗传算法在选择，编码，交叉，变

3、异等环节做出 了局部改善，局部改善，而且在一定程度上缓解了早熟和局部最优解等 问题 ，但是仍然需要改进。主要问题主要问题 在前人工作的基础上，对各种遗传算法的改进方法进行分析比较，寻找一种基于遗传算法的智能组卷方法，提高算法的效率和成功率，进一步缓解了早熟和局部最优解等问题。并应用到东师理想网络题库管理系统中。研究定位与目标研究定位与目标研究意义研究意义 理论意义理论意义 提供一种新的组卷方法 对于软件设计方法的研究也有一定的促进作用 现实意义现实意义 使老师从组卷工作中解脱出来 提高了组卷的质量和效率 深入研究遗传算法理论和考试理论比较各种算法之间的优点及其不足 探索遗传算法的各种改进措施对

4、算法的影响 总结早熟成因和应对措施从多方面对遗传算法进行改进 ，如：初始种群的选取遗传算法的编码和适应度函数的设计遗传算子的自适应设计小生境技术的应用研究内容研究内容应用创新： 应用到 东师理想网络题库管理系统东师理想网络题库管理系统算法创新： 对遗传算法的一种多方面改进多方面改进。 即比较几种成熟的而且效率较高、成功率较大的改进方 法，分析其改进原理及对算法的影响，并引入到本文。在损 失尽可能小的性能的前提下提高遗传算法的成功率。创新点创新点 遗传算法是求解满足多个约束条件的最优解的方法。也就是搜索解空间内的一个符合要求的模式。 选择算子：复制优秀模式 交叉算子：模式重组（搜索解空间） 变异

5、算子：增加新模式（保持模式的多样性） 模式在进化中的变化模式在进化中的变化 因此早熟现象发生的根本原因是种群多样性的过早丧失。因此早熟现象发生的根本原因是种群多样性的过早丧失。 用模式理论分析早熟原因用模式理论分析早熟原因算法介绍算法介绍-数学模型数学模型 假设每个试题为一个8维向量（题分-a1，题型-a2，难度等级-a3，章节-a4，时间-a5，知识点-a6，区分度-a7，认知程度-a8），那么一套试卷就是一个n*8的目标矩阵。n是一套试卷的试题数。例如：aij 就是第i题的第j个属性值（1= i =n, 1= j =8）。矩阵如下：适应度函数为：适应度函数为：F = 1 - f ，(0 F

6、 1) 目标函数为目标函数为:算法介绍算法介绍-适应度函数设计适应度函数设计gi(0=gi0,0= w1+w2+wn =1)是赋予第 i约束条件的权重。 例如：P是约束条件， 试卷要达到的总分，g1是约束分数与试卷实际分数的相差程度。 本文采用的策略是：始种群的创建可以通过例如总分、题型和答题时间的要求对题库进行初步过滤,达到加快算法收敛并减少迭代次数的目的。 群体规模既决定了多样性的多少，同时也影响算法的效率。那么规模控制在 n,2n的范围内本文认为比较合适。 (n为个体长度或试卷所含试题数量)。 最大进化代数设置为：500算法介绍算法介绍-初始种群初始种群十进制分段实数编码方法十进制分段实

7、数编码方法（与传统的二进制编码方式相比）：省略了编码和解码的过程，使编码更有实际意义，缩短求解时间减少了个体编码的长度便于分段进行交叉和变异等操作分段编码也有利于种群的初始化 算法介绍算法介绍-编码方式编码方式选择算子选择算子 选择既要符合物竞天择、适者生存的客观规律，还要有足够的随机性，那么本文选择轮盘赌选择机制。避免了种群中适应度比较大的个体流失或者被破坏掉 。 本文还有应用精英选择策略，就是要对适应度比较大的个体保护起来，使其能够保留到下一代 。算法介绍算法介绍-遗传算子遗传算子交叉算子交叉算子 交叉概率交叉概率:算法介绍算法介绍-遗传算子遗传算子其中， fmax为最大适应值，f为个体适

8、应值，favg为平均适应值。，当fmax f 越趋近于 0 ，那么Pc越趋近于 k1 ；反正Pc 将很小。 交叉方式交叉方式:变异算子变异算子 变异概率：变异概率： 算法介绍算法介绍-遗传算子遗传算子其中， fmax为最大适应值，f为个体适应值，favg为平均适应值。 ， k4 =0.005 ，当 fmax - f 越趋近于 0 ，那么 Pm 就越趋近于 k3 ；反之 Pm 很小。 变异方式变异方式：海明距离：海明距离： 在信息编码中，两个合法代码对应位上编码不同的位数称为码距，称海明距离 。例如：10110101 异或 10101010 = 00011111那么 hamming distan

9、ce = 5 应用小生境技术的思想是：应用小生境技术的思想是：惩罚函数为：惩罚函数为：算法介绍算法介绍-应用小生境技术应用小生境技术海 明 距 离个 体 编 码 长 度 最大染色体适应度满足要求（如大于），算法终止，返回最大染色体适应度的个体。 进化到规定的最大代数（500），算法终止，返回最大染色体适应度的个体。若此时最大个体适应度值不满足要求（如小于）则认为本次问题求解失败。 连续5代的平均适应度的比值在，1.005时，算法终止，返回最大染色体适应度的个体。若此时最大个体适应度值不满足要求（如）则认为本次问题求解失败。算法介绍算法介绍-终止条件终止条件 算法介绍算法介绍- -算法算法流程图流程图 算法介绍算法介绍- -算法类图算法类图 硬件环境硬件环境: 服务器为PC机， CPU为因特尔酷睿双核，主频， 内存2G，硬盘250G操作系统操作系统: Microsoft Windows XP数据库数据库: SqlServer2000技术平台技术平台：java EE技术（jsp，servlet）， eclipse 开发环境， JDK1.5 软件演示软件演示- -开发和运行环境开发和运行环境软件演示软件演示- -启动数据库启动数据库软件演示软件演示- -启动启动tomcattomcat软件演示软件演示- -组卷条件页面组卷条件页面软件演示软件演