一種基于混沌粒子群改進的果蠅優化算法*

劉曉悅，李朋園

（華北理工大學電氣工程學院，河北 唐山 063000）

0 引言

果蠅優化算法（Fruit Fly Optimization Algorithm，FOA）是一種新型的群智能全局優化算法，是近幾年臺灣學者潘文超于2012年以果蠅覓食行為為基礎最新研究出的一種優化算法[1]，與以往的群智能算法（如粒子群算法[2]，蟻群算法[3]等）相比，果蠅算法尋優機制簡單易懂，搜索過程僅包含嗅覺和視覺搜索，重要參數為種群規模和最大迭代次數，具有優良的全局優化能力[4]。因此，一經提出就引起了國內外學者的廣泛關注，目前已成功應用于函數優化[5]、神經網絡[6]、企業經營效績評估[7]等。

然而，由于FOA的優化過程具有較強的隨機性，其在搜尋最優解時引入了一些盲目搜索，會造成收斂過早和計算速度較慢等問題，尤其在求解高維復雜函數的過程中，FOA易陷入局部極值而造成較大的誤差[8]。

本文提出一種最新研究的改進果蠅優化算法，通過引入一些改進策略來提高其全局尋優能力及收斂速度。改進策略如下：

1）引入混沌映射中的Logistic映射來生成果蠅群體的初始位置，進而提高其初始種群的多樣性。

2）引入粒子群算法（PSO）的更新策略來降低FOA搜尋最優解時的盲目性。

1 基本果蠅優化算法

果蠅能夠通過其在嗅覺和視覺上先天的優秀特性，利用感知器官搜集空氣中的氣味，進而找到距離較遠的食物源。果蠅算法（FOA）即根據其覓食特性，模擬尋優過程，能夠在更寬范圍找出最優解。同時，它還具有邏輯易理解、需調整的參數少等特點[9]。圖1顯示了果蠅群落搜尋食物的迭代過程。

圖1 果蠅群體覓食過程

根據果蠅覓食特性，FOA尋優過程分為以下幾步：

Step1：位置初始化。

Step2：嗅覺搜索。

Step3：將Si代入到式（4）中求解得到個體所在坐標的氣味濃度（Smelli）：

式中，Si為氣味濃度判定值；Object function為判定函數。

Step4：在搜尋到群體中最佳的Smelli以及該個體的位置：

Step5：視覺搜索。

Step6：開始迭代優化，重復執行Step2～Step5。直到達到最大迭代次數為止。

通過分析等式（2）和式（3）可以發現，FOA有一些缺陷會限制其優化性能：

1）由于Si＞0，FOA在定義域中存在負數時，FOA無法解決優化問題。

2）當x_axis和y_axis的值固定時，Si不遵循均勻分布。由于其不遵循均勻分布，潛在解不能再定義域中均勻產生；也就是說，Si不能在定義域中均勻搜索，因此，果蠅群失去了搜索全局最優解的能力，陷入局部最優，降低了收斂速度和收斂精度，即過早收斂的問題。

2 IFOA

為了解決FOA收斂速度慢以及收斂過早的問題，引入了上述算法來對其記性改進，具體步驟如下：

Step1：參數初始化。主要參數為最大迭代次數（Maxgen），群體規模（Sizepop），初始權重 η0和權重系數（β），控制參數，初始值 Hi。

Step2：混沌算法對初值具有很強的敏感性，而且有較大的隨機性和遍歷性。因此，正是利用混沌搜索的這些特性在生成果蠅群的初始位置時來提高其多樣性[10]。而Logistic方程是一個典型的混沌映射系統[11]：

將式（7）引入進來得到初始位置x_axis，y_axis。

Step3：由果蠅個體與原點的距離計算氣味濃度判定值（Si）。

Step4：將Si代入式（11）中，計算出每個果蠅個體所在位置的氣味濃度值（Smelli）。之后由式（12）得到濃度極值，并求出適應度函數值。

最后選擇具有最佳適應度值的果蠅個體的位置為全局最優位置（gbestX，gbestY），選其最佳適應度為局部最優LbestX，LbestY。

Step5：通過PSO來更新搜索范圍，由下式來更新 Vx，Vy。

式中，ω 為慣性權重，r1，r2是在[0，1]范圍內的隨機值。

將 Vx，Vy代入式（14）中進行更新后，再代入到式（10）～式（11）中進行迭代運算。

ω則根據線性遞減權重（LDW）進行更新，設ω0=0.9，之后由LDW原則遞減到0.3，其具體形式為：

Step6：果蠅群體飛向Smelli極值對應個體的坐標（x，y）。

Step7：進行優化迭代，只有當適應度函數值不再優于上一步迭代的值或者gen達到最大時才停止。不然返回至Step5。

3 仿真驗證及分析

3.1 測試函數驗證

抽取了5個函數[13]為測試函數來對IFOA進行尋優驗證。IFOA會對每個函數尋優100次，只有當求得的最優解在10-4以內才停止。由以下兩個性能指標作為標準：平均有效迭代次數（Average Valid Iteration Number，AVIN）和成功率（Percentage of Success，PS）[14]。

式中，m表示100次運行中最優值達到理想效果的次數，ni表示第i次成功的迭代次數。

參數設置：

PSO：Maxgen=300，sizepop=50，c1=c2=2，ωmax=1.3，ωmin=0.3，Vmax限制在 20%。

FOA：Maxgen=300，sizepop=50，LR=[-20，20]，FR=[-20，20]。

GA：Maxgen=300，sizepop=50，具有交叉概率的單點交叉為0.7，具有突變概率的離散突變為0.1。

3.2 測試結果與分析

3.2.1 測試結果比較

每個函數重復100次，測試結果如下頁表2所示。從表2可以看出，在求解GP，SH，BR，RA，SP時，IFOA的平均值更接近于理論最優值，IFOA的標準差明顯小于FOA標準差。因此，得出結論，IFOA比FOA求解最優值性能更好。

從圖2可以看出，IFOA目標值的變化曲線比FOA的目標值下降得快得多，并且IFOA的搜索性能優于FOA。所以也可以得出結論，IFOA比FOA搜尋速度更快，精度更高。

圖2 4種算法在函數上的收斂曲線

表1 基準函數

表2 IFOA、FOA、PSO和GA的均值與標準差

表3 IFOA與FOA的魯棒性分析

表4 IFOA與PSO、GA的魯棒性分析

3.2.2 魯棒性分析

表3顯示了求解最優解100次后FOA和IFOA的PS和AVIN。從表3可以看出，IFOA能夠為每個函數找到最優解，并且PS更高。此外，IFOA的AVIN比明顯FOA要小。因此，得出結論，IFOA比FOA更有效可靠。

3.3 IFOA與其他算法的比較

由表2可知，在為所有函數求解時，IFOA的均值和標準差優于GA。且對于BR，RA和SP的求解，其均值和標準差優于PSO?？傻弥?，IFOA比PSO和GA更有效。圖2（a）～圖2（e）的曲線也正驗證了這一結論。

由圖2（b）和圖2（c）可知，IFOA 收斂性大大提高?？傮w而言，IFOA的表現優于PSO和GA。由表4可知，在搜尋全局最優解時，IFOA比GA和PSO具有更高的PS。綜上所述，IFOA的魯棒性更好。

4 結論

果蠅算法是一種新型啟發式群智能算法，但FOA算法與群智能算法一樣，普遍存在早熟、收斂精度低、收斂速度慢等不足。為此，為了提高果蠅初始種群的多樣性，采用混沌搜索去初始化果蠅位置，同時引入粒子群算法去優化果蠅算法的全局尋優能力進行二次尋優，通過函數驗證，并與其他傳統算法進行比較分析，仿真結果表明本文提出的IFOA算法魯棒性較強，收斂速度更快且精度更高。但是該算法有些問題還需要進一步研究和改善，在下一步研究工作中考慮引入模擬退火等算法來提高FOA的局部尋優能力。