论文部分内容阅读
[摘要]本文利用概率论与数理统计的原理，对采用遗传算法生成试卷时的交叉概率进行了自适应改进。这一方法对于生成试卷时，试题的快速进化将起到重要的促进作用。
[关键字]遗传算法 交叉概率 自适应改进
1.引言
随着信息技术和人工智能的发展，计算机辅助教学逐步走向普及， 题库系统成为计算机辅助教学系统中一个重要组成部分。遗传算法生成试卷是其中的一种新型的、模拟自然界生物进化过程的随机搜索、全局优化算法。从数学角度看，遗传算法实质上是一种搜索寻优技术。它从某一初始群体出发，按照一定的操作规则，不断迭代计算，逐步逼近最优解。
从现有的一些专用的自动组卷系统来看，常见的组卷方式大致采用误差补偿法、随机抽取法、回溯试探法。误差补偿算法是指在试题生成过程中，当有些约束条件无法满足的时候，适当地放宽约束条件，让试题在允许的误差范围内生成试卷；随机抽取算法是根据状态空间的控制指标，随机地抽取试题，重复此过程直到组卷完毕或己无法从题库中抽取满足指标的试题为止；回溯试探算法是一种有条件的深度优先算法，对于约束集的维数较小的组卷问题来说，组卷成功率较高。它是将随机取法得到的每一种状态都记录下来，当搜索失败时释放上一次记录的状态类型，然后依据一定的规律变换一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成完毕或者退回到出发点为止。
遗传算法（GeneticAlgorithm， GA）是近几年发展起来的一种新型的、模拟自然界生物进化过程的随机搜索、全局优化算法，该算法是由美国Michigan大学的John H.Holland教授于1975年首次提出来的，他采用简单的编码技术来表示各种复杂的结构，并通过对一组编码进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索方向。由于是采用种群的方式组织搜索，这使得它可以同时搜索解空间内多个区域，而且用种群组织搜索方式使得遗传算法特别适合大规模并行。在具有自组织、自适应、自学习等特征的同时，还具有不受搜索空间的限制性条件的约束、不需要辅助信息、搜索过程不易陷入局部最优点的特点。这些特点使得遗传算法不但可以获得较高的效率，而且具有简单、易于操作和通用的特点，从数学角度看，遗传算法实质上是一种搜索寻优技术。它从某一初始群体出发，按照一定的操作规则，不断迭代计算，逐步逼近最优解。
2.遗传算法基本流程
遗传算法的运行是一个典型的迭代过程，它是一种群体型的操作方式，该操作以所选群体中的所有个体为对象，通过选择、交叉和变异构成遗传操作。遗传操作的设计与参数编码、初始群体的生成、适应度函数的设计、控制参数设定一起构成了该算法的核心内容。遗传算法的基本步骤如下：
（1）在一定的编码方案下随机产生一个初始种群；（2）用相应的解码方法将编码后的个体转换为问题空间的决策变量，并求得个体的适应值。（3）按照个体适应度值的大小从种群中选出适应度较大的个体构成交配池。（4）利用交叉和变异这两个遗传算子对交配池中的个体进行操作，并形成新一代的种群。（5）反复执行（2）~（4），直到满足停止判断条件为止。
3.交叉概率Pc的自适应改进
在遗传操作过程中，交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性。交叉概率Pc越大，产生新个体的速度就越快，越容易保持群体的多样性，越容易避免过早地收敛于局部最优解。但是Pc过大，遗传模式被破坏的可能性就越大，使得具有高适应度的个体很快被破坏； Pc过小就会使遗传算法的搜索过程缓慢甚至停滞不前。变异概率Pm 过小，就不容易产生新的个体结构；过大会演化为纯粹的随机搜索算法。
自适应的交叉和变异操作就是根据当前群体中个体的多样性程度来自适应地调节交叉和变异概率。多样性用群体中个体的分散程度来表征，个体的分散程度由个体适应度的分散程度来决定。当群体中各个个体的适应度趋于一致或者趋于局部最优时，使Pc、Pm增加；当群体中的各个个体的适应度比较分散时，使Pc 、Pm 减少。如何判断个体的适应度是分散还是趋于一致呢，我们通过比较个体的适应度和平均适应度来判断。当个体的适应度值大于群体平均适应度时，应该尽量保护该个体进入下一代，此时对应于较低的Pc 、Pm；当个体的适应度值小于群体平均适应度时，应该尽量把该个体淘汰掉，此时对应于较高的Pc、Pm。设个体的平均适应度为，个体的适应度值应该是服从正态分布的随机变量，由切比雪夫不等式：
适应度值应该大部分集中在以均值f为中心，半径为3倍方差的范围内。适应度值与均值差距超过3倍方差即属于小概率事件。其中方差€%l可用样本标准差S来近似。
基于上述的自适应思想，我们建立如下的交叉和变异概率。
由上面的交叉概率和变异概率可以看出，当个体适应度越接近最大适应度值时，交叉率和变异率就越小；当等于最大适应度值时，交叉率和变异率就等于零。这种调整方法对于群体处于进化后期比较合适，但对于进化初期不利，因为采用这样的交叉和变异概率，则初期群体中的较优个体几乎处于一种不发生变化的状态，而此时的优良个体不一定是优化的全局最优解，这使进化走向局部最优解的可能性增加。为此，可以做进一步的改进，使群体中最大适应度值的个体的交叉概率和变异概率不为零，分别提高到Pc1和Pm1，这就相应地提高了群体中表现 优良的个体的交叉概率和变异概率，使得它们不会处于一种停滞不前的状态。经过上述改进，交叉概率和变异概率的计算表达式如下：
4.实验结果分析
算法参数设置：种群大小：50；最大代数：50；试卷难度系数：0.70；变异率：0.001；实验结果如下表：
由上表可以看出，当交叉率较小时，由于搜索空间较小，算法很难得到最优解。随着交叉率的增大，算法得到最优解的可能性也增大，但是当交叉率过大（如Pc= 1.0）时，在一定程度上使得算法过多的扩展解空间，忽视了局部和区域搜索，同样不能较快地找到最优解。当Pc= 0.7时，实验中适应度最小值 0.0237，在此参数条件下，进化过程非常好。
5.结术语
本文针对遗传算法的交叉概率所进行的自适应改进，对于该提高该算法的效率将起到重要的促进作用，通过实际开发的智能组卷系统进行测试后，证明本文所阐述的改进行之有效。
参考文献
[1]E.B.Kottman， S.E.Blount.Artificial Intelligence and Automatic Programming in CAI.AI， 1975， 6:215-234
[2]朱明等.通用试题库开发系统[J].计算机工程，1996，22(3):451-460
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
[关键字]遗传算法 交叉概率 自适应改进
1.引言
随着信息技术和人工智能的发展，计算机辅助教学逐步走向普及， 题库系统成为计算机辅助教学系统中一个重要组成部分。遗传算法生成试卷是其中的一种新型的、模拟自然界生物进化过程的随机搜索、全局优化算法。从数学角度看，遗传算法实质上是一种搜索寻优技术。它从某一初始群体出发，按照一定的操作规则，不断迭代计算，逐步逼近最优解。
从现有的一些专用的自动组卷系统来看，常见的组卷方式大致采用误差补偿法、随机抽取法、回溯试探法。误差补偿算法是指在试题生成过程中，当有些约束条件无法满足的时候，适当地放宽约束条件，让试题在允许的误差范围内生成试卷；随机抽取算法是根据状态空间的控制指标，随机地抽取试题，重复此过程直到组卷完毕或己无法从题库中抽取满足指标的试题为止；回溯试探算法是一种有条件的深度优先算法，对于约束集的维数较小的组卷问题来说，组卷成功率较高。它是将随机取法得到的每一种状态都记录下来，当搜索失败时释放上一次记录的状态类型，然后依据一定的规律变换一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成完毕或者退回到出发点为止。
遗传算法（GeneticAlgorithm， GA）是近几年发展起来的一种新型的、模拟自然界生物进化过程的随机搜索、全局优化算法，该算法是由美国Michigan大学的John H.Holland教授于1975年首次提出来的，他采用简单的编码技术来表示各种复杂的结构，并通过对一组编码进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索方向。由于是采用种群的方式组织搜索，这使得它可以同时搜索解空间内多个区域，而且用种群组织搜索方式使得遗传算法特别适合大规模并行。在具有自组织、自适应、自学习等特征的同时，还具有不受搜索空间的限制性条件的约束、不需要辅助信息、搜索过程不易陷入局部最优点的特点。这些特点使得遗传算法不但可以获得较高的效率，而且具有简单、易于操作和通用的特点，从数学角度看，遗传算法实质上是一种搜索寻优技术。它从某一初始群体出发，按照一定的操作规则，不断迭代计算，逐步逼近最优解。
2.遗传算法基本流程
遗传算法的运行是一个典型的迭代过程，它是一种群体型的操作方式，该操作以所选群体中的所有个体为对象，通过选择、交叉和变异构成遗传操作。遗传操作的设计与参数编码、初始群体的生成、适应度函数的设计、控制参数设定一起构成了该算法的核心内容。遗传算法的基本步骤如下：
（1）在一定的编码方案下随机产生一个初始种群；（2）用相应的解码方法将编码后的个体转换为问题空间的决策变量，并求得个体的适应值。（3）按照个体适应度值的大小从种群中选出适应度较大的个体构成交配池。（4）利用交叉和变异这两个遗传算子对交配池中的个体进行操作，并形成新一代的种群。（5）反复执行（2）~（4），直到满足停止判断条件为止。
3.交叉概率Pc的自适应改进
在遗传操作过程中，交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性。交叉概率Pc越大，产生新个体的速度就越快，越容易保持群体的多样性，越容易避免过早地收敛于局部最优解。但是Pc过大，遗传模式被破坏的可能性就越大，使得具有高适应度的个体很快被破坏； Pc过小就会使遗传算法的搜索过程缓慢甚至停滞不前。变异概率Pm 过小，就不容易产生新的个体结构；过大会演化为纯粹的随机搜索算法。
自适应的交叉和变异操作就是根据当前群体中个体的多样性程度来自适应地调节交叉和变异概率。多样性用群体中个体的分散程度来表征，个体的分散程度由个体适应度的分散程度来决定。当群体中各个个体的适应度趋于一致或者趋于局部最优时，使Pc、Pm增加；当群体中的各个个体的适应度比较分散时，使Pc 、Pm 减少。如何判断个体的适应度是分散还是趋于一致呢，我们通过比较个体的适应度和平均适应度来判断。当个体的适应度值大于群体平均适应度时，应该尽量保护该个体进入下一代，此时对应于较低的Pc 、Pm；当个体的适应度值小于群体平均适应度时，应该尽量把该个体淘汰掉，此时对应于较高的Pc、Pm。设个体的平均适应度为，个体的适应度值应该是服从正态分布的随机变量，由切比雪夫不等式：
适应度值应该大部分集中在以均值f为中心，半径为3倍方差的范围内。适应度值与均值差距超过3倍方差即属于小概率事件。其中方差€%l可用样本标准差S来近似。
基于上述的自适应思想，我们建立如下的交叉和变异概率。
由上面的交叉概率和变异概率可以看出，当个体适应度越接近最大适应度值时，交叉率和变异率就越小；当等于最大适应度值时，交叉率和变异率就等于零。这种调整方法对于群体处于进化后期比较合适，但对于进化初期不利，因为采用这样的交叉和变异概率，则初期群体中的较优个体几乎处于一种不发生变化的状态，而此时的优良个体不一定是优化的全局最优解，这使进化走向局部最优解的可能性增加。为此，可以做进一步的改进，使群体中最大适应度值的个体的交叉概率和变异概率不为零，分别提高到Pc1和Pm1，这就相应地提高了群体中表现 优良的个体的交叉概率和变异概率，使得它们不会处于一种停滞不前的状态。经过上述改进，交叉概率和变异概率的计算表达式如下：
4.实验结果分析
算法参数设置：种群大小：50；最大代数：50；试卷难度系数：0.70；变异率：0.001；实验结果如下表：
由上表可以看出，当交叉率较小时，由于搜索空间较小，算法很难得到最优解。随着交叉率的增大，算法得到最优解的可能性也增大，但是当交叉率过大（如Pc= 1.0）时，在一定程度上使得算法过多的扩展解空间，忽视了局部和区域搜索，同样不能较快地找到最优解。当Pc= 0.7时，实验中适应度最小值 0.0237，在此参数条件下，进化过程非常好。
5.结术语
本文针对遗传算法的交叉概率所进行的自适应改进，对于该提高该算法的效率将起到重要的促进作用，通过实际开发的智能组卷系统进行测试后，证明本文所阐述的改进行之有效。
参考文献
[1]E.B.Kottman， S.E.Blount.Artificial Intelligence and Automatic Programming in CAI.AI， 1975， 6:215-234
[2]朱明等.通用试题库开发系统[J].计算机工程，1996，22(3):451-460
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。