基于遗传模拟退火算法的智能组卷研究:遗传模拟退火算法

　　摘要：考试数据库中的智能测试组卷是在一定约束条件下的多目标参数优化问题。通过应用传统的数学方法，很难解决这个问题。该文给了一个数学模型，并提出了一种新的遗传模拟退火算法来解决这个问题。通过对该算法的测试表明，新算法能够很好地提高组卷的成功率，并且在组卷的收敛速度和防止早收敛方面有了很明显地改善。
　　关键词：智能组卷；多目标参数；遗传模拟；退火算法
　　中图分类号：TP391.6文献标识码：A文章编号：1009-3044(2012)21-5183-04
　　Research of Intelligent Grouping Based on Genetic Simulated Annealing Algorithm
　　ZHAO Jian-xun, HUANG Ji-hai
　　(Information & Engineering College of Zhongzhou University, Zhengzhou 450044, China）
　　Abstract:The intelligent testpaper in the examination database optimizationproblem inmulti-targetparameters under certain con? straints. Through the application of traditional mathematical methods, it is difficult to solve this problem. The article gave a mathemati? cal model, and proposes a new genetic simulated annealing algorithm to solve this problem. Tests show that this algorithm, the new algo? rithm can improve the success rate of the test paper,and the convergence rate in the test paper to prevent early convergence as? pects have clearly improved.
　　Key words：intelligent test paper composition; multi target parameter; genetic simulated annealing algorithm
　　当前的教学内容、教学手段和教学方法伴随着计算机技术的快速发展，已经出现了一定程度的不适应性，人们越来越多地借助于计算机辅助考试系统来替代传统意义的考试，这也决定了计算机辅助考试系统已经成为人们关注和研究的热点之一。计算机辅助考试系统主要是通过计算机自动生成试卷以及自动评阅试卷，从而减少传统考试中的多个环节，达到了节约人力、财力和物力的效果。同时，通过计算机评阅试卷还能保证考试成绩的客观性，提高考试成绩的公平性。
　　目前计算机辅助考试系统所采用的最多的算法是遗传算法，由于遗传算法具有自适应寻优和良好的搜索特性，得到了众多学者的青睐。学者们通过理论推导和实践运用，发现遗传算法的收敛速度是非常快的，同时寻优的效率也非常高。遗传算法在许多领域内的应用都取得了卓越的成果[1-2]，在遗传算法的改进和理论研究方面也出现了许多成功的探索。
　　组卷算法的设计与实现是影响组卷效率和组卷质量的核心[3-5]，如何通过建立全新的数学模型，设置不同组卷的指标，从而使组卷模型具有较好的通用性；以及在该模型的基础上构造新的遗传算法编码方法，在避免出现适应值的重复计算和解码过程的复杂过度运算，提高运算效率方面达到良好的组卷效果，该文将给出具体的解决方法。
　　 2.1基因库的构造
　　为了减少遗传算法的迭代次数同时加快遗产算法的收敛，应根据试卷题型的比例和总分的要求，从初始化后并且包含知识点约束属性的试题库中随机产生试卷的初始试题，这样不仅能够满足试卷题型和总分的要求，同时也能够满足试卷对知识点的要求。基因库的具体构造步骤如下：
　　1）构造试题库的多个不同子集。子集中应该包含试题的知识点、题型和难度要求相关的属性，知识点、题型和难度相同或者相近的试题应该划在同一个子集中；
　　2）计算各题型包含的题目数以及在整套试卷中所占的分数比例。题目数应该满足用户对总分的要求、对题型覆盖情况的要求以及标准化题库中同种题型的试题分数是否相同的特点；
　　3）计算已经生成的试卷中是否需要同种难度题型的试题以及试题的数量，可以将此试题的数量设定为R；
　　4）去掉已经存在的试题，保证数据存储对象的低冗余性；
　　5）检查试题是否满足限制条件，试题需要随机地从各个子集中抽取，以保证不同知识点和难度的试题出现在生成的试卷中；
　　6）删除不满足限制条件的试题，转到5）继续；
　　7）将满足条件的试题插入到试卷中，并使R减1；
　　8）判断当前章节中的试题是否能够加入到当前的试卷中，如果能够加入到当前的试卷中，说明当前的知识点试题已经存在，需要从数据对象中全部删除，然后转到5）继续；如果该章节已经不能够加入试题了，说明该章节中的试题数量已经达到了试卷要求的最大值，则删除对应章节的全部试题，然后转到6）继续；
　　9）退出循环。退出循环的条件是R为0或者数据存储对象中的试题数量已经不能满足试卷的要求，当R为0时，表示生成试卷
　　5184
　　3.1实验参数
　　通过测试混合遗传模拟退火算法的性能，给出了两个具体问题的实验结果。实验环境是MathLab7.0模拟器和奔腾四2.8G/ 512M配置的电脑。在遗传模拟退火算法实验中，我们设置的最大遗传代数50，交叉概率为0.85，变异概率为0.005，惩罚因子1.2，退火初始温度是1，温度系数K为0.95。
　　3.2实验数据
　　作为遗传算法的控制参数之一，群体规模的大小将影响遗传算法的性能。我们在实验中设置的群体规模为：10,20,30,40,50,60, 70,80,90,100,120,150,180和200。相应地，我们进行了多次实验。其中两次实验结果如图1、图2和图3所示。图表中的数据分别为10次试验的平均值。
　　图3群体规模和算法平均耗时之间的关系
　　遗传模拟退火算法中，染色体的长度主要取决于解决问题的精度要求。更高的精度和更长的染色体，搜索空间更大。从这些数字中，我们可以看到，问题数量增加，但搜索空间变得更大，而所耗费的时间是有限的。仿真结果表明，遗传模拟退火算法的收敛速度快，可以采取。
　　该文主要研究组卷生成算法的使用。通过对测试文件中的每个约束条件进行仔细分析后，给出了一个新的基于遗传模拟退火算法的智能组卷问题的数学模型。试验结果证明，在论文中的算法是正确的，并为实际问题提供了妥善解决的方法，它可广泛应用于教学活动。