基于改进遗传算法智能组卷系统的研究

李国安

摘 要：智能组卷的方法有很多，目前应用遗传算法、模拟退火算法、随机抽取算法、回溯试探法等方法进行组卷，对比发现遗传算法在智能组卷问题上的解决方法具有一定的优越性。为了避免遗传算法的“早熟”，引入聚类思想，形成质心集，最终得到最优解，提高算法的性能。

关键词：遗传算法；智能组卷

【中图分类号】G 【文献标识码】B 【文章编号】1008-1216（2016）10C-0065-02

生成试卷的方法有很多，可以通过手工或通过算法智能组卷进行组合，满足一定规则下进行组卷。手工组卷不能高效、合理地完成组卷，智能组卷可以通过一定约束条件，完成一个组合问题，组合效率比较高。如何通过某种算法使组卷过程智能化，使试卷更有科学性、合理性？

智能组卷在国内从20世纪90年代开始逐渐增多，在中国知网搜索的“智能组卷”算法种类比较多，目前研究比较多的方法有遗传算法、模拟退火算法、随机抽取算法等。

随机抽取算法在组卷算法中是比较常用的一种算法，根据约束条件，满足用户需求，随机抽取试题，进行判断，满足条件，则生成试卷成功，否则，重新生成一组试卷，直到满足条件为止。这种算法的特点是在语言实现上比较容易，但是这种方式的组卷重复率高、成功率低，效率比较低，所需时间长。

回溯试探法是基于深度及广度搜索的算法，它建立在随机抽取算法的基础上，此算法对所有的情况进行穷尽搜索。在题库中存在满足约束条件的试题，系统最终一定会找出它的解。这种算法的结构复杂，运行起来比较耗费时间，所以适用于题量较少的情况。

遗传算法是解决并行计算问题，并逐步得到优化的解题过程，它通过模拟生物进化过程，对问题进行求解，迭代过程中找到最优解。操作步骤有选择、交叉和变异，完成这三个基本操作并抽取试题，最终得到满足约束条件的试卷集合。它具有运行效率高、灵活性大的特点，适用于具有多种约束条件的求解问题。

遗传算法是智能组卷中比较灵活的方法，将不确定的问题进行求解，这种但是在应用遗传算法过程中，应避免“早熟”，这也是遗传算法在智能组卷过程中值得研究的。目的就是解决组合优化问题，提高算法的执行效率。

一、改进遗传算法在组卷问题中的研究

组卷目标是从一个试题库集合中，通过某种方式重新组合成一组科学合理的组合试卷。

根据题目类型进行顺序排序，并在满足其他规则的情况下，根据确定的参数，从题库中根据算法组合成一组试卷，为了让试卷具有科学性，更接近确定的试卷，本文讨论的试卷生成主要满足题量、难度系数、区分度、知识点和题型等相关参数，使用遗传算法组合生成试卷，避免遗传算法“早熟”现象，将遗传算法进行改进。

（一）改进遗传算法基本思想

以遗传算法进行组合试卷，主要避免初始群体“早熟”现象发生，找到最优解。此过程中引入聚类思想，在不影响种群的情况下，将初始种群使用聚类算法，群体中的每个染色体代表一个初始聚类的中心集，根据评价函数（根据试题的属性完成聚类算法K-Means，得到一个数值）对每个染色体进行评价，得到适应值，染色体的适应值越大，说明染色体代表的中心集的聚类效果越好。根据约束条件进行选择，随机生成一组染色个体。进行交叉操作，染色体长度会发生变化，染色体长度的变化说明在遗传算法过程中，中心集的选择在发生变化，正是因为这一操作，经过多次迭代，可以得到聚类划分数目和最优的质心集。最后根据变异概率，进行变异操作，在寻找最优质心集迭代过程中，找到的个体具有多样性，从而保证了搜索全局，避免了“早熟”现象，找到最优解。