遗传算法组卷_基于遗传算法的组卷方法研究

　　摘要 本文在分析了自动组卷算法研究的传统方法的基础上，根据成卷技术指标要求，提出成卷前先进行组卷要求与题库分布相容性检测的方法，最后以知识、难度、题型为主要控制参数建立基于遗传算法的自动组卷问题数学模型，并在此基础上给出了基于实数编码的实例验证。
　　关键词 自动组卷；遗传算法；题库；实数编码；相容性检测
　　中图分类号O1 文献标识码A 文章编号 1674-6708（2011）35-0081-02
　　考试是一项“测量工程”。从统计学的角度来看，考试是一种抽样测量，通常我们告诉学生的应考内容是考查的总体，而试题实际考查到的内容则是我们从总体中抽取的样本。要提高考试质量，在实施考试之前，先要进行设计。为了更好地普及计算机命题，有必要研究一种采用科学、先进的组卷方法来实现快速、高效、科学组卷。本文着重对遗传算法在自动组卷中的应用研究，通过对遗传算法理论的研究，探讨一下遗传算法以解决智能选题成卷的问题。
　　1 自动组卷算法研究
　　国内外的许多科研单位、学校机构都在对组卷系统进行研究[1]。虽然组卷系统是一个被探讨了很长时间的问题，但至今还没有一个很好的解决其自动出题的算法方案。以前所采用的算法大多是随机选取和回溯试探法，他们虽然都能最终组出试卷，但是在实际的操作过程中，却发现他们不是耗费的时间很大就是容易进入死循环。
　　2 遗传算法概述
　　遗传算法GA[2]（Genetic Algorithm）是一种新型的、模拟自然界生物进化过程的随机搜索、优化方法。他是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是由美国Michigan大学的JohnH.Honlland教授于1975年首先提出来的。他采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。由于他采用种群的方式组织搜索，这使得他可以同时搜索解空间内的多个区域。而且用种群组织搜索方式使得遗传算法特别适合大规模并行。
　　3 基于遗传算法的组卷方法
　　首先，确定考试时间KSSJ、试卷的满分值MFZ和所用的题型以及各种题型的题目和分数，而且对一种考试而言，这种题型一一分数分布曲线LT常保持相对稳定，如英语等级考试、各种计算机等级考试等都是这样。
　　其次，获取难度一一分数分布曲线LD、内容一一分数分布曲线LC，教学要求度一一分数分布曲线LR及其各自允许的误差，曲线LC，LR及其允许的误差均由用户给出。曲线LD在很大程度上决定了考试成绩的分布，是很重要的一条曲线。
　　4 自动组卷的遗传算法设计与实现
　　4.1染色体编码及群体的初始化
　　经典遗传算法采用二进制编码，用1表示该题被选中，0表示该题未被选中，这种编码简单明了，但是进行交换等遗传操作时，各题型的题目数难以精确控制，而且，当题库中题量很大时，编码很长。
　　4.2适应度函数
　　在遗传算法中，以适应值大小来区分群体中个体的优劣。一般情况下适应值越大的个体越好，适应值越小的个体越差。
　　4.3遗传算子设计
　　1）选择算子
　　采用期望值模型选择机制，即先用公式1计算群体中各个个体期望被选中的次数：
　　公式（1）
　　其中M为种群规模，Fi为第i个个体适应值。用Ni的整数部份[Ni]安排个体i被选种的次数，这样其选出个个体，然后对Ni的小数部分作为概率进行贝努利试验，若试验成功，则该个体被选中，不断重复，直至选满为止。
　　2）交叉算子
　　将以上选出的个体进行两两随机配对，对每一对相互配对的个体采用有条件的“均匀交叉”，即两个配对个体的每一个基因座上的基因都按设定的交叉概率Pc和一定的条件（确保交换后个体仍是有意义的组合）进行交换，产生两个新个体。
　　3）变异算子
　　由于普通的变异操作可能会使用户指定范围外的题目出现在染色体中，也会使各题型的题目数难以保证，本文采用有条件的变异算子，即每个个体的每一个基因座上的基因都按设定的变异概率Pm在一定范围内变异。
　　4）最优保存策略
　　进行了选择、交叉、变异操作后，比较新一代的最好个体与上一代的最好个体的适应值，如下降，则以上一代最好个体替换新一代的最差个体。
　　5）算法实现
　　确定参数：最大代数MaxGene，群体规模Pop Size，交叉概率Pc，变异概率Pm；
　　接收用户的组卷要求：
　　产生初始群体；
　　当前代数Gene=0；
　　计算群体中各个体的适应值；
　　while（Gene 本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文