研讨组卷算法文献综述

《研讨组卷算法文献综述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、研讨组卷算法文献综述研讨组卷算法文献综述导读：组卷算法文献综述组卷算法作为在线考试系统的核心，其算法的优劣是评价一个考试系统好坏的重要指标。因此，近年来研究组卷算法的科研工也非常多。下面，对近年来的常用组卷算法进行分析。目前常规的组卷算法有：随机组卷算法[1,2]、回溯试探法[3,4]、遗传算法[5-7]。1.随机算法组卷策略1.1随机组卷策略的算法描述最早的组卷算法是随机算法，而且至今仍然还被采用，随机组卷算法是由计算机利用随机函数从试题集合中随机抽取一道试题，然后判断该试题是否满足当前的指标约束的限制，如果符合要求则将

2、该试题选到试卷中，之后修改约束条件中的对应指标，然后再次随机选下一试题；如果选的试题属性不满足约束条件则直接放弃本题，选择下一个试题进行新的判断，直至所有试题全部被判断过还不能满足当前试卷的约束条件，于是整个组卷过程失败。随机组卷算法的操作流程如图1-1所示。实际上随机组卷算法就是在试题库中不断重复的进行随机搜索满足条件的试题的过程，直到试卷生成操作完成或因不能搜索到满足约束条件的试题而导致试卷生成失败为止。因为在限制条件状态空间的控制下，随机选取法有时能够抽取出一组令用户满意的试题，并且随机性试卷能够防止作弊，而且实现简

3、单。因此，在许多的实际应用中任采用这种方法作为自动组卷的算法。图1-1随机组卷算法操作流程图1.2随机组卷策略的算法评价随机算法是利用计算机提供的随机函数在试题库中抽取符合条件的试题组成试卷。这种算法的优点是实现简单、并能保证两套试卷内容不同；但是该算法的缺点也是很明显：（1）时间复杂度很大；（2）没有记忆功能，不具有回溯性质，组卷不易成功。因为试题的选取是依据当前已选试题和约束条件的判断，一旦形成条件极端的状况将无法对已做的试题选择进行反悔，只能从头开始重新生成试卷。在实际应用过程中，随机选取是均匀选取，可以避免作弊，具

4、有相对公平性，但同时却不能充分利用题库资源。此外，该方法基本不能根据用户要求智能生成试卷，容易产生指标冲突而进入死角，尤其是题库中各种状态类型平均出题量时，有可能在无法抽取合适试题的区域内反复选题，进入死循环，最终导致组卷失败[7]。有的考试为了能随机出题成功而不考虑其他指标，这就可能造成抽取的各套考题难易度不均、知识点分配不均，对考生的考核不公平，所以通常的组卷算法都会将基本的随机算法进行修改或扩展。2.回溯试探组卷策略2.1回溯组卷策略的算法描述随机选取法没有记忆功能，不具有回溯性质，已选试题不能放弃，因此很容易造成选

5、题无解。回溯试探策略就是对随机算法的一种改进，该算法是一种既带有系统性有带有跳跃性的搜索算法[13]。该算法通过验证所选试题是否满足系统给定的目标条件，来决定对该试题是否进行抽取，当发现目前没有任何试题满足要求而组卷过程又没有完成时，取消上一选择，重新选题组卷[13]。回溯算法手下选取一个试题，然后将该试题和产生的状态类型记录下来，之后再依次选取下一试题，其中一旦发现选择的题目不能满足约束条件，则释放上次记录的状态类型，然后重新选题进行试探，通过不断回溯试探直至生成试卷成功或返回到出发点结束。回溯算法实际上是将所有试题看成

6、是解空间树中，从根节点为首节点，按照深度优先的策略搜索解空间树，算法搜索至解空间树的任一节点时，会先判断该节点是否包含问题的解，如果包含则进入该子树，并继续按深度优先的策略继续进行搜索；如果不满足约束条件则跳过对以该节点为根的子树的搜索，回溯到其上层节点。之后不断重复搜索和回溯的过程，直到找到满足条件的解，或者回溯到根节点，并且根节点的所有子树都被搜索，程序才结束[13]。回溯试探法组卷搜索树如图2-1所示。这种方法改进了随机选取法，保存了搜索的历史状态，方便反悔而增加成功率。图2-1回溯试探法组卷搜索树2.2回溯组卷策略

7、的算法评价回溯法是一种有条件的深度优先算法，如果库存量远远大于应选题量，组卷成功率较高。当然，由于本方法的性质，它也存在一些缺点，如：不具有随机性、效率低、速度慢、内存资源占有量大。特别是在出题量较多时，为了能够使试卷达到规定的要求，会经过多次回溯，造成其抽题时间更长，空间复杂度更大。没有优化的回溯方法，由于没有前瞻性，可能在抽取最后一道题的时候才会发现问题，然后又可能一直回溯到第一道题，这样的时间开销远远不止随机抽题的两倍。3遗传算法的描述及评价遗传算法（GA）是模拟生物进化自然选择和遗传机制的一种寻优算法。它的实质是通

8、过群体搜索技术，根据适者生存的原则逐代进化，最终得到最优解或准优解[5]。在目前的计算机智能组卷算法的研究中，许多研究者利用遗传算法在计算机智能组卷方法的应用展开了大量的研究[6-7,12]。但传统的遗传算法存在容易早收敛、进化后期搜索效率低的缺点，故使用效果并不令人满意[14]。传统遗传算法一般采用简