第八章 微粒群算法在函数优化中的应用

8.1使用函数“stretching”技术的 PSO算法

寻求性能良好的全局优化算法并使之能可靠收敛于问题的全局最优解，这一直是优化领域孜孜以求的研究目标及热点。目前已有的各种全局优化算法，如GA、ES、EP等，尽管已被成功地应用于各种优化问题及实际工程领域，但是当面对复杂的优化问题，尤其是多峰、多极值的多模态函数优化问题时，由于目标问题存在着众多的局部极值，因此不可避免地存在着早熟、收敛速度慢等缺陷。PSO算法虽然已被证明是一种高效、简单的全局优化算法，但是随着目标问题的复杂化，同样也面临着上述挑战。

为提高PSO算法对复杂问题全局最优解的探测能力，文献[Parsopoulos KE 2001a]在PSO算法中引入了一种函数扩展技术（Function “Stretching” Technique）[Vrahatis 1996]，这一技术能够有效地提高PSO算法的全局收敛性能。本节内容将基于复杂函数优化问题对此项技术做详细介绍。

8.1.1 函数扩展技术（Function “Stretching” Technique）

一般的函数优化问题均可以用下式进行描述：

minf(X) (8.1)

X?S?Rn;S?[ai,bi]in?1其中，S?R称为搜索空间，f(X)称为目标函数。具有上述形式的优化问题均可称为极小化问题。

定义8.1 对极小化问题（8.1式），设x'?S，若存在??0，使得当

nx?S?{x;||x?x'||??}时，总有下式成立

f(x')?f(x) (8.2)

则称x'是f(x)在S上的一个局部极小点。若上式中的严格不等式成立，则x'与f(x')分别称为严格局部极小点(局部最优解)和严格局部极小值（局部最优解）。

定义8.2 对极小化问题（8.1式），若存在x?S，使得对任意x?S都有下式成立

?f(x?)?f(x) (8.3)

?则称x是f(x)在S上的一个全局极小点。若上式中的严格不等式成立，则x与f(x)分别称为

??严格全局极小点(全局最优解)和严格全局极小值（全局最优值）。 8.1式所描述的优化问题中，有极大一部分问题其目标函数往往存在着符合8.2与8.3定义式的多个局部极值或多个全局极值，即多峰、多极值，并且具有很复杂的函数形态，其最优解或者被众多的局部极值所环绕，或者是多个最优解与局部极值交互错杂地分布在解空间中。对于这类问题的求解，即便是全局优化算法，也不可避免得会以较大的概率收敛于某些局部极值，出现所谓的“早熟”现象。要想有效地解决多模态函数的全局优化问题，必须使得优化问题在搜索过程中能够及时从各个局部极值点逃逸出来，从而保证算法以较大的机率收敛于问题的全局最优解。

96

基于这种考虑，Vrahatis MN提出了一种函数“Stretching”技术，用于帮助提高优化算法的搜索效率及全局收敛能力。

函数“Stretching”技术的实质是借助于问题的局部极值点信息，对原始目标函数进行一种“拉伸”变换，其目的是在优化算法的实施过程中，不断缩小目标函数的极值范围，从而降低优化问题的搜索难度。具体的变换定义如下：

G(x)?f(x)??1||x?x'||(sign(f(x)?f(x'))?1) (8.4)

H(x)?G(x)??2sign(f(x)?f(x'))?1 (8.5)

tanh(?(G(x)?G(x')))上述两种变换式中，x'是目标函数的局部极值点，符合定义式（8.2）；?1、?2和?是三个任意的正数常量；sign(?)为常见的符号函数：

?1,当x?0?sign(x)??0,当x?0 (8.6)

??1,当x?0?

也可采用人工神经网络中常用的线性激励函数sigmoid函数来近似计算：

sign(x)?logsig(x)?

2?x?1?tanh() (8.7)

1?exp(??x)2通常在使用函数“Stretching”技术之前，首先要通过优化算法按照常规的方法对其局部极值

点进行搜索。当算法探测到某一局部极值点x'之后，再通过8.4与8.5式，对目标函数进行两次变换。在整个变换过程中，函数的解空间根据已搜索到的局部极值f(x')信息，被划分为两部分来考虑。一部分为区域S1?{x|f(x)?f(x')|，另一部分为区域S2?{x|f(x)?f(x')|。分析8.4与8.5式可知，区域S1在整个变换过程中，始终保持原始目标函数的形态特征不变，即对于任意x?S1，均有G(x)?f(x)?H(x)，同样原始目标函数在区域S1中的极值点（包括全局极小点在内）也始终保留不变。区域S2则不同，在两次变换中，目标函数经历了不同程度的拉伸。实施8.4式变换后，目标函数由f(x)变换为G(x)，此时G(x)?f(x)?2?1||x?x'||，相当于原始目标函数在区域S2中的每一函数值均向上进行了拉伸，并且点x越远离局部极值点x'，则其函数值被拉伸的幅度越大。此次拉伸的结果，使得区域S2中目标函数的形态变得平缓，并且其中所包含的部分极值也由此转变为非极值，这意味着从搜索空间剔除掉了函数值高于f(x')的部分极值，从而降低了后续搜索的难度。区域S2中的目标函数经8.5式实施第二次变换后，由G(x)变换为

97

H(x)，此时 H(x)?G(x)?2?2。很显然，H(x)是将目标函数f(x)在

tanh(?(G(x)?G(x')))其中距离极值点x'越近且函数值越逼近f(x')的点，其拉伸程度G(x)的基础上进一步向上拉伸，

越大，因此第二次变换的实质是将局部极值点x'及其邻域范围内的点整体向上拉伸。既然点x'被

探测为目标函数的局部极值，则其邻域范围内的点往往与其具有接近的特性，因此第二次变换的实施是有一定意义的，可以进一步缩小后续的搜索空间。

下面将函数“拉伸”技术作用于第六章所介绍的多模态优化函数F6，Levy No.5函数。此函数是一个著名的两维测试函数，具有760个局部极值点。众多的局部极值点使得各种优化算法很难搜索到全局最优解。为方便起见，现重新表述如下：

f6(X)??[icos（（i?1）?i）]?[jcos（(j?1)x2?j）]x1i?1j?1 (8.8) 2?（x1?1.42513)?(x2?0.80032)2

图8.1~8.3分别描述了Levy No.5函数在拉伸变换前后函数的具体形态。 经过上述分析可知，Vrahatis所提出的函数“Stretching”技术，可以有效地降低目标函数的复杂性。把此项技术与全局优化算法相结合，利用优化算法不断去搜索问题的局部极值信息，每当探测到问题的一个局部极小点，即对函数进行两次拉伸变换，将局部极小点以及劣于局部极小点的函数极值从搜索空间剔除掉，而优于局部极小点的解以及全局最优点却始终保持不变。因此，

98

55