基于混沌的正余弦果蠅優(yōu)化算法

張 偉， 張 亞

(安徽理工大學(xué) 電氣與信息工程學(xué)院， 安徽 淮南 232001)

果蠅優(yōu)化算法(Fruit Fly Optimization Algorithm，F(xiàn)OA)是模擬果蠅尋找食物這一過程的優(yōu)化算法，和同類算法相比，具有結(jié)構(gòu)簡單、參數(shù)少等優(yōu)點(diǎn)，被應(yīng)用于解決諸多實(shí)際問題[1,2]。文獻(xiàn)[3]將FOA和支持向量機(jī)以及季節(jié)指數(shù)調(diào)整相結(jié)合構(gòu)造模型，用來預(yù)測(cè)月度旅游流量，為更好的旅游規(guī)劃和管理提供可靠指導(dǎo)。文獻(xiàn)[4]提出一種基于FOA的隨機(jī)森林預(yù)測(cè)方法，利用FOA對(duì)隨機(jī)森林的參數(shù)進(jìn)行優(yōu)化，構(gòu)造隨機(jī)森林模型。文獻(xiàn)[5]利用FOA對(duì)多目標(biāo)函數(shù)尋優(yōu)以獲得電流的最佳參考值，實(shí)現(xiàn)對(duì)聯(lián)網(wǎng)逆變器的協(xié)調(diào)控制，提高非均衡電網(wǎng)中聯(lián)網(wǎng)逆變器的整體控制性能。文獻(xiàn)[6]將FOA與局部搜索相結(jié)合尋找復(fù)雜物流網(wǎng)絡(luò)中有容量限制的多車廂車輛的最優(yōu)路徑，提高物流配送的效率，降低運(yùn)營成本。

由于算法本身特點(diǎn)，在迭代時(shí)容易發(fā)生早熟現(xiàn)象，在解決高維數(shù)學(xué)和實(shí)際應(yīng)用問題時(shí)難以達(dá)到預(yù)期效果。因此，諸多研究人員對(duì)標(biāo)準(zhǔn)FOA進(jìn)行改進(jìn)。文獻(xiàn)[7]將該算法的迭代步長值作為設(shè)計(jì)自適應(yīng)搜索的指導(dǎo)因素，協(xié)調(diào)全局和局部搜索。在算法后期，基于正態(tài)云提出了云逃逸機(jī)制，幫助算法更好地逃離局部最優(yōu)。文獻(xiàn)[8]使用蝙蝠聲納策略搜索全局最優(yōu)值，將高斯分布和生分布組成的混合分布機(jī)制用于搜索全局最優(yōu)的局部區(qū)域。結(jié)果表明所采用方法在解決連續(xù)和離散優(yōu)化問題方面的優(yōu)越性。文獻(xiàn)[9]提出將果蠅的搜索空間由二維空間改為三維空間，擴(kuò)大搜索范圍。將固定的步長更改為線性減小的步長，以避免被困在局部最優(yōu)值中，從而提高尋找食物的精度。然后，以改進(jìn)的FOA和廣義回歸神經(jīng)網(wǎng)絡(luò)為基礎(chǔ)建立模型，進(jìn)行災(zāi)害預(yù)測(cè)。文獻(xiàn)[10]將高斯變異算子引入基本FOA以避免過早收斂，采用混沌局部搜索方法，提高了種群的局部開發(fā)能力，然后將其應(yīng)用于特征選擇問題。

上述改進(jìn)的果蠅算法，解決了一些特定問題，但仍存在收斂速度慢和陷入局部最優(yōu)的問題。因此，本文提出一種基于混沌的正余弦果蠅優(yōu)化算法(chaos-based sine-cosine fruit fly optimization algorithm，CSC-FOA)。首先，混沌初始化種群的位置，利用混沌變量的遍歷性，使初始的果蠅個(gè)體處于最優(yōu)值附近。其次，引入正余弦搜索策略使果蠅向外或向最優(yōu)解飛去，以避免陷入局部最優(yōu)，提高算法收斂速度。

1 改進(jìn)的果蠅優(yōu)化算法

果蠅普遍分布于溫?zé)釒夂蛑?，擁有極佳的嗅覺和視覺。在覓食時(shí)，果蠅先通過嗅覺判斷食物大致方位，然后用視覺確定食物所在的具體位置[1]。

1.1 混沌初始化種群

作為啟發(fā)式算法的一種，F(xiàn)OA的性能受種群初值的影響較大。若初始化種群的位置靠近最優(yōu)值，則有利于算法的收斂速度加快，精度提高。然而FOA隨機(jī)產(chǎn)生的果蠅種群位置一般并不理想，遠(yuǎn)離最優(yōu)值，降低算法后期的尋優(yōu)速度。混沌是一種常見非線性現(xiàn)象，混沌變量具有隨機(jī)性、規(guī)律性以及遍歷性的特點(diǎn)。因此，本文采用logistic映射以改善隨機(jī)初始種群對(duì)FOA性能的影響。k為當(dāng)前迭代次數(shù)，Cxi為混沌變量，其迭代公式如下：

Cx(k+1)i=uCx(k)i(1-Cx(k)i)

(1)

式中，u為控制參數(shù)。如果所求問題變量滿足xi∈[σi,φi],σi,φi分別表示該變量取值范圍的下限與上限，那么該變量可通過式(2)和式(3)混沌變量的逆映射得到。本文通過變量間的映射關(guān)系，使果蠅位置均勻地分布于解空間，然后帶入目標(biāo)函數(shù)計(jì)算，選擇其中最優(yōu)值作為初始種群位置。

Cxi=(xi-σi)/(φi-σi)

(2)

xi=σi+Cxi(φi-σi)

(3)

1.2 正余弦果蠅優(yōu)化算法

正弦余弦算法[11]是近幾年提出的一種優(yōu)化算法，首先隨機(jī)產(chǎn)生多個(gè)候選解，在探索和開發(fā)階段，通過隨機(jī)選擇正弦或余弦更新位置信息，使它們向最優(yōu)解振蕩或向外飛去。大量研究表明，這種波動(dòng)搜索方法不僅可以提高收斂速度，而且可以避免候選解落入局部最優(yōu)值。正弦余弦算法的個(gè)體位置更新公式如下：

(4)

(5)

式中：(Xijg，Yijg)表示第g次迭代第i個(gè)果蠅在第j維的位置；(X_axisg，Y_axisg)表示當(dāng)代最優(yōu)位置；r1表示控制搜索方向，也是當(dāng)前解迭代所能達(dá)到的步長極值，其公式如式(6)所示。r2，r3，r4為3個(gè)服從均勻分布的隨機(jī)數(shù)：r2表示向當(dāng)前最優(yōu)果蠅靠近或遠(yuǎn)離的程度；r3描述了果蠅受當(dāng)前最優(yōu)果蠅影響程度；r4決定了算法進(jìn)行正弦搜索還是余弦搜索。

(6)

式中：a為常數(shù)，g為迭代數(shù)，maxgen為最大迭代數(shù)。

在FOA中，果蠅采用隨機(jī)策略更新位置，然后根據(jù)果蠅位置計(jì)算味道濃度判定值，以獲得候選解。隨機(jī)策略在平衡全局搜索和局部開發(fā)方面發(fā)揮著重要作用。而隨機(jī)策略中果蠅位置的更新受最優(yōu)果蠅位置以及步長的影響，導(dǎo)致算法容易陷入局部最優(yōu)，影響收斂速度。針對(duì)隨機(jī)策略的缺點(diǎn)和正弦余弦策略的優(yōu)點(diǎn)，本文提出使用正弦余弦策略而不是隨機(jī)生成的方向和距離來提高收斂速度，解決局部最優(yōu)停滯的問題。

為了使算法更好地兼顧算法全局搜索和局部開發(fā)，對(duì)正余弦搜索策略加以改進(jìn)。其中參數(shù)r1的變化對(duì)搜索策略的性能有重要影響。因此，通過非線性的方式調(diào)整r1，先加強(qiáng)全局搜索，然后逐步向局部開發(fā)過渡，加快迭代后期的非線性遞減以加強(qiáng)局部開發(fā)。調(diào)整后的表達(dá)式如下所示。

(7)

2 實(shí)驗(yàn)及結(jié)果分析

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

為了驗(yàn)證CSC-FOA的可行性，以求解函數(shù)最小值為目標(biāo)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)選用6個(gè)單、多峰函數(shù)，其中f1、f5為2個(gè)單峰函數(shù)，f6為2維函數(shù)，其余為多維函數(shù)。測(cè)試函數(shù)的各項(xiàng)參數(shù)信息如表1所示。實(shí)驗(yàn)參數(shù)設(shè)置為：種群數(shù)sizepop=30，最大的迭代數(shù)maxgen=200。

評(píng)估算法性能優(yōu)劣采取的方法：(1)固定迭代次數(shù)，評(píng)估算法的尋優(yōu)能力和穩(wěn)定性，并與粒子群算法以及文獻(xiàn)[12]的SHFOA進(jìn)行比較。各算法參數(shù)設(shè)置為：PSO的參數(shù)c1=c2=1.5，w=0.8；FOA的參數(shù)RandomValue∈(-10,10)；SHFOA的參數(shù)Wstart=1.5，Wend=0.1；CSC-FOA的參數(shù)a=2。(2)評(píng)估算法在多峰，高維函數(shù)的尋優(yōu)性能。

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

2.2 實(shí)驗(yàn)結(jié)果和分析

2.2.1 固定迭代次數(shù)，算法的收斂速度和精度

固定算法迭代次數(shù)200次，將FOA、PSO、SHFOA和CSCFOA算法分別對(duì)函數(shù)尋優(yōu)，所得結(jié)果的均值和標(biāo)準(zhǔn)差作為評(píng)價(jià)算法優(yōu)劣的指標(biāo)。為了避免單次實(shí)驗(yàn)的偶然性導(dǎo)致對(duì)算法性能的錯(cuò)誤認(rèn)識(shí)，對(duì)每個(gè)函數(shù)進(jìn)行20次連續(xù)獨(dú)立實(shí)驗(yàn)，實(shí)驗(yàn)所得結(jié)果的平均值如表2所示。

從表中可以看出，對(duì)于多峰函數(shù)，CSC-FOA的優(yōu)化性能優(yōu)于其他算法。其中，Griewank函數(shù)的極小值點(diǎn)無數(shù)，而只有x=0時(shí)，函數(shù)取得最小值，故在算法尋優(yōu)時(shí)很難找到其全局最優(yōu)。Schaffer函數(shù)為2維多峰函數(shù)，4種算法尋優(yōu)結(jié)果較佳，且優(yōu)于對(duì)單峰函數(shù)的尋優(yōu)結(jié)果。對(duì)單峰函數(shù)Sphere和Rosenbrock，CSC-FOA的均值和標(biāo)準(zhǔn)差均優(yōu)于其他算法。其中，Rosenbrock函數(shù)的尋優(yōu)效果不明顯，與其他算法處于同一數(shù)量級(jí)。Rosenbrock函數(shù)也稱山谷函數(shù)，其最小值位于值域變化不大的山谷中，導(dǎo)致CSC-FOA的優(yōu)勢(shì)表現(xiàn)不明顯。雖然CSC-FOA對(duì)不同測(cè)試函數(shù)的尋優(yōu)性能各不相同，但對(duì)同一個(gè)測(cè)試函數(shù)，無論是單峰還是多峰，CSC-FOA的尋優(yōu)性能強(qiáng)于FOA、PSO和SHFOA。

表2 算法優(yōu)化性能比較

續(xù)表2

為了更加直觀地比較和分析算法對(duì)函數(shù)的尋優(yōu)效果，圖1～圖6為相同迭代次數(shù)下各函數(shù)的適應(yīng)度曲線(為便于觀察，除Rosenbrock函數(shù)，其余函數(shù)適應(yīng)度取以10為底的對(duì)數(shù))。從多峰函數(shù)的進(jìn)化曲線中可以看出，與FOA、PSO、SHFOA相比，CSC-FOA無論是速度還是精度均有明顯提升。尤其是Griewank函數(shù)、Rastrigin函數(shù)和Schaffer函數(shù)，效果更為明顯且尋優(yōu)結(jié)果接近最優(yōu)值。對(duì)于單峰函數(shù)，CSC-FOA也能快速收斂，尤其是Rosenbrock函數(shù)雖尋優(yōu)結(jié)果欠佳，但相比其他3種算法，收斂速度有明顯提升。總體而言，CSC-FOA算法具有更好的優(yōu)化性能。

圖1 Sphere函數(shù)適應(yīng)度進(jìn)化曲線 圖2 Griewank函數(shù)適應(yīng)度進(jìn)化曲線

圖3 Ackley函數(shù)適應(yīng)度進(jìn)化曲線 圖4 Rastrigin函數(shù)適應(yīng)度進(jìn)化曲線

圖5 Rosenbrock函數(shù)適應(yīng)度進(jìn)化曲線 圖6 Schaffer函數(shù)適應(yīng)度進(jìn)化曲線

2.2.2 算法在多峰、高維函數(shù)的性能測(cè)試

為了驗(yàn)證CSC-FOA算法對(duì)高維、多峰函數(shù)的尋優(yōu)依舊具有優(yōu)勢(shì)，在3個(gè)多峰函數(shù)的維度依次遞增情況下，對(duì)CSC-FOA算法和FOA算法優(yōu)化結(jié)果進(jìn)行比較。種群大小為sizepop=30，最大迭代數(shù)為maxgen=200，算法參數(shù)保持不變，連續(xù)運(yùn)行20次。函數(shù)的維度從30維遞增至120維。測(cè)試結(jié)果如表3所示。

表3 算法在不同維度的性能比較

從表中可以看出，隨著測(cè)試函數(shù)維度的增加，算法的尋優(yōu)性能都有所下降，但CSCFOA的下降幅度較低，保持在同一數(shù)量級(jí)。對(duì)于同一函數(shù)，CSCFOA在高維度的尋優(yōu)結(jié)果遠(yuǎn)低于FOA低維度的結(jié)果。通過結(jié)果對(duì)比，我們可以發(fā)現(xiàn)CSCFOA在多峰、高維函數(shù)的尋優(yōu)上依舊保持較快的收斂速度和較高的收斂精度，進(jìn)一步說明了本文采用改進(jìn)策略的可行性。

3 結(jié) 語

在保持果蠅優(yōu)化算法良好性能的基礎(chǔ)上，提出了基于混沌的正余弦果蠅優(yōu)化算法。將混沌變量的遍歷性特點(diǎn)應(yīng)用于初始化果蠅種群位置，降低隨機(jī)初始化對(duì)果蠅算法性能的影響。采用正余弦搜索策略更新果蠅位置而不是隨機(jī)搜索策略，提高算法尋優(yōu)速度和逃離局部最優(yōu)。通過對(duì)6個(gè)函數(shù)的尋優(yōu)實(shí)驗(yàn)，結(jié)果表明，本文提出的CSC-FOA有效地提升了尋優(yōu)精度和收斂速度，驗(yàn)證本文改進(jìn)的算法在實(shí)際問題中的可行性是下一步研究的重點(diǎn)。