种群规模对遗传算法性能的影响

□文/刘晓霞 窦明鑫

（1.河北金融学院；2.中国地质大学长城学院 河北·保定）

引言

遗传算法（GA）由美国Michigan大学的Holland教授于1975年首先提出，后经De Jong、GoldBerg等人改进推广，广泛应用于各类问题。它是一种模拟自然界生物进化过程与机制的全局概率优化搜索方法。在经典的遗传算法中，种群的规模始终是固定不变的，这与实际的生物进化过程不符。在人类或其他生物进化的过程中，种群的规模的发展是有其一定的规律的，不可能固定不变。随着人类或其他生物对环境的适应度的提高，种群的规模也在逐步调整。经典的遗传算法采用固定的种群规模，使得种群不能根据其总体适应度来动态地调节其规模，不能很好解决全局收敛和收敛速度间的突出矛盾，在很大程度上影响了遗传算法的收敛速度和解的质量。

本文主要通过实验研究种群规模（PS）对遗传算法性能:进化代数（EGN）、收敛时间（CT）和全局搜索能力（GSC）的影响。通过四个经典函数的测试，结果表明种群规模对遗传算法各个性能的变化均有上升或下降的变化。

表1 测试函数定义

从直观上看，当种群规模增大时，算法的计算时间，也就是收敛时间将会增大；而种群规模如果增大了，那么算法收敛到最优解的可能性就会增大，即全局搜索能力会增强；再者，当种群规模增大了，在解空间中搜索时，可以在相对较少的代数中找到最优解，那么进化代数也随着种群规模的增大而变小了。

一、算法步骤

Step2.利用适应度函数来评价个体适应度；

Step3.若满足收敛条件，则停止迭代并给出最优个体，否则进行下一步；

Step4.进行遗传操作:

Step4.1.实行精英策略，保留本代一定比例的最优个体至下一代；

Step4.2.利用线性排序选择方法进行选择，采用两点线性交叉，执行均匀变异操作。

表2 进化代数和种群规模的关系

二、测试函数

试验所用的四个函数都是要找出他们的最大值。函数定义如表1。（表1）

三、实验结果及分析

在以下试验中，进化参数设置如下:对每个种群设置收敛精度为ε＝0.001，选择概率为 Ps＝0.25，交叉概率为 Pc＝0.7，变异概率为 Pm＝0.05，f1、f3进化代数为 800，f2、f4最大进化代数为 2000。

1、收敛代数（EGN）和种群规模（PS）之间的关系如表2所示。（表2、图1）从表2中可以看出进化代数随着种群规模的增加而降低，但不同的函数具有不同的下降速率曲线，并且呈波动型下降，而不是单调的下降。尤其是对Rosenbrock函数f4来说，它的收敛代数波动幅度最大。

表3 进化时间和种群规模关系

2、收敛时间（CT）和种群规模（PS）之间的关系如表3所示。（表3）由表3可以看出收敛时间在开始阶段下降，经过某个特定值之后，时间随着种群规模的扩大而增加。

3、为了测试全局搜索能力和种群规模的关系，我们把算法分别独立运行30次，得到全局最优解的总次数为k，利用k/30表示全局搜索能力。全局搜索能力（GSC）和种群规模（PS）的具体关系如表4所示。（表4）从表4可以看出，随着种群规模的扩大全局搜索能力会增强，但可以看出也不是单调的。

表4 全局搜索能力和种群规模的关系

四、结论

在研究了种群规模对GA的进化代数（EGN）、收敛时间（CT）、全局搜索能力（GPS）的影响之后，我们可以得到如下结论:（1）当种群规模增大时，进化代数降低；（2）当种群规模增大时，全局搜索能力增强；（3）当种群规模增大时，收敛时间在初始阶段会下降，而当种群达到某个规模后，收敛时间又会增加。同时，上述变化都不是单调增加或者减少的，而是随着种群规模的增大，改变是波动或震荡的；（4）对于四个不同的函数，各个性能的变化率都不相同，有不同的上升或下降速率，也就是说种群规模对算法性能影响的大小跟函数的选取也有关。

[1]李敏强，寇纪淞，林丹等.遗传算法的基本理论与应用[M].北京:科学出版社，2004.

[2]王力，侯燕玲.基于遗传算法通用试题库系统研究 [J].微计算机信息，2008.5.3.

[3]王小平，曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社，2002.