陳昌興，王建彬，陳建平

（肇慶學(xué)院計(jì)算機(jī)科學(xué)與軟件學(xué)院，肇慶526061）

0 引言

花授粉算法[1]是一種模擬花朵授粉行為的進(jìn)化算法，與其他進(jìn)化算法相比，其概念簡(jiǎn)單、參數(shù)少、容易實(shí)現(xiàn)。作為一種新的智能優(yōu)化方法，花授粉算法已經(jīng)成功應(yīng)用于函數(shù)優(yōu)化、氣象預(yù)測(cè)、工程設(shè)計(jì)等領(lǐng)域，在有關(guān)問(wèn)題上展示了較好的性能[2-5]。

目前，許多學(xué)者都提出了不同的改進(jìn)策略，常見(jiàn)的改進(jìn)方法主要圍繞花授粉算法中的參數(shù)和授粉方式展開(kāi)，包括概率大小、全局授粉時(shí)的萊維分布系數(shù)以及局部時(shí)的均勻分布系統(tǒng)等。Salgotra 等人[6]為算法設(shè)計(jì)了動(dòng)態(tài)切換概率以提高算法的搜索能力；劉升等人[7]依據(jù)正余弦算法思想，通過(guò)將正余弦算法嵌入到基本花授粉算法中進(jìn)行混合以解決局部收斂問(wèn)題；王興凡等人[8]通過(guò)在異花授粉時(shí)引入自適應(yīng)步長(zhǎng)提高搜索能力；段艷明等人[9]通過(guò)量子系統(tǒng)的態(tài)疊加特性以及波函數(shù)，使得算法能夠按照一定的概率密度在解空間進(jìn)行搜索，從而提高了求解的速度和精度；肖輝輝等人[10]則針對(duì)基本FPA 的全局尋優(yōu)部分，利用個(gè)體的萊維飛行以及萬(wàn)有引力共同實(shí)現(xiàn)個(gè)體位置的更新，提高算法后期的收斂速度。

上述這些改進(jìn)方法在一定程度上提高了算法的搜索能力，針對(duì)特定問(wèn)題取得了較好的效果，但是依然存在前期進(jìn)化速度慢、算法難收斂，后期全局搜索能力差的問(wèn)題。為此，本文提出一種混合重心重構(gòu)花授粉算法?；诟軛U力平衡原理，通過(guò)對(duì)函數(shù)重心的重構(gòu)，對(duì)搜索空間進(jìn)行合理壓縮簡(jiǎn)化，提高算法前期的局部搜索能力，同時(shí)在算法后期引入惰性變異機(jī)制以增強(qiáng)算法的爬山能力，跳出局部最優(yōu)。通過(guò)對(duì)測(cè)試函數(shù)的仿真實(shí)驗(yàn)，表明了算法改進(jìn)的有效性。

1 基本花授粉算法

基本花授粉算法是一種進(jìn)化算法，是受大自然中花朵授粉的行為啟發(fā)而得到的。研究表明，自然界中的花授粉行為90%為異化授粉，而另外的10%為自花授粉。基于這一研究，Yang 等人[1]于2012 年提出了FPA 算法，其基本步驟如下：

Step1 設(shè)定及初始化FPA 的基本參數(shù)：變量的個(gè)數(shù)、各變量的取值范圍、轉(zhuǎn)換概率、種群數(shù)量、最大迭代次數(shù)等；

Step2 產(chǎn)生初始解xit：根據(jù)適應(yīng)度函數(shù)計(jì)算適應(yīng)度值，并從初始解中選出當(dāng)前最優(yōu)值作為當(dāng)前全局最優(yōu)解g*；

Step3 生成隨機(jī)數(shù)rand ，并與轉(zhuǎn)換概率p 進(jìn)行比較，若p>rand，則按照式（1）進(jìn)行全局搜索，其中L 為服從萊維分布的步長(zhǎng)；

Step4 若p

Step5 將新產(chǎn)生的解與之前得到的解進(jìn)行比較，若新解優(yōu)于前解，則將前解替換為新解，否則保留前解，轉(zhuǎn)下一步；

Step6 判斷是否滿足最大迭代條件，若滿足，則停止迭代，輸出最優(yōu)解；否則，轉(zhuǎn)Step3。

2 重心重構(gòu)

2.1 物體重心與函數(shù)最優(yōu)解的關(guān)系

在力學(xué)研究過(guò)程中，通過(guò)杠桿原理可知，物體的重心總是靠近其質(zhì)量分布密集的區(qū)域，分布越稀疏的區(qū)域離重心的位置越遠(yuǎn)。為維持力矩平衡，質(zhì)量越大的點(diǎn)離重心的距離越近，質(zhì)量越小的點(diǎn)離重心的距離越遠(yuǎn)。如圖1 所示，對(duì)于由函數(shù)f(x)圍成的封閉區(qū)域，C表示它的最大函數(shù)值，通過(guò)分析可知，它的“重心”G 在最大值附近。

圖1 重心與函數(shù)最優(yōu)值的關(guān)系

由圖1 可知，函數(shù)的重心與其全局最優(yōu)值處于一個(gè)小的鄰域內(nèi)，該鄰域的取值范圍遠(yuǎn)小于函數(shù)的定義域。因此如果能夠找到函數(shù)搜索空間的重心位置，也就可以確定其全局最優(yōu)解的取值范圍。

2.2 重心重構(gòu)原理

對(duì)于復(fù)雜的優(yōu)化問(wèn)題，往往其函數(shù)值存在多個(gè)峰值，此時(shí)獲取的函數(shù)重心落在全局最優(yōu)值的鄰域內(nèi)的概率變低，這使得很難直接根據(jù)原函數(shù)重心位置來(lái)尋找全局最優(yōu)值的鄰域，因此需要進(jìn)行函數(shù)重心的重構(gòu)。本文利用函數(shù)填充技術(shù)[11]設(shè)計(jì)變換函數(shù)如下：

經(jīng)過(guò)變換函數(shù)（3）填充以后的效果如圖2 所示。

圖2 函數(shù)填充效果

通過(guò)調(diào)節(jié)參數(shù)δ，將函數(shù)原來(lái)的尋優(yōu)空間進(jìn)行分割，大于δ 的搜索區(qū)域維持不變；小于δ 的區(qū)域用函數(shù)值ξ 進(jìn)行填充，減小局部極值在搜索空間中所占的比例，從而增大全局最優(yōu)極值的相對(duì)比重，重構(gòu)重心在函數(shù)空間中的位置，提高重心落在最優(yōu)值鄰域內(nèi)的幾率。

3 花授粉算法的改進(jìn)

3.1 算法搜索空間

基于上一節(jié)的分析，采用重心公式（4）迭代更新重心的位置，實(shí)現(xiàn)尋優(yōu)空間的重心重構(gòu)。

其中xp和F(xp)為前k-1 次迭代過(guò)程中出現(xiàn)的最優(yōu)解及其函數(shù)值，M(k)為第k 次迭代時(shí)搜索區(qū)域范圍內(nèi)所產(chǎn)生的個(gè)體解的數(shù)量，即種群規(guī)模。

在傳統(tǒng)的智能優(yōu)化方法中，搜索范圍一般是固定的。這種方式雖然能夠確保全局最優(yōu)位于原始的搜索區(qū)域內(nèi)，但過(guò)大的搜索區(qū)域會(huì)增加尋優(yōu)的次數(shù)和難度，不利于快速尋優(yōu)。

為確保重構(gòu)的重心能更加逼近全局最優(yōu)所在的鄰域，同時(shí)提高計(jì)算效率，搜索范圍O(k)和種群規(guī)模M(k)需遵循以下原則：

（1）種群規(guī)模M(k)與搜索范圍O(k)應(yīng)成正比變化；

（2）搜索范圍O(k)應(yīng)隨著迭代次數(shù)k 的增加不斷減小。

令η=O(k)/O(k-1)<1，則經(jīng)過(guò)k 次迭代以后的搜索范圍為O(k)=ηkO(0)，其中O(0)為原始搜索區(qū)域范圍，從而得到算法的初始搜索空間為：

3.2 惰性變異機(jī)制

在算法進(jìn)化的中后期，由于花粉位置的過(guò)度集中，導(dǎo)致算法出現(xiàn)停滯現(xiàn)象，陷入局部最優(yōu)，從而形成“惰性花粉”，即算法的適應(yīng)值連續(xù)n 次迭代變化小于某一數(shù)值ρ。

為了避免算法陷入局部最優(yōu)，應(yīng)盡量在算法的中后期保持個(gè)體的多樣性。當(dāng)出現(xiàn)惰性花粉時(shí)，在函數(shù)的解空間中對(duì)其進(jìn)行一定的操作，改善得算法搜索的全局性，從而更有可能獲得全局最優(yōu)解。考慮到FPA算法自身的進(jìn)化機(jī)制，將以惰性花粉為中心的小鄰域內(nèi)的若干個(gè)花粉按照式（6）進(jìn)行反向變異[12]：

其中xi為惰性花粉，oxi為變異后的新花粉，xmax和xmin為搜索空間的上界和下界。

3.3 算法的實(shí)現(xiàn)

基于以上分析，算法具體步驟為：

Step1 設(shè)定重心重構(gòu)基本參數(shù)：重心重構(gòu)種群規(guī)模M(k)，搜索范圍壓縮比η，填充函數(shù)參數(shù)δ 和ξ，各變量的取值范圍，迭代次數(shù)k；設(shè)定和聲搜索的基本參數(shù)，惰性花粉持續(xù)代數(shù)n 及其相應(yīng)適應(yīng)值的變化范圍ρ；

Step2 根據(jù)杠桿原理進(jìn)行重心重構(gòu)；

a.按照公式（3）對(duì)原函數(shù)空間進(jìn)行填充改造；

b.進(jìn)行重心重構(gòu)，通過(guò)公式（4）迭代產(chǎn)生新的重心；

Step3 判斷是否到達(dá)迭代次數(shù)，如滿足轉(zhuǎn)下一步；否則返回Step2；

Step4 花粉授粉，以O(shè)init為初始搜索空間，初始化FPA 相關(guān)參數(shù)；

Step5 依據(jù)rand 與轉(zhuǎn)換概率p 的大小，根據(jù)式（1）和式（2）機(jī)制產(chǎn)生新解；

Step6 計(jì)算新解的適應(yīng)值，若新適應(yīng)值優(yōu)于已得到的最優(yōu)適應(yīng)值，則替換所對(duì)應(yīng)的變量；

Step7 判斷是否滿足終止條件，如不滿足則轉(zhuǎn)下一步，否則算法結(jié)束；

Step8 判斷是否出現(xiàn)惰性花粉，若出現(xiàn)，則按公式（6）進(jìn)行反向變異，返回Step4；否則直接返回Step4。

4 仿真實(shí)驗(yàn)及分析

針對(duì)文獻(xiàn)[8]測(cè)試的4 個(gè)基本的單模和多模函數(shù)，分別利用已有的PSO、HS、FPA 和GCRFPA 算法進(jìn)行測(cè)試，從而比較了四種算法的求解效果和收斂速度。所有試驗(yàn)都是在硬件環(huán)境為Intel Core i3 處理器，內(nèi)存8GB；軟件環(huán)境為Windows 7 操作系統(tǒng)，MATLAB 2013a版本的機(jī)器上運(yùn)行的。四個(gè)測(cè)試函數(shù)為：

（1）Sphere 函數(shù)：

搜索維數(shù)為2，搜索范圍[-100,100]，最優(yōu)解0。

（2）Ronsenbrock 函數(shù)：

搜索維數(shù)為10，搜索范圍[-30,30]，最優(yōu)解0。

（3）Ackley 函數(shù)：

搜索維數(shù)為10，搜索范圍[-30,30]，最優(yōu)解0。

（4）Griewank 函數(shù)：

搜索維數(shù)為10，搜索范圍[-600,600]，最優(yōu)解0。

在4 個(gè)經(jīng)典測(cè)試函數(shù)中，Sphere 函數(shù)和Rosenbrock 函數(shù)是單模函數(shù)，分別用于測(cè)試算法的求解精度和收斂速度。Arckly 函數(shù)和Griewank 函數(shù)是多模函數(shù)，擁有多個(gè)局部極值點(diǎn)，用于測(cè)試算法的全局尋優(yōu)能力。

為了分析每個(gè)算法的性能，每種算法單獨(dú)運(yùn)行100次，最大迭代次數(shù)max gen 為2000 次，種群規(guī)模為20。各算法的具體參數(shù)為：

對(duì)于PSO，C1=2，C2=2，權(quán)重W=0.8；

對(duì)于HS，和聲記憶庫(kù)大小HM=50，和聲保留概率HMCR=0.8，微調(diào)概率PAR=0.5；

對(duì)于FPA，轉(zhuǎn)換概率p=0.8 ，標(biāo)準(zhǔn)伽馬函數(shù)參數(shù)λ=1.5；

對(duì)于GCRFPA，算法的重心重構(gòu)迭代次數(shù)k 為5，搜索范圍壓縮比η=0.5，填充函數(shù)參數(shù)δ=0.01 和ξ =0.001，惰性和聲持續(xù)代數(shù)為10 次，ρ 為0.0001。

依據(jù)以上分析，對(duì)上述函數(shù)進(jìn)行運(yùn)算，結(jié)果如表1-表5 所示。其中表1 表示的是Sphere 函數(shù)的重心重構(gòu)過(guò)程，各個(gè)函數(shù)不同算法運(yùn)行比較結(jié)果如表2 至表5所示。表中m 為100 次迭代得到的最優(yōu)值的平均值，v 為方差，s 為成功率。平均最優(yōu)值反映的是算法的收斂精度，方差反映算法的穩(wěn)定性，成功率反映了算法的全局最優(yōu)能力。

由表1 可知，只需要經(jīng)過(guò)幾次迭代，重心重構(gòu)算法就可以非常好的壓縮搜索空間，從而縮小了和聲搜索算法的初始尋優(yōu)空間，大大提高了和聲搜索算法初期的局部搜索能力。

表1 Sphere 函數(shù)的重心重構(gòu)過(guò)程

表2 Sphere 函數(shù)比較結(jié)果

表3 Rosenbrock 函數(shù)比較結(jié)果

表4 Arckly 函數(shù)比較結(jié)果

表5 Griewank 函數(shù)比較結(jié)果

由表2-表5 中可以看出，GCRFPA 算法找到的最優(yōu)值、平均值、方差都比前面幾個(gè)算法要好，成功率比前幾個(gè)算法高。對(duì)于復(fù)雜的多峰函數(shù)，其他算法成功率低，而本算法仍能比較有效地跳出局部最優(yōu)解，從而找到全局最優(yōu)解。因此，從整體上看，GCRFPA 算法優(yōu)于另外三種算法。

5 結(jié)語(yǔ)

本文對(duì)花授粉算法進(jìn)行改進(jìn)，提出一種混合重心重構(gòu)花授粉算法。采用重心重構(gòu)方法壓縮簡(jiǎn)化函數(shù)的尋優(yōu)空間，減小和聲算法的搜索范圍，彌補(bǔ)基本花授粉算法前期局部搜索能力弱的缺陷，后期采用惰性反向變異機(jī)制，提升算法的全局搜索能力。仿真實(shí)驗(yàn)結(jié)果表明GCRFPA 具有很好的收斂速度和跳出局部最優(yōu)的能力。