基于均匀设计的并行变异遗传算法*

庞 博

（赤峰工业职业技术学院 赤峰 024000）

1 引言

遗传算法（Genetic Algorithm，GA）作为一种随机仿生优化算法，自20世纪70年代由Holland教授提出以来，经过数十年的发展，在理论仿真与工程实际中均取得了良好表现［1］。遗传算法通过对待优化问题编码，随机初始化群体，模仿自然界生物进化机制，按照“优胜劣汰”原则对群体进行选择、交叉、变异操作，逐步得到问题最优解或次优解，从而解决用常规数学方法难以解决的问题。标准遗传算法主要通过遗传操作选择与产生新个体进而实现进化，但各操作方式都存在随机性大导致优化速度和优化精度较差的问题。为此，许多学者分别在编码［2］、适应度函数［3］、初始群体［4～5］、选择［6］、交叉［7～9］、变异［10～11］等方面进行改进；有学者将其它算法与遗传算法相结合［12］，优势互补，取得了良好效果。本文在分析了标准遗传算法的不足及相关文献之后，提出一种基于完全均匀设计的并行变异遗传算法（Uniform Design-Parallel Mutation GA，UD-PMGA），力图用相对简单的思想实现遗传算法的高效搜索，通过测试函数仿真与比较，验证了算法的有效性。

2 初始化群体

初始群体的多样性对算法的全局收敛及寻优速度都有重要影响，因此，产生均匀分布的初始群体成为众多学者的研究内容。正交设计与均匀设计是初始群体均匀化的主流方法［4～5］。正交设计法由于试验数等于水平数的平方，因此要保证较高的水平数以实现高精度的初始化，其群体规模必然呈平方倍增长，基于区域分解组合思想的方法也不能从本质上降低计算量，造成计算量难以承受；如果采用较低的水平数，则初始群体的均匀性无法保证。均匀设计的水平数等于试验数，因此更适于遗传算法的群体初始化。

文献［13］以中心偏差作为目标函数，用改进的遗传算法获得均匀性良好的均匀设计表。但其计算量过大，且算法复杂难以实现普遍应用。文献［14］为均匀设计表的设计提供了简单实用的Matlab程序，只需要输入水平数和因素数，就可得到相应的多个中心偏差很小的均匀矩阵。本文根据文献［14］的方法生成均匀设计表UM，将基因的定义域均分为size（群体规模）个区间，取每个区间的中值作为水平值，群体规模等于水平数，即均匀矩阵的行数，问题的维数即基因的个数等于均匀矩阵的列数，进而生成均匀的初始群体。由于采用均匀设计初始化群体，同时对于连续变化的最值问题，实数编码比二进制编码方式效果更好［2］，因此本文选用实数编码方式。根据均匀设计理论［15］，一般情况下，水平数与因素数的比值越大，产生的矩阵均匀性越好。因此，群体规模不应太小，否则初始群体的均匀性会大大下降，对于高维优化问题更是如此。

3 遗传操作算子的改进

3.1 改进的锦标赛选择机制

选择算子模仿自然界中的“优胜劣汰”规律，按照一定的机制从父代群体中选择适应度较好的部分个体，经过复制生成子代种群。选择操作中比较常见的两种方法是轮盘赌和锦标赛。文献［6］的研究认为：锦标赛选择方法在求解精度和求解速度上整体要优于轮盘赌选择方法，竞赛规模为种群规模的60%～80%优化效果较好。如取种群规模为10，竞赛规模为60%，则选出的个体最多涵盖适应度排名前5的5个个体，此5个（或小于5个）个体经过不同数量的复制构成下一代群体进行交叉及变异操作。若群体规模为100，则只能选出适应度排名前41位的个体，且适应度越高的个体被选择的概率越大。经上述文献方法选择出的群体，具有一定的随机性，其均匀性并不可靠。为此本文提出两种改进的锦标赛选择机制。一是简单覆盖法，取适应度较高的一半个体覆盖整个群体。二是不同个体覆盖法，选择适应度排名靠前且各自不同的50%的个体覆盖父代群体。对于标准遗传算法的三个算子中，选择操作系统消耗比重最大，主要缘于轮盘赌选择或锦标赛选择方法的适应度计算与比较［16］。改进方法用一次排序和复制完成选择，在促进群体进化和保证群体多样性的同时，降低了算法的复杂性与计算量。

3.2 交叉算子

交叉算子模仿自然界生物繁衍过程中的基因重组，通过不同方式的交叉操作产生新个体，以期获得适应度更高的个体。文献［7］提出选择个体适应值最相近且空间距离最近的两个个体进行交叉可以提高交叉操作的搜索效率。文献［8］根据个体相似度对群体进行划分，之后在子种群之间和种群之内同时进行交叉操作，并用贪婪算法选出较优个体。文献［9］通过改进交叉算子，将子代个体落在两个父代个体之间及其两侧，认为交叉后的子代将大概率地优于父代个体，但其并没有全面分析适应度及空间距离对子代个体的影响。考虑一种极端情况，两个父代个体适应度相等且分居极值两侧时，如图1所示。

图1 两个交叉点在极值两侧且适应度相等示意图

在此情况下，采用常规交叉操作能以概率1获得优于两个父代个体的子代个体。对于多峰函数，随着进化的进行，多峰函数转化为单峰特性或单调特性［9］。因此本文提出适应度最相近且空间距离最大的两个个体作为父代个体进行交叉能够以较高的概率搜索到适应度更高的子代个体。

交叉操作具体流程如下：

1）在每一代选择操作之后，对群体适应度进行排序［X1，X2……Xn］。

2）判断Xi+1（i=1，2……n-1）与待交叉个体Xi（i=1，2……n）适应度是否相同，若相同，转入步骤2），若不同，取此个体放入配对池2，转入步骤3）。

3）判断Xi-1（i=2，3……n）与待交叉个体Xi适应度是否相同，若相同，转入步骤3），若不同，取此个体放入配对池2，转入步骤4）。

4）判断配对池1和配对池2是否为空，如果其中一个为空，则取另一个作为交叉对象；若两个都不为空，则分别计算两个配对池中两个个体与待交叉个体的欧式距离，取距离较大者作为交叉对象；若两个配对池均为空，则直接将待交叉个体放入子代群体。

5）按式（1）进行交叉操作。

交叉完成后，用子代个体和父代个体中适应度较高的两个个体替换原父代个体。需要注意的是，对于个体X（i）的最佳交叉对象是个体X（j），但个体X（j）的最佳交叉对象不一定是个体X（i），因此需要对每个个体寻找其最佳交叉对象。所有个体都完成上述操作后即完成此代交叉操作。

3.3 自适应并行变异

变异算子的思想来自生物的基因突变，标准变异算子对极少数个体进行变异操作，产生新个体以保持种群的多样性，但较低的变异概率严重限制了变异操作的搜索效率。许多自适应变异方法尽管有一定改善，但搜索效率仍有提升空间。文献［1］采用根据进化代数和基因定义域的自适应变异步长，变异操作公式较复杂，而且没有考虑个体适应度对搜索效率的影响。文献［10］提出标准变异操作和当前最优解变异操作并行的变异策略。若最优解变异得到一个更优解，则取更优解，否则取标准变异方法得到的随机值。如果此次变异操作未搜索到优于当前最优解的“更优解”，可能会把适应度低于父代个体的新个体直接放入下一代群体中，而且对于高维优化问题意义不大。文献［11］用当前最优解为变异操作指引方向，同时引入固定参数的按比例放缩变异，存在基因无法“过0”即正负数不能转换的缺陷。

本文提出一种基于高斯函数的自适应变异比例和自适应变异步长并行的变异搜索策略。通过对高斯函数适当变形，以进化代数为自变量，以变异比例和变异步长参数为函数值，通过合理设置函数参数实现进化初期变异比例和变异步长快速减小，以加快算法收敛；进化后期变异比例和变异步长缓慢减小加强局部搜索。相关代码如下：

miu=1；sigmaf=500；

n=exp（-（kg-miu）.^2/（2*sigmaf））*1.8+k；

%n为变异比例参数，kg为进化代数，k为调节参数。

fisum=0；fisum=fisum+fi（i）；

%对当前群体适应度求和。

fiavg=fisum/size；

n1avg（i）=fiavg/（fi（i）+0.001）；

%加0.001是为防止发生除零现象。

n1（i）=n*n1avg（i）；

%n1（i）为考虑适应度加权后的变异比例参数。

tem（i，j）=qunti（i，j）*（（rand+0.5）*n1（i）+1-n1（i））；

%自适应变异比例。

km=kmu/（exp（-（kg-miu）.^2/（2*sigmaf））*1.8+k1）；

%变异步长参数，kmu=120，k1=0.01。

tem1（i，j）=qunti（i，j）+（rand*2-1）*（max-min）/km；

%自适应变异步长。

上述代码中，关键参数为 sigmaf、k、kmu、k1。对于参数k，建议前1/3进化代数取0.1，中间1/3进化代数取0.01，后1/3进化代数取0.001。仿真过程中发现，上述四个参数在数量级范围内变化不会对算法的优化结果造成明显影响，说明算法对参数设置不敏感，这是任何优化算法期望出现的特点。自适应变异比例参数n1应限定在［0.005，1.9］区间内。如果变异操作后基因值超出定义域，则取当前值到相近定义域端点之间的随机值。两种操作同时进行，并与父代个体进行适应度比较，取适应度最高者进入下一代群体。

3.4 预选择机制

预选择机制属于小生境遗传算法的一种进化机制，由Cavichio在1970年提出，其基本思想是：当子代个体的适应度超过其父代个体的适应度时，所产生的子代个体才能替代其父代而遗传到下一代群体中，否则父代个体仍保留在下一代群体中。由于子代个体与父代个体之间编码结构的相似性，所以替换掉的只是一些编码结构相似的个体，故能够有效地维持群体的多样性，并造就小生境的进化环境［17］。本文将预选择思想应用在交叉与变异操作中，通过保留当前局部最优解，加快算法寻优速度的同时还可以保证算法的收敛性与有效性。

4 仿真测试与分析

4.1 测试函数

为了验证本文算法的改进效果，通过15个常见的函数进行测试，函数表达式及定义域如表1所示。为避免算法对个别函数存在较好搜索效果的特殊性，选择不同类型、不同特性的函数对UD-PMGA算法进行测试，并与相关文献算法进行比较。测试函数 f5又叫Rosenbrock's Vally函数，最优解位于一个平坦且狭长的山谷谷底，一般算法很容易搜索到山谷底部，但由于山谷底部点的函数值变化很小，所以想要搜索到全局最优解很困难，因而经常被用来测试各种优化算法的搜索性能［18］。表1中函数f1、f2为1维函数，f3、f4、f5、f7为2维函数，f6为10维函数，其余函数为30维。函数f1、f2、f3求最大值，其余函数求最小值。仿真环境为Matlab，在Dell Inspiron 15 5000 Series笔记本电脑运行30次所得UD-PMGA算法优化结果。

表1 测试函数及相关要求

4.2 仿真结果

表2为UD-PMGA算法对函数f1～f6的优化结果及与文献［18］IAGA算法和文献［19］NCGA算法的比较。算法参数设置与对比文献一致。函数f4、f5取群体规模分别为100和50做两次试验以方便与相关文献进行比较，其余函数群体规模均为100。函数f5分别在群体规模为100、定义域为［-5，5］和群体规模为50、定义域为［-10，10］两组参数下进行两次试验以方便与文献［18］和文献［19］进行比较。进化代数为1000。函数f2收敛精度要求1E-4，函数f6收敛精度要求1E-3，其它函数收敛精度要求均为1E-6。采用平均值、最优值、最差值和平均收敛代数作为算法评价标准。

通过优化结果比较发现，除函数f5以外，UD-PMGA算法对其它函数每次搜索到的最优解均相同，说明UD-PMGA算法有着非常强的稳定性。尽管UD-PMGA算法对表中个别函数收敛到指定精度的速度稍慢于IAGA、NCGA两种算法，但其最终解的质量及算法的稳定性明显优于两种对比算法。本文在用UD-PMGA算法对函数f5进行仿真的过程中，首先采用前文2.1节中的第一种选择方法进行选择，但最终解的质量及算法稳定性并不理想，因此改用第二种选择方法进行选择操作。结果表明，采用第二种选择方法可以获得更优解及更高的稳定性，但算法的收敛速度明显低于其它两种算法。由此可以看出，第二种选择方法是以收敛速度的下降为代价进而获得更高质量的解及更高的算法稳定性。

表3所示为UD-PMGA对函数f7～f15的优化结果及与文献［11］DMMGA算法、文献［8］GACM算法的比较。算法参数设置与对比文献一致。群体规模为100。f7进化100代，其他函数进化1000代。对函数f11、f14、f15，采用第二种选择方法进行选择操作，其他函数均采用第一种选择方法。采用平均值和标准差两个指标对算法进行评价。

从表3仿真结果看出，UD-PMGA对函数f7优化解的质量及算法稳定性明显优于GACM算法，对函数f14的优化结果优于GACM算法几个数量级，虽然不及DMMGA算法，但相差不大。对于其它所有函数，UD-PMGA算法所得优化结果相比两种对比算法，解的平均值及标准差均有一个或几个数量级的提高。总体来说，UD-PMGA算法在解的质量与算法稳定性方面要优于DMMGA和GACM两种算法。为了与文献［19］的算法进行全面比较，对UD-PMGA算法在参数设置为群体规模50、进化1000代、定义域为［-10，10］的情况下对函数f7进行仿真测试，所得最优解平均值为-1.03162845，标准差为0，仍然优于文献所得结果-1.03162813。总体来说，UD-PMGA算法的搜索性能要优于NCGA算法。

表2 UD-PMGA与IAGA、NCGA算法的比较

表3 UD-PMGA与DMMGA、GACM算法的比较

图2所示为函数f6用UD-PMGA算法和SGA算法优化的仿真结果。从仿真结果可以看出，UD-PMGA算法在收敛速度及收敛精度两个方面的表现均优于SGA。在其它测试函数的仿真过程中发现，SGA对于部分单峰函数或低维函数的优化效果与UD-PMGA算法的优化效果相差并不太大，但对于多峰函数和高维函数，UD-PMGA算法的优越性变得非常明显，这也说明了UD-PMGA算法对于标准遗传算法的易陷入局部最优和局部搜索能力差的缺陷有了较大改善，验证了本文算法的有效性。

通过对15个测试函数的仿真结果全面比较，相比其它文献所提出的算法，对于低维函数，UD-PMGA算法能以非常高的稳定性收敛到全局最优解附近，所得最优解均优于其他对比算法，体现出UD-PMGA算法具有较高的搜索效率。这一方面得益于遗传操作算子的改进对算法性能的提升，同时也说明基于全面均匀设计的初始群体能够更加均匀地覆盖解空间，提高了初始群体的多样性，从而提高算法的搜索效率。相比于低维函数，UD-PMGA算法优化高维函数的稳定性逊色一些，这是因为高维函数的解空间非常大，初始群体对解空间的覆盖率相对较低，均匀设计方法对算法效率的提升会有折扣，因此标准差并不为0，但由于采用改进的遗传操作算子，UD-PMGA算法仍能到达函数最优解附近。

图2 函数 f6用SGA和UD-PMGA算法优化对比

5 结语

本文针对标准遗传算法收敛速度慢和局部搜索能力不足的缺点，提出UD-PMGA算法。算法采用完全均匀设计方法初始化种群，提出两种改进的锦标赛机制进行选择操作，降低算法的计算成本，同时增加种群的多样性；提出如何选择每个个体的最佳交叉对象，并用基于进化代数、个体适应度以及定义域自适应变化的变异比例和变异步长进行并行变异操作以提高算法的收敛速度和寻优精度。通过多个测试函数的仿真，与相关文献算法进行比较，表明UD-PMGA算法具有较好的全局搜索能力和较高的局部搜索能力。但交叉对象的确定和并行变异操作增加了计算成本，使得UD-PMGA算法的运行时间较长，不利于算法的实际应用，因此如何以更低的计算成本获得良好的搜索性能有待进一步研究，这也是遗传算法及其它优化算法的改进与发展方向。