一種混合重心重構花授粉改進算法

陳昌興，王建彬，陳建平

（肇慶學院計算機科學與軟件學院，肇慶526061）

0 引言

花授粉算法[1]是一種模擬花朵授粉行為的進化算法，與其他進化算法相比，其概念簡單、參數少、容易實現。作為一種新的智能優化方法，花授粉算法已經成功應用于函數優化、氣象預測、工程設計等領域，在有關問題上展示了較好的性能[2-5]。

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

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

1 基本花授粉算法

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

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

Step2 產生初始解xit：根據適應度函數計算適應度值，并從初始解中選出當前最優值作為當前全局最優解g*；

Step3 生成隨機數rand ，并與轉換概率p 進行比較，若p>rand，則按照式（1）進行全局搜索，其中L 為服從萊維分布的步長；

Step4 若p

Step5 將新產生的解與之前得到的解進行比較，若新解優于前解，則將前解替換為新解，否則保留前解，轉下一步；

Step6 判斷是否滿足最大迭代條件，若滿足，則停止迭代，輸出最優解；否則，轉Step3。

2 重心重構

2.1 物體重心與函數最優解的關系

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

圖1 重心與函數最優值的關系

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

2.2 重心重構原理

對于復雜的優化問題，往往其函數值存在多個峰值，此時獲取的函數重心落在全局最優值的鄰域內的概率變低，這使得很難直接根據原函數重心位置來尋找全局最優值的鄰域，因此需要進行函數重心的重構。本文利用函數填充技術[11]設計變換函數如下：

經過變換函數（3）填充以后的效果如圖2 所示。

圖2 函數填充效果

通過調節參數δ，將函數原來的尋優空間進行分割，大于δ 的搜索區域維持不變；小于δ 的區域用函數值ξ 進行填充，減小局部極值在搜索空間中所占的比例，從而增大全局最優極值的相對比重，重構重心在函數空間中的位置，提高重心落在最優值鄰域內的幾率。

3 花授粉算法的改進

3.1 算法搜索空間

基于上一節的分析，采用重心公式（4）迭代更新重心的位置，實現尋優空間的重心重構。

其中xp和F(xp)為前k-1 次迭代過程中出現的最優解及其函數值，M(k)為第k 次迭代時搜索區域范圍內所產生的個體解的數量，即種群規模。

在傳統的智能優化方法中，搜索范圍一般是固定的。這種方式雖然能夠確保全局最優位于原始的搜索區域內，但過大的搜索區域會增加尋優的次數和難度，不利于快速尋優。

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

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

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

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

3.2 惰性變異機制

在算法進化的中后期，由于花粉位置的過度集中，導致算法出現停滯現象，陷入局部最優，從而形成“惰性花粉”，即算法的適應值連續n 次迭代變化小于某一數值ρ。

為了避免算法陷入局部最優，應盡量在算法的中后期保持個體的多樣性。當出現惰性花粉時，在函數的解空間中對其進行一定的操作，改善得算法搜索的全局性，從而更有可能獲得全局最優解?？紤]到FPA算法自身的進化機制，將以惰性花粉為中心的小鄰域內的若干個花粉按照式（6）進行反向變異[12]：

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

3.3 算法的實現

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

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

Step2 根據杠桿原理進行重心重構；

a.按照公式（3）對原函數空間進行填充改造；

b.進行重心重構，通過公式（4）迭代產生新的重心；

Step3 判斷是否到達迭代次數，如滿足轉下一步；否則返回Step2；

Step4 花粉授粉，以Oinit為初始搜索空間，初始化FPA 相關參數；

Step5 依據rand 與轉換概率p 的大小，根據式（1）和式（2）機制產生新解；

Step6 計算新解的適應值，若新適應值優于已得到的最優適應值，則替換所對應的變量；

Step7 判斷是否滿足終止條件，如不滿足則轉下一步，否則算法結束；

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

4 仿真實驗及分析

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

（1）Sphere 函數：

搜索維數為2，搜索范圍[-100,100]，最優解0。

（2）Ronsenbrock 函數：

搜索維數為10，搜索范圍[-30,30]，最優解0。

（3）Ackley 函數：

搜索維數為10，搜索范圍[-30,30]，最優解0。

（4）Griewank 函數：

搜索維數為10，搜索范圍[-600,600]，最優解0。

在4 個經典測試函數中，Sphere 函數和Rosenbrock 函數是單模函數，分別用于測試算法的求解精度和收斂速度。Arckly 函數和Griewank 函數是多模函數，擁有多個局部極值點，用于測試算法的全局尋優能力。

為了分析每個算法的性能，每種算法單獨運行100次，最大迭代次數max gen 為2000 次，種群規模為20。各算法的具體參數為：

對于PSO，C1=2，C2=2，權重W=0.8；

對于HS，和聲記憶庫大小HM=50，和聲保留概率HMCR=0.8，微調概率PAR=0.5；

對于FPA，轉換概率p=0.8 ，標準伽馬函數參數λ=1.5；

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

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

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

表1 Sphere 函數的重心重構過程

表2 Sphere 函數比較結果

表3 Rosenbrock 函數比較結果

表4 Arckly 函數比較結果

表5 Griewank 函數比較結果

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

5 結語

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