遗传算法的计算性能的统计分析

岳嵚冯珊

（华中科技大学控制科学与工程系）

摘要：本文通过对解析函数的多次重复计算并对计算结果的进行统计分析来讨论遗传算法的可靠性和可信度，结果表明：遗传算法的计算结果具有一定的稳定性，可以通过采用多次重复计算的方法提高计算结果的可信度，并用以评价算法及其改进的实际效果。

关键词：遗传算法；计算可靠性；置信区间

分类号：TP18

1遗传算法的随机性

遗传算法是将生物学中的遗传进化原理和随机优化理论相结合的产物，是一种随机性的全局优化算法[1]。遗传算法作为一种启发式搜索算法，其计算结果具有不稳定性和不可重现性；遗传算法的进化过程具有有向随机性，整体上使种群的平均适应度不断提高。现在学术界对遗传算法中的某些遗传操作的作用机制还不十分清楚，遗传算法的许多性能特点无法在数学上严格证明。遗传算法的计算过程会受到各种随机因素的影响，如随机产生的初始种群和随机进行的变异操作等，尤其初是始种群对计算结果影响较大。但另一方面，大量的实算结果表明，遗传算法的计算结果具有一定的规律性，在统计意义上具有一定的可靠性，这样就可以对待求解问题进行多次重复计算后取平均值的方法，提高遗传算法在实际计算中的准确性和可信度。

包括遗传算法在内的启发式搜索算法主要用于解决大型的复杂优化问题，这些问题一般难以使用传统的优化算法解决。遗传算法对这类问题的计算结果也难达到精确的最优解。这给对用遗传算法解决实际工程优化问题的计算结果的评价带来了困难，在实际工程计算中也难以评价遗传算法及其改进型的计算效果的优劣。

为了分析遗传算法的计算性能，本文采用的计算对象是一个复杂的解析函数。使用这类函数评价遗传算法计算性能的好处是可以事先通过其他方法求得最优解，这样便于评价遗传算法及其改进型的计算效果。本文从统计学角度对多次重复计算的结果进行分析，试图得到遗传算法的稳定性和可信度方面的相关结论，通过分析遗传算法及其改进型求解解析问题的计算效果，再把所得到的相关结论推广应用到复杂的工程实际问题中去。

遗传算法在实际使用中有多种形式的变型，经典遗传算法是遗传算法的最简单的形式，但是经典遗传算法并不理想。本文使用的是粗粒度并行遗传算法。粗粒度并行遗传算法是遗传算法的一个重要改进型。它具有比经典遗传算法更好的计算性能。

2算例、实验方法和实验结果

2.1算例

本文所使用的算例是Deb 函数：

]10,10[,)]4cos(10[10)(12−∈⋅−+=∑=i n i i i Deb x n x x x f i π（1）

Deb 函数是一个高维的非凸函数，该函数在点（9.7624，9.7624，…，9.7624）上取得最大

2.2实验参数

为了保证小数点后四位的精度，10个输入变量都采用18位二进制表示，也就是说个体的总串长是180位。杂交率取0.75，变异率取0.15。本文采用的粗粒度并行遗传算法的参数设置参考文献【3】，具体取值为：种群规模为180、最大进化代数为200、子种群的个数为9。实验进行50次重复计算。

2.3实验结果

用粗粒度并行遗传算法重复计算Deb函数50次，得到50个计算结果并由小到大排序如表1所示。

115.1538115.1553115.1553115.1576115.1577

115.1579115.1591115.1601115.1609115.1610

115.1616115.1627115.1629115.13115.19

115.1658115.1673115.1673115.1678115.1685

115.1685115.1693115.1698115.1706115.1706

115.1709115.1716115.1716115.1724115.1726

115.1728115.1742115.1746115.1749115.1750

115.1753115.1760115.1767115.1773115.1776

115.1776115.1780115.1780115.1785115.1785

115.1788115.1791115.1793115.1796115.1802

表250个重复计算结果按大小重新排序

由表1数据可以得到这些数据的统计参数：其方差为0.000058058；均方差为0.007620；均值为115.1696。

由于这50个计算结果都分布于115.1525至115.1825之间，将其分为6个子区间，可得概率分布的直方图如图1所示。

图150个计算结果的概率分布直方图

3计算结果的统计分析

3.1计算结果初步分析

由于遗传算法具有随机性，50个数据难以精确描述计算结果的密度分布状况。但是从图1平滑后的大致形状可以判断，计算结果的概率分布与威布尔分布相似，是中间高两边渐低、最高峰偏向一边的不对称的单峰形状。威布尔分布的密度函数如下式。

为常数αλαλλααλα,,0,000

0)(1>>⎪⎩⎪⎨⎧≤>⋅⋅⋅=−−x x e x x p x

Wbl （2）

但是由于Deb 函数是求最大值的优化问题，计算结果存在最大值115.1833，且计算结果高峰偏向右边；而威布尔分布的最小值为0，且最高峰偏向左边。所以在用威布尔分布对计算结果做统计分析之前，应该先进行数据预处理，对计算结果做如下变换：

X

X −=′1833.115（3）

对X ’进行统计分析完后，再用式（4）变换回来。X X ′−=1833.115（4）

3.2采用威布尔分布的统计分析

如果遗传算法的计算结果服从威布尔分布，即：),(~αλW X 。因为实际参数λ和α均未知，根据区间估计原理，取置信度为95%，可以得到计算结果的相关参数的区间估计：

平均值的置信度为95%的置信区间为(115.1673,115.1714)。方差的置信度为95%的置信区间为(0.00005166,0.000002)；则均方差的置信度为95%的置信区间为(0.007188,0.008001)。

如果将置信度设为98%，则参数的置信区间如下：

平均值的置信度为98%的置信区间为(115.1668,115.1716)。

方差的置信度为98%的置信区间为(0.00005091,0.00006588)；均方差的置信度为98%的置信区间为(0.007135,0.008117)。

从以上数据可以看出：将置信度从95%提高到98%时，平均值的置信区间的长度从0.0041提高到0.0052，均方差的置信区间的长度从0.000813提高到0.000982，增加的比例都为百分之二十几。置信区间的长度越小越好，因为置信区间的长度反映了参数估计的精确程度。

3.3采用正态分布分析的统计分析

因为遗传算法的计算结果并不完全符合威布尔分布，而用不同分布形式分析计算结果的差别未知，所以本文使用另一种常见分布分析计算结果，再和威布尔分布的分析结果做比较，用于评估这种统计分析的准确性。本文使用的是正态分布，正态分布也是中间高两边渐低的单峰形状，但是正态分布是对称的。

如果计算结果服从正态分布，即：),(~2σµN X 。根据区间估计原理，可得置信度为95%的参数的置信区间如下：

μ的置信度为95%的置信区间为(115.1674,115.1718)；σ2的置信度为95%的置信区间为

(0.000041339,0.000091996)；σ的置信度为95%的置信区间为(0.0030,0.009591)。

如果将置信度提高为98%，则参数的置信区间如下：

μ的置信度为98%的置信区间为(115.1670,115.1723)。σ2的置信度为98%的置信区间为(0.000038751,0.00010030)；σ的置信度为98%的置信区间为(0.006225,0.010015)。

从以上数据可以看出：将置信度从95%提高到98%时，平均值的置信区间的长度从0.0044提高到0.0053，均方差的置信区间的长度从0.003161提高到0.003790，增加的比例也都约为20%。

3.4两种分布的分析结果的比较

从3.2节和3.3节的统计分析结果可以看到：使用同样的置信度时，用威布尔分布进行统计分析所得到的置信区间比正态分布所得到的置信区间更小。根据统计学原理[4]，对统计样本所使用的分布越是准确，分析所得到的置信区间越小。这也说明遗传算法对Deb 函数的计算结果更符合威布尔分布。由于计算结果也并非精确符合威布尔分布，可以假设计算结果符合某种未能确知的分布，则如果采用这种未知分布进行统计分析，所得到的置信区间应该比用威布尔分布分析所得到的置信区间更小。也就是说，遗传算法的计算可靠性比用威布尔分布分析所得到的结果更好。

从3.2节和3.3节对参数的置信区间的计算可以看出，威布尔分布和正态分布所得到的结果差别不大；而遗传算法的计算结果的密度函数图形和威布尔分布的密度函数图形很相似，其相似度高于正态分布和威布尔分布的密度函数图形的相似度。既然威布尔分布和正态分布的分析结果差别不大，那么用威布尔分布分析的结果应该和实际参数的差别更小。所以可以认为用威布尔分布分析遗传算法的计算结果已经具有较高的准确性和可信度。

3.5对重复计算次数的讨论

虽然无法判定遗传算法的计算结果符合那种分布，但是根据概率论原理，如果随机变量X 符合均值为μ、均方差为σ的某种分布，那么50个同样的随机变量的均值X 符合均值为μ、均方差为50

1σ的同样形式的分布。同样的，如果要将计算结果的精度提高10倍，就需要将计算的次数增加100倍。但是遗传算法是用于解决那些用普通优化算法难以解决的大型复杂优化问题，实际使用遗传算法时无法进行很多次的重复计算。也就是说很难通过增大重复计算次数的方法基本消除遗传算法的随机性。只能在一定可行度的条件下达到计算结果的精度。

相对来说提高置信度对重复计算次数的要求就不是很高了。根据统计学原理，如果要将置

信区间的长度缩减20%，则重复计算次数应该提高1)%

2011(2−−=56.25%。也就是说，如果用威布尔分布分析遗传算法的计算结果时，要在保持统计分析精度的情况下将置信度从95%提高到98%，只需要多进行约60%的计算量。

现在，遗传算法在理论上很难有所突破，在这种情况下，对优化问题的实际计算成为了验证遗传算法的可行性和有效性的一种有效手段。而作为一种带有很强随机性的启发式搜索算法，实算中的不确定性只有通过多次计算的方法减弱。本文通过对已知最优解的解析问题的求解，得出量化评价遗传算法中的随机因素的方法。在理论上无法严格证明的遗传算法的某些性能和特点可以通过本文所提出的方法来证实或证伪，即通过对多次重复计算的结果进行统计分析来评价这些算法和算法的改进的效果，以使算法及其改型推广到工程实际问题。

4结论

通过对测试函数用遗传算法的多次求解计算和分析，可以得出以下结论：

a ．使用遗传算法解决优化问题虽然存在一定的不确定性，但同时遗传算法有具有一定的稳定性，可以通过采用多次重复计算然后取平均值的方法，提高计算结果的可信度。

b ．遗传算法的计算精度可以通过对多次重复计算的结果进行统计分析得出。

参考文献

[1]Holland J H．Building blocks,cohort genetic algorithms,and hyperplane-defined functions[J]．Evolutionary

Computation．2000,8(4):373~391

[2]Wang L,M aciejewski A A and Siegel H J．A comparative study of five parallel genetic algorithms using the traveling salesman problem[A]．P roc.of the1st Merged Int.Parallel Processing Symp.and Symp.on Parallel and Distributed Processing[C].Los Alamitos,CA．1998:345~349

[3]岳嵚，冯珊．粗粒度并行遗传算法的计算性能分析．武汉理工大学学报（自然科学版）．2008，30（7）：8~10

[4]刘顺忠．统计理论与应用．华中科技大学出版社．2005

The statistical Analyses for Computational

Performance of the genetic algorithms

Qin Yue,Shan Feng

Institute of System Engineering Huazhong University of Science and Technology,Wuhan430074,China

Key Word:genetic algorithms,computational stability,confidence interval

国家自然科学基金资助项目（60774084）

一般网络型供应链的安全库存优化配置