自动组卷算法_三种常用智能组卷算法剖析

时间：2019-04-03 03:18:36　来源：柠檬阅读网本文已影响人

　　摘要：当今社会已经进入了信息化时代，信息传递的高速化，信息产业的多样化，信息科技的高新化已经成为全球经济和社会发展的基本特征。随着计算机应用的日益普及和深入，传统的考试方式也面临着变革，而利用计算机考试系统实现无纸化考试已经成为一种重要的考试方式。基于计算机技术的在线考试系统可以借助于遍布全球的Internet进行，因此考试既可以在本地进行，也可以在异地进行，大大拓展了考试的灵活性。试卷可以根据题库中的试题即时自动生成，可避免考试前的压题；而且可以采用大量标准化试题，在这其中从题库中的试题即时自动生成试卷是在线考试系统中最关键的一个环节，是试题库系统的重要的核心部分，决定到试卷质量的好坏。目前这种智能组卷算法比较常见有随机组卷算法、回溯组卷算法、遗传组卷算法，下面逐一剖析这几种算法的应用。
　　关键词：智能组卷随机组卷算法回溯组卷算法遗传组卷算法
　　一、随机组卷算法
　　随机选取法根据状态空间的控制指标，由计算机随机的抽取一道试题放入试题库，此过程不断重复，直到组卷完毕，或已无法从题库中抽取满足控制指标的试题为止。该方法结构简单，对于单道题的抽取运行速度较快，但是对于整个组卷过程来说组卷成功率低，即使组卷成功，花费时间也令人难以忍受。尤其是当题库中各状态类型平均出题量较低时，组卷往往以失败而告终。
　　实现随机组题必须保证所随机产生的数据不能重复。因此，在开发系统时一般利用SQL语句实现随机的算法及其产生的优化随机算法。采用SQL语句中NewID（）可以解决好每抽一道题进行一次循环判断，而且提高运行中大量的资源空间利用率，运行速度较高，NewID（）语句是使数据库中的数据信息随机排序，然后按一定的题数，从数据库中读取试题。
　　用SQL语句随机访问则不需要循环判断，它只是在数据库中的表中数据随机重排后读取，因此速度相对很快。但用SQL语句则不能灵活地对多个表联合随机读取，而用VC语言则可以实现不同表的数据读取。因此，采取用SQL语句和VC语句混合编程算法则可以大大提高执行速度，并满足灵活性的需要。
　　二、回溯组卷算法
　　对于具有完备约束集D的一般问题P及其相应的状态空间树T，利用T的层次结构和D的完备性，在T中搜索问题P的所有解的回溯法可以形象地描述为：
　　从T的根出发，按深度优先的策略，系统地搜索以其为根的子树中可能包含着回答结点的所有状态结点，而跳过对肯定不含回答结点的所有子树的搜索，以提高搜索效率。具体地说，当搜索按深度优先策略到达一个满足D中所有有关约束的状态结点时，即“激活”该状态结点，以便继续往深层搜索；否则跳过对以该状态结点为根的子树的搜索，而一边逐层地向该状态结点的祖先结点回溯，一边“杀死”其儿子结点已被搜索遍的祖先结点，直到遇到其儿子结点未被搜索遍的祖先结点，即转向其未被搜索的一个儿子结点继续搜索。
　　在搜索过程中，只要所激活的状态结点又满足终结条件，那么它就是回答结点，应该把它输出或保存。由于在回溯法求解问题时，一般要求出问题的所有解，因此在得到回答结点后，同时也要进行回溯，以便得到问题的其他解，直至回溯到T的根且根的所有儿子结点均已被搜索过为止。
　　在用回溯法求解问题，也即在遍历状态空间树的过程中，如果采用非递归方法，则我们一般要用到栈的数据结构。这时，不仅可以用栈来表示正在遍历的树的结点，而且可以很方便地表示建立孩子结点和回溯过程。
　　回溯试探法是将随机选取法产生的每一状态类型记录下来，当搜索失败时释放上次记录的状态类型，然后再依据一定的规律（正是这种规律破坏了选取试题的随机性）变换一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成完毕或退回出发点为止，这种有条件的深度优先算法，对于状态类型和出题量都较少的题库系统而言，组卷成功率较好，但是在实际应用时发现这种算法对内存的占用量很大，程序结构相对比较复杂，而且选取试题缺乏随机性，组卷时间长，后两点是用户无法接受的。
　　三、遗传组卷算法
　　遗传算法是一种并行的、能够有效优化的算法，以Morgan的基因理论及Eldridge 与Gould间断平衡理论为依据，同时融合了Mayr的边缘物种形成理论和Bertalanffv一般系统理论的一些思想，模拟达尔文的自然界遗传学：继承（基因遗传）、进化（基因突变）优胜劣汰（优的基因大量被遗传复制，劣的基因较少被遗传复制）。其实质就是一种把自然界有机体的优胜劣汰的自然选择、适者生存的进化机制与同一群体中个体与个体间的随机信息交换机制相结合的搜索算法。运用遗传算法求解问题首先需将所要求解的问题表示成二进制编码，然后根据环境进行基本的操作：selection，crossover，mutation……这样进行不断的所谓“生存选择”，最后收敛到一个最适应环境条件的个体上，得到问题的最优解,其主要步骤如下：
　　第一步：编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。
　　第二步：初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体， N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。
　　第三步：适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。
　　第四步：选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。
　　第五步：交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。
　　第六步：变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.001~0.01之间。变异为新个体的产生提供了机会。
　　综上所综, 随机组卷算法对于纯单道题的抽取运行速度较快，能很好地控制试卷中试题难度的分布情况；回溯算法对于状态类型和出题量都较少的题库系统而言，组卷成功率较好，遗传组卷算法与前两种相比，具有良好收敛性、极高鲁棒性和广泛适用性的优化方法，一般来说，用户在自动组卷时会对试卷的质量提出多方面的要求，如总题量、平均难度、题型比例、章节比例、重点章节比例、知识点的交叉与综合等，自动组卷就应最大程度的满足用户的要求，适应性更强，效率更高，效果更好。
　　参考文献：
　　[1]王小平，曹立明.遗传算法——理论、应用与软件实现[M].西安：西安交通大学出版社，2002.1.123～140
　　[2]李律松.Visual C# + SQL Server数据库开发与实例[M].北京：清华大学出版社，2006.8.1
　　[3] Ansari N，Hou E.用于最优化的计算智能[M].李军，边肇译.北京：清华大学出版社，1999

相关热词搜索：三种算法剖析常用

自动组卷算法_三种常用智能组卷算法剖析

最新文章

热门文章