相关热词搜索：
计算机有关自动机的论文
计算机有关自动机的论文 计算机有关自动机的论文篇一 《基于遗传算法的自动组卷系统设计》 摘要：自动组卷系统是计算机辅助教学的重要组成部分，而遗传算法 以其全局寻优和智能搜索的特性，得到了广泛的运用。根据自动组卷系统的特点， 将遗传算法合理应用于自动组卷中，在遗传算法中，设计了双种群机制，并以试 卷难度、试卷区分度、试卷的估计用时、知识点分布为基础构造适应度函数，通 过轮盘赌选择方法、多点交叉和变异，较好地解决了自动组卷的多重目标寻优问 题。关键词：自动组卷;遗传算法;适应度函数 0引言 考试是教学过程中的一个重要环节，我们用它来检测教学效果，以期 提高教学质量。传统的手工方式，都是以教师的经验与知识的积累为依据出题， 带有一定的主观性，考试命题质量和科学性不能保证。另外，对于有些课程，我 们希望平时能够在计算机机房通过上机完成测验。所以，伴随人工智能的广泛应 用，自动组卷技术成为我们必须深入探讨的一个课题。现有不少自动组卷系统， 但其算法存在时间复杂度和空间复杂度偏大、程序结构复杂、试题缺乏随机性等 缺陷¥[1¥]。将遗传算法应用于自动组卷系统中，并将试卷难度、试卷区分度、 试卷的估计用时、知识点分布作为综合优化目标，对上述缺陷作出了改进。
1基于遗传算法的自动组卷算法设计 遗传算法的操作步骤为编码、随机产生初始种群、构建适应度函数、 对初始种群迭代执行选择、交叉、变异等遗传操作产生下一代种群，获取最优解、 解码¥[2¥]。本自动组卷算法设计如下。
1.1编码设计 整数编码直接采用解空间的形式进行编码，意义明确，易于引入特定 领域的信息，而且能大大缩短串长，遗传操作无须频繁地编码、解码，改善了遗 传算法的计算复杂性，提高了算法效率¥[3¥]。本算法采用整数编码将现实问题映射到染色体即个体形式。
实现时，按试卷的题型对个体进行分段编码。比如试卷由L种题型的 试题组成，则染色体编码划分成L个子段，每个子段对应一种题型。每个子段中 基因个数为该题型要求的题目个数。
试题库中每道题目，都有一个编号与其对应。比如现在生成了两张试 卷个体ExaPaper1、ExaPaper2。分别由选择、填空、判断、问答、综合5道题组 成。
1.2产生两个初始种群 在初始种群产生时，应采用某种算法，使优秀、中等的、劣质的个体 基本同概率存在。以保证初始种群产生的多样性和分布均匀性。并且采用产生2 个初始种群的方法，同时对解空间内多个区域进行搜索，并互相交流信息。这种 设置方法，虽然每次需执行与种群规模n成2倍的计算量，但实质上可进行大约O (n¥+3)个解的有效搜索。因此，这种2种群的设置方法，成本虽提高一倍，效率 则以指数形式上升。
实现时，本算法采用随机的方法产生320个个体，将他们分为40个子 空间，则每个子空间中有8个个体。然后从每个子空间中随机获取5个个体，这样 就形成了200个个体，对这200个个体再随机划分到两个初始种群中。
1.3构造适应度函数 一份卷子设计是否合理，通常从3个方面考察：第一，题型比例配置 是否适当;第二，题目难、中、易比例是否合理;第三，干扰项是否有效，能不能 反映考生的典型错误。本算法将试卷难度、试卷区分度、试卷的估计用时、知识 点分布4个目标作为综合优化目标，因此也将其作为构造适应度函数的主要依据。
适应度函数的构造过程为，首先以各目标为基础分别构造各自的目标函数，然后 使用加权的方法对各目标函数进行组合获得适应度函数。
1.3.1各目标函数构造 (1)试卷难度目标函数。
针对不同的考生，试卷难度要求也不同，因此将试卷难度作为构造适应度函数的一个依据。
Fc(X)=1-1[]total_score∑N[]i=1fc(i)*p(i)-Exp_Difficulty(1) 其中，X为种群中个体，N为X的长度，i表示X中第i个位置。对应到 自动组卷中，N为题目的个数，total_score为试卷的总分，i表示X这份试卷中第几 道题目。f¥-c(i)为i这道题目对应的难易度，p(i)为这道题目对应的分值。
Exp_Difficulty为对试卷的难度期望值。由此可知，F¥-c(X)值越大，说明试卷难 度符合要求的可能性越大。
(2)试卷区分度目标函数、试卷估计用时目标函数。
区分度是指试题对被试者情况的分辨能力的大小。区分度适当的试卷 能把优秀、一般、差三个层次的学生真正区分开。试卷区分度目标函数、试卷估 计用时目标函数构造方法与试卷难度目标函数构造方法类似。试卷区分度目标函 数构造如式(2)所示。
Fd(X)=1-1[]total_score∑N[]i=1fd(i)*p(i)-Exp_Difficulty(2) 其中，X为种群中个体，N为X的长度，i表示X中第i个位置。对应到 自动组卷中，N为题目的个数，f¥-d(i)为i这道题目对应的区分度，p(i)为这道题目 对应的分值。total_score为试卷总分值。Exp_Different为对试卷的区分度的望值。
由此可知，F¥-d(X)值越大，说明试卷难度符合要求的可能性越大。
试卷估计用时目标函数构造如式(3)、式(4)所示。
Ft(X)=T(X)T(X)11[]T(X)T(X)1(3) T(X)=∑N[]i=1ft(i)[]Exp_Time(4) 其中，X为种群中个体，N为X的长度i表示X中第i个位置。对应到自 动组卷中，N为题目的个数，f¥-t(i)为完成i这道题目的期望时间。Exp_Time为完 成本试卷估计用时的期望值。由此可知，F¥-t(X)值越大，说明试卷难度符合要求 的可能性越大。
(3)知识点分布目标函数。
教学大纲中，对不同章节知识点的掌握程度要求也不同。因此，设计 知识点分布目标函数，用来把握考察的知识点是否全面合理。知识点分布目标函数构造如式(5)、式(6)所示。
Fn(X)=(∑M[]j=1fw(j)*∑N[]i=1Fs(i))/total_score(5) Fs(i)=fs(i)第i题目属于第j章内容0第i题目不属于第j章内容(6) 其中，X为种群中个体，N为X的长度，i表示X中第i个位置。对应到 自动组卷中，M为本试卷要考察到的章节总数。fw(j)为课本第j章在试卷中占用 的权重。N为题目的个数，fs(j)为第i题目的分值。若第i题目是第j章节的内容， F¥-s(i)才存储f¥-s(i)的值，以便参与实际试卷中第j章节权重的计算。total_score 为试卷总分值。由此可知，F¥-n(X)值越大，说明试卷难度符合要求的可能性越 大。
1.3.2适应度函数构造 使用加权的方法对各目标函数进行组合，形成适应度函数。适应度函 数如式(7)所示：
F(X)=1Fc(X)+2Fd(X)+3Ft(X)+4Fn(X)(7) 其中，F¥-c(X)、F¥-d(X)、F¥-t(X)、F¥-n(X)分别为试卷难度、试卷区 分度、试卷的估计用时、知识点分布的目标函数。1、2、3、4分别为试卷难度、 试卷区分度、试卷的估计用时、知识点分布目标函数的权值。并且1+2+3+4=1。
权值1、2、3、4的取值应依据具体试卷考核目标而定。
1.4遗传操作 1.4.1选择操作设计 在本算法中，应用轮盘赌选择方法进行选择操作，决定将哪些个体复 制到新种群中¥[4¥]。并进一步根据适应度值对t+1代和t代种群最优个体进行比较 及选取，确保在t+1种群中，最优个体的适应度并不低于t种群的最优个体适应度。
1.4.2交叉操作设计 本文使用多点交叉操作。针对两个个体即两份试卷中的选择、填空、 判断、问答、综合5类题型，分别进行20%的基因点交叉。比如假设生成了表3、 表4所示两份试题。黑边框处为交叉点。交叉操作后，试卷1、卷2转换为表5、表 6所示内容。1.4.3变异操作设计 变异操作为对群体中某些个体的基因进行小概率扰动。本变异的操作 如下：以题型为基础，将个体分段，每段随机选择一个变异位置，并从同题型题 库中随机选择一个题目替换该变异位置题目，条件是新选的题目不能与当前试卷 中同题型其它题目重复。
1.4.4种群竞争设计 本算法采用产生2个初始种群的方法，同时对解空间内多个区域进行 搜索，并互相交流信息。种群竞争的具体设计思想为：对两个初始种群K11、K21 分别进行遗传操作产生新的种群，各经过T代(不同问题T的设定不同)后，获取到 新种群K1T、K2T。将K1T、K2T两个种群中个体合并，按适应度排序。前一半 个体形成新的K1T种群，后一半个体形成新的K2T种群。将新K1T、K2T再反复 执行上述过程，直到满足终止条件时进化结束。本算法的终止条件是当达到规定 的最大迭代次数HMAX或者最好个体的适应度函数值HMAX/5次达到了要求。
1.5选择最优解及解码 通过遗传算法最终可获得一组个体，对这组个体分别计算适应度值， 获取适应度最优的个体，作为最终解。因为是整数编码，个体中基因值即为题库 中被选中题的题号。因此，从最优个体可直接得到最终生成的试卷。
2结语 本文围绕自动组卷存在的问题，重点研究了遗传算法的改进及其在自 动组卷算法中的应用。通过运行基于该遗传算法的组卷程序，证明了该设计的可 行性、有效性。
