基于混合遗传算法的适应性组卷算法研究

摘要

现在是计算机技术与互联网的时代，科技的迅速发展也让我们的生活方式发生了极大改变。随着各种学业水平考试、招聘考试、职业技能等级考试等逐渐由线下转成线上，一批在线题库、在线考试系统也接踵而来，组卷问题作为其核心元素自然而然也引起了相应的关注。一个良好的组卷方法应不仅可以高效迅速组卷，还要确保试卷的生成质量，满足用户需求约束，最终使其不但可以适用于各种不同性质的考试，还可以在其他个性化教辅资源的定制上具有更加延伸的实际意义。 针对已有组卷方式存在的问题，本文提出了一种基于混合遗传算法(SNGA)的组卷算法，首先从研究对象的本源出发，提出了试卷模型的定义，并将组卷问题涉及到的多种约束条件进行了细致的划分与整理，并将其转化成了包含整体难度分布、知识点分布、章节分布等多条件约束的目标函数，基本上囊括了组卷所要求的大部分约束条件。然后本文在传统遗传算法的基础上进行了相应改进，先是针对种群的多样性度量方式进行了设计，在目前适用范围最广的种群熵的度量方式之上加入了试卷整体基因位相似度的评估，这样从不同适应度范围内的个体聚集程度和种群基因位的相似度两个方面对种群整体的多样性程度进行更为准确的衡量，也为后续交叉、变异概率的适应性调整打下基础;为了改善原有遗传算法可能陷入局部最优解的不足，将多小生境拥挤算法融入了遗传算法，与一般小生境遗传算法的不同之处在于多小生境拥挤遗传算法提倡试探性有条件的配对机制以及随机个体替换机制，这样在交配的时候能减少优良基因的破坏，在新老个体替换的时候也不仅仅局限于父子个体。然后基于种群多样性度量提出了一种适应性调整的交叉、变异概率，先是依据种群整体的多样性程度对种群整体的交叉、变异概率进行调整，之后又在整体概率的基础上对个体概率进行调整，在进化的前期与后期，概率随着种群多样性程度进行细微调整，进一步延缓了种群多样性在进化后期较为单一的问题。 最后基于团队已有的在线题库的真实数据，对多种相关算法进行了实验，并通过常用的组卷算法检测指标对实验结果进行判定，在综合各种指标的考量下，本文所提出的组卷算法与实验中其他的组卷算法相比在组卷效率和组卷质量上都略有提升，基本可以满足现实组卷所提需求。

目录

声明

摘要

第1章 绪论

1．1 研究背景与意义

1．1．1 研究背景

1．1．2 研究意义

1．2 国内外研究现状

1．2．1 基于随机算法的组卷

1．2．2 基于回溯算法的组卷

1．2．3 基于启发式搜索算法的组卷

1．2．4 遗传算法及其应用

1．3 本文的研究内容

1．4 本文的组织结构

第2章 相关概念和技术的介绍

2．1 遗传算法基本概念及流程

2．1．1 算法流程

2．1．2 基本编码方式

2．1．3 三种遗传算子

2．1．4 适应度函数选取原则

2．2 遗传算法早熟原因

2．3 小生境技术

2．4 本章小结

第3章 组卷问题概述

3．1 组卷基本原则

3．2 组卷过程简述

3．3 试卷评价指标

3．3．2 效度(Validity)

3．3．3 信度(Reliability)

3．3．4 区分度(Discrimination)

3．4 本章小结

第4章 改进的基于混合遗传算法的组卷算法

4．1 试卷模型

4．2 组卷约束条件表示

4．2．1 组卷约束条件

4．2．2 组卷目标函数

4．3 改进的混合遗传组卷算法

4．3．1 种群多样性评估改进

4．3．2 引入多小生境拥挤繁衍策略

4．3．3 自适应调整的交叉变异概率

4．4 组卷算法流程

4．5 组卷算法实施

4．5．1 基础参数设定

4．5．2 分段实数编码方式

4．5．3 适应度函数

4．5．4 选择算子

4．5．5 交叉算子

4．5．6 变异算子

4．6 本章小结

第5章 实验设计与结果

5．1 实验环境及评价指标

5．2 实验数据说明

5．3 实验效果分析

5．3．1 实验参数

5．3．2 性能测试

5．3．3 初始种群对组卷的影响

5．3．4 权重对组卷的影响

5．4 本章小结

第6章 总结与展望

6．1 总结

6．2 展望

参考文献

附录

致谢