组卷算法研究与实现

组卷算法研究与实现（精选7篇）

组卷算法研究与实现 篇1

市场竞争日趋激烈, 企业越来越重视后备人才的培养和储备, 作为人才培养活动中的重要环节, 考试不仅要公平合理, 还要向科学和高效的目标持续改进。组卷工作是考试过程中的核心环节, 试卷的优劣直接影响考试的结果。传统的组卷方式依赖于教师的经验和喜好, 主观程度大, 随意性强,无法确保试卷的合理性和科学性, 同时, 组卷工作也给教师带来重复劳动、耗费精力的问题。因此, 对组卷过程进行研究, 建立起一套科学规范的智能组卷系统成为了人才培养考核过程中一个亟待解决的问题。

1 智能组卷技术

组卷方法大致可以分为3类: (1) 将试题存入试题库,从库中选取符合约束条件的试题进行组卷, 此方法在实质上仍然是人工组卷, 费时费力, 组卷结果不理想;(2) 将试卷存放在数据库中, 需要时直接选取成型的试卷。此方法缺少灵活性, 对于组合好的试题结构无法更改;(3) 利用智能算法, 在试题库中搜寻符合条件的试题组合成试卷, 该方法利用了智能搜寻的优势, 搜索充分, 速度快, 结果理想。

常用的智能组卷策略包括基于线性规划算法的随机抽取法、回溯试探法和基于智能算法的智能搜寻法, 随机抽取法和回溯试探法 (本质上基于随机抽取法) 都是从试题库中随机选取试题, 与约束条件比对判断, 保留符合约束项的试题, 直至组合出满足条件的试卷。这两种策略都会面临由于随机性产生重复抽取的问题, 因此效率不高。另外, 回溯试探法需要较大的存储空间, 算法复杂, 计算时间往往超出可接受的范围。智能搜寻法则依据一定的智能算法 (例如粒子群算法等), 利用算法中潜在的并行性和交互性, 实现快速精确求解[1]。

2 智能组卷模型

组卷要求选用最具代表性的、有难度层级的试题, 从而保证试题的信度和效度。试题本身有很多属性, 如题目类型、难度和曝光度等, 组卷模型必须对试题属性有所体现。同时,受答题总分、测试时间等诸多条件限制, 组卷问题实质上是一个多约束条件下的组合优化问题, 其本身的非劣解不止一个, 称之为非劣解集。

设非劣解集为S, 则S可以视为由m个试题组成的集合,其中, 每个试题具有n个属性, 则S的形式化定义为: S=a11a12…a1na21 a22…a2nam1 am2 amn(公式1)

上式中的ai1,ai2…ain分别对应 于第i个题目的 各个属性(分数、题型、 章节、难度、 区分度、能力层次等 ) , 一个非劣解集就是一份试卷, 一份试卷对应一个“粒子”, 多个“粒子”在解空间中搜寻最佳位置, 搜寻结束后, 处于最佳位置上的“粒子”就是最能满足用户要求的试卷[2]。

组卷还须满足以下约束条件:

(1) 总分约束P=i=1nai1 (公式2)

(2) 题型约束

Tk=i=1n C2ai2(公式3)

公式3中的C2用来表征题目ai是否为要求的题型, 如果是则C2=1, 反之C2=0。Tk为试卷中第k种题型要求的分数, k取 (1,2…n, 在实际中可表示填空、单选、多选等题型)。

(3) 章节约束

Ck=i=1n C3ai3(公式4)

公式4中的C3用来表征题目ai是否为要求的章节, 如果是则C3=1, 反之C3=0。Ck为试卷中第k个章节要求的分数 ,k取 (1,2…n, n为总章节数 )。

(4) 难度约束

Dk=i=1n C4ai4(公式5)

公式5中的C4用来表征题目ai是否为要求的难度, 如果是则C4=1, 反之C4=0。Dk为试卷中 第k个难度级 要求的分数, k取 (1,2…n, n为难度级的最大值)。

与难度约束类似的, 还有区分度约束和能力层次约束等[3]。

曝光度也是试题的一个属性, 原则上应当保持试题始终处于低曝光度状态, 在组卷模型中, 曝光度随着试题的选取而自增, 增加到一定程度时则考虑在试题库中废弃该 题目。在实际操作中, 曝光度与试题最后被抽取到的时间相 结合 ,考察题目的使用频次。

3 粒子群优化算法

粒子群优化算法是一种基于群体协作 的随机搜 索算法 ,1995年由Eberhart博士和kennedy博士提出。该算法利用个体对信息的共享使整个群体的运动在求解空间中产生从无序到有序的演化过程。其基本公式为

vid=w*vid+c1r1pid-xid+c2r2 (pgd-xid) (公式6)

xid=xid+vid (公式7)

公式6中的c1和c2称为学习因子, r1和r2为 [0,1] 的随机数, w为惯性权重 系数 , 表征粒子 保持自身 速度的趋 势 ,c1r1(pid-xid) 记录粒子自身历史经验 , c2r2(pgd-xid) 记录整个粒子群体的历史经验。vid是粒子的速度, 取值范围为 [-vmax,vmax][4]。组卷过程中 , “粒子”依据上述公式不断调整自身的位置, 向着空间内最优解的位置靠拢。

4 评价函数

组卷的目标是获得一个与用户期望值差距最小的试题的集合, 即组卷目标是求得函数f (x) 的最小值, 用di表示试卷的各项属性与用户需求的差值的绝对值, wi代表各项属性所占的重要程度, 从而得到评价函数[5]如下:

fx=i=1nwidi(公式8)

5 求解过程及结果分析

模拟用户需要对问题进行求解, 粒子数为50, 迭代5000次, 得到如图1所示。

采用粒子群算法可以快速地找到满足适应度要求的结果。在前500代, 搜寻结果向着最优解迅速优化, 2000代后, 优化结果趋于稳定, 最佳结果为0.63, 满足实验要求, 如图2所示。

与人工组 卷时间进 行对比 , 试卷总分100, 题量为45,平均结果如表1所示。

表1显示, 智能组卷在时间上优势较大, 计算机强大的检索功能使得组卷过程几乎不受题库规模影响, 而人工组卷需要从大量的试题库中选取符合多重限制条件的试题并进行分析, 随着试题库规模增大, 人工组卷会的效率会明显下降。

抽取20份试卷统计各项要求的符合度, 结果如表2, 表3, 表4所示。

综合分析表2、表3和表4, 组卷结果与用户要求均出现不同程度的差异, 原因在于试题库中的试题属性的量化值并不完全一致; 同时, 抽取的观测样本不同, 得到的结果会有所差异; 另外, 对不同的属性赋予不同的权重值也会影响最终的组卷符合度, 但总体结果与用户要求的符合度较高 (偏差最高为6.25%, 最低为0.6%)。结果表明, 采用粒子群算法可以快速地对组卷问题进行求解, 求解结果稳定, 组卷结果与用户要求的符合度较高, 在时间上具备人工组卷无法相比的优势。

6 结语

结合企业内部的人才培养考核需求, 对组卷问题进行了研究, 分析了组卷约束条件和需要达到的目标, 确定出组卷的数学模型, 采用粒子群算法对问题进行了求解, 并在系统层面予以实现, 测试结果表明粒子群算法可以用于解决组卷问题, 在组卷速度和准确性上具备优势, 有实际应用的价值和意义。在此研究的内容有限, 后续工作将围绕人工方式与智能方式相结合, 在线考试、试题库批量分析和导入等内容展开, 以提高组卷的准确度和自动化程度。

摘要：依据企业人才培养的考核要求,对组卷环节进行研究和改善,建立起规范高效的智能组卷系统。组卷问题是一个在多约束条件共同作用下的优化问题,难以用传统的计算方法进行求解。引入粒子群优化算法,实现了问题的快速求解。实现了基于粒子群算法的组卷模型,测试结果表明,基于粒子群算法的自动组卷系统成功率高、耗时短,系统界面友好,满足用户需求,有效地提高了工作效率。

关键词：粒子群算法,智能组卷,组卷系统

组卷算法研究与实现 篇2

关键词：组卷,遗传算法,相似性检索,小生境算法,对比实验

网络化教育以其高速快捷和大信息量被广大学习者认可，而网络化考试作为网络化教育的主要组成部分之一[1]，成为研究者们热衷的课题，其中研究点之一就是智能组卷系统。智能组卷系统应用人工智能、机器学习理论，根据学习者的需求和考试试卷的特点建立数学模型，再依靠计算机强大计算能力“智能”地找到学习者的特点和需求，使计算机不断向智能化、人性化的方向迈进，在教育领域更加体贴的为学习者服务[2]。

近年来不断有学者对考试智能组装试卷的方法进行研究和探索[3]。而如何更准确地利用计算机智能的产生出具有针对性的、难度适中的、范围准确的考试试卷就成为了网络化考核之中又一个重要的研究环节。本文提出了将试题文本作为组卷参数之一的改进模式，通过对相似试题文本的排除达到遗传算法中早熟现象的免疫[4]。同时增加考试试卷的多样性。其次，提出遗传算法框架模式并研究遗传算法中适应度函数对函数收敛速度的影响。最后对研究算法进行测试，并对结果进行了实现。

1 遗传算法在组卷中的应用

1.1 目标函数及适应度函数

实际应用中，可能不会需要上述如此多的约束条件，比如只需要约束试卷的难度与题型分布，或者难度与知识点的分布等，对每一方面都做到完好的满足可能要花费很长的组卷时间，甚至组不出满足要求的试卷，这时需要在一定程度下放宽对组卷的约束要求。并且对于不同的约束条件，其容忍的误差也会有所不同。因此需要设定目标函数为：F=(X1,X2,...,Xn)。其中：X1为组卷需求中第i项约束条件取值变量；F为目标函数值，而X1,X2,...,Xn全部取到需求点时即为F的极值。适应度函数则由F的目标函数映射为非负、极大函数，以满足遗传算法中优胜劣汰的思想。

分析可以得出，如果组卷人指定了组卷的n个约束条件后，且约束条件相互独立，组卷算法中遗传算法的适应度函数就是一个n+1维单峰值最优化问题了。在n维度的自变量中，靠近要求的点的函数值越接近极值；再加上前面所要求的约束条件对函数值的贡献不同的因素则可以采用加权离差的方法来表示函数的自变量，则有：

式中：Wi表示第i项约束条件的权重，Wi与约束条件的重要性成正比，且满足;di为用户定义的第i项约束目标值；x为题库内试题选取。

目标函数为：

对于多点的复合条件，如题型设定与知识点设定，则选取分条件值。也可以通过分段编码来更高效地实现其中之一。对于遗传算法来说，将目标函数反转取得适应度函数的方法有：

在这种情况下，cmax存在多种选择方法，它可以是一个合适的输入值，也可以采用迄今为止进化过程中g(x)的最大值，但cmax最好与群体无关。由于参数cmax需事先预估，不可能精确，其结果常常使适应度函数不灵敏；但优点是计算量小，运算简单，线性函数也保证了收敛的规则性，在二维约束条件下其适应度函数为：

在这种情况下，适应值函数由于在极值附近高速上升，在轮盘赌的选择条件下收敛速度会大幅上升，但若速度过快的话也会导致早熟现象。

1.2 编码设计

用遗传算法进行求解问题时，必须在目标问题实际表示与遗传算法染色体结构之间建立联系，即确定编码和解码运算。在组卷系统中，二进制编码方式是以长度为N的二进制串表示选择题目数，N为题库中试题数量，二进制串中1的个数和为n，即组卷试题数量。

针对二进制编码的不足，本文采用实数编码、题型分割的编码方式进行个体组建。这种编码方式见图1。

这种编码方式中应注意的是在同一编码段即同一题型内不应出现重复试题。而对于小规模题库来说由于遗传算法的随机选择性，取得重复试题的概率会变大，去重的工作也会加大，故而实数编码比较适用于大规模试题库抽取试题量相对较小试卷的组卷情况。

1.3 组卷体系结构

如图2所示，组卷的体系结构要求抽象出组卷和遗传算法两种接口。图中：Assemble接口是组卷接口抽象出进行组卷和取得试题的方法；Generable是适应度接口，抽象出测试函数评估方法；Generation是遗传算法接口，抽象出遗传算法过程；Individual是遗传算法个体类。这种设计方法的好处是：

(1）抽象出组卷接口，其他模块可以直接关心接口方法而不必担心内部实现。

(2）通过适应度计算接口将遗传算法与组卷模块分离化。

(3）遗传算法接口的不同实现可以完成不同编码方式、不同进化方式甚至遗传算法防早熟优化措施的实现类共存和对比，使组卷模块做到可扩展且易使用，同时，对算法的对比研究也提供了良好的平台。

2 组卷系统中的遗传算法研究

2.1 早熟现象的克服方法

遗传算法过程中种群在选择算子的作用下，优秀模式大量增加，低劣模式会迅速减少，整个群体向好的方向进化，但是在选择算子的作用下，群体丧失了多样性[5]，群体进化中后期导致优秀个体的缺失即早熟现象。

本文以小生境算法为基础策略进行早熟现象的克服。基于这种小生境的遗传算法，可以更好地保持解的多样性，同时具有很高的全局寻优能力和收敛速度，特别适合于复杂多峰函数的优化问题[6]。

它的实现方法是：首先两两比较种群中个体之间的海明距离，如果个体间距离在指定的距离L内，即两个个体具有一定的相似程度[7]；则再比较二者的适应度大小，并对适应度低的个体增加惩罚值，使其适应度大大降低。以此保证种群空间内L距离内的个体只有一个适应度较高的个体更具有竞争性，而那些适应度较低的且受到惩罚的再选择过程中就极容易被淘汰。在种群空间中，优秀的个体距离会大于L，这样便保证了种群的多样性。

2.2 文本相似度计算方法

组卷过程中的另一个重要问题是组卷过程中出现重复性或相似性试题的问题。研究中尝试利用基础向量检索模型进行研究，使时间效率和算法复杂度都做到最简单。

定义在向量模型中，二元组(ki,dj)的权重Wi,j为非二元正数。并且，在查询语句中的索引词也赋予权重。令Wi,q为二元组(ki,q)的权重，其中。之后，查询向量定义为q=(W1,a,W2,a,...,Wt,a)。其中t为系统中索引词的总数量。文档dj的向量定义为：

因此，文档dj与查询语句q可以被表示为t维空间向量。向量模型根据向量之间的关系来判断文档dj与查询语句间的相似度。而这种关系通常也可以被定量地表示出来。

判断两文档的相似度可以通过将两文档的向量数量积相乘并除以两向量模得到向量余弦值，从而判断向量夹角。余弦值越大说明向量夹角越小，向量代表的文档越相似。进一步，判断整个文档集A也可以通过对特征词矩阵与其转置矩阵数量积相乘并除以对应行内向量模来得到整个文档内的相似度矩阵。

文档特征向量的构造整体流程如图3所示。

为了提高组卷时间效率，暂不考虑引入分词算法，而是直接切字分析。这里只面对分解完毕的特征词词组，并按照向量模型对特征词词组进行相似性比较。之后，利用停用词表，将考试中可能会频繁出现的词语过滤，其中包括助词、连词以及本次考试涉及到的知识点的常用词语。

在特征词抽取后，即可以将试题文本建立向量模型，利用相似性公式将抽取的试题进行相似性比较，两文本特征向量内容如图4所示。

如图4所示，Sym为特征词编码，W表示特征词在向量中的权重。设定每个向量各一个指针，判断两指针位置的特征词编码大小，小的特征词指针向后移动，若两个指针对应特征词相同，则进行权值相乘并累加，如图中所示i指针将向后移动，之后i,j指针所指特征字编码相等则相乘。当一个特征向量指到向量尾部时，向量乘法结束，分别除以两向量的模。

2.3 文本相似度控制

设计相似性检索调整组卷模型如下：

(1）适应度满足要求，产生试卷S。

(2）设定检测池P（线性表），令P=S中的所有试题。

(3）对P中试题进行两两重复检测和相似性检测，记录试题i在此试卷中的几何平均相似度，其中P为测试池中试题数量，并对重复试题进行标记。若无重复试题，跳转到步骤（6）；清空池P；对标记的试题和平均相似度高于设定阈值Simi>T1的试题集T′进行步骤（4），若所有试题都已执行完，重复步骤（3）。

(4）对T′中试题t，从试题库中查询试题m，要求试题m的约束条件与试题t相同。

(5）分析m与t的相似度Simmt，若相似度小于阈值|Simmt|<T2，将m加入池P，从T′中删去t，转到步骤（4）。

(6）若P≠S，跳转到步骤（2）；否则结束。

改进的组卷算法流程如图5所示。

3 结果分析与系统实现

3.1 实验结果分析

首先对比一般随机算法与遗传算法的收敛情况，测试实例中题库有400道试题，具有难度、区分度和认知程度的三项定量约束指标，定性其范围均为1～5，从中根据策略抽取10道试题，使试题参数的算术平均值满足约束条件。表1给出了基本遗传算法运行100次的平均命中代数与理论上随机抽取的速度对比。

由于遗传算法具有并行性，每代种群中设定为40个个体，即可以认为每代遗传算法测试了40次，这样也可以看出其收敛的速度。

小生境算法的收敛性适用于多峰值函数，以ShufferF6函数进行测试，其为减函数并最佳收敛于(x,y,z)的（0,0,-0.5）点，通过种群数量为400，交叉概率为0.7，变异概率为0.05的遗传计算1 000次，若进化100代仍未能抽取到（0,0）点则算法不能收敛，选取x,y值范围[-5,5]，分析排挤机制的小生境算法的平均收敛性，如表2所示。

经过计算分析，小生境排挤算法能极大地增强全局收敛的能力，并且在一定程度上提高算法的收敛速度。在组卷的实际应用中，多峰值的函数主要出现在诸如知识点分布以及不同多认知水平设计上，但更多情况是单峰适应度函数；在这种情况下还是需要对适应度，种群及其他遗传算子进行控制来避免早熟。

针对相似度算法，抽取试题库中的试题进行相似度计算，并对改进的组卷算法进行时间计算，分析平均时间[8]。经过计算，相似度算法模块能够比较有效地查询出文字上相似的试题，并加以排除。

对算法时间效率进行检测，测试用例为500道试题库中，利用交叉概率为0.7，变异概率为0.05，种群规模为400，适应度函数为线性函数的遗传算法，从中抽取10,20,40,100道试题组装试卷的时间模型，测试机器参数为：Core2 2.26,2 GB RAM，每组测试50次，并计算平均时间，融入相似性计算后的组卷算法时间效率见图6。

从图6中可以看出，在抽取试题较少时，相似性试题检测基本不会占用组卷时间，随着试题抽取量的上升，相似度检测会耗费较多的时间，但是仍不会占用大量时间。

3.2 系统实现

依照实际应用，采用B/S方式，利用Struts,Hibernate框架进行Web搭建，完成试题、试卷的管理，考试信息的管理，资源共享处理功能，组卷功能的实现以及安全策略的实现[9]。根据J2EE架构方案，设计四层架构模式进行实现，自下而上分别是Database,Dao/Model，业务逻辑层和表示层。利用MVC架构进行数据控制。利用工厂模式设计数据库访问接口，利用不同方式实现多种数据库的访问。同时，本系统利用QTI统一测试标准，搭建模块式设计，使与学习系统的其他部分松耦合、接口化，从而使考试部分能够高效地为学习者服务，提供标准化、科学化的考试服务平台。

4 结论

本文从现有的智能组卷技术出发，分析了组卷过程中涉及的经典测试理论和项目反应理论的信息参数和评价参数。利用小生境排挤机制和调整遗传算子的办法避免了组卷算法中早熟现象的发生。建立了向量空间查询模型，并对研究结果进行了实验对比和分析，最终依照实际应用，建立了一套高效的、智能的、符合用户测试需求的组卷系统。分析实验结果表明，利用文本相似度改进遗传算法实现的组卷系统具有较高的实用价值。随着人工智能与语言技术的进步，更为准确、高效的文本分析将会被应用于组卷算法中，从而产生更为人性化的测试试卷。这也将成为本课题下一步的研究重点。

参考文献

[1]周国文.基于XML的试题库自动组卷系统[D].长春:吉林大学,2013.

[2]王一萍,曲伟建,潘海珠.一种基于粒子群优化的组卷算法[J].兵工自动化,2009,28(2):39-42.

[3]田涛.在线考试系统设计与实现[D].成都:电子科技大学,2013.

[4]边霞,米良.遗传算法理论及其应用研究进展[J].计算机应用研究,2010,27(7):2425-2429.

[5]郭小磊.基于自适应遗传算法的组卷系统的设计与实现[J].电脑开发与应用,2010,23(8):67-68.

[6]华洁,崔杜武.基于个体优化的自适应小生境遗传算法[J].计算机工程,2010,36(1):194-196.

[7]齐畅,王冬霞,韩颖.多种遗传算法在函数优化方面的性能比较分析[J].辽宁工业大学学报(自然科学版),2013,33(5):290-293.

[8]王旭阳,万里.信息检索中语义相似度算法研究[J].计算机工程与应用,2012,50(10):124-127.

组卷算法研究与实现 篇3

基于B/S模式的在线考试系统主要完成用户的登录及验证、自动组卷、学生在线考试、评分和成绩查询功能。组卷是指从试题库中按给定的抽题策略,如知识面覆盖度、试卷的难易度、试卷的信度和区分度等参数,抽取试题组成试卷的过程,组卷既要满足给定的题型要求,又要使试卷中各试题的难度分配满足试卷的平均难度,同时又使试卷中的知识点不重复。本文就在线考试系统的组卷采用遗传算法用C#.NET进行程序设计,以实现自动组卷功能。

1 遗传算法概述

1.1 遗传算法

遗传算法提供一种求解复杂系统优化问题的通用框架,具有很强的通用性,被广泛应用于很多学科。用遗传算法解决问题时,首先要实现从表现型到基础因型的映射编码,产生一个可代表问题的初始种群。这个初始种群是由带有特征染色体的若干个体组成,染色体作为遗传物质的主要载体,决定了个体的形状的外部表现。在初始种群产生之后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来越好的近似解。根据每一代问题域中个体的适应度值挑选个体,并借助于遗传算子进行组合交叉和变异,产生出新的种群。像自然进化一样,整个过程中,后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码,即可作为问题近似最优解[1]。

自动组卷是根据出卷者给定的约束条件包括试题总数量、总分、知识点分布、难度系数、题型比例等因素,搜索试题库中与特征参数相匹配的试题,从而抽取最优的试题组合。由此可见,自动组卷问题是一个具有多重约束的组合优化问题。

1.2 遗传算法特点

(1)遗传算法是从问题解的串集开始嫂索,覆盖面大,利于全局择优;

(2)遗传算法同时处理群体中的多个个体,减少了陷入局部最优解的风险,易于实现并行化;

(3)遗传算法采用适应度函数值来评估个体,在此基础上进行遗传操作,由于适应度函数不受连续可微的约束,且其定义域可以任意设定,因此大大扩展了遗传算法的使用范围;

(4)遗传算法采用概率的变迁规则来指导它的搜索方向;利用进化过程获得的信息自行组织搜索时,适应度大的个体具有较高的生存概率,并获得更适应环境的基因结构[2]。

2 遗传算法设计

2.1 遗传算法流程框图

遗传组卷算法实施流程如图1所示。

2.2 遗传算法的基本操作

(1)初始化:设置进化代数计数器,设置最大进化代数,随机生成N个个体作为初始种群;

(2)计算适应度:计算初始种群中每个体的适应度;

(3)选择:根据个体适应度,把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代,可采用的算法有:轮盘赌选择、随机遍历抽样、局部选择、截断选择、锦标赛选择等;

(4)交叉:是结合父代交配种群中的信息产生新的个体,依据个体编码表示方法的不同,可采用的算法有:实值重组、离散重组、线性重组;二进制交叉、单点交叉、多点交叉、均匀交叉等;

(5)变异:交叉之后子代经历的变异,实际上是子代基因按小概率扰动产生的基因值的变化,依据个体编码表示方法的不同,有实值变异和二进制变异等算法。

3 组卷遗传算法程序设计

3.1 产生初始种群

(1)定义种群个体实体类Inherit,包含编号、适应度、题数、总分、难度系数、知识点分布、包含的题目等信息。

(2)按个体数量,期望试卷知识点分布以及各类型题目数等条件产生初始种群:

3.2 计算种群个体的适应度

(1)计算知识点覆盖率

种群个体的知识点覆盖率用一个个体知识点的覆盖率来衡量,例如期望本试卷包含N个知识点,而一个个体中所有题目知识点的并集中包含M个(M<=N),则知识点的覆盖率为M/N,程序部分代码如下:

(2)确定种群适应度的公式为:f=1-(1-M/N)*f1-|EP-P|*f2,其中M/N为知识点覆盖率,EP为期望难度系数,P为种群个体难度系数,f1为知识点分布的权重,f2为难度系数所占权重。当f1=0时则只限制试题难度系数,当f2=0时则只限制知识点分布,实现代码如下:

3.3 选择算子

选择算子采用轮盘赌选择法,即适应度越大的被选择到的概率越大。比如说种群中有20个个体,那么每个个体的适应度除以20个个体适应度的和得到的就是该个体的被选择的概率。轮盘赌选择时,每个个体类似于轮盘中的一小块扇形,扇形的大小与该个体被选择的概率成正比,则扇形越大的个体被选择的概率越大,算法实现代码如下:

3.4 交叉算子

交叉算子是把多点交叉改为单点交叉,在交叉过程中既要保证总分不变,又要保证交叉后没有重复个体,算法实现如下:

3.5 变异算子

在变异过程中应保证替换题目至少包含一个被替换题的有效知识点,期望试卷中包含此知识点,并要类型相同,分数相同而题号不同,算法实现代码如下:

3.6 调用示例

设置初始种群大小为30,最大迭代次数为500,适应度为0.96,选择算子选择次数为10次,交叉算子产生的个体数量为20,期望试卷难度系数为0.70,总分为100分,各种题型题数为:单选20个、多选5个、判断10个、填空10个、问答5个,包含的知识点为:1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,则代码如下:

4 结语

以上遗传组卷算法代码程序是在Visual Studio 2008中,利用C#程序设计语言[3],通过建立一个WinForm应用程序,在窗体文件中设计并完成调试和运行,达到预期的组卷要求和目标。如需要应用到在线考试系统中,需要对程序作进一步的改进和完善。

摘要：组卷是在线考试系统中的一个重要环节,而组卷性能的优劣主要取决于组卷算法,将遗传算法应用于组卷中,使组卷的成功率和收敛速度都得到明显提高,不仅适合于较大型题库系统,而且也能满足复杂条件的组卷要求。利用C#.NET的类程序设计遗传组卷算法,既利于系统的模块化设计又利于组卷算法功能的优化和改进。

关键词：在线考试,遗传算法,适应度,交叉算子,变异算子

参考文献

[1]邵峰晶,于忠清.数据挖掘原理与算法[M].北京:中国水利水电出版社,2003.6.

[2]毛国君.数据挖掘原理与算法[M].北京:清华大学出版社,2009.6.

自动组卷算法分析与研究 篇4

传统的人工出卷, 教师可以根据考试命题双向细目表完成试卷编制;如果需要多份试卷的情况时, 即构建平行试卷, 显然传统试卷的组卷方法不适合。教师在多年的教学活动中积累了大量的试题, 在计算机技术的帮助下, 可以更加合理有效的使用它们, 将这些题目存入题库, 采用计算机程序自动试卷编制已经成为可能。

自动组卷算法要求适应测试的多种约束条件, 从题库中高效快速的组成多份彼此等值的试卷。常见的约束条件有统计学约束和非计量学目标, 统计学约束有区分度、难度、测量精度等, 非计量学目标有内容和题型分布、时间控制、敌对题的检测等等。研究者们对自动组卷算法进行了很多深入研究, 本文对若干组卷算法进行整理与分析, 为实际应用中如何选择合适的算法进行智能组卷提供一些建议。

1 简单易用的组卷算法

1.1 穷举算法

对某个题库中的试题进行排列组合, 产生个元组, 接着对每一个元组逐一根据组卷的约束条件验证, 全部满足就说明该元组满足该组卷所有约束条件, 即该套试卷可用, 只要有一个约束条件不满足就表示该套试卷不可用, 直到全部情况验证完毕。在有限的试题库中逐一地检验、挑选, 最终可基本组成满足所给条件的试卷。

显然, 穷举算法[1]的思路简单、实现简单。但是计算机组卷的试题库是非常大的, 利用穷举法需要对所有试题的排列组合加以检测, 其计算量非常大。其次, 穷举算法进行组卷效率不高, 穷举范围太大, 在时间上难以承受。

1.2 随机组卷算法

随机组卷算法[2]借助随机函数从试题库中提取试题, 在计算机自动组卷的过程中根据约束集的各项指标分量, 从试题库中随机挑选一个试题, 检验该试题是否满足当前的指标约束。若满足指标约束, 则将该试题放入当前的试卷中, 同时修改相应的约束条件的指标;若不满足则检验下一个题目进行新的判断。当所有的试题都经过试探但不能满足所给约束条件时, 则表明整个组卷过程失败。

随机组卷算法有着结构简单、就单次组卷过程而言运行速度较快的特点, 但是由于随机性强, 试题的重复率高, 组卷质量难以得到保证。李目海 (2007) 在随机算法上做了深入的研究改进[3], 给出了—个通用的多条件下组合多份试卷的随机抽取算法, 较好的解决了试题库组卷过程中重复试选及组卷不确定性等问题, 解决了备选题目大于要选试题的情况。

1.3 回溯试探组卷算法

回溯试探法[4]是以深度优先的方式求解的算法。在使用回溯试探算法组卷过程中, 首先根据试卷的约束条件采用随机算法在题库中抽取试题, 随时根据约束条件对选取的试题进行取舍, 若选取的题目不能够满足给定的约束条件就往前回溯, 重新选取新的题目来打破僵局。

回溯试探算法优于随机抽取法, 采用回溯试探算法进行组卷能够在一定程度上避免随机抽取法的盲目性。在题库数量和试卷需求量较少的情况下组卷, 效率会比较高。但是如果题库大, 在组卷过程中回溯试探算法会遍历每一种可能的状态组合, 在组卷过程中时间开销非常大。回溯试探法比较容易陷入死循环, 采用回溯试探法的组卷会对系统的性能造成一定影响。

2 基于软计算的组卷算法

2.1 遗传组卷算法

遗传算法 (Genetic Algorithm, 简称GA) 是模拟达尔文的遗传选择、自然淘汰的生物进化过程的计算模型[5]。这种算法的组卷方法对试题库中的每个试题进行了编码, 即进行种群的初始化。然后, 再对初始化后种群的试题调用适应度函数进行优劣的评估。其次, 对该种群中所有试题进行遗传操作, 如选择、交叉和变异等, 最终留下来的试题继续生存, 即产生新一代的试题群体。对新的试题群体再进行初始化……重复上述步骤, 直到挑选出满足试卷所有约束条件的试题或者到达算法终止的条件为止, 此时一套试卷完整组卷[6]。

遗传算法自动组卷的成功率和速度都得到了明显的提高, 但涉及到大量个体得到计算、问题复杂度较高时, 计算时间是一个问题。目前针对维数较低的问题, 能够得出的解较好, 但是在进化后搜索效率低的缺点也一定程度上制约了自动组卷的效果。

2.2 蚁群组卷算法

1991年, 蚁群算法是由意大利学者M.Dorigo等人通过模拟蚁群觅食行为提出的一种算法。蚁群算法通过对蚂蚁群落寻找食物过程的模拟, 在组合最优化问题中体现出优良的特性[7]。在作业调度问题、旅行商问题等方面都有了广泛的应用, 并且取得了比较好的仿真效果[8]。蚁群算法的基本原理就是正反馈机制, 即在一条 (最优) 路径上蚂蚁数量增加, 导致信息素强度增加, 蚂蚁选择该路径的概率增大, 该条路径上蚂蚁数量更多, 最终这条路径收敛, 产生最优路径解。在计算机组卷当中, 每只蚂蚁都在试题库中从一个试题向另一个试题移动, 当蚁群中的每一只蚂蚁都找到一条路径时, 就对应形成了一套试卷。

蚁群算法具有易产生局部最优、收敛速度慢的缺点。由于蚁群算法中的初始信息素比较少, 一般搜索时间较长, 在复杂度方面能反映这一点;况且这一种方法容易导致停滞, 即在搜索到一定程度后, 会发现所有的个体得到的解完全统一, 会对解空间停止搜索, 不利于发现更好的解。

2.3 基于粒子群优化算法

粒子群优化算法[9] (Particle Swarm Optimization, 简称PSO) 的组卷方法是一种基于迭代的搜索算法, 对鸟群觅食的行为研究产生了此类算法。在粒子群算法中, 首先采取随机法在题库中随机抽取出若干套试卷, 完成粒子群的初始化, 其中每一个粒子就代表了一套试卷。其次, 再采用适应度函数来计算每一个粒子的值, 同时进行判断其是否满足试卷的约束条件。若不满足试卷的约束条件, 则通过迭代的方法进行一定次数的迭代来找到最优解, 即找到符合条件的试卷。

对于计算机组卷具有多种约束条件的问题, 运用粒子群优化算法进行组卷有一定难度并且效果不是很好, 通常可以通过添加选择机制、改进编码方式等方式进行改进。

3 基于测验理论的组卷算法

3.1 线性规划离差加权模型组卷算法

离差加权模型[10] (WDM模型) 是Len Swanson&Martha L.Stocking提出的, 并在教育测量领域中灵活运用的一种计算模型。在计算机组卷中, 并非每个约束条件都能够完全满足, 于是希望最后对约束条件满足的总量最大, 对于所有约束条件无疑会有不同的权重, 有些约束条件可以适当的放松;再加上组卷者在自动组卷后对试卷的审查和微调, 可以使组卷结果达到一个比较好的结果, 这也是离差加权的核心思想。离差加权模型给每一个约束条件设置了上限和下限 (见图一) , 把约束条件的一个固定值拓展成为一个合理的区间 (若约束条件一定要等于一个固定值时, 区间退化成一个点) , 如果所得到的结果分布在这个区间内, 则认为满足约束条件, 根据约束条件的权重比值, 约束条件区间的宽度也随之不同。

在离差加权算法中, 将组卷的要求 (包括计量学的和非计量学的要求) 有机统一在线性规划中的目标函数与约束条件下, 转换成的0~1整数规划问题更形象化更易于组卷算法的实现。但是, 此模型严格控制了试题的数目, 对试卷的总分允许有偏差, 而且在所设置的约束条件中有试题的分值、试题的信息量和试题的数目, 由于各个约束条件的单位不同, 给后面计算比较带来一定的难度。漆书青 (1999) 等人对该问题进行了比较好的分析与解决, 其将WDM模型进行了修改, 分成了两步来解:第一步, 满足试卷总分、题型、内容等非计量学指标的约束条件进行组卷;第二步, 在第一步的基础上把已经选出的试题用题型、内容等计量学指标相同但信息量贡献大的试题替换。

3.2 最大优先级指标方法 (MPI)

最大优先级指标的组卷方法基于项目反应理论下最大信息量选题的改进策略。项目反应理论 (IRT) [11]是针对经典测量理论的局限性提出的新的心理统计学模型, 它用概率函数的形式来描述项目作答反应结果是如何受到被试能力水平和项目特性联合作用的影响。最大信息量选题策略[12]根据被试者的当前能力的能力值选择全部被试剩余题库中信息量最大的试题给被试者作答, 该策略的测验效率非常高。

最大优先级指标方法 (MPI) [13]是由程莹提出来的一种2阶段选题策略, 在最大信息量选题策略中加入约束指标, 对每类约束条件的上下限进行充分的考虑。最大优先级指标方法基本上能够对内容和限制上的不平衡进行完善, 但在有时仍会出现越界的情况。潘奕娆等人[14]对其进行了更深入的研究, 获得了改进的MPI方法 (MMPI) 。

4 结束语

对于简单易用的组卷策略而言, 计算机模拟人工方式进行组卷, 从逐一选择到随机性组卷, 再到回溯组卷, 在一定程度上提高了组卷的效率和质量, 但是其收敛时间与组卷质量有待进一步提高。虽然计算机运算速度越来越快, 组卷的题库与约束条件也会随之变多与复杂, 一般的组卷策略已经不能满足现代的组卷趋势。

对于现代的计算机组卷策略来说, 在完全模拟人工组卷的基础上增加了更多精细算法使得组卷的质量更加高、效率更加高。不仅在题库数量上拓展了, 还在组卷的完整性上增强了, 自动化程度提高, 在组卷过程中涉及到的各个方面的约束条件能够更加合理地满足, 并且更加科学合理地避免了有些试题难, 导致部分试题的区分度接近于0, 或者试卷中全部是中等难度的题, 难度差异过小。

从简单易用的组卷算法到基于软计算的组卷算法, 再到现在的基于测验理论的组卷算法, 组卷算法在不断发展, 对组卷的要求也越来越高, 基于项目反应理论的组卷算法能够很好的适应算法的发展方向, 是自动组卷发展的新方向。

摘要：自动组卷算法要求适应测试的多种约束条件, 从题库中高效快速的组成多份彼此等值的试卷。常见的约束条件有统计学约束和非计量学目标, 统计学约束有区分度、难度、测量精度等, 非计量学目标有内容和题型分布、时间控制、“敌对题”的检测等等。本文分析一些常用的计算机自动组卷算法, 结合各算法的特点, 为实际应用中如何选择合适的算法进行智能组卷提供一些建议。

基于遗传算法的组卷研究与设计 篇5

常用的随机组卷算法虽然简单、快速, 但要求样本分布好, 且组卷效率低。回溯试探法是将随机组卷的各种试探记录, 通过回溯确定最优方案[1], 所以存在耗时、编程复杂且对内存占用较大等缺点。遗传算法是模拟自然界中生物进化与自然选择过程的计算模型, 因其简单、快速收敛、鲁棒性强等特点, 被越来越多地应用于解决组合优化、人工智能、自动控制、规划设计等领域。

遗传算法 (Genetic Algorithms, 简称GA) , JohnH.Holland受模拟生物遗传、变异和自然选择的生物进化过程的启发, 于1975年在专著《自然界和人工系统的适应性》提出GA计算模型[2,3,4,5], 实现各个体适应性的提高。GA搜索机制最优解的过程模拟生物遗传学和自然选择过程, 通过繁殖、交叉、基因突变, 按一定的条件选择一组候选解, 经多次迭代从解群中选取较优的个体解。遗传算法是基于“适者生存”的高度并行、随机和自适应优化算法, 是将求解过程表示成生物遗传进化中适者生存的过程。

1 遗传算法构成要素

遗传算法由编码、初始群体设定、适应度函数设计、遗传操作设计及控制参数设定5个基本要素组成。

(1) 编码。将问题的解抽象成编码, GA通过编码实现解空间到搜索空间的映射。

(2) 初始种群。随机产生一个由若干初始解组成的样本群体用于繁殖。

(3) 适应度函数。适应度函数用于评价所有个体解好坏, 适应度函数值越大, 解的质量越好, 它是GA算法中进化过程的驱动力, 是自然选择的标准。

(4) 遗传操作过程。 (1) 选择算子:遗传算法使用选择运算来实现对群体中的个体解进行优胜劣汰操作, 适应度高的个体被遗传到下一代群体中的概率大, 反之则被遗传到下一代群体中的概率小。选择操作就是按某种方法从父代解群体中选取适应度高的个体遗传到下一代, 从解群体中选择适应性较强的后代, 淘汰弱者; (2) 交叉算子:两个体解相互对应的染色体按照交叉概率Pc进行相互交换其部分基因, 从而形成两个新的个体解。基因组合的交叉运算使新的解群体能获得较好基因组合, 进而获得可能优于交叉前的个体解; (3) 变异算子:按概率Pm将对群体中的个体串的某些基因值用其它基因值来替换, 使得算法能维持群体的多样性, 增强对局部的随机搜索能力。交叉运算和变异运算相互配合, 共同完成对搜索空间的全局搜索和局部搜索。

(5) 控制参数选择。主要包括种群规模、执行迭代数、交叉概率、变异概率及其它辅助控制参数, 参数的选择直接影响算法的效率与效果。

2 组卷遗传算法设计

2.1 编码设计

本例采用按试题编号的分段整数编码方式, 每个试题的自然数代码直接作为遗传算法的染色体编码, 降低了编号复杂度。通过染色体中试题编号基因片段可检索到该题所有特征属性。试卷染色体结构和编号23试题对应各项属性分别如表1、表2所示。

2.2 适应度函数设计

适应度函数为:

被选试题的Fit_a是章节属性值, TC是选题要求的章节属性值, i代表第i个试题, N是目标试卷中要求的试题总数。a、b、c、d分别是章节、时间、题型、难度对应的权重系数, 用于放大被选题属性值和设置属性值的差。如:d取10时, 被选题难度值Fit_d为2, 难度设置值为4, 难分项为10*|2-4|=20。f是分各项偏差的绝对值加权, f的值越小试题就越接近指定要求。

2.3 参数设置

N:染色体位串长度, 即用户指定题目总数。

M:群体大小, 即群体中所含个体的数量, 本文以200为例。

T:遗传运算的终止进化代数, 以100为例。

Pc:交叉概率, 以0.5为例。

Pm:变异概率, 以0.05为例。

2.4 算法设计

S1:随机产生200个样本的初始种群。

S2:评价种群中每个个体的适应度值。

S3:判断是否满足收敛准则, 若满足则输出结果;否则向下执行。

S4:根据适度大小选择最优的样本。

S5:按Pc概率进行对位交叉。

S6:对交叉生成的样本进行概率为Pc的位变异。

S7:返回S3继续执行上述操作。

3 遗传算法组卷实现过程

遗传算法模拟自然生物遗传变异和自然选择的过程, 算法中通过交叉、变异, 经选择较优解的多次迭代直到满足某种收敛指标从而选取解群中较优的个体。遗传算法的运行是一个典型的迭代过程。

3.1 生成初始种群

利用函数随机生成n (试题总数) 以内的随机数, 存放于二维数组gene[10, N]中构成含有N染色体的10个基因初始种群。

3.2 生成交配池

交配池用于存放第n代种群进行交配的母本, 通过适应度函数计算各染色体的适应值, 按照轮盘赌算法按遗传性与选中概率成正比的方式选择个体到交配池进行繁殖。设群体大小为n, 个体i的适应度为fi, 则个体i被选中遗传到下一代群体的概率为:

个体被选中的概率与其适应度函数值大小成正比, 使得优秀“基因”被遗传到下一代的可能性增大, 确保优化的正向性, 同时适度值小的“基因”也可以较小的概率参与繁殖, 避免经多次迭代后“基因”的单一性。

3.3 交叉

对交配池中轮盘赌算法选出的200个较好个体进行交叉。交叉时位按概率Pc进行交换, 产生200个子代个体。部分基因交换后可能产生具有较好基因组合优于交叉前的个体解析。交叉前和交叉后的情况分别如表3、表4所示。

3.4 变异

按照每位1%的概率进行变异, 变异取[1, …, N] (N为题目总数) 之间的随机整数。第n代样本通过杂交和变异生成第n+1代样本。变异前和变异后的情况分别如表5、表6所示。

3.5 竞争与终止

经过交叉和变异后产生了200个子代个体, 再和200个父本个体一起比较适应值竞争, 从而选择出200个遗传性状最好的个体。若经历i代后, 所有个体都还未满足设定要求, 要继续产生+1代的交配池再进行交叉和变异迭代。当样本中的某个体适应值达期望值或迭代次数达到设定值时, 则选择最优样本终止运算。

4 算法设计应考虑的因素

遗传算法的核心是选择、交叉和变异。常用变异算子有基本变异、正态变异、均匀变异等, 变异算子使得算法具有对解的局部搜索能力。若变异概率太小, 交叉迭代多次后样本的适应值基本不再变化, 使得样本易早熟收敛;若变异概率太大, 则算法将退化成随机搜索。

本例采用按试题编号的分段整数编码方式, 由于试题库中的试题可能进行增、删操作, 为避免样本的取值空间不连, 应使试题编号增、删仍然连续。如:编号80的试题已被删, 在生成初始种群或变异时可能选中本题而造成无效。为了避免上述情况可以通过以下方法解决:删除某试题时将题库尾部记录取代被删记录, 从而保证算法对试题编号连续性的要求。样本Fn如表7所示。

初始种群是通过对试题编号样本空间[1, N]随机取值得到的, 变异时也是通过对样本空间[1, N]随机取值得到的, 可能存在染色体重复出现的情况, 交叉时两个样本也可能包含相同的基因片段, 使得Fn+1代中出现试题重复。考卷中重复出现同一试题毫无意义, 可通过函数遍历数组防止出现重复样本。

5 结语

人们对组卷的要求越来越高, 在自动组卷过程中, 如何生成满足用户需求并具有随机性、合理性的试卷, 是近年来人们研究的一个热点。智能组卷的效率和质量完全取决于抽题算法的设计, 随着遗传算法在多个领域的应用, 遗传算法也出现了很多的改进型[6,7,8]。为了提高搜索效率和避免早熟收敛, 可对算法进行适当改进, 主要根据不同的需求调整选择、交叉及变异等算子, 也可通过与其它算法结合的方式取长补短。在具体的设计需求下如何设计算法、选择参数, 还需要对实际组卷的效果进行对比与分析。

参考文献

[1]徐立波.基于多目标约束数学模型的组卷算法研究[J].沈阳工程学院学报:自然科学版, 2012, 4 (5) :94-97.

[2]黄小明, 刘长安.改进遗传算法在自动组卷系统中的应用[J].科学技术与工程, 2010 (5) :23-24.

[3]周明, 孙树栋.遗传算法原理及应用[M].北京:国防工业出版社, 2002.

[4]张勤慧, 吴东洋.基于网格的在线考试系统的分析与研究[J].电脑知识与技术, 2012, 8 (7) :1537-1539.

[5]周艳丽.基于改进遗传算法的自动组卷问题研究[J].计算机仿真, 2010 (10) :41-42.

[6]李小勇.题库管理系统中的自动化组卷算法[J].西北师范大学学报:自然科学版, 2002 (4) :51.

[7]张赀, 王友仁.遗传算法在网络在线智能组卷中的应用研究[J].计算机测量与控制, 2005 (11) :67-68.

组卷算法研究与实现 篇6

关键词：智能组卷,遗传算法,题库

考试是教学活动中的重要环节,考试组卷是教师的一项重要工作。但是在教师组卷的过程中,存在着大量人力财力浪费的情况。近年来,随着教育事业的飞速发展,人工组卷考试的做法己很难满足现代教育教学的需要。因此,利用计算机及相关技术,通过建立结构合理的试题库,依据教师提出的要求,并按照一定的组卷策略进行自动组卷,可以克服人工出题的主观因素(如不能保证出题的科学性),节省资源,有利于教师把注意力集中到要实现的教学目标上来,真正关心学生的学习困难和错误所在,有利于提高教学水平和质量,促进教育教学技术的改革。

智能组卷系统的开发涉及到应用的具体算法和前台界面及后台数据库的设计和实现,本文以Access为后台数据库设计工具,介绍了一种基于遗传算法实现智能组卷的题库设计思路。

1 组卷问题描述

由组卷系统所生成的试卷必须符合考试学的基本原理,符合课程教学大纲的要求,同时还必须符合教师对本次考试的具体要求。对于组卷系统来说,上述三方面的要求是对命题试卷的一种模糊的约束,本组卷系统按照人工组卷的经验,将组卷要求中最重要的约束指标归纳为题型、知识点、难度、区分度、分值、答题时间等六个基本指标。假如一张试卷由m道试题组成,每道题存在以上六个属性,那么抽题组成的试卷就构成了如图1的一个m×6的矩阵。

其中m是试卷所包含的试题数,每一列对应组卷约束条件中的一个约束变量。矩阵的列元素分别满足用户对试卷的相关要求。所有这些指标都应与用户指定的要求相等或者误差最小。组卷要做的工作就是从这个矩阵空间构成所需的解,使解满足给定的约束条件,即满足在矩阵每列上提出的要求,比如知识点覆盖比例、难度约束等等。

2 智能组卷中遗传算法的思想

遗传算法GA(Genetic Algorithm)是模拟自然界生物进化机制的随机化搜索算法,是一种有效解决最优化问题的方法,由美国Michigan大学的J.HHolland于60年代提出,适用于处理传统搜索方法难于解决的复杂的组合优化问题。智能组卷问题本身是一个组合优化问题,使用遗传算法进行试题抽取操作,可以有效地优化搜索过程,加快组卷速度。

生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。与此相对应,遗传算法中最优解的搜索过程也模仿生物的这个进化过程,使用所谓的遗传算子作用于群体P(t)中进行选择、交叉和变异三种遗传操作,从而得到新一代群体P(t+1),具体算法的实现步骤有如下几点。

2.1 编码

编码是从表现型到基因型的映射。根据所求解问题的特点,确定一种将问题的解表示成字符串的编码方式。按照一定的编码方法和编码策略,科学、合理、准确地为每道试题进行编码是高效组卷的首要工作,完整的试题编码能大大提高组卷算法的效率和成功率。常见的遗传算法编码方式有二进制编码、实数编码、自然数编码等编码方式。其中,二进制编码应用最早、最广,当表示对象数据多时,它存在转换复杂、编码长度大、占用计算机内存多等问题。所以在确定编码方案时,笔者采用了整数(即题号)编码策略。

2.2 初始化

在算法执行的过程中,首次根据组卷要求从试题库中选出试题组成试卷染色体的过程被称为染色体初始化。这里的一个染色体就是由一张试卷的各试题组成,染色体初始种群往往是采用随机的方法产生。

2.3 评估染色体

任何一个染色体个体诞生后,我们都要看其对环境的适应度是否已经达到拟定的目标值,或者判断二者之间的差距是否已经达到最小,这个过程被称为评估。对于组卷问题而言,我们要选用合适的适应度函数来判断某试卷染色体是否已经满足用户的需求,如总分值是否达到要求,难易度是否合适,知识点覆盖率如何等。适应度函数将综合上述6个试题属性值来衡量,如果某一染色体的适应度函数值越大,就表示该染色体所代表的试卷越接近组卷目标。

2.4 选择

选择也可称之为“复制”,其目的是为了从当前群体中选出优良的个体,使它们有机会作为父代为下一代繁殖子孙。根据各个个体的适应度值,按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代群体中。

2.5 交叉

交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体,新个体组合了父辈个体的特性。将群体内的各个个体随机搭配成对,对每一个个体,以某个概率(称为交叉概率,Crossover Rate)交换它们之间的部分染色体。交叉体现了信息交换的思想。

2.6 变异

变异操作是以一定的概率随机选择一个个体,对于选中的个体改变其基因值,在组卷问题中就是删除掉该试题,以另一试题替代。同生物界一样,遗传算法中变异发生的概率很低。变异为新个体的产生提供了机会。

综上所述,遗传算法运算流程即是首先初始化染色体群体,其次,在不满足迭代结束条件的前提下对染色体进行评估、选择、交叉以及变异,进而生成新的优良的染色体群体。

3 数据库设计思路

基于上述遗传算法的思想,为了完现组卷过程中各染色体的适应性评估,必须在设计题库时将试题的各属性进行量化。因此,题库建设也是一项艰巨的系统工程,要解决好几个问题:1)题库的结构设计问题,包括题目的各属性值及度量标准的设置等。2)试题的收集与编制。为了使题库更加科学化、标准化,题库必须具有大量的、高质量的试题,而题目的来源主要有两个方面:一是收集正在大量使用的优秀试题,二是组织专家专门命题。3)确定各个试题的属性值。这一步是题库开发中极为重要的一步,因为以后试卷的生成主要依靠题目的这些属性值来确定选择哪些题目加入到试卷中。生成的试卷的质量在很大程度上取决于题库中各个试题指标的可靠性。其中问题1)、3)要在数据库设计中由开发者解决。

据前所述,要基于遗传算法实现自动组卷,第一步就是对染色体进行编码。在编码时,由于一个试题充当生物学当中染色体中一个基因的角色,致使试题库中试题记录越多,在自动组卷时其时间复杂度就越高,试题库中的属性越多,组卷的难度越高,以致效率就越低。基于这一考虑,在设计数据库时,要一方面尽可能减少试题库中对应的试题记录的数量,另一方面,在满足科学组卷需要的前提下,以教育学理论为指导,合理地控制试题属性的数量。具体思路有如下几点。

3.1 主要约束指标的数据实现

根据遗传算法的特点,本组卷系统设置了六个组卷约束指标,要在组卷时由用户提出,其中题型指标采用分表保存的办法,其余五个约束指标要分别进行数据量化,并建立数据表进行管理,同时要与试题表建立参照关系。难度属性分为四个档次:容易、中等、较难、难;区分度属性分为三个档次:低、中、高;知识点属性规定分为8个点,由具有丰富经验的任课教师来划分;分值属性分六个档次:1分(单选题)、2分(填空题或判断题)、3分(多选题)、5分(改错题)、10分(综合题)、15(综合题),其中综合题允许有两个档次分值。

3.2 试题表的属性结构

题型一般有单选题、多选题、填空题、判断题、综合题等。如果所有试题放在一个数据表中,在搜索时必然带来很大的困难,增加算法的复杂度,同时还需要增加“试题类型”属性。所以在确定编码方案时,笔者采用了分段的整数编码策略。每一段编码反映一种题型,各个题型各自进行整数编码,题型组之间的编码是独立的,也分别运用遗传算法求出最优解。分开处理有利于减少属性,进而提高算法的执行效率。

尽管采用的是各种题型在试题库中分别保存的方式,其实各表的结构是完全相同的,如表1是试题的属性表。

其中:

ID属性为主码属性,兼有题号的功能,由系统自动生成,最大值表示本题型的题目数,且随题目的录入自动增加。

QuestionTypes为试题类型,用于与试题类型总表建立关联。

Subject为试题的问题描述。

Knowledge表示试题内容所属的知识点,建库之前要由课任教师根据教学大纲将课程内容划分为几个知识点,在课程知识分布表中明确,便于出题教师选择。本题库规定课程有八个知识点。

Difficult为难度系数属性,难度系数反映试题的难易程序的指标。在试题库建设的初期,由出题教师根据经验设置,以后可以根据实际测试情况逐步修正。本题库试题的难度系数分为4个级别。在具体的实现界面中,用户只需要在“简单”、“一般”,“较难”,“难”中选择,系统会自动取其所对应的具体数据。

Distinction为区分度:根据测量学理论,对于一道试题,如果Q>=0.3认为区分度比较好,Q值太小时,表明该题太易或太难,此时这道题已无法区分考生的水平。严格来说,区分度应该通过测试后才得到,但对每题进行实测存在技术困难,而且实测的信度难以保证,因此,类似难度指标,我们采用预先给定经验值,在实际的环境中可进一步精确。本题库的区分度分三个档次。

Score为建议分值,表示本试题在一份标准试卷上所占的分数值。这里所说的标准试卷应符合下述三条要求:1)考试时间为120分钟;2)试卷的满分值为100分;3)用于学期结束评定学生成绩的考试(总结性考试)。根据常用的五种题型,本组卷系统在用户输入试题界面规定可采用的相应分值。

Time为学生解答该题所需的时间(分钟)的预估值,包括了下面三个时间之和:读题、审题所需的时间,进行解答书写的时间,可能的检查时间等。

3.3 数据库关系设计

将组卷系统涉及到的所有参数进行说明和量化后,可以用数据表表示和存放,通过Access建立表间关联关系。关系设计主要的功能是保持数据的完整性、一致性,减少数据冗余,提高应用程序的性能,有效地对数据库中的数据进行增加、删除、更新等管理,使数据库中数据与现实世界中的应用需求保持一致。如图2是一种题型与各约束指标数据表建立的关系。

由于试题已经过分类处理,所以在组卷时,必然要根据试题类型分步实现试卷的生成。将各题型的最优解(即各题型试题)组合起来形成一份完整的试卷。

4 结束语

根据分析,该思路设计下的数据库与不经过任何处理的试题数据库相比,在用遗传算法实现自动组卷时效率可以提高大约一倍,达到了数据存储与算法有效结合的设计目的。

参考文献

[1]肖洋,王强,刘凤新.在线考试组卷算法研究[J].北京:北京化工大学学报,2006(4).

[2]雷英杰等.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005:11-31.

[3]王珊,萨师煊.数据库系统概论[M].北京:高等教育出版社,2006:84-113.

[4]Hoffer J A.现代数据管理[M].袁方,译.北京:电子工业出版社,2006:67-102.

组卷算法研究与实现 篇7

关键词：智能组卷,组卷模型,PSO算法

0、引言

在线考试已经成为一种流行的教学考核方式, 是检验学生学习情况的重要手段之一, 该考核方式式正逐步取代传统的纸质考核方式。组卷是在线考试系统的核心, 因为试卷的质量高低与对学生的评估有直接的关系, 本文将从智能组卷的要求出发, 利用PSO算法和组卷的数学模型, 从如何保证试卷最大程度的满足考试需求, 以及如何保证试卷的质量和组卷速度等角度对组卷策略进行研究。

1、智能组卷的数学模型

1.1 组卷问题的数学建模

组卷问题就是按照分数、题型、难度、知识点等要求从题库中抽取相应的试题组成一份试卷。因此, 题库中的试题至少应该有题号、题型、题分、知识点和难度五种种基本属性, 然后在这五种属性的基础上根据需要添加其它属性, 如答题时间、区分度等属性。

在本文中.使用m*n的目标矩阵表示试卷中的试题, 如式 (1-1) :

其中, m代表一份试卷中试题的数目, n代表试题属性种类, ai1表示第i题的题型, ai2表示第i题的题分, ai3表示第i题的知识点, ai4表示第i题的难度, 其中i∈ (1, m) , 该矩阵前四列为试题的基本属性, 其它属性可根据需要进行添加。

1.2 约束条件

约束条件 (1-2) 为总分约束, 其中G表示试卷总分, m表示题目总数, 要求被选中的试题的分数之和应该与试卷总分相同。

约束条件 (1-3) 为题型总分约束, 其中Tj代表第j种题型的题目总分, 要求第j种题型的题目总分等于Tj。

约束条件 (1-4) 为知识点约束, 其中Fk是第K类知识点的题分总和, 改约束要求第K类知识点的题分总和等于Fk。

约束条件 (1-5) 为难度约束, 其中Nl是第l等难度的题目的题分总和, 该约束条件要求第l等难度的试题的题分总和等于Nl。

2、PSO算法基本原理

在算法模型中, PSO模拟鸟群的捕食行为。一群鸟在随机搜索食物, 在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

基于PSO算法的独特搜索机制, PSO算法初始化随机生成一群粒子 (随机解) , 即确定粒子的初始位置和初始速度, 其中位置用于表示问题解。例如, d维空间中的第i个粒子的位置和速度可分别表示为Xi=[xi, 1, xi, 2, …, xi, d], Vi=[vi, 1, vi, 2, …, vi, d]。通过对每个粒子的目标函数进行评价, 确定t时刻每个粒子所经过的最佳位置 (pbest) Pi=[pi, 1, pi, 2, …, pi, d]和群体所发现的最佳位置 (gbest) Pg, 再按公式 (2-1) 和公式 (2-2) 分别更新各粒子的速度和位置。

其中, 学习因子C1和C2是非负常数;rand () 是介于区间[0, 1]之间的随机数;如果C1*rand () 远大于C2*rand () , 粒子将会更多地被自己曾搜索到的最优位置所吸引, 否则, 会被整个群体曾搜索到的最优位置吸引。w为惯性权重 (Inertia Weight) , 通过w, 可以协调粒子群的全局和局部寻优能力。

3、PSO算法的改进

由于基本的PSO算法精度低、易发散等原因往往出现早熟收敛或收敛缓慢等缺点, 因此, 设计PSO算法的参数以及操作, 应主要针对如何保证种群的多样性, 以提高算法精度, 从而提高算法的搜索效率, 避免早熟收敛现象。本文在前人研究成果的基础上, 借鉴文献关于混合算法和文献[10]改进惯性权重的思想, 设计了一种改进PSO算法。来平衡全局搜索能力和局部搜索能力, 提高收敛速度, 从而减少获得最优解所需的运行代数。

3.1 结合模拟退火算法

模拟退火 (Simulated Annealing, SA) 算法是1982年由Kirkpatriek等人提出的一种随机优化方法, 它模拟了物理中金属的降温过程。由于它具有很强的全局搜索能力, 在搜索中具有概率突跳的能力, 所以对搜索非劣解集非常有利, 能够有效避免搜索陷入局部极小解。

由于在公式 (2-1) 中, 所有的粒子都将趋向于局部极小解, 从而导致搜索的分散性变差, 使得全局探索能力减弱。所以, 为了使算法在运行过程中, 尽可能少的陷入局部极小解, 本文将从Pi中选取一个位置, 记作NewPg, 来代替更新公式中的Pg。改进后的更新公式如公式 (3-1) 所示。

为了性能好的Pi有较高的概率被选中, 借用SA算法的机制, 认为Pi是Pg差的特殊解, 从而可计算问题t时Pi相对Pg的突跳概率f为目标函数值, 然后将此突跳概率值当做Pi的适配值, 则Pi代替Pg的概率公式如公式 (3-2) 所示。

公式 (3-2) 中的N为种群大小。然后, 根据上述替代概率, 采用轮盘赌策略随机确定哪个Pi将成为NewPg。

3.2 惯性权重参数的修改

在PSO算法的参数中, 惯性权重w用来调整全局和局部搜索的能力。w大的, 容易实现全局搜索, w小的, 有利于局部搜索。为了既能在进化初期得到大的搜索空间避免陷入局部最优, 又能在进化后期进行更精细的搜索以加快收敛速度, 需用公式 (3-3) 不断更新惯性权重参数w:

其中:iter为当前迭代次数, itermax为最大迭代次数, wini为初始惯性权重值, wend为运行至最大迭代次数时的惯性权重值。

3.3 改进后的粒子群算法

改进后的PSO算法的步骤:

(1) 在需要求解的问题的解空间中, 初始化一个粒子群, 即随机产生各粒子的初始位置和速度;

(2) 根据目标函数计算每个粒子对应的“适应值”, 用以衡量粒子在该位置所达到的优化程度;

(3) 令各粒子的自身最佳位置Pi及其适应值为当前位置及其适应值, 令群体最佳位置Pg及其适应值为所有Pi中的最佳位置及其适应值;

(4) 确定初始温度;

(5) 根据公式 (3-2) 确定当前温度下各Pi的适配值;

(6) 采用轮盘赌策略从所有Pi中确定NPg, 然后根据公式 (3-1) 和 (2-2) 更新各粒子的速度和位置;

(7) 计算各粒子新位置对应的适应值;

(8) 更新各粒子的Pi及其适应值, 更新群体的Pg及其目标值;

(9) 根据公式 (3-3) 计算出惯性权重;

(10) 退温操作;

(11) 如达到迭代终止条件 (通常为一个预设的最大迭代代数) , 则程序终止输出Pg及其适应值, 否则返回 (5) 进行新一轮迭代。

4、实验结果与分析

试验数据为一个含有1000套题目的题库, 其中题型为4种, 10个知识点, 难度等级分为5等, 需要从该题库中抽取3套试题, 笔者分别用基础的粒子群优化算法和改进的粒子群优化来进行组卷测试, 算法参数设置及组卷策略如下:

(1) 算法参数设置:

种群规模为100;最大迭代次数itermax=300;优先性权重分别为鄣1=0.4, 鄣2=0.28鄣3=0.32, wini=0.9, wend=0.4;退火速率α=0.9。

(2) 组卷策略:

卷面总分为100分;知识点分数比例:从中选取5个知识点作为试卷考察目标, 5个知识点所占分数比例为2:2:1:2:3;题型分数比例:从中选取5类题型:填空题、选择题、判断题、简答题、论述题5类题型所占分数比例10:20:10:3:1;平均难度:0.6

根据改进的PSO算法优化结果如下:当迭代次数分别达到152次、145次和177次的时候适应度函数收敛, 得到试卷, 而基础的粒子群优化算法在迭代300次后均没有得到结果, 组卷失败。

试验结果表明, 使用本文提出的改进的粒子群优化算法对于求解智能组卷问题, 在组卷时间上优于基础的粒子群优化算法, 这说明本文提出的改进的粒子群算法的优化效果比基础的粒子群优化算法要好, 由此可以证明本算法模型的正确性与可行性

5、结束语

5.1 总结

本文首先对智能组卷问题进行简单描述并建立了相应的数学模型。其次, 对传统的PSO算法进行了改进。最后通过实验说明改进的PSO算法能够有效的解决智能组卷问题。

5.2 有待研究的问题与方向

本文对智能组卷问题, 结合PSO算法进行了研究, 但是由于本人学识能力和时间上的限制, 对有些问题和方向的研究还不够, 比如在实际的组卷过程中, 由于试题的属性多样, 组题约束条件更多, 并不仅仅局限于本文提出的四种约束条件, 在组卷约束中再加入区分度、答题时间等约束条件是下一步需要研究的。

参考文献

[1]潘正君, 康立山, 陈毓屏.演化计算[M].北京:清华大学出版社.1998:3-4

[2]李波.基于粒子群与模拟退火协同进化方法的电力系统无功优化[学位论文].济南:山东大学, 2008.

[3]袁富宇.用于多目标数据互联的模拟退火算法[J].系统工程理论与实现, 1998, 18 (10) ;52-54

[4]高鹰, 谢胜利.免疫粒子群优化算法[J].计算机工程与应用, 2004, 40 (6) :4-6.