嵌入演化策略的双种群遗传算法

2.5.1　引言

经研究发现,标准遗传算法(SGA)可以极快达到最优解的90%,但真正达到最优解却要花很长时间。特别是对实数范围的非线性约束优化问题求解,往往只能得到近似最优解,而且在精度要求比较高时很难得到较理想的解。

德国柏林技术大学的Ingo Rechenberg和Hans-Paul Schwefel在一次风洞实验中提出演化策略(ESs,Evolution Strategies)的思想[20]。ESs的开发主要针对数值优化,因此在数值函数优化方面,其效率性和精度性明显好于GA,这一点在解的搜索域小时更为突出。

针对标准遗传算法的不足。本节面向一般非线性约束优化问题,提出基于演化策略的双种群搜索算法,以改善标准遗传算法的不足。并在遗传操作过程中加入了移民算子以增加解的多样性,避免早熟。

2.5.2　算法简介

2.5.2.1　遗传算法

遗传算法是一种模拟生物进化过程的优化算法。SGA基本步骤及其采用的算子,使其本身存在缺陷,带来早熟、随机漫游等问题,这些现象严重影响求解的效率和精度。本文针对上述问题对标准遗传算法进行改进。

1)适应度函数

对一般极值问题,设目标函数为f(x),适应度函数F(x)可表示为:

其中,x best、x worst分别为当前种群的最优解和最劣解;c 0、c 1为起评值和终评值。当种群收敛可能会出现除零,所以实际操作时分母可加较小常数a(如(2)式),可取a＝0.0001。

2)自适应遗传算子(详见上一节)

3)移民算子[19]

移民算子是避免早熟的一种好方法。在“移民”的过程中不仅可以加速淘汰差的个体,而且可以增加解的多样性。所谓的“移民”机制,就是在每一代进化过程中将P t%(淘汰率P t%一般取15%到30%)的最差个体淘汰,然后用随机产生的新个体代替。这样进化系统成为以开放系统,不断获取外界信息。

4)双种群搜索[21]

鉴于标准遗传算法局部搜索能力的不足,本节应用文献[21]的方法,在大范围全局搜索之后引进小种群搜索。当全局搜索到达一定条件时,从中选取最好的个体集x i。然后以x i为中心,在一定范围内随机生成小种群,然后进行局部搜索得到较好解,并替换x i。

2.5.2.2　演化策略

演化策略主要使用了一个进化算子:变异。不同于SGA,ESs将个体表示成一对浮点向量,即v＝(x,σ)(x是搜索空间的一个解,σ是标准偏差向量)。变异是通过对x的操作而实现的:

式中,N(0,σ)是期望为零、标准偏差为σ的随机Guass向量(取值方法参考文献[8]的“1/5成功法则”)。这与对生物界的观察相一致:较小的变化比较大的变化更经常地发生。当F(x k＋1)＞F(x k)时,则后代(x k＋1,σ)替换其亲体(x k,σ);否则就依概率替换。具体操作方案如下所示:

for(i＝0;i＜种群规模;i＋＋)

程序中,rand()为随机数发生器;P e是变异后产生较差解的接受概率(可采用自适应算子)。

2.5.2.3　惩罚函数[6,22]

在约束优化问题中,如何处理非可行解是算法要解决的又一问题。一般可采用惩罚函数法—对非可行解惩罚,而可行解则不惩罚。如何有效惩罚非可行解,是解决问题的关键。目前罚函数的种类很多,如:动态罚函数、自适应罚函数、双重罚函数、障碍罚函数法等[6]。这里采用动态罚函数,当演化到第t代时,按下式计算个体目标函数值:

其中,f i(x)为约束函数,i＝1,2,…m;C,α,β,皆为正的常数,通常取C＝0.5,α＝β＝2。

2.5.2.4　基于演化策略的双种群搜索方法

在不失遗传算法全局搜索能力的情况下,为加强局部搜索能力,本节采用基于以下算法结构的嵌入演化策略的双种群方法。

算法结构如下:

2.5.3　算例结果

应用本节提出的基于演化策略的双种群遗传算法,作者将其应用到多个非线性约束问题的优化中,结果令人满意。限于篇幅,仅举一个测试函数[6]说明:

求解过程发现该算法能很快、很好的得到可行最优解:G(x∗)＝680.624825。同时还采用标准遗传算法优化测试函数,并将两者进行比较。结果表明作者所提算法在收敛性、精度性等方面明显优于标准遗传算法,性能比较如图2.13、2.14所示。

图2.13　进化收敛性比较

图2.14　违约情况比较

图中深色曲线为本节算法,浅色曲线为标准遗传算法(SGA)。图2.13是收敛性的比较,前者在保证全局优化的情况下收敛性明显优于后者,迅速接近全局最优解,而且局部搜索能力较强;图2.14则重点比较两种算法寻求可行解的能力。显然,本节所提出的算法明显优于SGA。需要说明的是,两图中所出现的波动现象是由于惩罚函数动态性引起的。

通过利用各种方法对众多测试函数优化,还可总结出以下结论:搜索空间较小时,演化策略的效率和精度都很好,此时即使约束条件难度较大其结果也能令人满意,而对规模较大问题则无能为力。本节将遗传算法和演化策略通过双种群有效的结合可弥补不足之处。

本节中,通过对融合遗传算法和演化策略,并改进遗传算子及实施双种群搜索,有效地提高了求解约束非线性优化问题的能力。具体地表现于:移民算子增加解的多样性,小种群加强局部搜索能力,演化策略的引入有效提高其效率等。尽管如此,改进后的算法仍存在一些问题,需要进一步完善以解决不同情形下特别是规模大、约束难度强、精度要求高的问题。对此作者将进行深入的研究。