论文部分内容阅读
摘 要：随着计算机应用技术的不断发展，由计算机与教育相结合而产生的计算机辅助教育系统得到了快速发展。在目前的素质教育下，考试仍然是衡量教师教学能力和学生学习成绩的主要衡量标准之一，同时不同层次的考试对试卷衡量标准也是不尽相同的。那么，如何依靠算法组出一套科学合理且高质量的试卷是评定计算机与教育结合效果的手段之一。因此，对高效智能组卷算法的研究是非常具有实际应用价值的。
关键词：计算机辅助教育；智能组卷；遗传算法；
主要内容
随着计算机应用技术的不断发展，由计算机与教育相结合而产生的计算机辅助教育系统得到了快速发展。在目前的素质教育下，考试仍然是衡量教师教学能力和学生学习成绩的主要衡量标准之一，同时不同层次的考试对试卷衡量标准也是不尽相同的。那么，如何依靠算法组出一套科学合理且高质量的试卷是评定计算机与教育结合效果的手段之一。因此，对高效智能组卷算法的研究是非常具有实际应用价值的。
遗传算法是一种模拟自然界生物进化过程与机制的元启发式搜索技术，被广泛应用于求解复杂的优化问题。通常，穷尽搜索完整的输入空间是不可行的，遗传算法可以用来通过搜索较小的输入空间，在合理的时间里求出好的问题解。传统遗传算法通过顺序执行选择、交叉、变异等遗传操作，寻找问题的最优解。传统遗传算法用于求解复杂的优化问题时，通常需要较长的计算时间。
为了解决遗传算法带来的计算性能问题，本发明提供一种基于Spark的并行化遗传算法。Spark是一种快速、通用的并行计算框架，它的核心是一种弹性分布式数据集RDD。Spark通过对RDD进行并行切片，然后分发到集群中的多个节点上完成相应的变换操作，最后由行动操作触发所有的运算。Spark的这种运算方式非常适合并行化遗传算法的实现。
试题库自动组卷是运用信息处理技术，从试题库中自动选择试题组成试卷的。自动组卷的主要难题是如何保证生成的试卷能最大程度地满足用户的需要，并具有随机性、科学性、合理性。因此需要选择一个高效的自动组卷算法。
目前，已有运用遗传算法进行自动组卷的方法。遗传算法是一种模拟自然界适者生存的淘汰选择方式和遗传机制的计算机随机优化算法。遗传算法的遗传操作主要有 ：选择、交叉、变异。遗传算法需要采用某种编码方式将解空间映射到编码空间。类似于生物染色体结构，这样容易用生物遗传理论解释，各种遗传操作也易于实现。因此，编码理论是遗传算法效率的重要决定因素之一。二进制编码是最常用的编码方式，算子处理的模式较多也较易于实现。但是，自动组卷过程中，采用二进制编码的方式往往效率较低。
因此，在利用遗传算法进行自动组卷的过程中，就需要选取合适的编码方式。另外，也需要对遗传操作进行改进，以实现更好的组卷效果。
具体实施方式
本发明旨在解决上面描述的问题。本发明的目的是提供一种利用遗传算法的自动组卷方法，根据本发明的一个方面，本发明提供了一种利用遗传算法的自动组卷方法，所述自动组卷方法包括以下步骤 ：（1） 根据设定的条件生成初始种群，所述初始种群中包括 n 个个体，其中 n 为正整数，每个个体的生成方法如下 ：将题库中的试题根据题型形成多个题型集合并将每个题型集合中的试题按照实数方式排序，从各个题型集合中选取设定数量的试题，并按照相同题型集合中的试题序号相邻的方式将所选取试题的序号组成实数序列，所述实数序列即為种群中的个体 ；（2） 计算每个所述个体的适应度函数值，如果有个体的适应度函数值符合优化准则，则选中适应度函数值符合优化准则的个体并结束所述自动组卷方法，如果没有个体适应度函数值符合优化准则，则执行步骤 （3） ；（3） 进行遗传操作，所述遗传操作包括选择操作、交叉操作、变异操作，其中，根据所述个体的适应度函数值对种群中的个体进行选择操作，根据题型集合将所述实数序列分成相应的序列段，根据序列段进行交叉操作 ；（4） 由所述遗传操作生成的新个体生成新一代的种群，并返回到步骤 （2）。
其中，所述步骤 （2） 中的述适应度函数值的计算公式为：
其中，Psi 为该个体适应度函数值，fi 为每个条件要素的权值，Fi 为每个条件要素的适应度，M 为所有条件要素的个数，且 fi 满足：
其中，所述条件要素的适应度 Fi 的计算公式为 Fi = 1-（|ai-bi|/bi），bi 为条件要素的要求得分，ai 为条件要素的实际得分。
其中，所述条件要素包括试卷难度、分值分布。
其中，所述步骤 （3） 包括 ：（31） 对种群中的个体进行选择操作，得到第一个体，然后对种群中剩下的个体进行选择操作，得到第二个体 ；（32） 将所述第一个体和所述第二个体进行交叉操作，得到两个交叉后的个体 ；（33） 对所述两个交叉后的个体进行变异操作，得到两个新个体 ；（34） 重复步骤 （31）、步骤 （32） 和步骤 （33），直到生成满足种群中个体数量的所有新个体。
其中，所述步骤 （31） 中的选择操作包括 ：（311） 累加种群中每个所述个体的适应度函数值，得到总值 ；（312）生成随机数，所述随机数大于等于零，小于等于1 ；（313）将所述总值乘以所述随机数，得到转轮值 ；（314） 依次累加种群中每个所述个体的适应度函数值，得到与所述个体相应的总值′，如果所述总值′大于或等于所述转轮值，则与所述总值′相对应的所述个体被选中。
其中，所述步骤 （32） 包括 ：（321） 随机选择一个题型集合 ；（322） 将选择操作得到的所述第一个体和所述第二个体中与所选择的题型集合相应的序列段进行交换，从而得到所述两个交叉后的个体。
其中，在所述步骤 （1） 中，所述设定的条件包括 ：总体量、章节分值分配、题型分值分配。
其中，在所述步骤 （2） 中，所述优化准则为个体的适应度函数值大于设定的阈值。 本发明的利用遗传算法的自动组卷方法，在遗传算法中引入有条件生产初始种群、对个体进行实数编码，以及在交叉操作中进行分段交叉的方式，使得所利用的遗传算法搜索速度快，尽量避免同一试卷中出现同一考查点多道题的情况，使试卷的覆盖面广，组出更合理的试卷。此外，该自动组卷方法大大减少教师在考试命题中的工作量，同时还可以避免由于人为因素造成的偏差，在对目前的组卷系统进行分析了解的基础上结合实际命题经验，并利用了遗传算法的全局寻优和收敛速度快的特点。
参照附图来阅读对于示例性实施例的以下描述，本发明的其他特征和优点将变得清晰。
附图说明
并入到说明书中并且构成说明书的一部分的附图示出了本发明的实施例，并且与描述一起用于解释本发明的原理。在这些附图中，类似的附图标记用于表示类似的要素。下面描述中的附图是本发明的一些实施例，而不是全部实施例。对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，可以根据这些附图获得其他的附图。
图 1 示例性地示出了根据本发明的利用遗传算法的自动组卷方法的流程图。
技术方案：基于Spark的并行化遗传算法智能组卷方法，包括如下步骤：
（1）适应度值计算并行化：随机生成初始种群，从初始种群创建Spark的RDD，并将RDD划分为多个分区分布到集群的多个节点中，每个分区对应一个子种群，各个子种群在各自的节点上进行适应度值的计算，并将计算结果收回到Spark的主节点上；
（2）遗传操作并行化：将带有适应度值的种群划分为多个子种群，并作为RDD的多个分区再次分布到集群的多个节点中，各个子种群在各自的节点上进行独立进化，在进化满足终止条件时收集RDD不同分区中的最好的个体，并将结果返回到Spark的主节点上。
进一步的，步骤（1）具体包括如下子步骤：
（1.1）随机生成初始种群，随机生成的初始种群通过Spark的parallelize函数转换为种群RDD，并将种群RDD划分为多个分区分布到集群的多个节点中，RDD包含的分区的数量，以及每个分区包含的个体的数量，由Spark自动分配；
（1.2）通过Spark的mapPartitions（assessFitness（））函数将种群RDD转换为适应度值RDD，该RDD包含键值对，其中key是一个个体，value是该个体的适应度值，函数assessFitness（）用于计算个体的适应度值，它被分布到集群中不同的节点上并行计算；
（1.3）Spark的collect函数触发Spark的运算流程，完成步骤（1.2）中的所述转换，并将这些键值对收回到主节点上。
进一步的，步骤（2）具体包括如下子步驟：
（2.1）将带有适应度值的种群再次通过Spark的parallelize函数变换为种群RDD；
（2.2）通过Spark的mapPartitions（evolution（））函数将种群RDD中的各个子种群分布到Spark集群的不同的工作节点上，并转换为进化RDD，函数evolution（）用于执行遗传操作，被分布到集群中不同的节点上并行进化，所述遗传操作包括选择、交叉和变异；
（2.3）通过Spark的map（getBest（））函数将进化RDD转换为最优个体RDD，该RDD包含键值对，其中key是一个键值对，value是发现解决方案时的进化代数；函数getBest（）用于获得每个子种群中的最好个体，被分布到集群中不同的节点上并行执行；
（2.4）Spark的collect函数触发Spark的运算流程，将步骤（2.3）中每个子种群中的最好个体都收回到主节点上，找出其中最好的一个，作为最优结果输出。
进一步的，步骤（2.2）中所述遗传操作具体为：选择操作采用适应度值比例法；交叉操作采用多点随机交叉；变异操作采用多点随机变异。
有益效果：本发明利用Spark的基于内存的计算模型，充分利用Spark分布式并行计算能力，从适应度值计算和遗传操作两方面将遗传算法并行化，提高了遗传算法的性能。大提高了通过遗传算法获取最优个体的效率，使得出卷的效率更高，成功率更高。
备注：
parallelize：函数来创建并行集合。
mapPartition：为每个partition创建一个链接。
assessFitness：用于计算个体的适应度值。
collect：收集键值对到主节点上。
evolution：执行遗传操作，并行进化。
getBest：获得每个子种群中的最好个体。
关键词：计算机辅助教育；智能组卷；遗传算法；
主要内容
随着计算机应用技术的不断发展，由计算机与教育相结合而产生的计算机辅助教育系统得到了快速发展。在目前的素质教育下，考试仍然是衡量教师教学能力和学生学习成绩的主要衡量标准之一，同时不同层次的考试对试卷衡量标准也是不尽相同的。那么，如何依靠算法组出一套科学合理且高质量的试卷是评定计算机与教育结合效果的手段之一。因此，对高效智能组卷算法的研究是非常具有实际应用价值的。
遗传算法是一种模拟自然界生物进化过程与机制的元启发式搜索技术，被广泛应用于求解复杂的优化问题。通常，穷尽搜索完整的输入空间是不可行的，遗传算法可以用来通过搜索较小的输入空间，在合理的时间里求出好的问题解。传统遗传算法通过顺序执行选择、交叉、变异等遗传操作，寻找问题的最优解。传统遗传算法用于求解复杂的优化问题时，通常需要较长的计算时间。
为了解决遗传算法带来的计算性能问题，本发明提供一种基于Spark的并行化遗传算法。Spark是一种快速、通用的并行计算框架，它的核心是一种弹性分布式数据集RDD。Spark通过对RDD进行并行切片，然后分发到集群中的多个节点上完成相应的变换操作，最后由行动操作触发所有的运算。Spark的这种运算方式非常适合并行化遗传算法的实现。
试题库自动组卷是运用信息处理技术，从试题库中自动选择试题组成试卷的。自动组卷的主要难题是如何保证生成的试卷能最大程度地满足用户的需要，并具有随机性、科学性、合理性。因此需要选择一个高效的自动组卷算法。
目前，已有运用遗传算法进行自动组卷的方法。遗传算法是一种模拟自然界适者生存的淘汰选择方式和遗传机制的计算机随机优化算法。遗传算法的遗传操作主要有 ：选择、交叉、变异。遗传算法需要采用某种编码方式将解空间映射到编码空间。类似于生物染色体结构，这样容易用生物遗传理论解释，各种遗传操作也易于实现。因此，编码理论是遗传算法效率的重要决定因素之一。二进制编码是最常用的编码方式，算子处理的模式较多也较易于实现。但是，自动组卷过程中，采用二进制编码的方式往往效率较低。
因此，在利用遗传算法进行自动组卷的过程中，就需要选取合适的编码方式。另外，也需要对遗传操作进行改进，以实现更好的组卷效果。
具体实施方式
本发明旨在解决上面描述的问题。本发明的目的是提供一种利用遗传算法的自动组卷方法，根据本发明的一个方面，本发明提供了一种利用遗传算法的自动组卷方法，所述自动组卷方法包括以下步骤 ：（1） 根据设定的条件生成初始种群，所述初始种群中包括 n 个个体，其中 n 为正整数，每个个体的生成方法如下 ：将题库中的试题根据题型形成多个题型集合并将每个题型集合中的试题按照实数方式排序，从各个题型集合中选取设定数量的试题，并按照相同题型集合中的试题序号相邻的方式将所选取试题的序号组成实数序列，所述实数序列即為种群中的个体 ；（2） 计算每个所述个体的适应度函数值，如果有个体的适应度函数值符合优化准则，则选中适应度函数值符合优化准则的个体并结束所述自动组卷方法，如果没有个体适应度函数值符合优化准则，则执行步骤 （3） ；（3） 进行遗传操作，所述遗传操作包括选择操作、交叉操作、变异操作，其中，根据所述个体的适应度函数值对种群中的个体进行选择操作，根据题型集合将所述实数序列分成相应的序列段，根据序列段进行交叉操作 ；（4） 由所述遗传操作生成的新个体生成新一代的种群，并返回到步骤 （2）。
其中，所述步骤 （2） 中的述适应度函数值的计算公式为：
其中，Psi 为该个体适应度函数值，fi 为每个条件要素的权值，Fi 为每个条件要素的适应度，M 为所有条件要素的个数，且 fi 满足：
其中，所述条件要素的适应度 Fi 的计算公式为 Fi = 1-（|ai-bi|/bi），bi 为条件要素的要求得分，ai 为条件要素的实际得分。
其中，所述条件要素包括试卷难度、分值分布。
其中，所述步骤 （3） 包括 ：（31） 对种群中的个体进行选择操作，得到第一个体，然后对种群中剩下的个体进行选择操作，得到第二个体 ；（32） 将所述第一个体和所述第二个体进行交叉操作，得到两个交叉后的个体 ；（33） 对所述两个交叉后的个体进行变异操作，得到两个新个体 ；（34） 重复步骤 （31）、步骤 （32） 和步骤 （33），直到生成满足种群中个体数量的所有新个体。
其中，所述步骤 （31） 中的选择操作包括 ：（311） 累加种群中每个所述个体的适应度函数值，得到总值 ；（312）生成随机数，所述随机数大于等于零，小于等于1 ；（313）将所述总值乘以所述随机数，得到转轮值 ；（314） 依次累加种群中每个所述个体的适应度函数值，得到与所述个体相应的总值′，如果所述总值′大于或等于所述转轮值，则与所述总值′相对应的所述个体被选中。
其中，所述步骤 （32） 包括 ：（321） 随机选择一个题型集合 ；（322） 将选择操作得到的所述第一个体和所述第二个体中与所选择的题型集合相应的序列段进行交换，从而得到所述两个交叉后的个体。
其中，在所述步骤 （1） 中，所述设定的条件包括 ：总体量、章节分值分配、题型分值分配。
其中，在所述步骤 （2） 中，所述优化准则为个体的适应度函数值大于设定的阈值。 本发明的利用遗传算法的自动组卷方法，在遗传算法中引入有条件生产初始种群、对个体进行实数编码，以及在交叉操作中进行分段交叉的方式，使得所利用的遗传算法搜索速度快，尽量避免同一试卷中出现同一考查点多道题的情况，使试卷的覆盖面广，组出更合理的试卷。此外，该自动组卷方法大大减少教师在考试命题中的工作量，同时还可以避免由于人为因素造成的偏差，在对目前的组卷系统进行分析了解的基础上结合实际命题经验，并利用了遗传算法的全局寻优和收敛速度快的特点。
参照附图来阅读对于示例性实施例的以下描述，本发明的其他特征和优点将变得清晰。
附图说明
并入到说明书中并且构成说明书的一部分的附图示出了本发明的实施例，并且与描述一起用于解释本发明的原理。在这些附图中，类似的附图标记用于表示类似的要素。下面描述中的附图是本发明的一些实施例，而不是全部实施例。对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，可以根据这些附图获得其他的附图。
图 1 示例性地示出了根据本发明的利用遗传算法的自动组卷方法的流程图。
技术方案：基于Spark的并行化遗传算法智能组卷方法，包括如下步骤：
（1）适应度值计算并行化：随机生成初始种群，从初始种群创建Spark的RDD，并将RDD划分为多个分区分布到集群的多个节点中，每个分区对应一个子种群，各个子种群在各自的节点上进行适应度值的计算，并将计算结果收回到Spark的主节点上；
（2）遗传操作并行化：将带有适应度值的种群划分为多个子种群，并作为RDD的多个分区再次分布到集群的多个节点中，各个子种群在各自的节点上进行独立进化，在进化满足终止条件时收集RDD不同分区中的最好的个体，并将结果返回到Spark的主节点上。
进一步的，步骤（1）具体包括如下子步骤：
（1.1）随机生成初始种群，随机生成的初始种群通过Spark的parallelize函数转换为种群RDD，并将种群RDD划分为多个分区分布到集群的多个节点中，RDD包含的分区的数量，以及每个分区包含的个体的数量，由Spark自动分配；
（1.2）通过Spark的mapPartitions（assessFitness（））函数将种群RDD转换为适应度值RDD，该RDD包含键值对
（1.3）Spark的collect函数触发Spark的运算流程，完成步骤（1.2）中的所述转换，并将这些键值对收回到主节点上。
进一步的，步骤（2）具体包括如下子步驟：
（2.1）将带有适应度值的种群再次通过Spark的parallelize函数变换为种群RDD；
（2.2）通过Spark的mapPartitions（evolution（））函数将种群RDD中的各个子种群分布到Spark集群的不同的工作节点上，并转换为进化RDD，函数evolution（）用于执行遗传操作，被分布到集群中不同的节点上并行进化，所述遗传操作包括选择、交叉和变异；
（2.3）通过Spark的map（getBest（））函数将进化RDD转换为最优个体RDD，该RDD包含键值对
（2.4）Spark的collect函数触发Spark的运算流程，将步骤（2.3）中每个子种群中的最好个体都收回到主节点上，找出其中最好的一个，作为最优结果输出。
进一步的，步骤（2.2）中所述遗传操作具体为：选择操作采用适应度值比例法；交叉操作采用多点随机交叉；变异操作采用多点随机变异。
有益效果：本发明利用Spark的基于内存的计算模型，充分利用Spark分布式并行计算能力，从适应度值计算和遗传操作两方面将遗传算法并行化，提高了遗传算法的性能。大提高了通过遗传算法获取最优个体的效率，使得出卷的效率更高，成功率更高。
备注：
parallelize：函数来创建并行集合。
mapPartition：为每个partition创建一个链接。
assessFitness：用于计算个体的适应度值。
collect：收集键值对到主节点上。
evolution：执行遗传操作，并行进化。
getBest：获得每个子种群中的最好个体。