变量数目与种群规模的关系
2012-03-05刘晓霞窦明鑫
□文/刘晓霞 窦明鑫
（1.河北金融学院；2.中国地质大学长城学院 河北·保定）
变量数目与种群规模的关系
□文/刘晓霞1窦明鑫2
（1.河北金融学院；2.中国地质大学长城学院 河北·保定）
在遗传算法的参数选择中，种群规模是一个重要的参数。本文通过实验取收敛时间和收敛代数的平均值作为评价指标来研究在确定遗传算法参数时，种群规模跟决策变量个数n有着一定的关系，通过经典函数的测试表明：比较合适的种群规模应控制在4n到6n之间。
遗传算法；种群规模；决策变量个数；收敛代数；收敛时间
收录日期：2012年5月10日
引言
遗传算法（GA）由美国Michigan大学的Holland教授于1975年首先提出，后经De Jong、GoldBerg等人改进推广，广泛应用于各类问题。它是一种模拟自然界生物进化过程与机制的全局概率优化搜索方法。
在遗传算法的参数选择中，种群规模（PS）是一个重要的参数，如何选择合适的种群规模至今没有确定的指导思想。种群规模选择过大会增加计算负担，收敛时间会显著增加，过小则降低种群的个体多样性，容易早熟，可能难以搜索到全局最优解。因此，我们希望找到种群规模与变量个数之间的对应关系，能够根据所给出函数的变量个数来选取相对合适的种群规模，使得算法的性能达到更好。
下面选择三个典型的测试函数，利用不同的种群规模和不同的变量个数进行试验，期望找到变量个数与种群规模之间的最佳关系。
一、测试函数
为了研究变量个数与种群规模对GA性能的影响，我们选择了以下三个函数。试验时每个函数的变量个数从10依次增加到20分别进行试验。（表1）
二、实验结果及分析
表1 测试函数的定义
表3 函数f1的PS与EGN测试结果
表4 变量个数与最小收敛代数关系
表6 函数f2的PS与EGN测试结果
表7 变量个数与最小收敛代数关系
在以下试验中，进化参数设置如下：对每个种群设置收敛精度为ε＝0.01，选择概率为 PS＝0.25，交叉概率为 PC＝0.7，变异概率为Pm＝0.05，进化代数为2000。种群规模从n依次增加到8n。每种规模的种群独立运行30次。取收敛时间（CT）和收敛代数（EGN）的平均值作为评价指标，函数收敛性能指标利用收敛时间（T）、进化代数（E）、全局搜索能力（P）加权后的值PGA=ω1T＋ω2E＋ω3（1-P）作为评价指标。
表 2 函数f1的PS与CT测试结果
表5 函数f2的PS与CT测试结果
表8 函数f3的PS与CT测试结果
1、函数f1的试验结果如表2所示。（表 2、图 1）
图1表现了函数f1收敛时间与种群规模的关系，函数的曲线随着种群规模的扩大一致地呈现了几乎直线上升的状态，说明种群规模对GA计算时间的影响十分明显。（表 3、表 4）
从表4可以看出，最小收敛代数有1次 n，2 次 4n，2 次 5n，3 次 6n，1 次 7n，1次8n。
2、函数f1的试验结果如表5所示。（表 5、图 2）
图2表现了函数f2收敛时间与种群规模的关系，函数的曲线随着种群规模的扩大一致的呈现了几乎直线上升的状态，说明种群规模对GA计算时间的影响十分明显。（表 6、表 7）
从表7可以看出，最小收敛代数有1次 3n，1次 4n，3次 5n，5次 6n，1次 7n。
3、函数f3的试验结果如表8所示。（表 8、图 3）
图3表现了函数f3收敛时间与种群规模的关系，函数的曲线随着种群规模的扩大一致的呈现了几乎直线上升的状态，说明种群规模对GA计算时间的影响十分明显。（表 9、表 10）
表9 函数f3的PS与EGN测试结果
表10 变量个数与最小收敛代数关系
从表10可以看出，最小收敛代数有4次 4n，5次 5n，1次 6n，1次 7n。
从以上图表及分析可以看出，种群规模的扩大对GA的搜索收敛时间有很大的影响，因此如果要想在较短时间内得到最优解，就不应该选取过大的种群规模。
对于三个测试函数来说，在变量个数一定的情况下，收敛代数最小的种群规模在 4n到6n之间，因此在确定遗传算法种群规模参数时，可以选择在4n到6n之间。
三、结论
在确定遗传算法参数时，种群规模的确定与决策变量个数n有着一定的关系，比较合适的种群规模应该控制着4n到6n之间。而且，推荐选用比较小的种群规模去进行计算，这样会节约大量的计算时间。
[1]李敏强，寇纪淞，林丹等.遗传算法的基本理论与应用[M].北京：科学出版社，2004.
[2]王小平，曹立明.遗传算法——理论、应用与软件实现[M].西安：西安交通大学出版社，2002.
[3]蒲若昂，李志华，宋国新.一种新的改进遗传算法及其应用[J].计算机应用与软件，2007.24.10.
[4]王力，侯燕玲.基于遗传算法通用试题库系统研究 [J].微计算机信息，2008.5.3.
TP3
A
