浅析遗传算法在智能组卷系统中的应用

龚利　史杨

摘要：该文介绍了遗传算法的基本原理和构成要素，分析了遗传算法的特点，在遗传算法的研究基础上，找到了一个很好的策略过程应用于智能试卷，提高运行的速度，避免了标准算法容易早熟现象，具有更好的健壮性，是一种很有发展潜力的优化方法。

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

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）16-3879-02

Abstract： This paper introduces the basic principle and constituent elements of genetic algorithm， while analysing the characteristics of genetic algorithm. I find a better strategy in the process of the intelligent test paper generation through the study of genetic algorithm .This algorithm improve the speed of the operation and avoid prone to premature phenomenon of the standard algorithm， It has a better robustness， it is a optimization method with development potential.

Key words： genetic algorithm； intelligent test paper generation

在大部分的试卷系统的开发中，智能组卷应该是整个系统的关键因素。在完成试卷系统开发后，如果用户使用智能组卷操作，首先要输入的相应参数值进行设置约束条件，然后系统根据参数值被最符合需求的试卷，最后生成试卷满足用户的需求。定义转换的参数，这些参数和算法，称为组策略。该文试图用遗传算法研究智能组卷，找到最好的组策略。

1 什么是遗传算法

遗传算法基于自然群体遗传进化机制，是模拟生物的遗传、进化过程的自然环境，最后形成的一种自适应、全局优化概率的搜索算法，这是一种比较高效的探索算法。它将可能的解决方案的问题域，作为一个个体或染色体组，并且对每个编码的字符串形式模拟达尔文的遗传选择和生物进化的自然选择过程[1]。

基于遗传组重复的操作，根据适应度函数来评价每个预定的目标，根据适者生存，优胜劣汰的进化规则，不断得到更好的优化，同时并行全局搜索方法搜索最好的个人组织优化，最终达到满足要求的最优解。

2 遗传算法的5个基本要素

遗传算法的5个基本要素为：初始种群、染色体编码、适应度函数、控制参数和遗传算子。具体如下：

1） 初始种群：从初始种群开始，首先对种群初始化， 一个问题的最优解可能是解决空间的初始种群。在解决的过程中进行遗传操作，初始化的种群是第一代，然后第二、第三代……第N代，直到你找到最优的解决方案。它是模拟自然进化的选择机制和消除算法，是解决这一问题的解决方案。

2） 染色体编码：先对染色体编码，一般有二进制编码、浮点编码、自然数编码、编码、交叉编码方法等染色体编码。

3） 适应度函数：在搜索的过程中，首先计算每个适应值，然后对比终止条件时，如果条件满足，就找到最优的解决方案，然后退出搜索；否则，将继续搜索，直到找到最优的解决方案。通常个体适应值较高，表明个体越好，被选的概率就越高。

4） 控制参数：一般来说根据初始种群的大小和算法实现迭代等方式，对于特定的问题，对应的控制参数也不同。

5） 遗传算子：在具体的搜索的进程中，先算出适应值，按照算法选择相应的机制，选择变异操作和个体交叉，最后生成新的个体将保持个体的多样性。遗传算法的流程图如图1所示。

3 遗传算法的特点

1）遗传算法不需要求导、或者其他辅助知识。只需要确定目标函数和适应度函数值的计算，可以指导搜索过程朝着一个更好的解决方案的搜索空间区域，加大了遗传算法的应用。

2）遗传算法具有自学习、自组织和自适应的特点。遗传算法自动根据算法来计算的实现个体选择和繁殖，产生新的种群，并最终找到最优和次优的解决方案，具有自学习、自组织和自适应能力【2】。

3）遗传算法若给予一个特定的问题，就会产生很多的解决方案，最后可以由用户决定。

由于遗传算法可以通过整体搜索策略和优化搜索方法，只要确定目标函数，并确定适应度函数和一系列的约束，就可以基于系统解决一般约束优化问题。不需要求导、不需要其他辅助知识，并且可以更好的减少算法的盲目性和随机性，所以可以满足网络考试系统多样的组卷要求。

2 遗传算法在智能组卷中的研究

1）什么是智能组卷

智能组卷是根据老师的要求生成满足要求的，对于每一个学生都是公平公正的试卷。大多数考试系统采用的是手动组卷，这种方式效率低，并且消耗老师们大量精力来组建的试卷也不能完全满足考试的需求。因此，许多高校正在努力开发的网络考试系统，大多要求实现能够进行智能组卷，从而将将教师摆脱沉重的组卷任务，提高教学质量和考试效率。现在很多基于智能组卷算法，主要基于是否优先策略、随机策略、回溯试探策略是本文将关注的遗传算法，智能组卷的步骤是相似的。

2）遗传算法在智能组卷系统的应用

在大多数智能组卷系统中，遗传算法解决问题基本思想是：对于某个问题，首先随机获得N×n（N>=2，n>=2）个样本，然后把这些样本拆分成N个子种群，这样一来每个子种群就包含n个样本，我们对每个子种群进行单独运行各自的遗传算法，并且达到一定次数。

将这样的每个种群记为GAi（i=1，2， 3，4…，N）。根据算法当每个子种群的遗传算法开始循环运行到一定的代数以后，通过二维数组G[1..N，1..n]记录N个遗传算法的计算的结果，则[G[i，j]（i=1...M，j=1...m）]表示GAi的结果种群的第j个个体。同时采用数组K[1..N]记录这N个结果种群的平均适应度值，K[i]表示GAi的结果种群平均适应度值。其应用于智能组卷系统的遗传算法流程图如图2。

通过算法流程图我们可以看到，这种遗传算法在和上一层的个体交换上，它不需要人工控制交换一个相应的个体，也不需要设置某个特定的处理器来交换出某个体。这不仅改善了遗传算法与遗传算法在每个处理器上运行，同时每个处理器不断产生新种群的更高一层的运算和控制。

3 小结

本文主要研究了智能试卷算法在组卷系统中的应用。首先介绍了什么是遗传算法，并介绍了遗传算法5个基本要素和特点；然后介绍了什么是智能组卷，重点介绍了遗传算法如何应用于智能组卷系统，给出了算法的流程图。通过对遗传算法解决问题的算法分析，我们发现遗传算法在智能试卷过程中，能够提高系统的运算速度，避免了标准算法容易早熟现象，具有更好的健壮性，是一种很有发展潜力的优化方法。

参考文献：

[1] 史杨.基于改进遗传算法的智能组卷系统研究[D].武汉：武汉理工大学，2011：100-135.

[2] 刘洋.算法在数字滤波器设计中的应用研究[D].成都：电子科技大学，2004：60-89.

[3] 宋照红.通用智能实时反垃圾邮件机的设计与实现[D].成都：电子科技大学，2004：75-96.endprint

摘要：该文介绍了遗传算法的基本原理和构成要素，分析了遗传算法的特点，在遗传算法的研究基础上，找到了一个很好的策略过程应用于智能试卷，提高运行的速度，避免了标准算法容易早熟现象，具有更好的健壮性，是一种很有发展潜力的优化方法。

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

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）16-3879-02

Abstract： This paper introduces the basic principle and constituent elements of genetic algorithm， while analysing the characteristics of genetic algorithm. I find a better strategy in the process of the intelligent test paper generation through the study of genetic algorithm .This algorithm improve the speed of the operation and avoid prone to premature phenomenon of the standard algorithm， It has a better robustness， it is a optimization method with development potential.

Key words： genetic algorithm； intelligent test paper generation

在大部分的试卷系统的开发中，智能组卷应该是整个系统的关键因素。在完成试卷系统开发后，如果用户使用智能组卷操作，首先要输入的相应参数值进行设置约束条件，然后系统根据参数值被最符合需求的试卷，最后生成试卷满足用户的需求。定义转换的参数，这些参数和算法，称为组策略。该文试图用遗传算法研究智能组卷，找到最好的组策略。

1 什么是遗传算法

遗传算法基于自然群体遗传进化机制，是模拟生物的遗传、进化过程的自然环境，最后形成的一种自适应、全局优化概率的搜索算法，这是一种比较高效的探索算法。它将可能的解决方案的问题域，作为一个个体或染色体组，并且对每个编码的字符串形式模拟达尔文的遗传选择和生物进化的自然选择过程[1]。

基于遗传组重复的操作，根据适应度函数来评价每个预定的目标，根据适者生存，优胜劣汰的进化规则，不断得到更好的优化，同时并行全局搜索方法搜索最好的个人组织优化，最终达到满足要求的最优解。

2 遗传算法的5个基本要素

遗传算法的5个基本要素为：初始种群、染色体编码、适应度函数、控制参数和遗传算子。具体如下：

1） 初始种群：从初始种群开始，首先对种群初始化， 一个问题的最优解可能是解决空间的初始种群。在解决的过程中进行遗传操作，初始化的种群是第一代，然后第二、第三代……第N代，直到你找到最优的解决方案。它是模拟自然进化的选择机制和消除算法，是解决这一问题的解决方案。

2） 染色体编码：先对染色体编码，一般有二进制编码、浮点编码、自然数编码、编码、交叉编码方法等染色体编码。

3） 适应度函数：在搜索的过程中，首先计算每个适应值，然后对比终止条件时，如果条件满足，就找到最优的解决方案，然后退出搜索；否则，将继续搜索，直到找到最优的解决方案。通常个体适应值较高，表明个体越好，被选的概率就越高。

4） 控制参数：一般来说根据初始种群的大小和算法实现迭代等方式，对于特定的问题，对应的控制参数也不同。

5） 遗传算子：在具体的搜索的进程中，先算出适应值，按照算法选择相应的机制，选择变异操作和个体交叉，最后生成新的个体将保持个体的多样性。遗传算法的流程图如图1所示。

3 遗传算法的特点

1）遗传算法不需要求导、或者其他辅助知识。只需要确定目标函数和适应度函数值的计算，可以指导搜索过程朝着一个更好的解决方案的搜索空间区域，加大了遗传算法的应用。

2）遗传算法具有自学习、自组织和自适应的特点。遗传算法自动根据算法来计算的实现个体选择和繁殖，产生新的种群，并最终找到最优和次优的解决方案，具有自学习、自组织和自适应能力【2】。

3）遗传算法若给予一个特定的问题，就会产生很多的解决方案，最后可以由用户决定。

由于遗传算法可以通过整体搜索策略和优化搜索方法，只要确定目标函数，并确定适应度函数和一系列的约束，就可以基于系统解决一般约束优化问题。不需要求导、不需要其他辅助知识，并且可以更好的减少算法的盲目性和随机性，所以可以满足网络考试系统多样的组卷要求。

2 遗传算法在智能组卷中的研究

1）什么是智能组卷

智能组卷是根据老师的要求生成满足要求的，对于每一个学生都是公平公正的试卷。大多数考试系统采用的是手动组卷，这种方式效率低，并且消耗老师们大量精力来组建的试卷也不能完全满足考试的需求。因此，许多高校正在努力开发的网络考试系统，大多要求实现能够进行智能组卷，从而将将教师摆脱沉重的组卷任务，提高教学质量和考试效率。现在很多基于智能组卷算法，主要基于是否优先策略、随机策略、回溯试探策略是本文将关注的遗传算法，智能组卷的步骤是相似的。

2）遗传算法在智能组卷系统的应用

在大多数智能组卷系统中，遗传算法解决问题基本思想是：对于某个问题，首先随机获得N×n（N>=2，n>=2）个样本，然后把这些样本拆分成N个子种群，这样一来每个子种群就包含n个样本，我们对每个子种群进行单独运行各自的遗传算法，并且达到一定次数。

将这样的每个种群记为GAi（i=1，2， 3，4…，N）。根据算法当每个子种群的遗传算法开始循环运行到一定的代数以后，通过二维数组G[1..N，1..n]记录N个遗传算法的计算的结果，则[G[i，j]（i=1...M，j=1...m）]表示GAi的结果种群的第j个个体。同时采用数组K[1..N]记录这N个结果种群的平均适应度值，K[i]表示GAi的结果种群平均适应度值。其应用于智能组卷系统的遗传算法流程图如图2。

通过算法流程图我们可以看到，这种遗传算法在和上一层的个体交换上，它不需要人工控制交换一个相应的个体，也不需要设置某个特定的处理器来交换出某个体。这不仅改善了遗传算法与遗传算法在每个处理器上运行，同时每个处理器不断产生新种群的更高一层的运算和控制。

3 小结

本文主要研究了智能试卷算法在组卷系统中的应用。首先介绍了什么是遗传算法，并介绍了遗传算法5个基本要素和特点；然后介绍了什么是智能组卷，重点介绍了遗传算法如何应用于智能组卷系统，给出了算法的流程图。通过对遗传算法解决问题的算法分析，我们发现遗传算法在智能试卷过程中，能够提高系统的运算速度，避免了标准算法容易早熟现象，具有更好的健壮性，是一种很有发展潜力的优化方法。

参考文献：

[1] 史杨.基于改进遗传算法的智能组卷系统研究[D].武汉：武汉理工大学，2011：100-135.

[2] 刘洋.算法在数字滤波器设计中的应用研究[D].成都：电子科技大学，2004：60-89.

[3] 宋照红.通用智能实时反垃圾邮件机的设计与实现[D].成都：电子科技大学，2004：75-96.endprint

摘要：该文介绍了遗传算法的基本原理和构成要素，分析了遗传算法的特点，在遗传算法的研究基础上，找到了一个很好的策略过程应用于智能试卷，提高运行的速度，避免了标准算法容易早熟现象，具有更好的健壮性，是一种很有发展潜力的优化方法。

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

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）16-3879-02

Abstract： This paper introduces the basic principle and constituent elements of genetic algorithm， while analysing the characteristics of genetic algorithm. I find a better strategy in the process of the intelligent test paper generation through the study of genetic algorithm .This algorithm improve the speed of the operation and avoid prone to premature phenomenon of the standard algorithm， It has a better robustness， it is a optimization method with development potential.

Key words： genetic algorithm； intelligent test paper generation

在大部分的试卷系统的开发中，智能组卷应该是整个系统的关键因素。在完成试卷系统开发后，如果用户使用智能组卷操作，首先要输入的相应参数值进行设置约束条件，然后系统根据参数值被最符合需求的试卷，最后生成试卷满足用户的需求。定义转换的参数，这些参数和算法，称为组策略。该文试图用遗传算法研究智能组卷，找到最好的组策略。

1 什么是遗传算法

遗传算法基于自然群体遗传进化机制，是模拟生物的遗传、进化过程的自然环境，最后形成的一种自适应、全局优化概率的搜索算法，这是一种比较高效的探索算法。它将可能的解决方案的问题域，作为一个个体或染色体组，并且对每个编码的字符串形式模拟达尔文的遗传选择和生物进化的自然选择过程[1]。

基于遗传组重复的操作，根据适应度函数来评价每个预定的目标，根据适者生存，优胜劣汰的进化规则，不断得到更好的优化，同时并行全局搜索方法搜索最好的个人组织优化，最终达到满足要求的最优解。

2 遗传算法的5个基本要素

遗传算法的5个基本要素为：初始种群、染色体编码、适应度函数、控制参数和遗传算子。具体如下：

1） 初始种群：从初始种群开始，首先对种群初始化， 一个问题的最优解可能是解决空间的初始种群。在解决的过程中进行遗传操作，初始化的种群是第一代，然后第二、第三代……第N代，直到你找到最优的解决方案。它是模拟自然进化的选择机制和消除算法，是解决这一问题的解决方案。

2） 染色体编码：先对染色体编码，一般有二进制编码、浮点编码、自然数编码、编码、交叉编码方法等染色体编码。

3） 适应度函数：在搜索的过程中，首先计算每个适应值，然后对比终止条件时，如果条件满足，就找到最优的解决方案，然后退出搜索；否则，将继续搜索，直到找到最优的解决方案。通常个体适应值较高，表明个体越好，被选的概率就越高。

4） 控制参数：一般来说根据初始种群的大小和算法实现迭代等方式，对于特定的问题，对应的控制参数也不同。

5） 遗传算子：在具体的搜索的进程中，先算出适应值，按照算法选择相应的机制，选择变异操作和个体交叉，最后生成新的个体将保持个体的多样性。遗传算法的流程图如图1所示。

3 遗传算法的特点

1）遗传算法不需要求导、或者其他辅助知识。只需要确定目标函数和适应度函数值的计算，可以指导搜索过程朝着一个更好的解决方案的搜索空间区域，加大了遗传算法的应用。

2）遗传算法具有自学习、自组织和自适应的特点。遗传算法自动根据算法来计算的实现个体选择和繁殖，产生新的种群，并最终找到最优和次优的解决方案，具有自学习、自组织和自适应能力【2】。

3）遗传算法若给予一个特定的问题，就会产生很多的解决方案，最后可以由用户决定。

由于遗传算法可以通过整体搜索策略和优化搜索方法，只要确定目标函数，并确定适应度函数和一系列的约束，就可以基于系统解决一般约束优化问题。不需要求导、不需要其他辅助知识，并且可以更好的减少算法的盲目性和随机性，所以可以满足网络考试系统多样的组卷要求。

2 遗传算法在智能组卷中的研究

1）什么是智能组卷

智能组卷是根据老师的要求生成满足要求的，对于每一个学生都是公平公正的试卷。大多数考试系统采用的是手动组卷，这种方式效率低，并且消耗老师们大量精力来组建的试卷也不能完全满足考试的需求。因此，许多高校正在努力开发的网络考试系统，大多要求实现能够进行智能组卷，从而将将教师摆脱沉重的组卷任务，提高教学质量和考试效率。现在很多基于智能组卷算法，主要基于是否优先策略、随机策略、回溯试探策略是本文将关注的遗传算法，智能组卷的步骤是相似的。

2）遗传算法在智能组卷系统的应用

在大多数智能组卷系统中，遗传算法解决问题基本思想是：对于某个问题，首先随机获得N×n（N>=2，n>=2）个样本，然后把这些样本拆分成N个子种群，这样一来每个子种群就包含n个样本，我们对每个子种群进行单独运行各自的遗传算法，并且达到一定次数。

将这样的每个种群记为GAi（i=1，2， 3，4…，N）。根据算法当每个子种群的遗传算法开始循环运行到一定的代数以后，通过二维数组G[1..N，1..n]记录N个遗传算法的计算的结果，则[G[i，j]（i=1...M，j=1...m）]表示GAi的结果种群的第j个个体。同时采用数组K[1..N]记录这N个结果种群的平均适应度值，K[i]表示GAi的结果种群平均适应度值。其应用于智能组卷系统的遗传算法流程图如图2。

通过算法流程图我们可以看到，这种遗传算法在和上一层的个体交换上，它不需要人工控制交换一个相应的个体，也不需要设置某个特定的处理器来交换出某个体。这不仅改善了遗传算法与遗传算法在每个处理器上运行，同时每个处理器不断产生新种群的更高一层的运算和控制。

3 小结

本文主要研究了智能试卷算法在组卷系统中的应用。首先介绍了什么是遗传算法，并介绍了遗传算法5个基本要素和特点；然后介绍了什么是智能组卷，重点介绍了遗传算法如何应用于智能组卷系统，给出了算法的流程图。通过对遗传算法解决问题的算法分析，我们发现遗传算法在智能试卷过程中，能够提高系统的运算速度，避免了标准算法容易早熟现象，具有更好的健壮性，是一种很有发展潜力的优化方法。

参考文献：

[1] 史杨.基于改进遗传算法的智能组卷系统研究[D].武汉：武汉理工大学，2011：100-135.

[2] 刘洋.算法在数字滤波器设计中的应用研究[D].成都：电子科技大学，2004：60-89.

[3] 宋照红.通用智能实时反垃圾邮件机的设计与实现[D].成都：电子科技大学，2004：75-96.endprint