局部搜索遗传算法优化自动组卷：GALS方法

"基于局部搜索的遗传算法求解自动组卷问题 (2009年)" 本文探讨了在自动组卷领域中如何改进现有的算法以解决约束条件不完善和组卷结果不佳的问题。作者提出了一种名为基于局部搜索的遗传算法（GALS），该算法旨在克服传统组卷算法的不足，并能生成更优的试卷。 遗传算法是一种模拟生物进化过程的优化方法，通常用于解决复杂的组合优化问题。在自动组卷场景中，这一问题表现为如何在满足各种约束（如题型分布、难度平衡、重复性限制等）的同时，生成一份高质量的试卷。GALS算法采用了按题型分段的编码方式，将试卷看作是由不同题型组成的序列，每段对应一个题型。 首先，算法的交叉操作是按题型分段进行的，这样可以保持每个题型的题目数量在交叉后不变，从而确保全局搜索的均衡性。这意味着在交叉过程中，算法能够跨越不同题型，同时保持各题型的题目比例。 其次，GALS引入了基于禁忌表的局部搜索变异机制。通过使用禁忌表，算法能够记录并避免已经搜索过的解，防止陷入局部最优。这允许算法在题库中进行随机关联搜索，增加了探索新解的能力，从而提高搜索效率。 最后，选择策略采用了组合优化进化算法中的μ+λ策略。这种策略结合了μ个最优解和λ个新生成的解，有助于在维持种群多样性的同时，增强算法对局部最优解的挖掘。 实验结果显示，与传统组卷算法相比，GALS在相同的迭代次数下能发现更优的解。这表明，结合局部搜索策略的遗传算法在处理自动组卷问题时，能够更好地应对约束条件，提高组卷质量，为教育信息化提供了更有效的工具。 关键词: 计算机辅助教学; 遗传算法; 组合优化; 局部搜索; 自动组卷 中图分类号: TP311（计算机科学技术）; 文献标识码: A（表示具有学术价值的科研成果） 文章编号: 1671-5489(2009)05-0961-08（期刊内部的唯一标识） 该研究为自动组卷问题提供了一种新的解决方案，利用遗传算法的适应性和局部搜索的高效性，有效地解决了传统组卷算法的局限性，提升了试卷生成的质量。这项工作对于教育领域的信息化发展以及教育技术的研究有着重要的参考价值。