毕业设计-遗传算法

一、引言随着计算机在教学领域的应用和发展，试题库的编制和应用也越来越显示出其重要性，而智能组卷是试题库系统研制的一个难点。智能组卷要求用户只需输入极少的参数值就可由计算机自动生成一种试卷模式，并据此抽题组成试卷，最终形成一份既符合用户要求又符合教学要求的试卷。一个自动组卷系统的性能评价主要取决于组卷算法和相对于算法的试题库的库结构。因此，试题库的库结构设计和组卷算法的设计师智能型试卷自动生成系统的重要内容。本文提出了一种用改进的遗传算法来求解试题库组卷问题的方法和一种使组卷效率更高、速度更快、数据冗余度更小的试题库结构。二、智能型试卷自动生成系统的组卷问题综合遗传算法的特点，系统所采用的试题库结构要全面客观反映试题的本质，并且易于遗传算法操作，使组卷实现智能化，组卷效率高、速度快、数据冗余度小。因此，所确定的试题结构（或试题的属性）如下：章节：试题内容所属的篇章；试题编号：试题编号具有与每一道试题一一对应的性质，它不参与遗传算法在智能组卷中的运算，仅作为参与运算的数据结构的不变分量，用于指示运算结果具体记录；试题类型：可分为判断题、选择题、填空题、简答题、计算题、证明题、算法设计题、编写程序题、综合题，参与运算时可用编码值代替，并且为了在生成试卷时能够快速选取指定类型的试题和减少冗余度，在建库时可为每种题型建立一个库文件；试题难度：在试卷命题过程中，针对不同的考试对象，不同阶段的考试，命题难度也不同，所以应在数据库中增加难度系数。用平均失分率来表示，取值范围是0.0-1.0，值越大难度越大；试题的内容：不参与组卷运算的过程；已出题次数：为了使遗传算法更好的应用于组卷，应加一字段来表明已经出题次数，以此决定此题再出的概率，这一结够对出题的影响是：结构中的值越大，在出此题的概率越小，提高命题质量；试题内容相关性：在试卷命题过程中避免相同内容的试题太多，从而无法对学生所学的知识进行全面的考核，因此可用平均相关系数ρ和相关性分布η两个指标来考核。一份试卷的平均相关系数应在3~7之间；考查点：为了适应不同教材的需要，可按大纲要求将某门课的内容分为不同的考查点，选题时以考查点为依据，统一试卷中不能有考查点重复的试题，它是和相关性密切相关的结构；题分：试题的分数；能力层次：可分为识记、理解、应用、综合等；估时：完成该题所需时间的估计值；试题答案：不参与组卷运算的过程。经过应用，这种结构能很好的配合遗传算法实现智能组卷。2.2智能型组卷自动生成系统中组卷的功能要求考试内容由用户决定，可以按篇章为单位决定，也可以按题类或考查点为单位决定；考试时间由用户决定；整卷的难度系数由用户根据学生的水平决定，一般取0.2~0.5；每份试卷满分由用户指定，其中主观题、客观题所占的分数比例由用户指定；试卷各篇章内容所占分数比例应与教学时数成比例；各种题型的题目数由用户确定，但要注意总分达到满分的要求；全卷分数按知识能力层次要求的分布由用户指定，如：识记：20%，理解：30%，应用：35%，综合：15%；各题类内容中，对层次必须满足一个分数比例表；全卷的区分度、期望值等由用户指定。2.3智能型试卷自动生成系统中组卷的数学模型组卷中决定一道试题，就决定它的上述12个属性，也就是说决定一个12维的向量（a1，a2，a3，，……a12）（ai相当于2.1节的第i个属性），决定一份试卷有n道试题，实际上就是决定一个n*12阶矩阵；s=[这就是一个问题求解中的目标状态矩阵，从2.2节中指出的组卷的功能要求可以看出，目标状态矩阵应满足如下相应的约束条件：试卷总分由用户给定，即试卷分数的约束。考试内容可以按篇章为单位决定，也可以按题类或考查点为单位决定，因此，在计算总分时可以先计算各篇章为单位决定考试内容为例来计算总分，其他类推。Mk（第k篇章的题分）=k=1nckai，9，其中ck=考试时间=由用户指定，即试卷总时间的约束；试卷难度=由用户给定，即试卷难度约束；j为能力层次，即能力层次约束。j的取值可为：识记、理解、应用、综合等，具体总类和所占的分值由用户给定。同理，教学要求、各种题型比例、区分度、期望值等等约束条件，和上面类似由用户组卷时给定。但根据我们的经验，指标过多对组卷问题增加难度降低效率，因此在组卷是可以根据用户组卷要求给出相应的约束条件。可以看出，组卷问题的实际是求多约束条件的最优解，而且满足条件的最优解不是唯一的。3改进遗传算法在智能型试卷自动生成系统中的应用3.1遗产算法的基本思想大自然的生物进化中，一个生物群体要经过交配、变异、自然选择的过程，形成下一代群体，如此循环下去，不断净化，最后生存下来的总是最优的。将这种思想运用下去，就形成了遗传算法，它的基本结构可描述为：随机初始化种群=p(0)={X1,X2,……,Xn|,gen=0;}计算p(0)中个体的适应度值。while(不满足终止准则)do{根据个体的适应度值及选择策略从p(gen)中选择生成下一代父体p(gen)；执行杂交、变异和再来生产新的种群p(gen+1)；计算p(gen+1)中个体的适应度值；gen=gen+1}经典的遗传算法存在搜索后期效率低和易形成未成熟收敛的情况。为此，人们尝试了许多改进方法，包括设计不同的选择、交叉及变异算子，改变算法结构，设计自适应交叉和变异概率，将遗传算法与其它优化智能方法相结合等。根据遗传算法，在采用遗传算法寻优时，通常按以下主要步骤进行：基因编码；初始群体生成；群体中个体适应度值的计算；对群体中个体进行遗传操作（即选择、交叉和变异）适应度值的再次计算；如果满足终止条件，迭代停止，输出问题的最优解；否则，转向步骤4上述遗传算法的每一步都对优化搜索的收敛速度和解的质量有影响。3.2改进型遗传算法在智能型试卷自动生成系统中应用针对试题组卷的具体情况，我们对简单遗传算法进行改进后应用于智能型试卷自动生成系统中，下面给出具体的解决方案：确定编码方案用遗传算法求解问题，一般不是直接在问题的解空间上，而是利用解的某种编码表示的。在智能型试卷自动生成系统中，由于在建库时为每种题型建立了一个库文件，故每种题型可各自独立编码。因此，编码方案可采用分组实数编码策略，就是根据各题型各自进行实数编码，然后对每一个题型再采用传统二进制编码策略进行处理，但题型组之间的编码是独立的，每一组编码反映一种题型。这样，可以克服以往采用二进制编码搜索空间过大和编码长度过长的缺点。生成初始群体p(0)为了加快遗传算法的收敛并减少迭代次数，试卷初始种群p(0)完全随机的方法产生，而是根据题型（或各篇章内容或各考查点）所占分数比例、总分的要求。确定适应度函数适应度函数是用来评判试卷群体中个体的优劣程度的指标，遗传算法利用适应度值这一信息来指导搜索方向。我们采用以下形式的适应度函数：F=1/（1+）i=1……n其中ei对应为第i组卷因素对组卷约束的误差，ki为权值系数，且ki>0。这种采用加权误差适应度函数可以较好的反映求解智能组卷问题的特征，当试卷个体对各项组卷约束条件的误差越小时，它的适应度值就越大，表示试卷个体越接近组卷目标。智能型试卷自动生成系统中对遗传算子的改进在简单的遗传算法中，由于交叉后的子代个体取代进行交叉的两个父代个体，导致较快地丢弃了父代的信息，而交叉生成的新个体未必优于父代个体，两者均不利于算法的快速收敛。另外，由于在初始种群产生时题型（或篇章或考查点）。总分都满足要求，为了不破坏初始种群中已满足的约束，所以此算法对交叉、变异及选择步骤做如下的改进：各种题型在各自的编码组中独立进行交叉和变异操作，即交叉算子改进为在相同题型组内进行单点交叉，变异算子也改进为在同一题型组内进行单点变异。交叉后即评价新产生的两个体的适应度值，将其与父代两个体比较，若适应度值相同则视为无效交叉个体，被淘汰掉；若不同则保留，但不取代父代个体。有效交叉及变异后产生的新个体与未被取代的父代个体均参与评价和选择，即从大于N小于2N个体中采用轮盘赌选择法，同时考虑已经出题次数（即an，6）这个约束条件，从中选出N个个体组成新的种群（N为种群规模）。智能型组卷自动生成系统中遗传算法的控制参数控制参数主要包括种群规模N，算法执行的最大代数Maxgen，执行不同的遗传操作的概率（如：交叉概率Pc和变异概率Pm等）及一些辅助性的控制参数（如：用户的组卷要求等）。遗传算法在进化过程中，一代代地往前进化，由于选取最佳遗传参数有一定的困难，参数的选取不一定十分合适，从而容易导致遗传算法的局部收敛即早熟现象，一旦陷入早熟现象，进化不能停止不前，而又无法判断它是否是最优解，从而陷入僵局。例如，种群规模N的值较大进化较慢，但易搜索到全局最优解，而N的值较小时进化速度快，却不易搜索到最优解，权衡智能型试卷自动生成系统的组卷效率和生成试卷的质量，一般N取值为200左右。又如，在遗传算法的运用过程中，交叉概率Pc和变异概率Pm是较难选择的两个参数，一般来说，交叉概率与变异概率选取越大，群体的多样性较差。在智能型试卷自动生成系统中，可采用在进化过程中动态定标交叉概率和变异概率，当群体中各个体较为集中时，增大交叉概率和变异概率。这种自适应遗传算法在保持试卷群体多样性的同时，也保证了遗传算法的收敛性并防止遗传算法陷入局部最优。终止条件出现种群满足用户的组卷约束要求或者是得到用户的满意试卷时；当前种群中最大适应度值与以前各代中最大适应度值相差不大时，这时说明进化效果已经不太显著，再进化下去没有必要；达到指定的进化代数；4实验结果及分析实验条件：将《数据结构》中700道试题按要求分别建立5个库文件，其中判断、填空、算法设计题各100道，选择、综合题各200道。为了使试题的各种属性分布合理，各可用随机函数产生试题的各种属性值。遗传算法的控制参数为：种群规模N=200;最大代Maxgen=500;初始交叉概率Pc=0.6；变异概率Pm=0.1；智能型试卷自动生成系统中约束条件：总分为100分；估计时间为120分钟；题型分数比例为：判断、填空各占10%，选择占20%，综合题占40%，算法设计题占20%；能力层次为：识记：20%，理解：30%，应用：35%，综合：15%；难度为：容易：20%，中等30%，较难40%，