论文部分内容阅读
摘 要：本文研究智能组卷系统，针对传统遗传算法极易未成熟收敛和后期搜索效率低的情况，引入小生境技术，提出优化的混合遗传算法，改进了组卷策略等关键技术，实验结果表明，新算法在全局搜索性能和收敛速度上有显著提高。
关键词：智能组卷；遗传算法；小生境
1 引言
目前，教育也面临着现代化和智能化[1]。基于网络的考试充分利用了网络无限广阔的空间，可以随时随地对学生进行考试，试卷由系统从题库中随机抽取产生，因而有效的避免了考试作弊和试题泄露等问题的发生，保障了考试的公平性和安全性[2]。因此，智能组卷系统研究是一项具有非常重要意义的实际课题。
2 研究现状
随着计算机软硬件技术的飞速发展，特别是计算机网络技术的日新月异，信息处理技术和数据库系统等新技术为考试系统的发展提供了新动力。
然而，现有组卷系统常采用随机选取法、回溯试探法和遗传算法等[3]。前两者耗时长，组卷成功率低；而遗传算法GA（Genetic Algorithms）[4]虽然是一种全局优化搜索算法，但容易陷入局部最优，产生早熟现象。远远无法满足智能考试取代传统笔试的要求。
3 优化的组卷算法
3.1 算法描述
优化的混合遗传算法是在遗傳算法的基础上，引入了小生境算法的思想，改进了自适应交叉和变异算子。算法步骤如下：
Step1 随机产生N个个体组成初始种群，设置进化代数计数器t=1，求出每个个体的适应度 。
Step2 按照个体适应度值进行排序，并计算出各个个体的被选概率 。
Step3 选择。选择N个子个体的种群 。
Step4 交叉。用自适应交叉运算对种群 进行操作，得到 。
Step5 变异。用自适应变异运算对种群 进行操作，得到 。
Step6 对新一代种群适应度值 进行计算。
Step7 进行小生境淘汰运算。求出 中每两个个体bi和bj之间的海明距离，得种群 。
Step8 终止条件判断。如果现阶段不满足终止条件，将 作为新的一代群体 ，转Step3；若满足终止条件，则输出结果，算法结束。
3.2 优化选择算子
设父代种群 个体的适应度为 ，子代群体初始为 ，则具体选择算子的过程为：
⑴将父代群体X中所有个体的适应度的总和计算出来。
⑵计算出所有个体的被选概率。
⑶采用多轮轮盘赌选择种群。
⑷对所有被选择的个体进行存储。然后返回。
4 实验结果
为了验证改进的混合遗传算法的可行性和有效性，以《大学计算机基础》为例，针对计算机基础课题库，按照上述思想用就java语言编制了程序，进行组卷试验。
我们将遗传算法和优化的混合遗传算法通过进化相同代数，比较两种算法产生的最优解的适应度值。取进化代数为10、20、50、100、200，小生境半径取0.5，运行后，如下表1所示：
由上表对比可看出：传统的遗传算法，在早期便可获得次优解，在后代中存在大量的局部最优的近亲子孙，很难有有意义的新个体产生。而优化的混合遗传算法采用了自适应调整交叉和变异算子技术后，函数的收敛速度明显加快，获得的解更优。
5 结束语
智能组卷系统涉及到合理的软件架构、综合全面的组卷规则和强大的组卷算法，本考试系统在湖南工学院试运行的过程中，为计算机基础课相关内容的的练习和考试都带来了很多便利之处，取得了良好的效果，并且大幅度提高了学生计算机等级考试的过级率。
[参考文献]
[1]陈磊.通用考试系统的设计与实现.计算机工程，2007，17（2）：140～143.
[2]杨永斌.网络智能试题库系统建设研究.计算机科学，2007，12（8）：296～298.
[3]陈友文.一种改进选择算子和基于小生境的算法.计算机与数字工程， 2009，6（236）：21～24.
[4]Dirk Krafzig，Karl Banke.Enterprise SOA：Service-Oriented Architecture Best Practices.Prentice Hall PTR，2004：21～23.
关键词：智能组卷；遗传算法；小生境
1 引言
目前，教育也面临着现代化和智能化[1]。基于网络的考试充分利用了网络无限广阔的空间，可以随时随地对学生进行考试，试卷由系统从题库中随机抽取产生，因而有效的避免了考试作弊和试题泄露等问题的发生，保障了考试的公平性和安全性[2]。因此，智能组卷系统研究是一项具有非常重要意义的实际课题。
2 研究现状
随着计算机软硬件技术的飞速发展，特别是计算机网络技术的日新月异，信息处理技术和数据库系统等新技术为考试系统的发展提供了新动力。
然而，现有组卷系统常采用随机选取法、回溯试探法和遗传算法等[3]。前两者耗时长，组卷成功率低；而遗传算法GA（Genetic Algorithms）[4]虽然是一种全局优化搜索算法，但容易陷入局部最优，产生早熟现象。远远无法满足智能考试取代传统笔试的要求。
3 优化的组卷算法
3.1 算法描述
优化的混合遗传算法是在遗傳算法的基础上，引入了小生境算法的思想，改进了自适应交叉和变异算子。算法步骤如下：
Step1 随机产生N个个体组成初始种群，设置进化代数计数器t=1，求出每个个体的适应度 。
Step2 按照个体适应度值进行排序，并计算出各个个体的被选概率 。
Step3 选择。选择N个子个体的种群 。
Step4 交叉。用自适应交叉运算对种群 进行操作，得到 。
Step5 变异。用自适应变异运算对种群 进行操作，得到 。
Step6 对新一代种群适应度值 进行计算。
Step7 进行小生境淘汰运算。求出 中每两个个体bi和bj之间的海明距离，得种群 。
Step8 终止条件判断。如果现阶段不满足终止条件，将 作为新的一代群体 ，转Step3；若满足终止条件，则输出结果，算法结束。
3.2 优化选择算子
设父代种群 个体的适应度为 ，子代群体初始为 ，则具体选择算子的过程为：
⑴将父代群体X中所有个体的适应度的总和计算出来。
⑵计算出所有个体的被选概率。
⑶采用多轮轮盘赌选择种群。
⑷对所有被选择的个体进行存储。然后返回。
4 实验结果
为了验证改进的混合遗传算法的可行性和有效性，以《大学计算机基础》为例，针对计算机基础课题库，按照上述思想用就java语言编制了程序，进行组卷试验。
我们将遗传算法和优化的混合遗传算法通过进化相同代数，比较两种算法产生的最优解的适应度值。取进化代数为10、20、50、100、200，小生境半径取0.5，运行后，如下表1所示：
由上表对比可看出：传统的遗传算法，在早期便可获得次优解，在后代中存在大量的局部最优的近亲子孙，很难有有意义的新个体产生。而优化的混合遗传算法采用了自适应调整交叉和变异算子技术后，函数的收敛速度明显加快，获得的解更优。
5 结束语
智能组卷系统涉及到合理的软件架构、综合全面的组卷规则和强大的组卷算法，本考试系统在湖南工学院试运行的过程中，为计算机基础课相关内容的的练习和考试都带来了很多便利之处，取得了良好的效果，并且大幅度提高了学生计算机等级考试的过级率。
[参考文献]
[1]陈磊.通用考试系统的设计与实现.计算机工程，2007，17（2）：140～143.
[2]杨永斌.网络智能试题库系统建设研究.计算机科学，2007，12（8）：296～298.
[3]陈友文.一种改进选择算子和基于小生境的算法.计算机与数字工程， 2009，6（236）：21～24.
[4]Dirk Krafzig，Karl Banke.Enterprise SOA：Service-Oriented Architecture Best Practices.Prentice Hall PTR，2004：21～23.