遗传算法在通用考试系统自动组卷中的研究与应用

　　摘要： 本文根据教师教学效果及考生考试所存在的问题，阐述了利用计算机组卷实现考试规范化、科学化的必要性。通过分析有关组卷策略，选择模拟退火遗传算法解决自动组卷中组合优化问题。通过对组卷过程及各种影响它的重要因子的分析，确定其数学模型，并根据遗传算法的思想，对数据进行预处理以及选择染色体编码方案，经过适应度评价、选择算子、交叉算子、变异算子以及迭代终止条件，最后将其应用于实践。实验结果表明，本文采取的数学模型是适合用户的需求的。本文对自动组卷系统进行了设计，其研究结果具有一定的参考价值。
　　关键词：遗传算法 模拟退火算法 模型 自动组卷
　　
　　引言
　　
　　随着计算机技术和人工智能的发展，计算机技术已进入现代教育领域并形成一门新兴的边缘科学。利用计算机建立试题库，实现计算机自动选题、组卷，是实现考试规范化科学化的重要措施，更是实现考教分离的一个重要手段。如何从试题库中快速地、能满足用户各项要求地抽出试题组成一份试卷就是组卷需要解决的问题。本文在对组卷系统进行研究的同时，结合遗传算法理论，利用我院的《编程语言基础》课程，探讨一种合适的算法解决考试系统中的自动组卷的问题。
　　
　　一、遗传、模拟退火算法概述
　　
　　模拟退火遗传算法是将遗传算法与模拟退火算法相结合而构成的一种优化方法。遗传算法的局部搜索能力很差，但把握搜索过程总体的能力较强；而模拟退火算法具有较强的局部搜索能力，并能使搜索过程避免陷入局部最优解，但模拟退火算法对整个搜索空间的状况了解不多，不便于使搜索过程进入最有希望的搜索区域，从而使得模拟退火算法的运算效率不高。但如果将遗传算法与模拟退火算法相结合，互相取长补短，则有可能开发出性能优良的新的全局搜索算法，这就是遗传模拟退火算法的基本思想。
　　与基本遗传算法的总体运行过程类似，遗传模拟退火算法也是从一组随机产生的初始解（初始群体）开始全局最优解的搜索过程，它先通过选择、交叉、变异等遗传操作来产生一组新的个体，然后独立地对产生的各个个体进行模拟退火过程，以其结果作为下一代群体中的个体。这个运行过程反复迭代地进行，直到满足某个中止条件为止。
　　传统遗传算法存在提前收敛的缺陷，而模拟退火算法由于采用概率接受目标函数值变好的试探点，因此这种搜索策略有利于避免搜索过程因陷于局部最优解而无法自拔的弊端。将这两个方法结合起来形成遗传模拟退火算法可以更好地解决组卷的优化工作。
　　
　　二、自动组卷系统设计
　　
　　自动组卷系统［１，２］实质上也是一个信息处理系统。本课题要设计一个自动组卷系统，该系统能够从题库中选择合适的试题组成满足考试要求和用户要求的考试试卷系统。教师通过该系统，先在系统中设置试卷的各种约束条件及要求，系统自动地从试题库中快速地组出针对不同测评目的的试卷，以满足各类考试及测评要求。自动组卷系统要有一个开放式的数据库，可以让教师将自己收集到的试题经审查后录入到试题库中，使得题库不断地丰富，组出来的试卷分布更合理。
　　根据需求分析的结果，本系统主要由5个模块组成：系统管理模块、试卷管理模块、试题管理模块、系统维护以及帮助等。系统层次结构如图1所示。
　　
　　
　　三、实验结果及分析
　　
　　为验证该模拟退火遗传算法的可行性与有效性，以《编程语言基础》课程为例，在试验中题库共有1000道题，填空、选择、写程序执行结果、完成程序、编程5种题型，8个知识点。设置试卷中各题型所占的分值比例为2∶3∶2∶1∶2，题目数量的比例为20∶15∶4∶5∶2，8个知识点所占的比例为10∶20∶10∶20∶10∶10∶10∶10，难∶较难∶中∶较易∶易为5∶15∶50∶20∶10。整卷的难度系数为0.6。
　　经过测试，将得到的试卷用于学生测试，测试的试卷分析表如表1所示。由此可见，这个结果是符合要求的。
　　
　　由于该算法在当前的智能教学系统的理论研究与实际应用具有重要意义，本课题的研究是十分必要的，它也为构建一个完善的ICAI系统打下了很好的基础。
　　
　　参考文献：
　　［1］程艳.计算机自适应考试的理论模型研究.计算机与现代化，2006，133(9)：24-27.
　　［2］毕忠勤，陈光喜，徐安农.计算机自适应测试系统的算法.桂林电子工业学院学报，2004，24(6)：50-53.
　　［3］王远志，孙立镌.基于遗传模拟退火算法约束求解算法.2005，10(2)：26-30.
　　［4］Li Shouzhi，Li Minyuan，Pan，Yongxiang.Genetic Annealing Algorithm and Its Convergence Analysis.CONTROL THEORY AND APPLICATIONS，2001，19(3)：376-380.