科技信息 高校理科研究 基于题型和知识点的遗传组卷算法酌应用 河南省管理干部学院 王璞 刘明利 ［摘要］本文介绍了自动组卷与手动组卷的区别，并详细介绍了３种自动组卷算法，提出了基于题型和知识点的遗传组卷算法，实 验表明，所设计的组卷方法性能好、效率高，是一种实用、有效的组卷方法。 ［关键词］遗传算法 自动组卷 １．引言 在学校，考试是检测学生学习成绩好坏的必要手段。传统的考试增 加了老师的工作量，而且不利于对考试试卷进行有效的管理与分析。因 ｓｏｍｅ）带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的 集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的 外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组 此，我们需要建立一个试题库，对试题及试卷进行管理，通过计算机对 建成的试题库根据一定的组卷算法抽取试题，组成符合每个老师所要 求的试卷，组卷算法决定了自动组卷系统的效率和组卷质量。 ２．自动组卷算法 组卷功能实现的好坏决定了一个考试系统是否具有可用性。目前 考试系统的组卷方式包括手动组卷和自动组卷。手动组卷是由命题人 在题库中查找到符合条件的所有题型，然后选取其中的一部分作为考 试试题；由于命题人根据自己的知识、风格、经验来收集、选取试题，编 制试题，所以试题的效度、信度较高，但也存在着一些缺点：主要表现是 试题制作质量由于人为因素不能稳定；选题范围狭窄；耗费命题量 的时间、精力；不利于实现教考分离；出卷成果难以与其他出题者共享。 所谓自动组卷就是根据用户输入的试卷规则要求，计算机自动从试题库 中选择试题组成一份符合要求的试卷。组卷要求包括了覆盖面大，重点 突出，各章节分数分布均衡，各题型分数分布合适，难度符合目的，总 分、总时符合要求，以及考察知识点不相重复等多项层次不同的要求『ｌ＿。 这些较为抽象的组卷要求必须明确化： ①教师根据教学内容的要求设置试卷指标，用来量化衡量一张试 卷； ②通过给各项指标设置权重，或将其划分到不同重要性等级的方 法，反映出特定考试中教师对各项指标的不同重视程度； ③组卷时让教师对这些预定指标提出希望值，然后系统据此选题 组卷。 自动组卷是题库管理模块中最重要的环节之一。目前具有自动组 卷功能的考试系统一般采用随机选取法、回溯试探法和遗传算法。 随机选取法该算法根据状态空间中的状态指标，由计算机产生一 随机数，不断重复，直到组卷完毕或已无法从该试题库中抽满足控制指 标的试题为止。该方法实现起来比较简单，对于单道题的抽取运行速度 较快。若各种题型分开抽取，不考虑整张试卷的试题难易比重的话，就 是说要衡量其难易等各项指标使考生的成绩分布大致呈正态分布。其 组卷成功率低，即使组卷成功，花费时间也令人以忍受，尤其是当题库 中各状态类型平均出题量比较低时，组卷往往失败Ｉ２］。 回溯试探法。在问题求解过程中，有时会发现应用一条不合适的规 则会阻扰或拖延到达目标的进程。在这种情况下，需要有这样的控制策 略：先试一试某一规则，如果以后发现这条规则不合适，则允许退回去， 另选一条规则来试 。用回溯试探法来组卷，我们可以将随机选取法产 生的每一状态记录下来，当搜索失败，即遇到“不可解节点”走人“死胡 同”时，就可回溯到路径中最近的父节点（即上一记录的状态），然后再依 据一定的规则从另一种新的状态类型进行试探搜索，这样通过不断地 回溯试探直到试卷生成或退回起点为止。这样就避免了随机选取法中 一条路走到黑的做法。该算法对于状态类型和出题量都较少的试题库 系统而言，组卷成功率较高。但是这种算法要求内存的容量要大，程序 结构也相对比较复杂，且选取的试题缺乏随机性，组卷时间也长。因此 它不是一种很好的自动组卷算法。 遗传算法（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍｓ）是模拟达尔文的遗传选择和自然淘 汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最 优解的方法。它由美国Ｍｉｃｈｉｇａｎ大学Ｊ．Ｈｏｌｌａｎｄ教授于１９７５年首先提 出来的，并出版了颇有影响的专著（（Ａｄａｐｔａｔｉ０ｎ ｉｎ Ｎａｔｕｒａｌ ａｎｄ Ａｒｔｉｉｆｃｉｌａ Ｓｙｓｔｅｍｓ）），ＧＡ这个名称才逐渐为人所知，Ｊ．Ｈｉｌｌａｎｄ教授所提出的ＧＡ通 常为简单遗传算法（ＳＧＡ）。遗传算法是从代表问题可能潜在的解集的 一个种群（ｐｏｐｕｌａｔｉｏｎ）开始的，而一个种群则由经过基因（ｇｅｎｅ）编码的 一定数目的个体（ｉｎｄｉｖｉｄｕａ１）组成。每个个体实际上是染色体ｃｈｒｏｍｏ— 合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工 作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编 码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（ｇｅｎｅｒａ— ｔｉｏｎ）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适 应度（ｆｉｔｎｅｓｓ）大小挑选（ｓｅｌｅｃｔｉｏｎ）个体，并借助于自然遗传学的遗传算 子（ｇｅｎｅｔｉｃ ｏｐｅｒａｔｏｒｓ）进行组合交叉（ｃｒｏｓｓｏｖｅｒ）和变异（ｍｕｔａｔｉｏｎ），产生出 代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代 种群比前代更加适应于环境，末代种群中的最优个体经过解码（ｄｅｃｏｄ— ｉｎｇ），可以作为问题近似最优解。 ３．无纸化考试系统组卷算法 人工组卷的工作过程是出卷人要确定试卷总分数和考试时间；其 次要确定试卷中的题型种类，以及每种题型的大概分值和考核的知识 点，接着出卷人将分题型按照知识点去选题，将选出来的各种题型放在 一起就形成了试卷。 从以上可以看出，整个人工组卷过程的主线是题型和知识点，结合 人工组卷过程，本考试系统采取基于题型和知识点的遗传组卷算法。 （１）染色体编码方案 遗传算法的关键之一是进行编码处理．本算法采取０／１编码机制，某 基因座上的０表示对应的题目不选取，１表示选取，因此一条染色体就代 表一种可能的组卷方案，然后用矩阵表示该染色体的基因链编码。 （２）定义适应度函数 各类题型分值尽要能接近目标值，应满足ＸＩ＝（ Ｉ ｔ 一 Ｉ厂ｒＪ且ｘ，≤Ｂ， 其中ｔ 表示试卷中包含的第ｉ类题型的实际分值，Ｔ．表示试卷的第ｉ类 题型的目标分值，Ｍ为试卷中试题类型的总数，Ｂ表示试卷的各类型分 值允许的最大误差。 各知识点分值尽可能接近目标值，应满足Ｘ２＝（ ｌ Ａ—Ａ ｌ／Ａ￣）Ｒ ｘ２＜￣－ｑ， 其中Ａ表示试卷中包含的第ｉ个知识点的实际分值＇Ａｌ表示试卷第ｉ个 知识点的目标分值，ｗ为试卷知识点的总数，１１表示试卷的各知识点分 值允许的最大误差 。 在本问题中，对于种群数目为Ｎ的染色体群，第ｉ个染色体目标函 数Ｆ，为： Ｆ ＝ ｌｘｄｌ＋ ２ｘｄ２ ｉ＝ｌ，２，３…，Ｎ 为了便于遗传算法求解问题，通过以下转换把目标函数Ｆ．转化为 适应度函数￡，适应度函数￡的值越大，则表示该个体配性越强。 ￡： ‘ 。时 …一１０。当Ｆ ｉ≥１００时 ｉ＝１，２，３－－－，Ｎ （３）遗传算子设计 ①选择算子 在遗传算法中，通常用轮盘赌选择方法复制对象，它是目前遗传算 法中最基础也是最常用的方法【２５】。基本思想如下： １）依次累计群体内个体的适应度，得到相应的累计值ｓ．，最后一个 累计值为Ｓｎ； ２）在［０，ＳｎｉＰ－间内产生均匀分布的随机数Ｒ； ３）依次用ｓ与Ｒ进行比较，第一个出现ｓ，大于或等于Ｒ的个体ｉ 被选为复制对象； ４）重复２，３直至满足所需要的个体数目。 ②交叉算子 先随机从群体中选取两个个体，对这两个个体进行交叉运算。为了 科技信息 高校理科研究 代的最好个体与上一代的最好个体适应度，如下降，则以上一代最好个 体替换新一代的最差个体，此策略可以保证迄今为止的最优个体不会被 交叉、变异等运算所破坏，它是遗传收敛性的一个重要保证。 ⑤算法实现过程 确定参数：最大代数ＭａｘＧｅｎ，群体规模ＰｏｐＳｉｚｅ，交叉概率Ｐｃ，变异 概率Ｐｍ； 保证试卷中各种题型试题的题量不变，采用段问交叉的方法：首先随机 选择一个交叉点，检查这个交叉点处的试题属于哪一种题型，并查找该 题型试题的首位置，将该首位置作为实际交叉点，进行单点交叉操作。 通过在群体中随机挑选两个染色体，并随机在染色体某一点 进行点交换从而得到下一代的新个体，完成交叉的工作。在分段遗传算 法的组卷过程中，考虑到组卷最终必须满足题型题量的要求，在许多实 际应用中，按照题型的变化采用分段进行操作，每种题型对应染色体中 的一个分段进行交叉时采用分段单点交叉，按题型分段来进行交 叉，整个染色体就表现为多点交叉。交叉的实现过程：将群体中的染色 体任意进行两两配对，对每对染色体产生一个【０，１】的随机数ｒ，若ｒ≤ Ｐｃ，则分段随机产生一个交叉点，然后分段进行右半段互换以得到下一 代交叉后生成的子代的新段有可能是非法的，因为有可能存在重复的 题号，但这种重复的题号只可能出一次。出现这种情况要将第二次出现 的题号换成该段中没有出现过的题号，这样重新得到新子代。计算新子 代的适应度函数，然后和对应的父代适应度函数比较，以决定保不保留 新子代，即从这四个染色体中选择两个适应度函数大的染色体保存下 来，从而保持群体规模不变。 ③变异算子 首先是随机选取一个个体进行变异，再随机在该个体中选取一个 变异点，判断该点对应的试题属于哪种题型，并根据该点对应的试题是 否被选中进行相应的操作。若该点为ｌ，则表示该题被选中，然后从该 点对应的试题所在题型中再随机选取一个为０的点并将该点置为ｌ，最 后将变异点置为０。若该点为０，则表示该题未被选中；然后从该点所对 应的试题所在题型中再随机选取一个为１的点，并将该点置为０，最后 将变异点置为ｌ。通过这样的操作，可以保证每种题型中被选中的试题 数量保持不变。 在遗传算法中，变异概率一般较小，本算法不分段进行变异，而是 只对某段上的某个基因进行变异。对某个染色体，随机生成一个［０，１］范 围内的实数ｒ，若ｒ≤Ｐｍ，则对该染色体进行变异，否则不进行变异。变异 的操作如下： 在 ，ｎ】范围内随机生成一个段号ｉ（ｎ为段的数目），设该段的段长 接收用户的组卷要求； 产生初始群体； 当前代数ｇｅｎ＝１； 计算群体中各个体的适应值； ｗｈｉｌｅ（ｇｅｎ＜ＭａｘＧｅｎ＆＆最好个体的目标函数值未达到要求） ｆ根据个体适应值及选择策略从当前群体中选择生成下一代的父 体： 执行交换操作和变异操作生成新一代群体； 计算新一代群体中各个体的适应值； 比较新一代的最好个体与上一代的最好个体的适应值，如下降，则 以上一代最好个体替换新一代的最差个体； 输出当前代数，群体的平均目标函数，最好个体的目标函数值； ｇｅｎ＋＋； ｝ 输出组卷方案。 ４．结束语 本系统的组卷算法能很好地按照组卷要求进行组卷，试卷的各项 性能指标能较好地满足试卷要求，说明基于遗传算法的自动组卷是有 效的。且在同样的组卷要求下，可以从试题库中抽出几份内容差异很 大，但各项性能指标保持一致性的试卷。结果表明基于遗传算法的自动 组卷算法具有一定的稳定性。 参考文献 为Ｌ，则在 Ｌ）范围内随机生成一个变异位置Ｐ，在考试要求范围内与 原基因题型相同的题号中选择一个变异基因。用选中的变异基因替换 原基因，得到新的个体。变异操作是保持群体多样性的有效手段，所以 直接用新个体替换发生变异的个体，以保持群体规模不变和群体的多 样性 。 ④最优保存策略 在完成以上选择、交叉、变异步骤后，产生一个试卷模型，比较新一 （上接第１３２页） …≤ｘ ≤…－＜ｘ￣ｉ．＝ｂ．＋．，最后分别将ｘ 变换得到参 ．［１］李竹宁－试卷质量的统计分析与评价．教学与管理，２００６，（３６）． ［２］桂阳，王修信，农京辉．大学物理试题库智能组卷随机抽取法的 改进［ｆ］．广西物理，２００８，２９（２）：２３～２５． ［３］管宝云，尹琦．基于混合智能算法的自动组卷问题研究［Ｊ］天津 工业大学学报，２００６，２５（４）：９７—１００． ［４］袁峰．遗传算法在自动组卷系统中的应用［＿Ｉ］．山东师范大学学 报，２００６．０３． ［５］赵跃新，许军林．基于遗传算法自动组卷的实现［Ｊ］计算机与信 息技术，２００９年Ｏ３期． ｌ ３ ｊＲ．Ｃ Ｇｏｎｚａｌｅｚ ａｎｄ Ｒ．Ｅ．Ｗｏｏｄｓ，Ｄｉ垂ｔａｌ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ Ｐｒｅｎ— ｔｉｃｅ—Ｈａｌｌ，Ｎｅｗ Ｊｅｒｓｅｙ，２００２． 考空间中的ｃ ，实现整个特征值分布到参考分布的变换。 自适应直方图均衡化（ＡＨＥＱ）主要改变了传统方法构造累积直方 图时区间大小完全相等的缺点。采用这种自适应的方法可以使分割的 区间大小随着特征值样本聚集程度的变化而变化，并且对同一区间的 特征值按照其大小线性地映射到参考空间内对应的区间上，因此在得 到相同性能的条件下，使变换过程的计算量降低，得到的变换特征值的 分布更符合实际，即在相同区间个数条件下，ＡＨＥＱ比ＨＥＱ对因噪声 １ ４ ＪＪ．ｃ Ｓｅｇｕｒａ，Ｃ．Ｂｅｎｉｔｅｚ，ｄ ｄｅ ｌａ Ｔｏｒｔｅ，ＡＪ Ｒｕｂｉｏ，ａｎｄ Ｊ Ｒａｎｌｉｒｅｚ， “Ｃｅｐｓｔｒａｌ Ｄｏｍａｉｎ Ｓｅｇｍｅｎｔ￣Ｎｏｎｌｉｎｅａｒ Ｆｅａｔｕｒｅ Ｔｒａｎｓｆｏｒｍａｔｉｏｎｓ ｆｏｒ Ｒｏｂｕｓｔ Ｓｐｅｅｃｈ Ｒｅｃｏｇｎｉｔｉｏｎ，”ＩＥＥＥ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｌｅｔｔｅｒｓｖｏ１．１１，Ｍａｙ ２００４，ＰＰ． ，５１７－５２０． １ ５ Ｊ丘．ｄｅ ｌａ Ｔｏｒｒｅ，Ａ Ｍ．Ｐｅｉｎａｄｏ，Ｊ．Ｃ．ＳｅｇｕｒａＪ．Ｌ．Ｐ ６ ｒｅｚ—Ｃ ６ ｒｄｏｂａ，Ｍ Ｃ Ｂｅｎｉｔｅｚ，ａｎｄ ＡＪ Ｒｕｂｉｏ，“Ｈｉｓｔｏｇｒａｍ Ｅｑｕａｌｉｚａｔｉｏｎ ｏｆ Ｓｐｅｅｃｈ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｆｏｒ Ｒｏｂｕｓｔ Ｓｐｅｅｃｈ Ｒｅｃｏｇｎｉｉｔｏｎ”，ＩＥＥＥ Ｔｒａｍ．Ｓｐｅｅｃｈ ａｎｄ Ａｕｄｉｏ Ｐｒｏｃｅｓｓｉｎｇ， ｖｏ１．１３，Ｍ叫２００５，ｐｐ．３５５—３６６． 引起的失真的补偿性能更加有效。 四、小结 １ ６ ｊｓ．Ｍｏｌａｕ，Ｆ．Ｈｉｌｇｅｒ，Ｄ．Ｋｅｙｓｅｒｓ，ａｎｄ Ｈ Ｎｅｙ，“Ｅｎｈａｎｃｅｄ Ｈｉｓｔｏｇｒａｍ Ｎｏｒｍａｌｉｚａｔｉｏｎ ｉｎ ｔｈｅ Ａｃｏｕｓｔｉｃ Ｆｅａｔｕｒｅ Ｓｐａｃｅ，”Ｐｒｏｃ ＩＣＳＬＰ，２００２，ＰＰ．１４２１— １４２４． 在鲁棒语音识别这一方面，基于空间的方法已经广泛应用，这是由 于其容易理解、计算简便并且能提高效率。噪音和通道扭曲引起的声环 境变化相当于倒谱或者对数谱特征空间的非线性转换 ”。传统的基于 线性特征空间的方法例如倒谱均值减法或者倒谱平均和方差标准化方 法往往受限。作为一种能够改善线性转换方法缺点的替代方法，直方均 衡法（ＨＥＱ）已经被用于弥补声失配。但直方图均衡化方法用于图像处 理时，由于灰度级是一定的，因此计算直方图非常简便；然而语音识别 中的特征矢量是的，而且其值也是随机的，采用传统的直方图均衡 法不仅增加了变换的计算量，而且浪费了资源。所以不少研究者开始尝 试寻找用于语音识别的更优化的直方图均衡法。基于分类的直方均衡 法、自适应直方图均衡法在实验中都取得了较好的识别结果。我们有理 由相信直方图均衡法在语音识别方面会越走越远！ 参考文献 １ ７ ＪＥＴＲＩ Ｊｏｕｒｎａｌ，Ｖｏｌｕｍｅ ２８，Ｎｕｍｂｅｒ ４，Ａｕｇｕｓｔ ２００６． １ ８ ｊＳｋｏｓａｎ Ｍ，Ｍａｓｈａｏ Ｄ Ｊ．Ｍｏｄｉ？ｅｄ ｓｅｇｍｅｎｔａｌ ｈｉｓｔｏｇｒａｍ ｅｑｕａｌｉｚａｔｉｏｎ ｏｒｆ ｒｏｂｎｓｔ ｓｐｅａｋｅｒ ｖｅｒｉｉｆｃａｔｉｏｎ．Ｐａｔｔｅｒｎ Ｒｅｃｏｇ—ｎｉｔｉｏｎ Ｌｅｔｔｅｒｓ，２００６，２７（５）： ４７９－４８６ 【９ ｊＤｈａｒａｎｉｐａｒｇｄａ ｓ，Ｐａｄｍａｎａｂｈａｎ Ｍ．Ａ ｎｏｎｌｉｎｅａｒ ｕｎｓｕｐｅｒ—ｖｉｓｅｄ ａｄａｐｔａｔｉｏｎ ｔｅｃｈｎｉｑｕｅ ｏｒｆ ｓｐｅｅｃｈ ｒｅｃｏｇｎｉｔｉｏｎ．Ｉｎ：Ｐｒｏ—ｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ６ｔｈ Ｉｎ— ｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｐｏｋｅｎ Ｌａｎ—ｇｕａｇｅ Ｐｒｏｃｅｓｓｉｎｇ．Ｂｅｉｊｉｎｇ，Ｃｈｉｎａ：ＩＳ— ＣＡ．２０００ ５５６－５５９ ｌ １０］Ｈｉｌｇｅｒ Ｆ，Ｎｅｙ Ｈ．Ｑｕａｎｔｉｌｅ ｂａｓｅｄ ｈｉｓｔｏｇｒａｍ ｅｑｕａｌｉｚａｔｉｏｎ ｆｏｒ ｎｏｉｓｅ ｒｏｂｕｓｔ ｓｐｅｅｃｈ ｒｅｃｏｇｎｉｔｉｏｎ．Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ７ｔｈ Ｅｕｒｏｐｅａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｐｅｅｃｈ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ａｎｄ Ｔｅｃｈ—ｎｏｌｏｇｙ Ａａｌｂｏｒｇ，Ｄｅｎｍａｒｋ：ＩＳＣＡ， ２００１．１１３５－１１３８ ［１］马大猷现代声学理论基础．北京：科学出版社，２００４ ［２］赵力语音信号处理［Ｍ］机械工业出版社，２００８ ｌ １ １ ｊＸ．Ｈｕａｎｇ，Ａ．Ａｃｅｒｏ，ａｎｄ Ｈ—ｗ Ｈｏｎ，Ｓｐｏｋｅｎ Ｌａｎｇｕａｇｅ Ｐｒｏｃｅｓｓｉｎｇ， Ｐｒｅｎｔｉｃｅ－Ｈａｌ１．２００１
