计算机有关自动机的论文

计算机有关自动机的论文

　　自动机原来是模仿人和动物的行动而做成的机器人的意思。但是现在已被抽象化为如下的机器。时间是离散的(t=0，1，2……)，在每一个时刻它处于所存在的有限个内部状态中的一个。对每一个时刻给予有限个输入中的一个。那么下一个时刻的内部状态就由现在的输入和现在的内部状态所决定。下面是学习啦小编给大家推荐的计算机有关自动机的论文，希望大家喜欢!

　　计算机有关自动机的论文篇一

　　《基于遗传算法的自动组卷系统设计》

　　摘要：自动组卷系统是计算机辅助教学的重要组成部分，而遗传算法以其全局寻优和智能搜索的特性，得到了广泛的运用。根据自动组卷系统的特点，将遗传算法合理应用于自动组卷中，在遗传算法中，设计了双种群机制，并以试卷难度、试卷区分度、试卷的估计用时、知识点分布为基础构造适应度函数，通过轮盘赌选择方法、多点交叉和变异，较好地解决了自动组卷的多重目标寻优问题。

　　关键词：自动组卷;遗传算法;适应度函数

　　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结语

　　本文围绕自动组卷存在的问题，重点研究了遗传算法的改进及其在自动组卷算法中的应用。通过运行基于该遗传算法的组卷程序，证明了该设计的可行性、有效性。

　　参考文献：

　　[1]黎军.基于遗传算法的自动组卷设计[J].电脑学习，2009(3).

　　[2]陈国良，王煦法，庄镇.遗传算法及其应用[M].北京：人民邮电出版社，1996.

　　[3]张超群，郑建国，钱洁.遗传算法编码方式比较[J].计算机应用，2011(3).

　　[4]丁承层，强传生，张辉.遗传算法纵横谈[J].信息与控制，1997(1).

　　计算机有关自动机的论文篇二

　　《基于改进遗传算法的自动组卷研究》

　　摘要：通过详细分析试卷的各项约束条件，建立了一个以知识点、难度系数、区分度等为核心属性的自动组卷数学模型，并利用改进的遗传算法实现了自动组卷。

　　关键字：自动组卷;数学模型;遗传算法

　　自动组卷就是根据用户的要求，采用一定的算法自动地从试题库中抽取一定数量的试题组成试卷。自动组卷算法的好坏直接影响到试卷的质量，如何从试题库中选出试题组成符合用户要求的试卷，并使组卷具有较高的效率和成功率是当前研究的热门课题。现有的自动组卷算法一般有三种：随机选取法、回溯试探法和遗传算法。遗传算法是一种新发展起来的并行优化算法，它很适合解决自动组卷问题。

　　1 试题核心属性的确定

　　在自动组卷系统中，一些试题库设置了试题的各类属性，如章节、层次、要求、题型、难度系数、难度级别、各章节分值等属性，其实过多的属性会增加实际组卷的难度，降低效率。以教育学理论为指导，选择以下属性作为试题的核心属性。

　　(1) 题号。试题的编号，用来唯一标识试题。

　　(2) 题型。试题的类型。

　　(3) 知识点。某道题属于某门课程的哪个知识点，知识点的设置不以章节为依据，从而可以避免教材的不同对组卷造成影响。

　　(4) 难度系数。难度系数[1]是表示某一试题的难易程度，通常用未通过率来表示，即一次考试中未答对某道试题的考生数在其总体中所占的比例。一般来说，难度系数值为0.5时，是中等难度，如果小于0.3试题太简单，如果大于0.7试题太难，对考生都会做或都不会做(难度系数为0或为1)的试题，属于无意义的试题，必须淘汰。

　　(5) 区分度。区分度[2]是指某道题对不同水平考生加以区分的能力。区分度高的试题，对学生水平有较好的鉴别力。区分度的计算公式为：

　　其中，B表示试题的区分度，H表示样本中高分组在某题上所得的平均分，L表示样本中低分组在某题上所得的平均分，K表示某题满分。高分组和低分组一般各占样本的25%～30%，最好取27%。一般来说，试题的区分度在0.4以上就被认为是很好的。在0.3～0.39之间，认为良好;在0.2～0.29之间，认为可以;在0.19以下，认为差，必须淘汰或加以修改。对在校学生的达标考试，试卷的区分度不宜太高，因为它不是选拔性质的考试。但也不能过低，否则对学生的鉴别效果差，不能很好的达到考试的目的。一般区分度控制在0.2～0.3之间为宜。

　　(6) 分值。某小题的分数。

　　(7) 答题时间。完成某题估计所需的时间。

　　2 自动组卷数学模型的建立

　　自动组卷中决定一道试题，其实就是决定一个包含题号、题型、知识点、难度系数、区分度、分值、答题时间的七维向量(a 1，a 2，a 3， a4，a 5，a 6，a 7)。假设一套试卷中包含n道试题，一套试卷就决定了一个n×7的矩阵S：

　　这就是问题求解中的目标矩阵，其中a i1 、a i2 、 a i3 、a i4、a i5、 a i6 、a i7分别表示试卷中第i道题的题号、题型、知识点、难度系数、区分度、分值、答题时间。从矩阵S可以看出组卷问题是一个多重约束目标的问题求解，且目标状态不是唯一的。

　　在实际组卷时，用户会对试卷提出多方面的要求，用户的每一个要求对应试卷的一个约束条件。要组成一份符合要求的、高质量的试卷，目标矩阵的分布要满足以下试卷约束条件。

　　(1) 试卷中包含的题型以及每种题型的题量要与用户的设置相符。

　　k种题型的题量=

　　(2) 试卷中包含知识点即考核知识点以及各考核知识点所占分数的比例要与用户设置相符。

　　K种考核知识点所占分数=

　　(3) 试卷的难度系数要满足用户的要求，试卷的难度系数一般用试卷中每道试题的难度系数的加权平均来计算。

　　即：试卷的难度系数=

　　(4) 试卷的区分度要满足用户的要求，试卷的区分度一般用试卷中每道试题的区分度的加权平均来计算。

　　即：试卷的区分度=

　　(5) 试卷的总分要与设置相符。

　　即：试卷的总分=

　　(6) 试卷的总答题时间要与用户设置相符。

　　即：试卷的总答题时间=

　　在实际组卷时，试卷的总分、考核知识点、各题型每小题分值、试卷中包含的题型、各题型的题量都应该是精确达到的。试卷中各考核知识点所占的分数、试卷的难度系数、区分度和试卷的总答题时间这四个约束条件可以存在一定的误差。误差的大小由用户的期望值和各约束条件的重要性决定。在实际应用中，各约束条件的重要性是不同的，因此，目标函数就取各项误差的加权和。目标函数f可以表示为：

　　为了不至于各项误差相互抵消，实际值与用户要求值的误差都取绝对值。其中，试卷中各考核知识点所占的分数和试卷的总答题时间这两项的误差为实际值与用户要求值的误差绝对值与用户要求值的比，试卷的难度系数和区分度这两项的误差为实际值与用户要求值的误差的绝对值。w i表示第i个约束条件的权值，w i通常由专家经验或试验给出，0≤w i ≤1。由上式可知，目标函数f的值越小，即误差越小，问题的解越优，即生成的试卷越接近用户的需求。

　　3 遗传算法

　　遗传算法[3，4，5]是以适应度函数(或目标函数)为依据，通过对群体中的个体进行遗传操作实现群体内个体结构重组的迭代处理过程。在这一过程中，群体中的个体一代一代地得以优化，并逐渐地逼近最优解，最终获得最优解。传统遗传算法的主要步骤包括初始染色体群体生成、适应度评估和检测、选择操作、交叉操作和变异操作。传统遗传算法流程图如图1所示(其中t为进化代数，t0为最大进化代数)。

　　4 基于改进遗传算法的自动组卷

　　传统的遗传算法采用二进制编码，用1表示某题被选中，0表示某题没有被选中，这种编码非常简单，但在进行交叉和变异操作时，各题型的题量很难控制，而且当试题库题量很大时编码很长。传统的遗传算法以进化代数等于最大进化代数作为终止条件，但是在实际组卷过程中并不知道种群进化到第几代就能得到试卷的最优组合。因此用遗传算法实现自动组卷时，要对传统遗传算法进行一些改进。

　　4.1 改进的遗传算法

　　4.1.1 染色体编码

　　通过对编码的大量分析，提出了一种分段实数编码机制，首先将染色体分成若干段，每一段对应一种题型，组成试卷的各道试题题号直接映射为基因，编码时将同一题型的试题放在同一段，同一段内题号各不相同。以题号编码的方法所表达的意义清楚、明确、不需解码，从而可以提高算法性能，提高运算效率。而且交叉和变异操作都在各段内部进行，因此可以保证组卷过程中各题型题量的正确匹配。

　　4.1.2 适应度函数设计遗传算法在进化搜索中仅以适应度函数为依据，利用种群中每个个体的适应度值来进行搜索。因此，适应度函数的选择至关重要，一般而言，适应度函数是由目标函数变换而成的。上面提出的自动组卷模型是最小化问题，采用如下方法可将目标函数f转换成适应度函数F。

　　由上式可知，F的取值范围为0～1，适应度函数F的值越大，说明个体越好，个体越接近问题的最优解。

　　4.1.3 初始化染色体群体

　　随机生成初始染色体群体，在初始染色体群体中，染色体的长度为n，群体的大小为m，m太小时，难以求出最优解，太大时则增长收敛时间。群体的大小一般根据需要，按经验或试验给出，一般m=30～160。

　　4.1.4 遗传算子

　　(1) 选择算子

　　在遗传操作中，为了保留较优的个体，以概率1完全地复制每一代群体中按适应度值从大到小依次排列的前面2个个体。为了保持群体大小不变，同时删除适应度排列的后面的2个个体。然后从排列在前面的m-2个个体中随机抽取p(p≤m-2)个个体进行交叉和变异操作。这种选择策略使得适应度小的个体也有可能被选中，这样有助于增加下一代群体的多样性。

　　(2) 交叉算子

　　在遗传操作中，采用了分段的思想，交叉的时候按题型段进行交叉，因此交叉后不存在段内试题重复的问题，也不会改变每种题型的题量。交叉概率p c太小时难以向前搜索，太大时则容易破坏高适应度的结构。一般p c=0.4～0.6。 (3)变异算子在遗传操作中，变异在染色体的题型段内进行。变异概率p m太小时难以产生新的基因结构，太大时使遗传算法成了单纯的随机搜索。一般p m=0.01～0.2。

　　4.1.5 终止条件

　　在改进的遗传算法中，设置了期望适应度值，把每一代计算出来的最高适应度个体的适应度值与期望适应度值相比较，当适应度最高的个体的适应度值大于或等于期望适应度值时则停止进化，否则继续进行遗传操作、计算适应度值、反复迭代直到组卷成功。

　　4.2 主要算法描述

　　基于改进遗传算法的自动组卷的主要算法描述如算法1所示。

　　算法1：

　　int GJGA(p c，p m，m，f0)

　　{

　　t=0;

　　initialize(p(t));//随机产生初始染色体群体

　　计算初始染色体群体的适应度值;

　　while (maxf

　　{

　　selection(p(t));//选择操作

　　crossover(p(t));//交叉操作

　　mutation(p(t));//变异操作

　　得到下一代染色体群体q(t+1)，计算下一代染色体群体的适应度值;

　　t++;

　　}

　　输出当前染色体群体中适应度最高的染色体;

　　}

　　4.3 遗传算法复杂度分析

　　在遗传算法中，绝大部分处理都集中在适应度的计算上，因此可以用计算个体适应度操作的时间复杂度作为算法的时间量度。遗传算法的时间复杂度为O(t*m*n)。因为试题库中的题量一般都很大，所以改进后的遗传算法的时间复杂度一般要比传统遗传算法的时间复杂度小。遗传算法的空间复杂度可以用初始染色体群体所占的空间来衡量，遗传算法的空间复杂度为O(m*n)。因为改进后的遗传算法的染色体的长度远比传统遗传算法的染色体的长度小，所以改进后的遗传算法的空间复杂度远比传统遗传算法空间复杂度小。

　　5 结论

　　算法的改进往往不能顾及问题每一个方面，如果算法设计的核心是提高解的精度，则算法可能在搜索范围和搜索精度上花去更多的时间，如果算法的设计主要在于尽快收敛，得到结果，则在解的精度上考虑很少，算法往往侧重于减少进化代数。改进后的遗传算法使生成试卷的质量得到了保证，但要使组卷的收敛速度得到进一步改进，还需进一步研究。

　　参考文献

　　[1] 文海英. 智能型试卷自动生成系统中试卷难度控制技术的研究(J).湖南科技学院学报，2005，26(5)：153-156

　　[2] 常振江. 学生成绩分布与一种简便的评估试卷命题质量的方法(J). 辽宁师范大学学报：自然科学版，2003，26(1)：109-112

　　[3] 丁卫平. 基于遗传算法的智能组卷应用研究.电气电子教学学报(J)，2005，27(2)：93-95

　　[4] 朱黎明. 基于单亲遗传算法的试题生成及其应用研究(D). 长沙：湖南大学，2005

　　[5] T.Lynda，C.Chrisment，Boughanem Mohand. Multiple Query Evaluation Based on Enhanced Genetic Algorithm. Information Processing and Management，2003，39(2)：215-231