智能组卷策略

智能组卷策略（共7篇）

智能组卷策略 篇1

在英语题库系统建设中, 组卷策略是关键环节。英语题库建成后, 组卷者只需要输入一些组卷参数, 系统就可以根据这些参数从英语题库中进行选题, 自动生成符合教学或教师要求的英语考试试题 (包括考试内容, 题目类型, 难易程度, 可信度, 区分度, 时间等一系列的指标) 组成一份合格的试卷对于这个问题, 目前通用的方法是随机自动组卷[1,2,3]。该方法能最大程度地满足用户的不同需要, 但它具有很大的随机性和不确定性, 无法从整体上把握教学的要求, 不具有智能性。

基于生物进化思想发展起来的进化算法[4,5]是一种并行、有效的智能优化方法, 其最先是由Holland[4]于1995年提出, 最后逐渐发展成为一种通过模拟自然生物进化过程解决最优化问题的计算模型, 它能解决随机自动组卷的随机性, 并能从群体中选出更好的满足条件的个体, 具有很大的智能性。另外, 基于英语试题库中题型多、题目量大等特点, 因此, 基于生物进化机理发展起来的进化算法为从英语试题库中组建有效的试题提供了很好的解决方法。

1 英语试题智能组卷模型

要组建一份完整有效的英语考试试卷, 就是如何从预先给定的英语试题库中按照教师或教育教学要求自动生成一份试题。目前, 我国英语试题基本形成了包含篇章、题类和一些细目, 每一道试题又包含多个属性。其中在组卷中教师要求的一般有:1) 篇章, 试题内容所属篇章。2) 题目类型, 内容所属的题型。如:听力, 词汇, 完形填空, 阅读理解, 翻译, 写作。3) 难易程度, 一般按得分率分为四个级别:容易, 中等, 较难, 难。4) 区分度, 试题对考生的知识能力水平鉴别和区分程度的指标。5) 考试时间, 完成每一道题目所需的大致时间。6) 题目的分值, 根据题目所包含知识点的分量事先确定的分值。7) 用户要求, 试题对学生知识和能力的要求, 一般分为掌握, 理解, 运用, 灵活应用。因此, 组一份n道试题的试卷就是从题库中抽取n道试题, 每道试题的7个属性决定一个n×7的矩阵S一行元素的值。

undefined

该矩阵S就是一份英语试卷求解的目标状态矩阵。矩阵S的列元素的分布分别满足用户指定的试卷的总体要求, 也就是:各篇章所占的分数、试卷中各种题型的题数、反映不同教学层次要求的试题所占的分数比例、各种难度的试题所占的分数比例、各种区分度的试题所占的分数比例、所有试题的估时总和、所有试题的分数总和这7个指标都应等于用户指定的要求, 或者误差最小。在实际应用中, 设定整卷指标f来综合反映这7个指标与用户要求的误差, 由于它们的重要程度不同, 因此整卷的指标f就是7个指标的加权和, 同时为了不至于各个误差相互抵消, 这7个指标与用户要求的误差都取绝对值。可以用下式表示

undefined

其中fi表示第i个指标与用户要求的误差的绝对值, wi表示第i个指标的权值。

依据组卷原则, 目标函数是越小越好, 而适应度函数则是越大越好, 所以要将目标函数转换成适应度函数。因指数比例既可让非常好的个体保持多的复制机会, 同时又限制其复制数目以免其很快控制整个群体, 提高了相近个体间的竞争, 故采用指数比例变换方法将其转换为适应度函数。采用指数变换法, F=exp (-αf) , 其中:系数α (由经验取法α一般可取值0.04) 决定了复制的强制性, 其值越小, 算法复制的强度就越趋向于那些具有最大适应度的个体。

2 智能组卷的智能进化算法

2.1 编码表示

设题库中总共有m道题, 用X1, X2, …, Xm表示这m道题, 那么组卷就是从X1, X2, …, Xm中选出n道题, 使得整卷指标f最小。在此, 用一个m位的二进制串来表示问题解。形式如下:L1L2L3…Lm。如果L1为1, 表示该题被选中, 若为0, 则表示该题未被选中。假设该套试卷要求有n道试题, 则L1L2L3…Lm串中有n个1。

2.2 种体初始化

随机生成初始化种体。在实际组卷中, 将群体规模设为n, 每个个体都是通过rand (m) 这个随机函数在1至m中随机选择n道题, 其中m为题库中试题的题量。

2.3 个体适应度计算

首先通过解码, 得到个体的组卷参数矩阵S。具体过程如下:根据串L1L2L3…Lm的值, 可知试卷中包含的试题的题号, 然后把这些试题的属性写到组卷参数矩阵S中 (由此可以看到:组卷参数矩阵S的值是由题库中的试题属性组成的, 这就保证了按照矩阵S来选题时不会出现找不到题的情况) 。然后调用评价函数得到每个个体的适应度, 在实际应用中, 通过计算个体的整卷指标f来反映个体的适应度, 整卷指标f越小, 个体的适应度越高。

2.4 选择策略

根据适应度对群体中的个体排序, 并对每个个体分配一个选择概率, 所有概率的和为1。适应度高的串 (整卷指标f相对小的个体) 就用较大的选择概率生成下一代。

2.5 杂交策略

杂交即交换, 是2个串按照杂交概率pc从某一位开始逐位互换, 先在群体中随机地选择2个串, 对每对串随机地选择一个交换点, 是否发生交换操作, 还要受交换概率的控制, 选择好一对串后, 在0—1之间产生一个随机数, 若该数大于pc则发生交换, 否则, 保持原状, pc一般为0. 5左右。

2.6 变异策略

首先是随机选取一个个体进行变异, 再随机在该个体中选取一个变异点, 判断该点对应的试题属于哪种题型, 并根据该点对应的试题是否被选中进行相应的操作。若该点为1, 则表示该题被选中, 然后从该点对应的试题所在题型中再随机选取一个为0的点并将该点置为1, 最后将变异点置为0。若该点为0则表示该题未被选中, 然后从该点所对应的试题所在题型中再随机选取一个为1的点, 并将该点置为0, 最后将变异点置为1。通过这样的操作, 可以保证每种题型中被选中的试题数量保持不变。这里:变异概率pm通常取为0.001—0.1。

2.7 终止条件

由于对不同的种群, 用户的要求不同, 所以, 在进化算法中并不能规定群体进化到了第几代就得到了最优个体 (试卷的最优组合) 。因此, 在进化算法中设一个标志f, 用来标志群体中是否仍然有个体在进行交叉和变异, 即种群中的个体是否仍然在进化, 是否向更优解的方向接近。如f=1, 则还有更优个体;否则, 就己找到了最优解, 群体进化到这一代就结束了, 程序满足条件退出。

3 实验设计及分析

为了说明方法的有效性, 把本文方法与文献[3]中的方法进行了比较, 在试验中, 将600道试题按要求存于试题库中, 并给出要生成的试卷要求, 算法中的参数分别为:试题库中试题总数m=600, 杂交概率pm=0.8, 变异概率pm=0.1, 运行结果见表1, 从表1中可以看出, 本文所给组卷方法与传统的随机组卷算法相比, 能用较短的时间成功地组成一份满足教学和教师要求的试卷。

由于进化算法实行了全局并行搜索, 搜索空间大, 并且在搜索过程中不断向可能包含最优解的方向调整搜索空间, 从而易于找到最优解。从实验结果可以看出, 进化算法能有效地解决英语试题库智能组卷问题, 与其它方法相比, 它能较早地找到满足条件的群体。同时该组卷方法也为其它各种试题的组卷提供了类似于该问题的一种新的有效方法。

参考文献

[1]李小勇, 王瑛.题库管理系统中的自动化组卷算法.西北师范大学学报 (自然科学版) , 2002;38 (4) :41—43

[2]乐光学, 彭小宁, 曾志峰.试题库自动组卷系统的算法设计与实现.计算机应用, 2001;21 (8) :198—200

[3]孙勇, 柏云.基于遗传算法的试题库组卷策略.淄博学院学报, 2002;4 (3) :27—28

[4]Holland J H.Adaption in natural and artificial systems.Michigan:The University of Michigan Press, 1975

[5]Jin Y C, Branke J.Evolutionary optimization in uncertain environ-ments-A survey.IEEE Transactions on Evolutionary Computation, 2005;9 (3) :134—137

智能组卷策略 篇2

智能组卷算法是计算机辅助教学领域中考试系统的核心。组卷过程中需要考虑章节分值比例、题型数量分值、试卷难度以及知识点覆盖等多约束条件。在这些约束中关于知识点的选择是组卷的核心，不论使用何种题型其目的都在于考核学生是否掌握了重要的知识点。一份合理的试卷首先应该满足“知识点覆盖全面且考核重点突出”这一原则。在课程教学大纲编写规范要求中明确指出，教学知识点分为三级:掌握(较高要求)、理解(一般要求)、了解(最低要求)，表明教学内容的重要性。因此在智能组卷选取知识点时应该参考知识点的考核层次，优先考核重要的知识点。

目前常规的组卷算法有:随机组卷算法[1,2,3]、回溯试探法[4]、遗传算法[5,6]及各种人工智能方法[7,8,9,10]。大部分算法都在满足章节比例、题型分值、试卷难度等约束上进行优化改进，对知识点均匀覆盖以及如何突出考核重点鲜有提及。部分算法仅给出了知识点名称，采用线性结构管理知识点，通过随机选取的方式实现知识点的均匀覆盖[1,2,5]，未提及知识点考核层次。文献[6,10]中要求人为指定组卷中各个知识点分配的分值，隐含给出了知识点的重要性。文献[11]要求指定不同考核层次占用的分值。这种方法人工干预较多且有一定主观性。

综上所述，目前针对智能组卷策略的研究集中于如何更快更有效地处理与组卷相关的多约束条件之间的关系，对根据知识点考核要求实现均匀覆盖未作深入探讨。本文提出一种基于树型结构带权重的知识点管理策略，能较好地解决智能组卷系统中知识点选取的问题，实现所选知识点的相关度低，且各类考核要求知识点的选取比例合理，实现了知识点选取均匀分布且重点突出。

1 知识点选取原则

1.1 知识点均匀分布

通常知识点定义以章节来划分，在一章中的知识点被定义为线性结构。因此知识点均匀分布以章节为单位，保证在某章内的选题对该章的知识点选取实现均匀分布。如果知识点定义密度太小(数量少)，则无法区别相似的知识点，且题目归属不明确，在一个知识点中选多道题目有可能题目相似度很高。如果知识点定义密度太大(数量多)，则相似的知识点会被认为是完全不同的，在随机选取中也有可能导致题目相似度高。

以“计算机图形学”课程中“光栅图形学”章为例，知识点罗列如下:直线绘制(包括DDA算法、中点画线法、Bresenham直线算法)、圆绘制(包括中点画圆算法、Bresenham画圆算法)、区域填充(包括种子填充算法、种子扫描线算法)、多边形扫描(包括射线法、扫描线转换算法)、裁剪算法(包括直线裁剪、多边形裁剪)。按照线性结构有两种定义方法。

第一种方法如表1所示定义5个知识点，假设该章需要8道题，采用知识点随机选择后至少有3个知识点被选择2次。假设“直线绘制”知识点选择2道题，由于不区分细节，则有可能2题都源于DDA算法，但是显然最好是在三种直线绘制算法中任选2个不同的。此为知识点定义密度小所产生的问题。

第二种方法如表2所示定义11个知识点，假设该章需要8道题，在11个知识点中随机选择可能会出现1、2、3号同时被选中，由上述分析可知，三者均属于直线绘制算法，可以看出该知识点相似度较高。此为知识点定义密度大所产生的问题。

综上所述需要制定合理的知识点管理方法，采用树形结构管理知识点，可以有效解决知识点密度问题，在智能组卷中真正实现知识点的均匀分布。首先按照大类分为若干一级知识点，在每个一级知识点下可以定义分类更细的二级知识点，记为“一级知识点|二级知识点”。上述实例知识点用树形结构管理如表3所示。在选择知识点时可以先选一级再选二级。

1.2 知识点优先级

在有些组卷算法中，要求指定必考知识点，实际就是对某些知识点提高了优先级。任何一门课程在教学大纲中都规定了每个知识点的考核要求，如:熟练掌握、掌握、理解、了解。通常教师在组卷中优先考核要求“熟练掌握”及“掌握”的知识点。因此在智能组卷时也应该满足这一原则:重点关注考核要求高的知识点，能自动优先选择重要的知识点。避免每次组卷时都要人为指定。

根据考核要求指定二级知识点的权重，一级知识点权重应根据下属二级知识点的权重综合决定。原则:(1)一级权重应能体现二级中的最高权重，以确保首先选取包含要求“熟练掌握”的二级知识点的一级知识点。(2)一级权重应能体现二级知识点的数量。综合考虑上述要求，定义一级知识点权重的计算公式。

假设考核层次“了解、理解、掌握、熟练掌握”分别对应权重1、2、3、4。某一级知识点包括n个二级知识点，xi表示二级知识点中第i个知识点的考核层次权重值。记W为该一级知识点的权重，计算方法如式(1)所示。因为1～4的权重值不足以凸显“熟练掌握、掌握”考核层次的重要性，因此为每个考核层次乘以一个重要系数。

综上所述，定义基于权重的知识点树形管理结构如图1所示。其中二级知识点权重与该知识点在教学大纲中规定的考核要求有关，一级知识点权重通过式(1)计算得到。

2 分级带权重知识点选取策略

2.1 算法描述

首先根据图1建立分级的树形结构知识点管理链表，根据考核要求指定二级知识点的权重，使用式(1)根据二级知识点权重计算一级知识点权重。在分级选取中根据章节待选题量和该章的一级知识点数量，计算每个一级知识点内应该选取的二级知识点数量，并参考权重优先选择权重大的知识点。带权重的知识点均匀分布选取算法描述如下:

Step1对每章的知识点构建分级的树形结构链表，并指定二级知识点(叶子节点)权重。

Step2使用式(1)计算每个一级知识点权重。

Step3对每章的一级知识点按照权重降序排序;对每个一级知识点下的二级知识点按照权重降序排列。

Step4假设每章待选m道题，有n个一级知识点，令a=m/n,b=mmodn，则该章前b个一级知识点中分别选取a+1个二级知识点，后续n-b个一级知识点中分别选取a个二级知识点。在选取二级知识点时按照权重降序依次选取不同的知识点。

Step5如果有待选题的章节，转Step3。

Step6对所有选中的知识点，按照组卷要求选取相应的试题。算法结束。

2.2 算法评价指标

定义知识点相关度表明知识点均匀分布的程度。计算各权重知识点的选取比例表明选取是否实现了重点突出。

1)知识点的相关度

说明:(1)如果两个知识点同属一个一级知识点则认为相关，否则认为不相关。(2)如果两个知识点相同，认为相关度极大。

假设Ei表示第i章选中的二级知识点的集合，集合元素个数p,表示该集合中第k个知识点，k=1,2，…，p。对任意之间的相关度记为如式(2)所示。显然

记Q表示一次组卷中全部所选知识点的相关度，定义如式(3)所示。用相关度值累加的方法计算相关度，相关度值较小表明知识点相关度不高，说明均匀分布良好。

2)各权重知识点的选取比例

定义:若Mi表示权重为i的二级知识点总数，Ni表示所选知识点中权重为i的知识点数量。记ui表示权重为i的知识点选取比例，如式(4)所示。当知识点选取注重优先级时，ui应与权重值成正比，权重大的知识点选取比例高说明重点突出。

3 算法测试

某课程共计5章，知识点考核层次分为4级:了解、理解、掌握、熟练掌握，其权重对应定义1、2、3、4。定义wi表示第i级权重值，i=1,2,3,4。按照所构建算法中step1和step2建立树形结构对知识点管理如表4所示。由于算法与知识点权重有关，与知识点具体名称无关，因此表4中省略知识点名称，仅给出每个知识点权重。

由表4可统计出各权重知识点总量M=[8,10,7,7]。已知各章需求试题知识点数量:B=[3,4,1,1,6],Bi表示第i章需求知识点数量。按照带权重的知识点均匀分布选取算法中step3～step5步骤依次在各章选取知识点，计算相关度，统计各权重知识点数量并计算选取比例，结果如表5所示。

使用相同的课程知识点，采用线性结构随机选取算法进行知识点选取，计算各测试指标结果如表5所示。比较测试结果可知，带权重的知识点均匀分布所选知识点的相关度明显较低，说明知识点能均匀分布。各权重知识点的选取比例合理，说明重要知识点覆盖面广，重点突出。

使用不同的课程知识点结构以及不同的章节需求知识点数量，分别用分级带权重的知识点均匀分布算法和线性结构随机选取算法进行多次测试，结果如表6所示。分析数据可知分级算法能较好地实现知识点的均匀分布，并且对重要知识点覆盖率高。线性随机算法当多次使用后各权重的知识点选取率基本在50%，符合随机测试的规律，但对组卷而言，无法体现知识点的优先级，且知识点的相关度较大。

4 结语

智能组卷算法是计算机辅助教学领域中考试系统的核心，其中知识点是考核内容的主体。通过建立分级的树形结构知识点管理链表，可以解决知识点线性管理中知识点密度过大或过小的问题，实现知识点的均匀分布。同时根据知识点的考核层次合理定义权重，体现知识点的优先级，构建了参考权重分级选取的策略。测试结果表明，该策略可以有效地实现知识点选取均匀分布且重点突出。如何将该策略与智能组卷算法中其他环节有效结合，提高组卷的质量，有待于进一步研究。

参考文献

[1]周文胜,潘中柱.一种实用的随机组卷算法的设计思想[J].湖南科技学院学报,2005,26(11):299.

[2]王萌,金汉均,王晓荣.集合随机抽选法在智能组卷中的研究[J].计算机工程与设计,2006,27(19):3583-3585.

[3]李目海.组卷中的随机抽取算法分析与实现[J].枣庄学院学报,2007,24(2):299-301.

[4]林培光,樊孝忠,余正涛,等.基于背包问题的在线组卷算法[J].计算机工程与应用,2006,7(5):165-166.

[5]马德良,陆昌辉,王小乐.基于改进遗传算法的智能组卷方法[J].计算机应用,2009,29(7):1884-1886.

[6]李军.基于遗传算法的智能组卷系统研究[M].天津大学,2008.

[7]刘毅.人工智能在自动组卷建模中应用研究[J].计算机仿真,2011,28(8):385-416.

[8]杨檬,宋建社,曹继平,等.蚁群优化算法应用研究概述[J].计算机仿真,2009,26(6):52-55.

[9]何福男,陈树越,史国栋.猎潜算法及其在智能组卷中的应用[J].湖南科技大学学报,2011,26(3):86-90.

[10]任剑,卞灿,全惠云.基于层次分析方法与人工鱼群算法的智能组卷[J].计算机应用研究,2010,27(4):1293-1296.

[11]李静梅,李静,焦平.一种可调整式的多元变量渐近寻优组卷策略[J].应用科技,2009,36(10):53-57.

智能组卷策略 篇3

智能组卷系统是将教育学、教育统计学、教育测量学、考试学及心理学等多学科与人工智能技术有机结合,采用合理的组卷算法,由计算机自动从题库中选择试题,组成满足多重约束目标的试卷[1]。在实际应用中,为保证生成的试卷能最大程度地满足组卷质量和速度的要求,而且试卷的区分度、信度、效度等方面都要达到预期效果,智能组卷系统除要有先进智能的组卷算法外,如何选择科学合理的组卷策略也是决定组卷效率和质量的重要因素之一[2]。

航理智能组卷系统根据部队多机型、多专业、多层次的考核要求,提出了一种基于试题属性矩阵,采用试题分值和专业占比优先的组卷算法,实现了航理综合考核的自动组卷功能。但在实际应用中发现存在以下问题:一是智能组卷系统对组卷者的要求较高。如果组卷者不了解考核的对象,或者不熟悉相关专业理论,无法合理配置试卷表参数时,自动组卷的效果就会受到影响。二是智能组卷系统对某些有特殊要求的考核的组卷效率较低。如实际考核时,经常会有需指定考核题目或考核内容的要求。为此,本系统设计了人工干预组卷功能,可对自动组成的试卷进行换题、加题、删题等人工干预操作,以提高组卷效率和考核的针对性。

1 系统设计

航理智能组卷系统主要用于机关对飞行员进行训练等级评定考核时使用,要求试题库内的试题要覆盖多个机型的所有航理专业的知识点。

系统由管理子系统、建库子系统和组卷子系统构成。管理子系统主要实现系统管理、用户身份验证等功能,可保证组卷工作的独立性和保密性;建库子系统主要实现各机型航理试题的录入、修改以及机型、专业等题库属性编辑的功能。组卷子系统可按机型、专业、难度、考核对象、考核内容及训练阶段等多个约束条件实现智能组卷,最后按试卷模版生成Word标准格式的试卷和参考答案。

1.1开发平台

本系统的开发平台为VB 6.0+Access。VB 6.0支持面向对象的程序设计,且具有强大的数据库管理功能。VB 6.0本身提供三种数据接口:DAO,RDO和ADO。其中ADO是建立在微软OLEDB技术上的数据对象,能够处理任何类型的本地或远程数据,它通过内部的属性和方法提供统一的数据库访问接口,是使用VB开发数据库应用程序的首选方法[3]。在VB中基于ADO技术实现数据库访问的操作有两种方式,一种是通过ADO Data控件非编程访问方式,另一种是利用ADO对象编程访问方式[4]。本系统选择ADO对象编程访问方式实现数据库的访问。

Access是微软公司推出的一种关系型数据库,具有界面友好、开发简单、接口灵活等特点,是目前桌面数据库应用开发流行工具之一。

1.2 系统题库的数据结构设计

由于本系统要求题库中的试题涵盖部队的主要机型及各航理专业,并可按机型或专业分别组卷进行专项考试或综合考核。因此本系统的组卷约束条件除知识点、题型、难度、分值外,还要有考核类型、机型和专业等条件。为此本系统题库的数据结构定义如表1所示。

1.3 组卷子系统的设计

组卷子系统根据航理考核涉及多机型、多专业、多层次的应用特点,为满足实际应用中既要能自动组卷,又要能指定部分考核内容的要求,采用自动组卷和人工干预组卷相结合的组卷策略来实现航理考核的智能组卷。

其中自动组卷是基于试题属性矩阵,采用试题分值和专业占比优先的组卷算法,从备选试题库中抽取试题,自动组成试卷并提取答案。人工干预组卷是在自动组卷的基础上,根据考核的要求对已生成的试卷进行试题替换、增减试题等操作。组卷子系统实现智能组卷的流程如图1所示。

2 人工干预组卷功能的实现

人工干预组卷模块要求能够实现在试卷临时库和备选试题库之间进行的换题、加题、删题等选题操作。该功能模块的设计思想为:首先将备选题库和试卷临时库中的每道试题的th,jx,zy,zsd,tx及nd等字段的属性值组合编码成试题的序列号(ID),作为该试题的唯一性标识。然后通过人机交互方式输入试题的序列号来实现在试卷临时库和备选试题库中相关试题的定位,进而完成换题、加题、删题等人工干预操作。该模块的人机操作界面如图2所示。

界面中的两个Rich Text Box控件分别作为已选中的试题和备选试题库中的备选试题的浏览窗口,除显示试题各属性值外,还可显示每道试题的序列号(即ID);一个Combo Box控件可实现按题型分类浏览备选试题;四个Text Box控件用于输入试题的序列号以实现换题、加题、删题等人工干预选题操作。

由于试题的换题、加题、删题等人工干预选题操作均需在试卷临时库和备选试题库之间进行数据源的连接、SQL查询、数据记录属性值修改等操作,为减少重复代码,提高系统的运行效率和可扩展性,在系统的HHTK.my TK类模块中设计了数据操作的自定义函数,具体如表2所示。

以换题操作为例,部分程序代码如下:

3 结语

经应用实践反馈,本系统采用自动组卷和人工干预组卷相结合的组卷策略,在实现航理考核试题智能组卷的基础上,有效地提高了航理考核的客观性和针对性。特别是大大提高了部队按机型进行指定专业或指定内容考核的组卷效率。

摘要：为提高航理智能组卷系统的组卷效率和考核的针对性,提出了一种自动组卷和人工干预组卷相结合的组卷策略。系统采用了VB面向对象的编程技术,基于ADO数据访问接口,设计了人工干预组卷功能,可对自动组成的试卷进行换题、加题、删题等人工干预操作。应用表明,系统操作简单,运行稳定,组卷效果好,有效地提高了航理考核的客观性和针对性。

关键词：VB,ADO,智能组卷,人工干预组卷

参考文献

[1]李建锋.智能组卷系统的研究与实现[J].计算机与数字工程,2008,36(3):63-65.

[2]刘伟科.智能组卷系统中的组卷策略研究[J].电脑与信息技术,2010,18(5):40-41.

[3]杨启亮.面向SQL Server的OPC Client开发[J].计算机应用与软件,2007,24(2):95-97.

[4]王丽芳.基于ADO.NET的O/R Mapping中间件的研究[J].西北工业大学学报,2006,24(6):759-762.

[5]朱守业.智能组卷中组卷目标的满足性检查与处理[J].微计算机信息,2007,23(21):268-269.

[6]张振国.新型组卷策略的研究与实现[J].计算机工程与设计,2008,29(20):5348-5350.

智能组卷系统的设计 篇4

一、系统需求分析

从系统的经济需求、可用性需求、功能需求、性能需求系等几个方面,进行了系统的需求分析。下面重点探讨的是系统的功能需求。

通过对调查数据进行分析,确定了《嘉兴南洋学院智能组卷系统(计算机文化基础)》的功能包括组卷管理、试卷管理、试题管理、用户管理、系统管理。

组卷管理。该系统的试卷,可以手工组卷,也可以智能组卷。手工组卷由用户根据考试要求,在试题库中查询试题,手工选择符合要求的试题,组成最终的试卷。智能组卷则要求用户先输入组成试卷的各项参数,如试卷难度、考试题型、考察知识点等,由系统根据组卷策略,从试题库中抽取试题,组成符合需求的试卷。

试卷管理。在试卷管理功能中,能够对生成的试卷进行管理,如预览试卷、微调试卷、删除试卷、查询试卷等。无论是使用手工组卷,还是使用智能组卷,都可以对生成的试卷进行预览。如果符合考试要求,则生成最终使用的试卷。如果生成的试卷不符合要求,可以对试卷进行微调,或者删除试卷,重新生成新的试卷。用户也可以输入科目、考试时间、班级等关键字,查询已经生成的试卷。

试题管理。试卷的生成,是由系统从试题库中抽取试题,自动生成的。试题管理功能可以管理试题库中的试题。使用该功能,可以向试题库中添加试题、删除试题库中试题、修改试题库中试题以及查询试题库中试题。在操作时要注意保证试题库的安全性和可靠性。

系统管理。为了保证系统能够稳定、安全地运行,离不开系统管理功能。该功能主要完成初始化试题库、设置访问权限、扩充试题库、备份与恢复等操作。

二、系统设计

系统虽然能够以手工组卷与智能组卷两种方式进行组卷,但还是以智能组卷方式为主。对于智能组卷系统来说,是否能够生成符合要求的试卷,主要取决于组卷策略的设计。好的组卷策略,能够高效地进行智能组卷。目前国内使用的智能组卷曾略主要有遗传算法、回溯试探算法和随机抽取算法这三种。

随机抽取算法最简单,最容易实现,尤其是抽取单道试题速度比较快。对于抽取多道试题,完成一个组卷过程而言,其速度是极其慢的,不适合在线考试。使用随机抽取算法抽取的题目过于随意,组卷的成功率也很低。所以,随机抽取算法并不是一种好的智能组卷策略。

回溯试探算法作为一种有条件的深度优先的算法,其组卷成功率是非常高的。但是,这种算法结构非常复杂,占用的存储空间比较大,组卷占用的时间比较长。

遗传算法是一种比较好的智能组卷算法。该算法能够模拟遗传机制,进行自然选择与随机优化,从而在解空间中搜索出最优解。遗传算法随机生成初始种群,而不需要过多的先验条件。随后从一个群体开始搜索,而非从一个点开始搜索。在搜索过程中,变异操作可以使算法很好地收敛到较优解上。由此可见,遗传算法具有智能搜索能力,且具有很好的收敛性,能够满足基于网络的在线考试系统的需求。

三、数据库设计

智能组卷系统中,试题库是整个系统的基础。数据库的设计必须合理,具有比较少的数据冗余,而且拥有良好的伸缩性,使得数据库比较容易扩充,以及方便数据库的维护。因此,在该系统中,数据库的设计也起着举足轻重的作用。智能组卷系统涉及到的数据比较多,为了避免大量的数据冗余,不能把所有数据放到同一个数据表中。在该系统中,将关系密切的数据放在同一个数据表中。经过认真的分析以及精心的设计,整个智能组卷系统的数据库包括用户表、课程表、知识点表、题型表、组卷参数表、试卷表、答案表等几个重要的数据表。

经过以上分析,最终确定《嘉兴南洋学院智能组卷系统(计算机文化基础)》采用My SQL数据库系统创建数据库,智能组卷的策略采用能够满足在线考试系统的遗传算法。最终实现了系统的组卷管理、试卷管理、试题管理、用户管理、系统管理等功能,满足了该课程的实际需求。

摘要：随着计算机网络技术的发展,基于网络的在线考试成为现实。设计开发《嘉兴南洋学院智能组卷系统(计算机文化基础)》,能够将教师从繁琐的任务中解脱出来,考试结果也更加公平、客观、准确,能够体现出学生对课程的实际掌握情况,更符合教学要求。遗传算法具有较好的收敛性,能够高效地实现智能组卷,符合在线考试系统的要求。

关键词：在线考试,智能组卷,遗传算法

参考文献

[1]张兵,胡建华.计算机考试系统的研究现状及基于C/S结构的计算机考试系统的实现[J].硅谷,2009(5).

基于EDPSO算法实现智能组卷 篇5

1 分布估计的离散粒子群优化算法 (EDPSO)

1.1 基本的PSO算法

粒子群优化 (Particle Swarm Optimization-PSO) 是一种基于群体智能的进化计算技术, 是1995年Eberhart和kennedy博士提出的, 其思想来源于对鸟群、鱼群等群集行为的模拟[2]。PSO源于对鸟群捕食的行为研究, 设想这样一个场景:一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。它通过追随当前搜索到的最优值来寻找全局最优, PSO从这种模型中得到启示并用于解决优化问题。PSO中, 每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。粒子i在N维空间里的位置表示为矢量Xi=[x1, x2, …, xn]所有的粒子都有一个由被优化的函数决定的适应值, 每个粒子还有一个速度Vi=[v1, v2, …, vn], 决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子 (随机解) 。然后通过叠代找到最优解。在每一次叠代中, 粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pid。另一个极值是整个种群目前找到的最优解。这个极值是全局极值pgd。粒子根据这两个最优值来更新自己的速度和位置:

k是迭代次数, vundefined是粒子的速度, xundefined是当前粒子的位置。rand () 是介于 (0, 1) 之间的随机数。c1, c2是学习因子。通常c1=c2=2。

上述PSO主要适用于求解连续优化问题。Kennedy和Eberbart也提出了一个离散版本的PSO (DPSO) [3], DPSO把标准PSO的第2个方程替换为:

其中undefined为Sigmoid函数。

1.2 分布估计算法

分布估计算法的基本思想是在每一次迭代中, 依据当前优质解信息的概率分布模型来产生新解。具有概率分析的理论基础[4,5]。EDAs的基本框架可描述如下:

第一步:t=0, 随机产生初始种群Xbase (t) ;

第二步:选择, 从当前种群Xbase (t) 中根据某种选择机制选择若干粒子构成父代种群Xparent (t) ;

第三步:建模, 采用某种概率模型评估Xparent (t) 构建一个概率分布模型p (t) ;

第四步:抽样, 依据概率p (t) 分布模型抽样产生新解Xoffspring (t) ;

第五步:判断是否满足终止条件, 若满足则转到第六步;否则t=t+1, 转到第二步;

第六步:种群Xbase (t+1) 为所求解。

EDAs的核心部分是选择、建模和抽样, 它首先随机生成初始种群, 然后根据某种机制选择拥有较好目标函数值的若干个体组成父代种群, 再建立一个能反映父代种群的概率分布模型, 根据概率分布模型抽样产生新种群。EDAs的实质是抽取优质解的整体信息, 然后评估它们的分布, 再利用这种分布产生新种群。

1.3 分布估计的离散粒子群优化算法

在标准PSO的 (E) 中, ω, pid和pgd三项可以解释为随机——局部搜索项、个体历史最优信息项和全局最优项[6]。在这里选择所有个体的历史最优信息, 建立一个反映优质解分布的概率模型, 这个概率模型标识解空间中最具潜力解的区域分布信息。对于新的种群, 随机从概率模型和全局最优信息项中获取解信息, 相应的随机——局部搜索项功能, 通过变异或者通用的局部搜索算法实现。

EDAs中采用一阶统计量的UMD (Univariate marginal distribution) , 单变量边缘分布概率模型来建模[5], 评估整个解空间中优质解的分布情况。

完全按文献[7]的设计, 在EDPSO中, 第t次迭代时粒子i的位置xid (t) ∈{0, 1}。首先统计个体历史极值的每一维出现1的个体数量, 要概率模型计算出一个实值概率向量, 表示为P= (p1, p2, …, pd, …, pD) , Pd表示粒子的第d维取值为1的概率。然后, 这个概率向量P引导粒子在0-1的解空间进行。在产生下一代种群时, 以大概率β从概率向量抽样产生新解, 以小概率1-β直接复制种群全局最优解作为新解。即个体粒子的部分维值由概率向量来决定, 部分维值直接来源于群体最优个体。

EDPSO产生新个体粒子的机制是:

概率向量用下列方程 (1) 进行初始化:

在每一次迭代中, 按照PBIL (Population Based Incremental Learning, 基于人口增量学习的进化算法) 的概率更新规则更新概率向量P:

其中λ∈[0, 1]是学习率, 式中右边的pd代表上一代概率向量信息, undefined是在当代优质解估计出的新的概率信息。为了避免算法的早熟, 在抽样产生的新解上以一定的变异概率α实施按位变异来保持种群的多样性:

2 基于EDPSO的组卷方案

智能组卷是根据用户输入的组卷要求, 搜索试题库中与特征参数相匹配的试题, 生成满足用户要求的试卷。自动组卷系统理论基础涉及试卷评价指标与组卷要求、数学模型、智能组卷算法、试题库中试题属性及编码方法。本文用于测试的题库结构和组卷目标模型采用文献[1]的描述方案。

2.1 算法实现过程设计

采用文献[1]的编码方案, 按题型进行分段编码, 以缩小解的搜索空间。

第一步:初始化种群, 按组卷目标中各种题型的分值要求, 对每个独立代码段采用随机抽题的方法, 并保存所有题的个体历史极值和全局最优[7]。

第二步:用 (1) 式初始化概率向量P, 即标识题库中最具潜力解的区域分布信息。

第三步:根据文献[7]中产生新个体粒子的机制, 以大概率β从概率微量抽样产生新解, 以小概率1-β直接复制种群全局最优解作为新解。

第四步:按 (3) 式进行变异, 产生新的种群, 即新的题库。

第五步:评价新库中所有题的适应度。

第六步:比较适应度值更新当前的全体历史极值和全局最优值。

第七步:使用PBIL的概率更新规则更新概率向量P, 即 (2) 式。

第八步:同化检验处理。

第九步:判断是否满足终止条件, 若满足则结束进行过程, 完成;否则转到第三步继续迭代抽题的过程。

2.2 适应度函数

利用试题的历史信息对试题进行筛选, 历史信息控制函数[8]作为适应度函数:

f (x) =F/ (γA·λg (B) ) , 其中F表示试题的抽取标志、A表示抽取次数、B表示最近选用时间日期, g (B) 为时间转换函数, 它是B与当前组卷时间的差, γ, λ为A, B的权重系数, 反映A, B对组卷的影响程度。

2.3 避免或降低同化率

在文献[9]的组题算法实现过程中, 先将各级难度系数的试题从试题库中抽出, 并分别建立临时试题库, 然后从中抽掉知识点与其他题型重复的那些试题, 再从临时库中抽取给定的题量, 每抽一题, 删掉临时库中知识点相同的试题, 然后反复抽取试题, 直至组卷完成[9]。

这个方法可以有效避免或降低同化率 (知识点重复) 问题, 同时也可减少余下粒子的搜索范围, 提高收敛速度。所以文本也借鉴文献[9]的这种建立临时库、边抽边删的思想, 在算法的实现过程的第八步上比较检验同化的处理过程, 以避免知识点的重复。在处理同化检验过程中要考虑题库的健壮程度, 避免缺题现象, 有效控制鲁棒性。

3 组卷实验

本文以铁路《车辆检车员鉴定系统》为例, 对本文所提出的系统方案分三个阶段进行了实验:第一阶段在原始题不变, 编码方案及参数不进行完善改造的情况应用EDPSO组卷;第二阶段对题库先按专家系统和文献[9]提出的方法改进后应用EDPSO组卷;第三阶段在第二阶段基础上, 再按文献[10]对组卷目标进行满足目标检查, 然后应用EDPSO。题库规模600道题, 其中单选260题, 多选题80题, 填空100题, 判断120题, 问答题40题, 难度5级。每一阶段所用的各项参数一致:种群规模60 (试卷题量) 、每一阶段抽取试卷10套, 最大迭代次数50、题型要求及分数标准默认, 其他参数按惯例;EDPSO用到的参数:β控制产生新粒子的方式, 为了让算法具有更好的学习能力, 取β=0.9;λ学习率均衡算法的全局探索能力和局部开采能力, 为了让算法具有较好的搜索性能, 设λ=0.7;α变异率是粒子发生变异的概率, 变异的目的是为了防止算法陷入局部极小值, 变异太大会变成随机搜索, 取α=0.001。

4 结束语

实验结果表明, 将分布估计的离散粒子群算法应用于智能组卷, 可通过分布概率的调整, 较好地达到目标要求, 在组卷效率上能达到满意的效果。

参考文献

[1]Xiaoying SUN.Study on algorithm of intelligent test paper[C].2008Intermational conference on multimedia and information technology (MMIT 2008) .Published by IEEE computer society, 2008:86-89.

[2]Kennedy J, Eberhart R C.Particle Swam Optimization[C].Procee-dings of IEEE International Conference on Neural Networks.Pisca-taway, NJ:IEEE Press, 1995:1942-1948.

[3]Kennedy J, Eberhart R C.A discrete binary version of the particleswarm slgorithm[C].Proceedings of the World Multiconference on Sys-temics, Cybemetics and Informatics.Bscataway.NJ, 1997:4104-4109.

[4]Baluja S.Population-based incremental learning:A method for inte-gratin genetic search based function optimization and competieive lear-ning[J].School of Comput.Sci, Carnegie Mellon Univ, Pittsburgh, PA, Tech Rep CMU-SC-94-163, 1994.

[5]M uehlenbein H.The equation for response to selection and its use forprediction[J].Evolutionary Computation, 1997, 5 (3) :303-346.

[6]周驰, 高亮, 高海兵.基于PSO的转换流水车间调度算法[J].电子学报, 2006, 34 (11) :2008-2011.

[7]周雅兰, 王甲海, 印鉴.一种基于分布估计的离散粒子群优化算法[J].电子学报, 2008, 36 (6) .

[8]郝彦, 陈丽燕.基于题库信息的智能组卷算法[J].浙江海洋学院学报:自然科学版, 2006, 25 (2) .

[9]林雪明, 张钧良, 蒋伟.基于知识占的试题库组卷算法的建立[J].微机发展, 2001 (2) .

试题库智能组卷算法研究 篇6

1、智能组卷的数学模型

智能组卷实质上是一个多目标和多约束的组合优化问题, 通常可根据某效用函数将多个目标依照各自权重组合成单一目标来优化处理以期找到问题的近似最优解。

组卷的目标是生成多份有差别的能准确考核学生对知识的掌握情况的高质量等效试卷, 基于组卷的实际需要与问题的复杂性, 精选试题的属性定义试卷;在组卷策略中, 采用的试题相关属性定义如下: (1) 题目编号:试题的唯一标识; (2) 题型编号:主要包括单项选择题、多项选择题、填空题、判断题、名词解释题、简答题、综合题等题型; (3) 题分:试题的分值; (4) 知识点编号:试题所考核的知识点, 与科目的章节有关; (5) 难度:试题的困难程度, 分为:难, 较难, 一般, 较易, 易; (6) 考核要求编号:试题在教学内容上的要求层次, 一般分为:了解、理解、掌握、熟练掌握与综合; (7) 估时:完成该试题所需的时间, 以分钟为单位; (8) 区分度:试题对学生学习水平的鉴别能力, 分为:好, 较好, 一般, 差; (9) 选用次数:该题曾被选中的次数, 表示使用频度。

假设生成的一份试卷的试题数目为n, 试卷则由以下矩阵S决定, 其中每道试题上述的9个属性决定矩阵S某一行元素的值, 其定义如下:矩阵S=[aij], 其中aij表示试卷中第i题中第j个属性值, 且1≤i≤n, 1≤j≤9。上述矩阵S的列元素的分布分别体现了以上9种用户指定的试卷要求或者误差最小。组卷问题即可转化为一个多目标多约束的组合优化问题。

在实际应用中, 我们设定整卷指标f来综合反映这9个指标与用户要求的误差, 由于它们的重要程度不同, 所以整卷的指标f就是9个指标的加权和, 同时为了不至于各个误差相互抵消, 这9个指标与用户要求的误差都取绝对值。可以用下式表示:

其中fi表示第i个指标 (即所有第i列) 与用户要求的误差的绝对值, wi表示第i个指标的权值。组卷的目标就是使整卷指标最小, 或者尽可能小。[1]

2、试题库结构设计

在试题库系统的建设中, 试题库的结构设计是至关重要的, 良好的试题库结构往往会收到事半功倍的效果。本文建立了一个能使用遗传算法智能组卷的试题库管理系统, 建立了以下试题库数据模型:

(1) 题目内容表 (试题编号、题目内容、答案、备注) ;

(2) 题目属性表 (试题编号、所属课程、题型编号、难度系数、认知层次、知识点、区分度、答题时间、抽题标记、备注) ;

(3) 题型表 (题型编号、试题类型) ;

(4) 题目其他情况表 (试题编号、出题人、出题时间、有效期) ;

(5) 题目反馈情况表 (试题编号、答对率、良好率) ;

(6) 组卷方案表 (方案编号、课程名称、编制教师、目标难易程度、目标区分度、题目数量) ;

(7) 组卷方案明细表 (方案编号、试题类型、题目数、分值、总体顺序) ;

(8) 组卷方案章节分布表 (方案编号、所属章节、所占比例) 。

另外, 还可建立一些诸如知识点设置情况表、大纲设置情况表等辅助支持数据库, 以方便组卷算法的实现。

3、遗传算法组卷

3.1 遗传算法原理

遗传算法GA (Genetic Algorithms) 由美国学者J.H.Holland于1975年首先提出, 它是一种模拟自然界生物进化过程的计算模型。它的求解问题是从多个可行解开始, 然后通过一定的法则进行迭代以产生新解, 直到得到最优结果。就实质而言, 遗传算法是一种具有自适应调节能力的搜索寻优技术。遗传算法同时具有简单通用、鲁棒性强、内在的并行性以及应用范围广等显著特点, 能有效地解决计算量大的问题, 这些都适宜于处理试题库组卷的问题。

简单遗传算法的主要步骤可描述如下:

(1) 基因编码;

(2) 初始群体生成;

(3) 群体中个体适应度函数值的计算;

(4) 对群体中个体进行遗传操作 (即选择、交叉和变异) ;

(5) 适应度函数值的再次计算;

(6) 如果满足停止搜索判据, 迭代停止, 输出问题的最优解;否则, 转向步骤4。

3.2 基于遗传算法组卷

3.2.1 确定编码方案

用遗传算法求解问题, 一般不是直接在问题的解空间上, 而是利用解的某种编码来表示的。在智能型试卷自动生成系统中, 由于在建库时为每种题型建立了一个库文件, 故每种题型可各自独立编码。因此, 编码方案可采用分组实数编码策略, 就是根据各个题型各自进行实数编码, 然后对每一个题型再采用传统二进制编码策略进行处理, 但题型组之间的编码是独立的, 每组编码反映一种题型。这样, 可以克服以往采用二进制编码搜索空间过大和编码长度过长的缺点。

3.2.2 生成初始群体

为了加快遗传算法的收敛并减少迭代次数, 试卷初始种群不是完全随机的方法产生, 而是根据题型 (或各篇章内容或各考查点) 所占分数比例、总分的要求随机产生, 使得初始种群已经满足了题型 (或篇章或考查点) 和总分的要求。

3.2.3 适应度函数的确定[2]

适应度函数的选择是影响智能组卷算法性能好坏的关键。在一般情况下, 适应度函数是由目标函数变换而成的, 在遗传算法中是以适应度大小来区分群体中个体的优劣, 其值越大个体越好。依据组卷原则, 目标函数是越小越好, 而适应度函数则是越大越好, 所以要将目标函数转换成适应度函数。因指数比例既可让非常好的个体保持多的复制机会, 同时又限制其复制数目, 以免其很快控制整个群体, 提高了相近个体间的竞争, 故采用指数比例变换方法将其转换为适应度函数。采用指数变换法:f=e-af, 这种变换法的基本思想来源于模拟退火过程, 其中的系数a决定了复制的强制性, 其值越小, 复制的强度就越趋向于那些具有最大适应度的个体。

3.2.4 遗传算子的改进

3.2.4. 1 选择算子

本文采用轮盘方式复制对象。轮盘算法可以简单地描述如下:[3]

(1) 依次累计群体内各个体的适应度, 得到相应的累计值S, 最后一个累计值为Sn;

(2) 在[0, Sn]区间内产生均匀分布的随机数R;

(3) 依次用Si与R进行比较, 第一个出现Si大于或等于R的个体i被选为复制对象;

(4) 重复 (2) , (3) , 直至满足所需要的个体数目。

3.2.4. 2 交叉算子

通过在群体中随机挑选两个染色体, 并随机在染色体中央某一点进行点交换从而得到下一代的新个体, 完成交叉的工作。在分段遗传算法的组卷过程中, 考虑到组卷最终必须满足题型题量的要求, 本文按照题型的变化采用分段进行操作, 每种题型对应染色体中的一个独立分段, 在段间进行交叉。

3.2.4. 3 变异算子

变异算子也改进为在同一题型组内进行有条件的单点变异, 即个体的每一个基因座上的基因都按设定的变异概率Pm, 在一定范围内 (与该基因题型相同且考查点与本个体其他基因的考查点不重复) 变异。通过变异算子可以达到局部搜索的目的。

3.2.5 遗传算法控制参数[4]

遗传算法中的交叉概率Pc和变异概率Pm的选取对算法的性能有重要的影响, 如果Pc和pm过大, 可能使算法变为随机搜索;而Pc过小, 会使搜索过程缓慢, Pm过小, 则不易产生新的个体结构, 可能使算法早熟收敛, 陷入局部最优。为了加快遗传算法的搜索效率和有效地防止其陷入局部最优, 同时保护优良试卷个体, 根据种群的进化情况来动态地调整交叉概率Pc和变异概率Pm, 这种遗传算法在保持试卷群体多样性的同时, 保证遗传算法的收敛性并防止遗传算法陷入局部最优。在试题组卷中采用了如下公式进行自适应调整:

其中, Pc是交叉概率, Pm是变异概率, fmax为群体适应函数最大值, favg为群体适应函数的平均值, f为两个交叉个体中的适应函数值较大的一个, f'为变异个体的适应函数值, a、b为概率系数a≤1, b≤1。

3.2.6 最优个体保存策略

进行选择、交叉、变异操作后, 比较新一代最好个体与上一代最好个体适应度值, 如下降, 则用上一代最好的换新一代最差个体, 此策略可保证最优个体不被选择、交叉、变异操作所破坏, 它是遗传算法收敛性的一个重要保证条件。

3.2.7 终止条件

(1) 出现种群满足组卷约束要求时 (个体的适应度值达到预先设定值) ; (2) 进化中连续若干代中的最优个体不被替换所持续的代数超过某一设定值, 则迭代停止; (3) 达到设定的最大迭代数时, 则迭代强制停止;

4、仿真实验

在本实验中, 将1000道试题按要求分别赋予各项特征值存于试题库中, 给出要生成的试卷的要求, 分别用传统的遗传算法和本文提出的改进式遗传算法对我们开发的多媒体医学影像在线考试系统进行实验。实验环境是:CPU主频2.4 GHz, .NET平台, 1G内存。由于组卷是组成一份误差在可接受范围内的试卷, 并非要求此试卷的整体指标一定是全局最优, 因此在实验中试卷总分、试卷题型分布及各题型试题量分布这两个约束要求没有误差, 而在试卷难度系数、区分度等上的一定范围内的误差是可以接受的。设交叉概率Pc=0.6, 变异概率Pm=0.07, 实验了100次, 得到结果如下:对于传统遗传算法:成功组卷次数64, 平均迭代次数389, 平均组卷时间 (s) 62;对于本文改进的遗传算法, 成功组卷次数85, 平均迭代次数57, 平均组卷时间 (s) 35。

5、总结

本文采用改进的遗传算法实现了组卷系统, 已应用到我们开发的医学影像在线考试系统。下一步研究的方向是融合教育测量理论更好的遴选好的组卷因素, 应用到无纸化网络自动考试中, 实现一个完整的网络化教学系统。

摘要：本文讨论了适合于智能组卷的数学模型、数据库结构、并将遗传算法应用于在线医学影像试题库系统的智能组卷中。

关键词：智能组卷,数据库,遗传算法,试题库,在线考试

参考文献

[1].刘艺.自动组卷算法的研究[J].渤海大学学报, 2005, 26 (2) :124-127

[2].荆霞.网上考试系统自动组卷功能实现[J].南京审计学院学报, 2009, 6 (1) :90-92

[3].陈宇.启发式遗传算法组卷模型研究[J].计算技术与自动化, 2006, 25 (1) :50-52

智能组卷策略 篇7

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

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

智能组卷系统的开发涉及到应用的具体算法和前台界面及后台数据库的设计和实现,本文以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.