張水平，高 棟

江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000

1 引言

2011年，潘文超博士提出了一種新的可用于全局優(yōu)化的群智能進(jìn)化算法[1]，即果蠅優(yōu)化算法（Fruit Fly Optimization Algorithm，F(xiàn)OA）。該算法思想源于對(duì)果蠅覓食行為的模擬，相比其他群智能算法，該算法可塑性強(qiáng)，結(jié)構(gòu)簡(jiǎn)單，易于理解且便于實(shí)現(xiàn)，僅有3 個(gè)參數(shù)需要調(diào)整（遺傳、粒子群、人工魚(yú)群算法均需調(diào)整5 個(gè)參數(shù)，蟻群算法需調(diào)整7 個(gè)參數(shù)），同時(shí)具有較快的搜索速度和較低的算法復(fù)雜度，自從提出便受到國(guó)內(nèi)外廣大學(xué)者的關(guān)注，現(xiàn)已成功地應(yīng)用于科學(xué)和工程等諸多領(lǐng)域[2]。

果蠅優(yōu)化算法作為群體智能算法的一種，其存在共性缺陷的同時(shí)，也有特性缺陷，如不能解決最優(yōu)值為負(fù)數(shù)的問(wèn)題等。針對(duì)其存在的缺陷，在近幾年的研究中，關(guān)于果蠅優(yōu)化算法的改進(jìn)和應(yīng)用逐步涌現(xiàn)。馬巧梅等[3]對(duì)味道濃度進(jìn)行修正，一定程度上解決了味道濃度判定值不能為負(fù)數(shù)的問(wèn)題；信成濤等[4]通過(guò)對(duì)個(gè)體的搜索距離進(jìn)行自適應(yīng)調(diào)整，使算法的收斂精度得到提升；張前圖[5]、劉成忠[6]等對(duì)種群進(jìn)行劃分，進(jìn)行多種群協(xié)調(diào)搜索以達(dá)到平衡全局和局部搜索能力的目的；張彩宏等[7]提出設(shè)計(jì)混合算法，從而提高了算法的局部尋優(yōu)能力。上述改進(jìn)算法都在一定程度上提高了果蠅優(yōu)化算法的優(yōu)化性能，但均未對(duì)種群的進(jìn)化方向進(jìn)行充分的利用；部分改進(jìn)算法在尋優(yōu)過(guò)程中未對(duì)種群的多樣性進(jìn)行動(dòng)態(tài)調(diào)整，以降低算法陷入局部最優(yōu)的概率；當(dāng)算法陷入局部最優(yōu)時(shí)，其跳出局部最優(yōu)的能力不強(qiáng)，尋優(yōu)速度和尋優(yōu)精度還有待于進(jìn)一步提高。

本文研究提出了一種動(dòng)態(tài)調(diào)整搜索策略的果蠅優(yōu)化算法（Fruit fly Optimization Algorithm with Dynamic Adjustment of Search Strategy，F(xiàn)OAASS）。該改進(jìn)算法從種群位置初始化、尋優(yōu)搜索策略、迭代搜索半徑、跳出局部最優(yōu)四方面進(jìn)行優(yōu)化。對(duì)6 個(gè)經(jīng)典性能函數(shù)進(jìn)行仿真運(yùn)算，結(jié)果表明，本文提出的改進(jìn)算法有較好的尋優(yōu)精度和收斂速度。

2 標(biāo)準(zhǔn)果蠅優(yōu)化算法

果蠅群體廣泛分布在熱帶和溫帶地區(qū)，相比其他生物，其嗅覺(jué)和視覺(jué)能力更為發(fā)達(dá)。在覓食過(guò)程中，果蠅先利用自身的嗅覺(jué)發(fā)現(xiàn)食物氣味，并將氣味信息發(fā)送給周?chē)墓墸ɑ蚪邮沼芍車(chē)壈l(fā)送的氣味信息）；之后，通過(guò)對(duì)比得到當(dāng)前種群中獲取最優(yōu)氣味信息的果蠅個(gè)體位置，群體中的其他果蠅均利用其發(fā)達(dá)的視覺(jué)器官向該位置飛去，并繼續(xù)進(jìn)行搜索[8]。

根據(jù)以上所述果蠅覓食行為的特點(diǎn)，可將標(biāo)準(zhǔn)果蠅優(yōu)化算法歸納為以下7個(gè)必要的尋優(yōu)步驟[9]：

步驟1 初始化設(shè)置算法的相關(guān)參數(shù)，主要包括算法運(yùn)行的最大迭代次數(shù)(MaxTimes) 、果蠅種群的規(guī)模(SizePop) 、果蠅群體的可活動(dòng)范圍(LR) 和搜索半徑(SR)，并根據(jù)式（1）隨機(jī)初始化種群中每個(gè)果蠅個(gè)體的初始位置(X_axis,Y_axis)。

步驟2 賦予每只果蠅隨機(jī)搜索的距離方向。

步驟3 計(jì)算種群中每只果蠅個(gè)體的位置坐標(biāo)與坐標(biāo)原點(diǎn)的距離Disti和其味道濃度判定值Si，其中Si為Disti的倒數(shù)。

步驟4 將味道濃度判定值Si帶入適應(yīng)度函數(shù)（或目標(biāo)函數(shù)）中，計(jì)算種群中每個(gè)果蠅個(gè)體的味道濃度值Smelli。

步驟5 找出當(dāng)前種群中味道濃度值最佳的果蠅個(gè)體，記錄其位置信息和相應(yīng)的味道濃度值。

步驟6 保留最優(yōu)迭代坐標(biāo)和最佳味道濃度值，群體中的其他果蠅均利用視覺(jué)向該位置飛去。

步驟7 開(kāi)始進(jìn)行迭代尋優(yōu)，將步驟2～步驟5重復(fù)執(zhí)行，并同時(shí)判斷當(dāng)前的迭代次數(shù)是否小于最大迭代次數(shù)，當(dāng)前迭代所求得的味道濃度是否優(yōu)于歷史味道濃度，若均是，則執(zhí)行步驟6。

3 動(dòng)態(tài)調(diào)整搜索策略的FOA

針對(duì)標(biāo)準(zhǔn)FOA 存在的缺陷，F(xiàn)OAASS 分別從四方面進(jìn)行改進(jìn)：采用“以迭代次數(shù)換取初始位置數(shù)量”的策略，擴(kuò)大初始位置數(shù)量，并利用混沌映射增強(qiáng)初始位置的均勻性和隨機(jī)性；改變種群中部分果蠅的尋優(yōu)策略，使其沿著種群中心點(diǎn)及全局最優(yōu)解的連線(xiàn)或延長(zhǎng)線(xiàn)進(jìn)行搜索；采用新的搜索半徑計(jì)算方式，通過(guò)種群進(jìn)化信息動(dòng)態(tài)調(diào)整其大小，同時(shí)引入轉(zhuǎn)換概率，使果蠅在每次嗅覺(jué)搜索時(shí)隨機(jī)選取搜索范圍，平衡局部和全局搜索之間的能力；通過(guò)種群適應(yīng)度方差判斷算法是否陷入早熟，當(dāng)陷入早熟時(shí)，改變種群中所有果蠅個(gè)體下次迭代的搜索策略，不再繞全局最優(yōu)點(diǎn)飛行，而是隨機(jī)進(jìn)行混合變異，此策略在一定程度上提高了種群的多樣性，并有較大可能跳出局部最優(yōu)點(diǎn)。

3.1 利用混沌映射確定種群初始位置

在算法運(yùn)行的過(guò)程中，種群初始位置所產(chǎn)生的解的質(zhì)量起到了至關(guān)重要的作用，好的初始位置，既有利于找到全局最優(yōu)解，也能加快算法的收斂速度。分析可知，初始解的質(zhì)量受到種群中初始位置的數(shù)量及分布情況兩方面的影響。

3.1.1通過(guò)等價(jià)替換增大初始位置數(shù)量

為了在實(shí)驗(yàn)初期得到較多的初始位置點(diǎn)，本文提出采用“犧牲迭代次數(shù)換取初始位置個(gè)數(shù)”的策略（在FOA中，迭代N次將遍歷N×SizePop個(gè)位置矢量），在算法運(yùn)行時(shí)，用N倍的迭代次數(shù)換取M個(gè)位置點(diǎn)，一定程度上可以提高初始解的質(zhì)量。

3.1.2通過(guò)混沌映射改善初始位置分布

隨機(jī)產(chǎn)生的初始位置可能導(dǎo)致果蠅群體不能均勻分布，從而導(dǎo)致果蠅群體不能全面地搜索解空間?；煦缬成渚哂须S機(jī)性、遍歷性和規(guī)律性等特點(diǎn)，其基本思想是將待優(yōu)化變量通過(guò)混沌映射規(guī)則映射到混沌變量空間的取值區(qū)間，利用混沌變量的遍歷性和規(guī)律性進(jìn)行尋優(yōu)搜索，之后將獲得的優(yōu)化解線(xiàn)性轉(zhuǎn)化到優(yōu)化空間中[10]。

本文首先將果蠅種群的位置映射到（0，1）區(qū)間，映射公式如下所示。

其中，zmax和zmin為種群中個(gè)體位置的最大值和最小值。

然后將得到的數(shù)值利用Logistic映射[11]產(chǎn)生混沌值z(mì)ci+1，并以此更新初始果蠅種群。本文使用的映射迭代如下所示：

其中，μ是控制參數(shù)，隨著μ值的增大，序列的分布越來(lái)越均勻，當(dāng)μ等于 4 時(shí)，Logistic 映射的分布最均勻，本文中μ取值為4。

最后通過(guò)式（12）將經(jīng)過(guò)混沌映射后的混沌值轉(zhuǎn)化到種群的變量空間中，從而使果蠅種群的初始位置分布更加均勻。

3.2 調(diào)整部分果蠅尋優(yōu)策略

在標(biāo)準(zhǔn)果蠅優(yōu)化算法中，群體中的所有果蠅均圍繞最優(yōu)位置進(jìn)行搜索尋優(yōu)，未考慮果蠅種群的迭代進(jìn)化方向信息。通過(guò)大量實(shí)驗(yàn)研究FOA算法中果蠅的飛行路徑，發(fā)現(xiàn)果蠅種群的進(jìn)化方向是有一定規(guī)律可循的。圖1給出了30次迭代的種群中心點(diǎn)二維坐標(biāo)和最優(yōu)個(gè)體飛行路徑，雖然并不是每次迭代的最優(yōu)位置和種群中心點(diǎn)連線(xiàn)及延長(zhǎng)線(xiàn)上的點(diǎn)均接近下次迭代的最優(yōu)值，但從總體上看來(lái)，沿著該方向更容易找到下次迭代的最優(yōu)位置。通過(guò)以上規(guī)律，可以一定程度上預(yù)測(cè)下次迭代的進(jìn)化方向，并可以將其推廣到高維空間中。

圖1 果蠅尋優(yōu)路徑及種群中心點(diǎn)位置

因此，本文動(dòng)態(tài)調(diào)整果蠅的尋優(yōu)策略，使得果蠅群體中1/4 的果蠅沿著預(yù)計(jì)的進(jìn)化方向進(jìn)行直線(xiàn)搜索，如式（13）所示，其他果蠅環(huán)繞最優(yōu)位置進(jìn)行搜索，此策略一定程度上可以加快尋優(yōu)速度并提高種群多樣性。

其中，avg為種群位置的中心點(diǎn)，λ為[-2,3]之間的隨機(jī)數(shù)，當(dāng) 0 ≤λ≤1 時(shí)，將生成兩點(diǎn)連線(xiàn)上的點(diǎn)，當(dāng)λ>1時(shí)，將生成中心點(diǎn)端點(diǎn)外延長(zhǎng)線(xiàn)上的點(diǎn)，當(dāng)λ<0時(shí)，將取得最優(yōu)位置點(diǎn)外延長(zhǎng)線(xiàn)上的點(diǎn)。

3.3 隨機(jī)選取動(dòng)態(tài)搜索半徑

果蠅優(yōu)化算法的重要研究方向之一是對(duì)搜索半徑進(jìn)行改進(jìn)，標(biāo)準(zhǔn)果蠅優(yōu)化算法中以固定半徑進(jìn)行隨機(jī)搜索，多數(shù)改進(jìn)的果蠅優(yōu)化算法均采用搜索半徑遞減或自適應(yīng)的策略，使算法在迭代初期有較大的搜索半徑，從而加強(qiáng)全局搜索能力，隨著迭代次數(shù)的增加，算法后期的搜索范圍逐漸減少以便進(jìn)行精細(xì)搜索，此改進(jìn)一定程度上增強(qiáng)了算法的尋優(yōu)性能。分析發(fā)現(xiàn)，無(wú)論是標(biāo)準(zhǔn)FOA，還是現(xiàn)有的改進(jìn)算法，在同一次迭代過(guò)程中，種群中每個(gè)果蠅的搜索范圍都是相同的，并沒(méi)有具體的分工。因此，本文結(jié)合果蠅種群進(jìn)化信息設(shè)計(jì)了新的搜索半徑計(jì)算方式：

其中，SR1、SR2、SR3分別為三種不同的搜索半徑計(jì)算公式，SRmin為最小搜索半徑，SRmax為最大搜索半徑，SR0為初始搜索半徑，MaxT為最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)，avgSmt、bestSmt分別為第t次迭代時(shí)，種群中平均味道濃度和最優(yōu)味道濃度值，旨在引入濃度差值變化率[12]。

為了明確種群中果蠅個(gè)體的分工，引入轉(zhuǎn)換概率p(p∈[0,1])，在每次迭代時(shí)將果蠅種群隨機(jī)分為三類(lèi)：當(dāng)0 ≤p≤0.25 時(shí)，搜索半徑通過(guò)遞增公式SR1生成，有利于部分果蠅進(jìn)行全局搜索并盡可能跳出局部最優(yōu)；當(dāng)0.25

3.4 更改策略以跳出局部最優(yōu)

以上對(duì)種群位置初始化、尋優(yōu)搜索策略及迭代搜索半徑進(jìn)行優(yōu)化，提高了算法的搜索速度和尋優(yōu)精度，也在一定程度上降低了算法發(fā)生早熟收斂的可能性，但是群智能算法的特性決定了其仍然無(wú)法避免陷入局部最優(yōu)，一旦受到局部最優(yōu)值的約束，現(xiàn)有搜索策略很難擺脫束縛。

因此，本文以種群味道濃度方差(α2)判斷算法是否陷入局部最優(yōu)，α2反映了果蠅種群的聚集程度，α2越大，代表種群的聚集程度提高，種群多樣性降低，算法的尋優(yōu)過(guò)程逐步陷入停滯狀態(tài)[13]。種群味道濃度方差α2計(jì)算公式如下：

式中，平均味道濃度值avgSmt由式（17）確定。

算法在運(yùn)行時(shí)，當(dāng)α2≤η（η代表種群的味道濃度方差閾值）時(shí)，認(rèn)定種群陷入局部最優(yōu)，此時(shí)更改下次迭代的搜索策略，果蠅個(gè)體均不再?lài)@最優(yōu)位置進(jìn)行隨機(jī)搜索，而是對(duì)所有果蠅位置進(jìn)行隨機(jī)的混合變異（群體中的1/2果蠅進(jìn)行高斯變異，1/2的果蠅進(jìn)行非均勻變異），增強(qiáng)種群中個(gè)體的逃逸能力，從而跳出局部，拓展新的進(jìn)化方向，在空間中的其他區(qū)域繼續(xù)搜索，直到找到全局最優(yōu)值。

高斯變異是指將一個(gè)服從高斯分布的隨機(jī)擾動(dòng)項(xiàng)加在原有個(gè)體的狀態(tài)上，如式（19）所示。

式中，N(0,1)為標(biāo)準(zhǔn)高斯分布。

非均勻變異是對(duì)原有的位置做隨機(jī)擾動(dòng)，以擾動(dòng)后的結(jié)果作為變異后的新位置[14]，如式（20）所示。

式中，[LB,UB]為果蠅的搜索范圍，r為[0，1]區(qū)間均勻分布的隨機(jī)數(shù)，Δ(x,y)的值由式（21）確定，t是當(dāng)前迭代次數(shù)，MaxT是最大迭代次數(shù)，b是決定變異運(yùn)算時(shí)非均勻度的系統(tǒng)參數(shù)。

3.5 FOAASS算法實(shí)現(xiàn)步驟

基于標(biāo)準(zhǔn)果蠅優(yōu)化算法原理及上述改進(jìn)方法，本文動(dòng)態(tài)調(diào)整進(jìn)化方向的果蠅優(yōu)化算法具體尋優(yōu)步驟如下：

步驟1 參數(shù)初始化，設(shè)置種群規(guī)模SizePop、最大迭代次數(shù)MaxTimes、味道濃度方差閾值η、等價(jià)替換因子N、初始搜索半徑SR0等。

步驟2 種群位置初始化。首先利用“等價(jià)替換”原則確定初始位置數(shù)量；其次通過(guò)混沌映射改善種群初始位置(X_axis,Y_axis)的質(zhì)量。

步驟3 運(yùn)行標(biāo)準(zhǔn)果蠅優(yōu)化算法中的步驟2～步驟5一次，從而得到初始解等信息，并由式（18）計(jì)算種群初始味道濃度方差α2。

步驟4 進(jìn)行方差判斷，若α2≤η，則認(rèn)定算法陷入局部最優(yōu)，轉(zhuǎn)至步驟6調(diào)整搜索策略，否則轉(zhuǎn)至步驟5。

步驟5 根據(jù)式（13）～（15）計(jì)算種群中前1/4 的果蠅位置信息，其余果蠅隨機(jī)選擇搜索半徑并通過(guò)式（2）更新位置信息，然后轉(zhuǎn)至步驟7。

步驟6 進(jìn)行變異操作，利用式（19）對(duì)群體中部分果蠅位置進(jìn)行高斯變異，其余果蠅位置利用式（20）進(jìn)行非均勻變異，完成后轉(zhuǎn)至步驟7。

步驟7 執(zhí)行標(biāo)準(zhǔn)果蠅優(yōu)化算法中的步驟3～步驟6。

步驟8 利用式（18）更新種群內(nèi)的味道濃度方差α2，并利用式（16）計(jì)算下次迭代的搜索半徑。

步驟9 判斷是否滿(mǎn)足終止條件，若滿(mǎn)足條件，則轉(zhuǎn)至步驟10，否則轉(zhuǎn)至步驟4進(jìn)行下一次尋優(yōu)探索。

步驟10 輸出全局最優(yōu)解。

改進(jìn)算法具有了防止算法早熟收斂及跳出局部最優(yōu)的能力。FOAASS算法運(yùn)行的偽代碼如下所示。

算法動(dòng)態(tài)調(diào)整搜索策略的果蠅優(yōu)化算法

輸入：目標(biāo)函數(shù)f(x)、種群規(guī)模SP、味道濃度方差閾值η、最大迭代次數(shù)MT、初始搜索半徑SR0等。

輸出：全局最優(yōu)解。

1. 利用等價(jià)替換及混沌映射初始化種群

2. 在初始種群中找到最優(yōu)解SmellBest，并利用式（18）計(jì)算初始種群味道濃度方差α2

3. fort=1:MT-N

4. fori=1:SP%循環(huán)遍歷果蠅個(gè)體

5. ifα2＜η

6. 隨機(jī)選取式（19）或式（20）更新位置

7. else

8. ifi

9. 按照式（13）、（14）、（15）更新位置

10. else

11. 按照式（2）更新位置

12. end

13. end

14. 對(duì)生成的位置進(jìn)行邊界化處理

15. 將處理后的位置代入式（3）、（4）、（5）得到味道濃度值

16. end %果蠅個(gè)體迭代結(jié)束

17. 找到種群中最優(yōu)的解

18. 判斷本次循環(huán)得到的解是否優(yōu)于全局最優(yōu)解，若是，更新全局最優(yōu)解和最優(yōu)位置

19. 利用式（18）重新計(jì)算種群味道濃度方差α2

20. 利用式（20）計(jì)算下次迭代的搜索半徑SR

21. end %迭代循環(huán)結(jié)束

22. 輸出找到的最優(yōu)解

3.6 FOAASS算法時(shí)間復(fù)雜度分析

時(shí)間復(fù)雜度是指算法執(zhí)行所需要的計(jì)算工作量，主要取決于問(wèn)題重復(fù)執(zhí)行的次數(shù)。在標(biāo)準(zhǔn)果蠅優(yōu)化算法中，時(shí)間復(fù)雜度主要受到種群規(guī)模S和迭代次數(shù)M的影響，在迭代過(guò)程中，每個(gè)個(gè)體迭代需要的計(jì)算量為O(1)，則FOA算法的時(shí)間復(fù)雜度為O(N×M)。

FOAASS 算法是由FOA 算法改進(jìn)而來(lái)，根據(jù) 3.5 節(jié)中算法步驟和偽代碼可知，F(xiàn)OAASS在FOA算法的基礎(chǔ)上增加了計(jì)算搜索半徑、計(jì)算味道濃度方差、判斷調(diào)整搜索策略等步驟：第20步搜索半徑的計(jì)算復(fù)雜度為O(M)，第19 步種群味道濃度方差計(jì)算復(fù)雜度為O(M)，第5～13 步循環(huán)判斷調(diào)整搜索策略的計(jì)算復(fù)雜度為O(N×M),因此本文算法的時(shí)間復(fù)雜度為O(N×M+N×M)。

由上述分析可知，F(xiàn)OAASS算法的時(shí)間復(fù)雜度相對(duì)較高，這是提高尋優(yōu)精度和收斂速度所付出的代價(jià)，尋求較低的時(shí)間復(fù)雜度將是日后研究的重點(diǎn)。

4 實(shí)驗(yàn)仿真與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

為了檢驗(yàn)本文所提出算法的有效性，選取了6個(gè)經(jīng)典性能測(cè)試函數(shù)對(duì)標(biāo)準(zhǔn)果蠅優(yōu)化算法、本文改進(jìn)算法和參考文獻(xiàn)中的四種改進(jìn)算法在相同環(huán)境下進(jìn)行Matlab4仿真實(shí)驗(yàn)對(duì)比（求最小值），一是比較算法的收斂速度和尋優(yōu)精度（通過(guò)固定種群規(guī)模和迭代次數(shù)），二是比較算法的成功率和平均迭代次數(shù)（通過(guò)固定收斂精度）[15]。

表1 列出了6 個(gè)測(cè)試函數(shù)的名稱(chēng)、表達(dá)式、搜索空間、維度及峰值等信息。當(dāng)函數(shù)的自變量搜索空間越廣、維度越大、目標(biāo)的收斂精度越高時(shí)，順利搜索到最優(yōu)解的難度也就越大，對(duì)所優(yōu)化的算法的性能要求就越高。

4.2 固定種群規(guī)模和迭代次數(shù)的性能測(cè)試

為了降低算法隨機(jī)性對(duì)實(shí)驗(yàn)數(shù)據(jù)的影響，以20次獨(dú)立實(shí)驗(yàn)的平均值作為評(píng)估算法收斂速度和收斂精度的最終結(jié)果。具體參數(shù)設(shè)置如下：種群規(guī)模SizePop=30,最大迭代次數(shù)MaxTimes=1 000，等價(jià)替換因子N=10，6個(gè)測(cè)試函數(shù)的味道濃度方差閾值η均為1×10－6，初始、最大、最小搜索半徑分別為1、2、0.5。

表2給出了FOA算法、FOAASS算法和文獻(xiàn)[16-19]中的 ASCEFOA 算法[16]、MFOAADS 算法[17]、DCFOA 算法[18]、FOAMR 算法[19]在不同函數(shù)上的最優(yōu)值（best）、平均值（avg）、最差值（worst）和標(biāo)準(zhǔn)差（sd），結(jié)果保留4位小數(shù)，其中解的質(zhì)量由最優(yōu)值和最差值反映，算法所能達(dá)到的精度由平均值反映，算法的魯棒性及穩(wěn)定性由標(biāo)準(zhǔn)差反映。

表1 測(cè)試函數(shù)參數(shù)設(shè)置

表2 6種算法性能比較

從整體上看，無(wú)論多峰還是單峰函數(shù)，F(xiàn)OAASS算法都比FOA 算法有更好的搜索能力，整體上優(yōu)于文獻(xiàn)[16-19]中的算法，同時(shí)具有更快的收斂速度。其中Schaffer 函數(shù)、Sphere 函數(shù)、Griewank 函數(shù)、Rastrigin 函數(shù)都可以達(dá)到理論最優(yōu)值，對(duì)于A(yíng)ckley 函數(shù)，F(xiàn)OAASS相比FOA 算法在最優(yōu)解的精度上提高了14 個(gè)數(shù)量級(jí)，但是對(duì)于Rosenbrock 函數(shù)，其改進(jìn)效果并不明顯，搜索精度提升得有限。

圖2給出了以上6種算法在不同測(cè)試函數(shù)上進(jìn)行迭代尋優(yōu)的對(duì)比曲線(xiàn)，橫坐標(biāo)為迭代次數(shù)。同時(shí)為了更好地觀(guān)察對(duì)比兩種算法的迭代曲線(xiàn)，將得到的最佳味道濃度值取以10 為底的對(duì)數(shù)，則縱坐標(biāo)為收斂精度。結(jié)合迭代曲線(xiàn)及實(shí)驗(yàn)數(shù)據(jù)，分析如下：

（1）對(duì)比較簡(jiǎn)單的單峰值Sphere 函數(shù)而言，其尋優(yōu)難度并不是太大，F(xiàn)OAASS算法在迭代初期就沿著正確的方向逼近最優(yōu)解，并在第500次迭代左右便搜索到理論最優(yōu)值，標(biāo)準(zhǔn)差為0亦表明了改進(jìn)算法尋優(yōu)的穩(wěn)定性良好，相比另外4種改進(jìn)算法，可以更迅速地找到最優(yōu)解。

（2）Griewank函數(shù)是一種具有無(wú)數(shù)局部極小值點(diǎn)的可變維高峰函數(shù)，由圖2（b）可知，F(xiàn)OA 算法在第100 次迭代左右便陷入了局部極值點(diǎn)且一直無(wú)法跳出，但FOAASS、ASCEFOA、MFOAADS算法均可跳出局部極值點(diǎn)并繼續(xù)在大范圍內(nèi)搜索，直到找到全局最優(yōu)點(diǎn)，具有更好的穩(wěn)定性。

（3）由圖2可知，在6個(gè)性能測(cè)試函數(shù)中，6種算法對(duì)Rosenbrock函數(shù)進(jìn)行求解的性能均較差。雖然FOAASS算法相比其他4 種改進(jìn)算法，其求解的精度略有提高，但相比其他函數(shù)，對(duì)本函數(shù)的優(yōu)化效果不明顯。從函數(shù)本身分析，其全局最優(yōu)點(diǎn)位于一條平滑而狹長(zhǎng)的拋物線(xiàn)形狀的山谷底部，為算法提供的信息很少，算法很難辨別搜索方向，因此找到其全局極小值就顯得特別困難[20]。為此，接下來(lái)的算法改進(jìn)將考慮引入三角函數(shù)因子，利用三角函數(shù)具有的周期震蕩性使每個(gè)個(gè)體可獲得較強(qiáng)的震蕩性，并擴(kuò)大每個(gè)個(gè)體的搜索空間，從而可以引導(dǎo)個(gè)體逐步向全局最優(yōu)點(diǎn)靠近，以提高算法對(duì)本函數(shù)的求解精度或找到全局最優(yōu)點(diǎn)的概率。

（4）Rastrigin函數(shù)的三維空間圖形類(lèi)似于無(wú)數(shù)起伏不平的山峰，在迭代尋優(yōu)的過(guò)程中，F(xiàn)OA 和FOAMR 算法在第100次左右便陷入局部最優(yōu)，并一直在局部最優(yōu)點(diǎn)徘徊，無(wú)法跳出；FOAASS 和ASCEFOA 算法在尋優(yōu)過(guò)程中也會(huì)陷入局部極值點(diǎn)，但均可多次跳出局部極值點(diǎn)并找到全局最優(yōu)點(diǎn)。

（5）Ackley 函數(shù)是一種具有爬山形態(tài)的多峰值函數(shù)，全局最優(yōu)值極難尋找，從圖2（e）可以看出，F(xiàn)OA 算法對(duì)其求解的精度不高，尋優(yōu)速度十分緩慢，在迭代初期就陷入了局部最優(yōu)；MFOAADS和FOAMR算法對(duì)其尋優(yōu)精度略有提升；ASCEFOA 算法雖然在第100 次迭代左右便可迅速找到較高精度的解，但是其最終結(jié)果相比FOAASS算法的求解精度略有不足。

（6）由圖2（f）可知，F(xiàn)OA 和MFOAADS 算法對(duì)具有震蕩性、多峰值、多次優(yōu)點(diǎn)的Schaffer 函數(shù)尋優(yōu)難度較大，容易陷入局部最優(yōu)且難以逃離；FOAMR、DCFOA和ASCEFOA 算法對(duì)函數(shù)的求解精度及速度逐步提升，但均無(wú)法找到理論最優(yōu)值；FOAASS算法可迅速跳出并找到理論最優(yōu)值，其收斂速度和收斂精度均遠(yuǎn)遠(yuǎn)好于FOA算法，全局收斂性能相比而言更好。

圖2 函數(shù)進(jìn)化曲線(xiàn)

表3 算法成功率和平均迭代次數(shù)比較

經(jīng)上述分析可知，本文提出的FOAASS算法優(yōu)于標(biāo)準(zhǔn)的FOA 算法，雖然對(duì)Rosenbrock 函數(shù)的尋優(yōu)效果不理想，只提升了有限的搜索精度，但對(duì)另外5 個(gè)函數(shù)的尋優(yōu)效果均比其他4種改進(jìn)算法要好，充分說(shuō)明了本文的改進(jìn)算法具有更高的收斂精度和更好的搜索能力，同時(shí)更容易跳出局部最優(yōu)。

4.3 固定收斂精度下的性能測(cè)試

為了更好地驗(yàn)證FOAASS算法的收斂性，通過(guò)設(shè)置固定的收斂精度，對(duì)6 個(gè)測(cè)試函數(shù)進(jìn)行了性能測(cè)試，其20 次獨(dú)立運(yùn)行實(shí)驗(yàn)的成功率(K)和平均迭代次數(shù)(T)如表3 所示。在表3 中，成功率=達(dá)到精度的運(yùn)行次數(shù)/總次數(shù)，“—”表示該參考文獻(xiàn)未給出相關(guān)數(shù)據(jù)，“D”表示該實(shí)驗(yàn)所用的目標(biāo)精度。

分析可知，本文提出的FOAASS算法在6個(gè)測(cè)試函數(shù)上進(jìn)行了20 次獨(dú)立運(yùn)行實(shí)驗(yàn)，都很早達(dá)到了目標(biāo)精度，并且成功率均為100%。對(duì)于Rastrigin函數(shù)和Ackley函數(shù)，F(xiàn)OAASS 算法設(shè)置了更高的求解精度，但尋優(yōu)效果依舊不錯(cuò)。從整體上講，在固定收斂精度的情況下，F(xiàn)OAASS 算法具有更高的尋優(yōu)效率和更好的尋優(yōu)可信性，尋優(yōu)性能相對(duì)而言更好。

5 總結(jié)

通過(guò)對(duì)標(biāo)準(zhǔn)果蠅算法進(jìn)行分析，針對(duì)其存在的缺陷并結(jié)合現(xiàn)有文獻(xiàn)對(duì)其做出的改進(jìn)，本文提出了一種動(dòng)態(tài)調(diào)整搜索策略的改進(jìn)算法。在種群初始化過(guò)程中進(jìn)行等價(jià)替換和混沌映射，使果蠅種群初始解的質(zhì)量更好；調(diào)整部分果蠅的搜索策略，以引導(dǎo)種群在進(jìn)化過(guò)程中保持正確的搜索方向；隨機(jī)選取動(dòng)態(tài)搜索半徑，對(duì)種群內(nèi)的果蠅進(jìn)行分工；采用混合變異策略，方便跳出局部最優(yōu)。

最后，進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明本文算法相比標(biāo)準(zhǔn)FOA具有更高的求解精度、更快的求解速度和更好的穩(wěn)定性，比參考文獻(xiàn)中的改進(jìn)算法更易于跳出局部最優(yōu)并得到全局最優(yōu)，尋優(yōu)可信性更強(qiáng)。本文的改進(jìn)算法也存在時(shí)間復(fù)雜度較高、對(duì)個(gè)別函數(shù)尋優(yōu)效果不理想等缺陷，因此，尋求較低的時(shí)間復(fù)雜度，提高算法在部分函數(shù)上的尋優(yōu)性能，對(duì)算法的收斂性進(jìn)行詳細(xì)的研究分析以解決生活中的實(shí)際問(wèn)題，將是下一步研究的工作重點(diǎn)。