一種基于混沌粒子群改進(jìn)的果蠅優(yōu)化算法*

劉曉悅，李朋園

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

0 引言

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

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

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

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

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

1 基本果蠅優(yōu)化算法

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

圖1 果蠅群體覓食過程

根據(jù)果蠅覓食特性，F(xiàn)OA尋優(yōu)過程分為以下幾步：

Step1：位置初始化。

Step2：嗅覺搜索。

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

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

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

Step5：視覺搜索。

Step6：開始迭代優(yōu)化，重復(fù)執(zhí)行Step2～Step5。直到達(dá)到最大迭代次數(shù)為止。

通過分析等式（2）和式（3）可以發(fā)現(xiàn)，F(xiàn)OA有一些缺陷會限制其優(yōu)化性能：

1）由于Si＞0，F(xiàn)OA在定義域中存在負(fù)數(shù)時，F(xiàn)OA無法解決優(yōu)化問題。

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

2 IFOA

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

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

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

將式（7）引入進(jìn)來得到初始位置x_axis，y_axis。

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

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

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

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

式中，ω 為慣性權(quán)重，r1，r2是在[0，1]范圍內(nèi)的隨機值。

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

ω則根據(jù)線性遞減權(quán)重（LDW）進(jìn)行更新，設(shè)ω0=0.9，之后由LDW原則遞減到0.3，其具體形式為：

Step6：果蠅群體飛向Smelli極值對應(yīng)個體的坐標(biāo)（x，y）。

Step7：進(jìn)行優(yōu)化迭代，只有當(dāng)適應(yīng)度函數(shù)值不再優(yōu)于上一步迭代的值或者gen達(dá)到最大時才停止。不然返回至Step5。

3 仿真驗證及分析

3.1 測試函數(shù)驗證

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

式中，m表示100次運行中最優(yōu)值達(dá)到理想效果的次數(shù)，ni表示第i次成功的迭代次數(shù)。

參數(shù)設(shè)置：

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

FOA：Maxgen=300，sizepop=50，LR=[-20，20]，F(xiàn)R=[-20，20]。

GA：Maxgen=300，sizepop=50，具有交叉概率的單點交叉為0.7，具有突變概率的離散突變?yōu)?.1。

3.2 測試結(jié)果與分析

3.2.1 測試結(jié)果比較

每個函數(shù)重復(fù)100次，測試結(jié)果如下頁表2所示。從表2可以看出，在求解GP，SH，BR，RA，SP時，IFOA的平均值更接近于理論最優(yōu)值，IFOA的標(biāo)準(zhǔn)差明顯小于FOA標(biāo)準(zhǔn)差。因此，得出結(jié)論，IFOA比FOA求解最優(yōu)值性能更好。

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

圖2 4種算法在函數(shù)上的收斂曲線

表1 基準(zhǔn)函數(shù)

表2 IFOA、FOA、PSO和GA的均值與標(biāo)準(zhǔn)差

表3 IFOA與FOA的魯棒性分析

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

3.2.2 魯棒性分析

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

3.3 IFOA與其他算法的比較

由表2可知，在為所有函數(shù)求解時，IFOA的均值和標(biāo)準(zhǔn)差優(yōu)于GA。且對于BR，RA和SP的求解，其均值和標(biāo)準(zhǔn)差優(yōu)于PSO?？傻弥?，IFOA比PSO和GA更有效。圖2（a）～圖2（e）的曲線也正驗證了這一結(jié)論。

由圖2（b）和圖2（c）可知，IFOA 收斂性大大提高。總體而言，IFOA的表現(xiàn)優(yōu)于PSO和GA。由表4可知，在搜尋全局最優(yōu)解時，IFOA比GA和PSO具有更高的PS。綜上所述，IFOA的魯棒性更好。

4 結(jié)論

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