内容发布更新时间 : 2024/10/25 12:16:26星期一 下面是文章的全部内容请认真阅读。
龙源期刊网 http://www.qikan.com.cn
用遗传模拟退火算法进行智能组卷数学模型的求解及系统实现
作者：姚玉阁
来源：《硅谷》2013年第23期
摘 要 随着考试制度的不断推进，智能组卷问题得到更多的关注。面对传统随机式组卷方式的低效和组卷质量低劣问题，将行之有效的算法理论应用到组卷问题中成为必然。文章主要介绍在解决智能组卷问题上，遗传模拟退火算法作为改进的遗传算法所体现出的高效性和优越性，以及其系统实现的可行性。
关键词 智能组卷；遗传算法；退火算法
中图分类号：TP311 文献标识码：A 文章编号：1671-7597（2013）23-0043-01
作为计算机辅助教学的分支，智能组卷是实现计算机辅助教学的关键问题之一。其主要实现方式为借助现代计算机的平台，将先进的算法理论和教育专家的经验相结合，开发出能够生成专家水平的考试试卷的教学应用平台。因此开发先进的智能化组卷系统，成为当务之急。先进的算法理论是智能化组卷系统的必要支撑。遗传模拟退火算法在进行智能组卷数学模型的求解及系统实现上有着很大的改进，较传统的方法它表现出了更大的优越性。 1 关于算法概述 1.1 概述遗传算法
遗传算法的专业词汇为GeneticAlgorithms，简称为GA，它是由美国Miehigan大学的JohnH.Holland教授根据达尔文进化理论而创建的，是生物学应用向其它领域推广的体现，例如在计算机领域的应用，可以利用生物进化的机理来完善计算机求解问题的功能。此算法目前还未得到广泛应用，但是它就其本身的优越性在未来有着广大的发展前景。但是它也有其局限性：在收敛问题上存在收敛慢和收敛不成熟的缺点，但这些问题都在不断的完善与改进中。总之，遗传算法较传统的方法相比的优点有以下几点。
1）它可以自行组织、自行适应，更为智能化，比如用此方法求解问题时，确定合适函数、编码序列和遗传算法后，可利用在进化过程当中获取的信息进行相关自我搜索及组织，根据基因重组和基因突变原理，可以用来解决更为复杂结构的问题。 2）它有着本质的并行性。 3）它应用起来更加直接。
龙源期刊网 http://www.qikan.com.cn
4）它的求解答案不唯一，使用者可自行的选择相关合适解。 1.2 概述模拟退火算法
模拟退火的算法来源于物理退火原理：由于固体被加热并达到一定程度后，固体内部粒子处于无序状态，当固体温度慢慢降低并在常温时会表现出有序的基态。根据Metropolis准则，用固体的退火原理来模拟数据的组合优化问题并进一步演化为模拟退火算法。在实际应用中，模拟退火算法跟适用于解决大型组合优化问题。模拟退火算法由于计算过程简单通用，并且并行计算时的鲁棒性也可为人们所接受，在求解Max Cut Problem、Zero One Knapsack Problem、Scheduling Problem等问题时表现出色。 1.3 概述遗传模拟退火算法
实践证明，遗传算法在求解问题时最容易产生早熟现象，不能更快地在局部找出可行解，无法避免同一个可行解在不同次搜索中出现。而模拟退火算法却在局部搜索中，表现着巨大的优势，全局搜索中表现不好。因此把这两种方法有机融合，即为遗传模拟退火算法，其解决问题的能力会强上加强。这种算法的特点主要有两点：一是可以局部搜索全局的每个个体所对应的表现型，以便找出该局部环境下的最优解，以便改善全局总体的性能；二是可以对利用局部搜索所得到的局部最优解通过编码过程将其变成新的个体，从而形成了一个性能更优的新群体，更有利于下一代的遗传进化操作。 2 智能组卷数学模型的算法求解及系统实现 2.1 智能组卷原则
作为促进学生全面发展或是选拔人才的重要手段，考试已成为每个人必不可少的人生经历。为了保证考试的公平和水准，快速的完成高水平试卷出题演变成为一项繁重的“体力劳动”。依托高水平的专家试题题库进行智能化的组卷成为解决此问题的最有效方法，但是基于考试的本质和目的，智能组卷必须遵循一定的原则：考试范围合理、利于考试目的的实现、利于学生智力发展。为了更好地考察学生或是其他参考人员的素质，智能组卷还必须在试卷中体现出试题难度层次的变化。因此智能组卷需要高水准的算法理论和教育专家的宝贵经验协同作用，才能满足当代考试要求。 2.2 遗传模拟退火基本算法流程
组卷问题可简单描述为目标函数和约束条件问题，即构建一个目标函数。 1）进化代数计数器的初始化：N←0； 2）随机所产生的初始群体P（N）；
龙源期刊网 http://www.qikan.com.cn
3）评价的群体P（N）中个体的适应度； 4）个体选择操作：P'（N） ←seleetion[P（N）]； 5）个体交叉操作：P''（N） ←Crossover[P'（N）]； 6）个体变异操作：P'''（N） ←Mutation[P''（N）]；
7）个体模拟退火的最小值操作为：P'''min（N） ←SimulatedAtinealing[P'''min（N）]； 8）评价群体P'''（N）的相关适应度；
9）终止条件判断。若不能满足终止的相关条件，则：N←N+l，转到第4）步，继续进化过程；
若能够满足终止条件，则：输出当前最优的个体，那么算法结束。 2.3 遗传模拟退火算法的实施
需在一定遗传代数范围内进行，据课程要求的题目数量进行编码，并结合遗传算法要求进行相关选择、交换、变异等操作，从而筛选出不一样要求的题目类型和题目数量，并在每一代内找出符合适度函数的最小值个体，以此个体为基础，在指定的模拟退火的指定搜索层内进行相关搜索，进而找出它的最小值，并将它付给个体，然后按照新个体进行下一代遗传算法，直至代数满足最大的要求为止。 2.4 智能组卷的结论分析
尽管遗传模拟退火算法呈现的组卷效果较好，但是与其他算法进行比较，其运算的时间比较长， 在足够的退火范围内进行是遗传模拟退火算法想达到较好表现的条件，那么对于每个遗传算法中最小值的要求是必须要进行相应的退火算法，然而此运算过程相当复杂，它所需要的时间度与空间度也相应增多。 3 结束语
遗传模拟退火算法在智能组卷数学模型的求解及系统实现上具有很大的优势，是一种可行性的组卷方法。但是其自身存在的缺点还需在以后的应用中逐渐完善，并进行推广。 基金项目
基于遗传模拟退火算法的智能组卷研究，项目计划编号：NJZC13282；内蒙古自治区高等学校科学技术研究项目。