摘要:利用标准遗传算法解决大型复杂寻优问题时，收敛速度和计算精度是一对难以调和的矛盾。本文通过分析种群规模对遗传算法收敛性能和精度的影响，提出了一种基于小种群规模的改进遗传算法。在遗传算法进化过程中不断补充新的染色体来克服由于种群规模小、种群多样性降低而导致早熟收敛的弊病，使算法以比较快的速度收敛到全局最优解。多峰函数数值试验，以及石油测井储层参数计算的成功应用说明了算法的有效性。

关键词:遗传算法; 种群规模; 早熟收敛

中图分类号：TP1  文献标识码：A  文章编号：（2006）02-0059-03

 

一种基于小种群规模的改进遗传算法

 

李莉[1]

 

0 　引　言

遗传算法( Genetic Algorithms，简称GA) 是根据生物进化和遗传变异理论提出的一种基于种群全局概率搜索的优化算法。其思想是在遗传算子的作用下，使种群不断进化，最终收敛到优化解^[1]。GA针对染色体进行遗传操作，而不直接针对决策变量本身，对优化目标函数没有连续、可微等苛刻条件的限制。因此，在过去的20多年中,GA取得了许多成功的应用。但是随着研究和应用的不断深入,标准遗传算法(Sample Genetic Algorithms, 简称SGA)逐渐暴露出一些自身固有的缺点。SGA局部搜索能力较弱，它可以用极快的速度达到最优解的90%左右，但要达到真正的最优解则要花费很长的时间。特别是随着进化的进行，大量相似个体的出现使种群的多样性下降，从而导致早熟。很多学者对GA的收敛问题^[2,3]、早熟现象等进行了深入的研究，提出了许多改进方法^[4,5]。但是这些改进大多把注意力集中到算子本身，而忽略了群体规模和个体空间对收敛速度和精度的影响。

一般说来，选择较大数目的初始种群可以同时处理更多的个体，因而容易找到全局最优解。其缺点是增加了每次迭代的时间，尤其是对一些复杂的、精度要求比较高的问题，种群数的增加将导致计算量呈指数增长。但是当种群过小时，种群多样性下降，GA陷入局部极值而导致早熟现象出现的可能性大大增加。为解决这一矛盾，本文提出了一种基于小种群的改进遗传算法(Small Population GA，简称SPGA)。它能够用小规模的种群进行有效的全局搜索，避免早熟收敛，使算法以比较快的速度收敛到全局最优解。数值试验说明了该算法的有效性。

阿尔奇公式是石油测井资料油气水评价的理论基础，而准确地确定阿尔奇公式中参数 、 、 的数值一直是困扰石油测井学家的难题。本文应用SPGA成功地解决了阿尔奇公式中参数 、 、 的确定问题，为使用阿尔奇公式进行储层评价奠定了坚实的基础。

1            GA的基本理论

1.1 GA简介

对于一个求最大值的优化问题，可以表述如下：

                                                     （1）

                                                      （2）

                                                        （3）

其中， 为n维决策变量； 为目标函数；式(2)和式(3)为约束条件；U是基本空间；R是U的一个子集。

GA主要由选择、交叉和变异三部分组成。

(1) 选择(selection)

选择是将亲代的个体原封不动地传递到子代。适应度值的大小决定了个体能够被选择复制到下一代的概率。通过选择, 使得群体中的优秀个体数目不断增加, 整个进化过程朝着更优解的方向进行, 反映了“优胜劣汰”的原则。但是选择只是在一个固定的种群中进行，选择的结果依赖于初始种群，对于种群之外更好的个体是不可能被选择到的。

(2) 交叉(crossover)

选择只能在现有群体内进行个体的寻优复制,不能产生与亲代不同的个体。交叉算子的引入,使每一代的各个个体之间按一定的概率交换其部分基因, 产生新的基因组合, 使各个解有机会交流其优秀基因, 因此有望获得比亲代更好的解的结构。

(3) 变异(mutation)

选择和交叉只能在现有的基因型的排列组合内寻找最优, 不能产生新的基因型。变异算子是对每个字符串的每一位按一定的概率由1变0或由0变1, 从而产生新的基因型, 扩大了寻优范围。变异个体的选择以及变异位置的确定, 均采用随机方法产生。

 

1.2 种群规模与GA性能关系的理论基础

文献[5]中给出了种群规模与遗传算法收敛之间的关系。

定理1：设 上的初始无限种群 有分布：

则

其中：      

此定理说明仅考虑选择算子时，其群体收敛速度与种群规模N的大小有关，N越小收敛速度越快，其证明过程详见文献[6]。

独立考虑变异算子，用 表示经 步变异得到的个体，可以得到定理2^[7]：

定理2：设 为初始种群， ，从 代到 代，个体 被转移到的概率 为

其中： 

为变异概率， 为个体分量。

定理2说明变异算子将全部个体空间当作搜索空间,而其转移到某一个个体上的概率与个体空间的大小以及种群规模有关。个体空间小而种群规模大将有助于通过变异寻找空间中的点。在GA中，如果搜索的空间可以尽可能的小，而群体规模相对于搜索空间尽可能地大，GA搜索到最优解的可能性将大幅度提升。然而，在GA中，对于一些大型复杂的、精度要求很高的优化问题，染色体的位串很长，导致个体空间很大。在这种情况下，如何有效地控制种群规模就成为提高GA性能的关键。

2            基于小种群规模的改进遗传算法(SPGA)的实现

种群多样性的降低是导致GA早熟收敛的主要原因。就SGA而言，种群规模越大，算法收敛到全局最优解的可能性也越大。但是计算量也会大大增加。如果种群规模变小，虽然计算量会减小，但种群的多样性也会降低，算法早熟的可能性也将随之变大。在实际问题的求解过程中，种群规模是有限的。因此，如何在有限的种群规模条件下，保持种群多样性，进而快速产生优良后代是GA必须解决的问题。

为此，本文提出了基于小种群规模的改进遗传算法(SPGA)。在每代进化时，不断补充新的个体，改善由于群体规模小、多样性降低而导致的早熟现象。该算法实现简单，效果显著。

    (1) 基因表达

编码(encode)：采用二进制编码,染色体长度与变量的精度之间的关系为：

                                        (4)

其中 为染色体的长度； 为变量的值域； 为要求的精度。

解码(decode)：即将染色体的基因型转化为表现型，按公式(5)进行解码：

                                          (5)

其中， 表示变量 的二进制编码值； 与 的涵义同上；

(2) 个体评价

个体评价过程分以下两步：首先根据个体的表现型计算目标函数值；然后确定适应度函数，将目标函数值转换成适应度值。由于这里以三个函数的最大值为例，故适应度函数直接取对应的目标函数，适应度值即为对应的目标函数值。

(3) 确定遗传操作

选择运算采用轮盘赌选择法(roulette wheel selection)。设每串的选择概率为 （ 为个体适应度之和； 为第 个个体对应的适应度值）及累加概率 。产生[0，1]间随机数 ，若 ，则第 个子串入选；

交叉运算使用单点交叉算子。先对种群中的个体进行两两随机配对，然后对每一对相互配对的个体，随机设置一交叉点，最后按照设定的交叉概率在各交叉点处相互交换两个个体的部分染色体，从而产生出两个新个体；

变异运算采用基本位变异算子。首先对个体的每一个基因，依变异概率确定变异点，然后对其基因做取反运算，从而产生出一个新的个体。

(4) 算法终止条件的设定

    算法的终止条件通常有两种：一种以最大进化代数为算法的终止条件；另一种以任务要求的精度作为算法的终止条件。本文采用第一种方法。

初始种群产生后，经过适应度值的计算、评价、选择、交叉和变异后，从中选出70%的优良个体进入下一代；然后再随机生成种群规模的30%个体补充进种群中，一起进入到下一代进化。SPGA实现过程如下：

Step 1 确定种群规模、交叉概率、变异概率、最大进化代数；

Step 2 产生初始染色体；

Step 3 计算个体适应度值，对种群进行评价；若满足最大进化代数，则算法终止；否则令 ；

Step 4 执行遗传操作：

①     按轮盘赌选择策略执行选择复制操作；

②     以交叉概率 进行交叉操作；

③     以变异概率 执行变异操作，变异算子采用均匀变异策略；

Step 5 按照适应度值的大小从中选出70%的优良个体进入到下一代；

Step 6 随机生成30%新个体补充进种群，转至Step3。

程序流程图如图1：

 

3            数值实验与应用

3.1 数值实验

为验证算法的有效性，本文选用了下面三个函数进行测试，计算函数的最大值：

例1：

例2：

例3：

算法中采用的最大运行代数为150代，交叉概率为0.80，变异概率为0.05，测试结果分别如表1～表3所示：

从试验结果可以看出，本文提出的SPGA比SGA几乎快了一个数量级，并且精度很高。例如在表2中，当种群规模为14时，SPGA在第43代产生了最优解1.218994，而SGA运行到第96代才产生同样精度。可见，SPGA比SGA的速度提高了将近两倍。实验结果表明，在种群规模较小的情况下，采用SPGA算法，取得了令人满意的结果。

3.2 应用SPGA求解阿尔奇(Archie)公式中的参数

测井解释是目前石油工业中地层评价与油气分析的主要方法。传统的测井解释方法需要建立精确的数学模型，并有严格的条件限制，很难得到令人满意的结果。GA在解的搜索中不需要了解问题的内在性质，可以处理任意形式的目标函数和约束，并且可以同时确定多个参数。本文应用GA的上述优点，成功地解决了Archie含水饱和度公式中参数 、 、 的计算问题。

Archie含水饱和度公式为：                             (6)

其中 为岩性系数； 为胶结指数； 为饱和度指数； 为地层孔隙度； 为地层水电阻率； 为地层电阻率。参数 、 的选取对测井解释结果影响很大，合理选择这组参数非常重要。

用SPGA预测参数 、 、 的具体步骤如下：

(1)  基因表达

采用二进制编码，各决策变量精度取小数点后4位，由公式(4)确定了 、 、 分别为10、11、11位长编码，染色体长度为32位。

(2)  个体评价

建立优化模型如下：

     (7)

                                              (8)

式中 表示目标函数 的最大值； 、 、 为决策变量； 为样本数； 为地层水电阻率 ； 为第 个样品电阻率 ； 为用Archie公式计算出的含水饱和度； 为第 个样品的地层孔隙度; 为第 个样品的含水饱和度。在实际处理过程中，用分析样品所对应深度的深侧向电阻率代替 。

首先按照公式(5)解码，将染色体的基因型转化为表现型，然后再按照公式(7)计算出个体的适应度值。

(3)  参数确定

以某油田的100个岩心分析样作为样本。遗传终止代数设定为600，交叉概率为0.8，变异概率为0.05，参数 、 、 的计算结果如下：

    从表中可以看出，产生同样的精度，SPGA的收敛速度远远高于SGA。实践证明，SPGA取得了令人满意的结果。

4            总结

遗传算法的性能与种群规模的数量以及搜索空间的大小密切相关。种群规模越大，越有利于进化，但是计算量越大。种群规模越小，计算量越小，但是种群多样性下降也越快，也越不利于进化。由此看来，种群规模和优良进化似乎是一对不可调和的矛盾。本文针对这一问题，提出了基于小种群规模的遗传算法SPGA。该算法在不增加种群规模的前提下，通过每次进化都不断补充一定数量的新鲜个体到种群中，有效地保持种群的多样性，因而也就保证了种群进化的质量。数值试验和石油测井Archie公式中参数 、 、 的计算实例都说明了SPGA算法的有效性。

在实际应用时，针对遗传算法容易出现早熟收敛和搜索时间冗长等缺点，可以与其他局部搜索算法结合起来，互相取长补短，达到更好的优化效果；此外在进化过程中，如何动态调整参数，避免进化过程中出现的早熟或者进化缓慢问题，是本文进一步探讨与研究的方向。

 

 

参考文献：

[1] Holland J H. Adaptation in Natural and Artificial Systems [M ]. Michigan: The University of Michigan Press,1975.

[2] Radolph G. Convergence a analysis of canonical genetic algorithms [J]. IEEE Trans on Neural Network,1994,5(1).

[3] Qix F. Palmieri theoretical analysis of evolutionary algorithms with an infinite population size in continuous space [J]. IEEE Trans on Neural Network, 1994, 5(1).

[4] 张玲、张钹.  统计遗传算法[J ]. 软件学报，1997（5）.

[5] 张玲、张钹.  遗传算法机理的研究[J ]. 软件学报，2000（7）

[6] 张文修、梁怡. 遗传算法的数学基础[M ]. 西安: 西安交通大学出版社, 2001. 5.

[7] 李建华、王孙安. 最优家族遗传算法[J ]. 西安交通大学学报，2004，28(1).