混沌動態(tài)步長果蠅優(yōu)化算法*

廖建慶， 王 涵， 王咸鵬

(1.宜春學(xué)院 物理科學(xué)與工程技術(shù)學(xué)院，江西 宜春 336000； 2.海南大學(xué) 南海海洋資源利用國家重點(diǎn)實(shí)驗(yàn)室，海南 ?？?570228)

0 引 言

果蠅算法[1](fruit fly optimization algorithm，F(xiàn)OA)是臺灣學(xué)者潘文超首次提出的一種新的群智能算法。該算法是一種基于果蠅覓食行為而推演出的全局優(yōu)化算法，已成功應(yīng)用于求解函數(shù)優(yōu)化[2]、PID控制參數(shù)優(yōu)化[3]、支持向量機(jī)參數(shù)優(yōu)化[4]等領(lǐng)域。由于FOA起步較晚，雖然國內(nèi)外相關(guān)研究成果比較多，對算法的改進(jìn)研究也比較成熟，但較少有文獻(xiàn)從理論上對FOA及其改進(jìn)算法的收斂性方面做深入研究。相較其他群智能算法，F(xiàn)OA具有結(jié)構(gòu)和計算簡單、運(yùn)行時間和可調(diào)參數(shù)少等優(yōu)點(diǎn)[5]。比如FOA僅有4個參數(shù)需要調(diào)整，而有些優(yōu)化算法需要調(diào)整的參數(shù)相對較多，較多的參數(shù)不僅增大了調(diào)整工作量，而且還給算法分析帶來巨大困難，有時甚至還會出現(xiàn)使用一種算法去優(yōu)化另一種算法參數(shù)的情況。當(dāng)然，由于算法自身的特點(diǎn)，F(xiàn)OA與其他優(yōu)化算法一樣，也存在局部最優(yōu)、早熟收斂等不足。

本文提出了一種混沌動態(tài)步長改進(jìn)的果蠅優(yōu)化算法(modified fruit fly optimization algorithm with chaotic dynamical step factor,CDSFOA)，通過利用混沌特性來提高果蠅種群的多樣性和搜索的遍歷性，引入混沌擾動變量來提高算法的持續(xù)搜索能力；同時，通過引入動態(tài)步長調(diào)節(jié)因子對果蠅搜索步長進(jìn)行隨機(jī)動態(tài)調(diào)節(jié)，使得算法的收斂速度得到進(jìn)一步提高。因此，提出算法能有效地提高種群的多樣性和搜索的遍歷性，進(jìn)而提高算法精度，避免陷入局部最優(yōu)。

1 標(biāo)準(zhǔn)果蠅優(yōu)化算法[6]

1)初始化:種群規(guī)模數(shù)、最大迭代次數(shù)和隨機(jī)初始化果蠅群體位置;

2) 給果蠅方向和距離分配隨機(jī)參數(shù)，產(chǎn)生新位置;

3)估算果蠅與原點(diǎn)之間距離Disti，再計算味道濃度判定值Si;

4) 將Si分別代入味道濃度判定函數(shù)，求出果蠅位置味道濃度Smelli;

5)對Smelli值進(jìn)行排序，找出當(dāng)前Smelli最大的果蠅個體;

6) 根據(jù)最佳果蠅序號和位置，此時所有果蠅利用視覺向最佳位置飛去;

7) 最后迭代運(yùn)算，重復(fù)步驟(2)～步驟(5)，在尋優(yōu)過程中判斷當(dāng)前最佳味道濃度是否優(yōu)于上一迭代結(jié)果，且判斷當(dāng)前迭代次數(shù)是否小于最大迭代數(shù)；若是則執(zhí)行步驟(6)，否則結(jié)束。

2 混沌動態(tài)步長果蠅優(yōu)化算法

2.1 動態(tài)步長調(diào)整策略

在基本FOA中，迭代步長的選擇直接影響最佳濃度位置，進(jìn)而影響算法收斂速度和精度。本文借鑒文獻(xiàn)[7]的思想，引入一種動態(tài)步長因子(dynamic step factor，DSF)來動態(tài)地調(diào)節(jié)搜索步長，即對方向與距離產(chǎn)生的隨機(jī)搜索步長(Randvalue)分配不同的步長調(diào)節(jié)因子w(n)來實(shí)現(xiàn)對其自適應(yīng)地動態(tài)調(diào)節(jié)

w(n)=w0·exp[-20(n/M)a]

(1)

Randvalue=w(n)×(2·rand-1)

(2)

式中n為迭代次數(shù)，M為最大迭代次數(shù)Maxgen，w(n)為動態(tài)步長調(diào)節(jié)因子，a為調(diào)節(jié)參數(shù)，是可視具體情況取值范圍為[1,30]的整數(shù)[8]，rand∈[0,1]為隨機(jī)函數(shù)。則果蠅個體利用嗅覺搜尋食物的隨機(jī)方向與距離表達(dá)式調(diào)整為

式中 (X0，Y0)為隨機(jī)初始化果繩群體位置。則動態(tài)步長調(diào)節(jié)因子w(n)隨迭代次數(shù)的動態(tài)變化。

2.2 混沌優(yōu)化

混沌優(yōu)化算法[9]是一種利用混沌運(yùn)動特性進(jìn)行優(yōu)化搜索方法，本文引入Logistic映射，其數(shù)學(xué)模型為

x(k+1)=μx(k)[1-x(k)]

(4)

式中k為迭代次數(shù)，x(k)∈[0,1],μ為控制變量，研究表明，當(dāng)x(k)≠0,1時，Logistic映射處于混沌狀態(tài)[10]。依據(jù)式(4)，混沌變量Cxj(k)的一種變換式為

Cxj(k+1)=4Cxj(k)(1-Cxj(k))

(5)

式中Cxj為第j個混沌變量，顯然當(dāng)Cxj(0)≠0,1時，將產(chǎn)生混沌現(xiàn)象。式(5)中的優(yōu)化變量xj(k)∈[xL,j,xU,j]，利用式(6)和式(7)與混沌變量Cxj(k+1)進(jìn)行往返映射

Cxj(k)=(xj(k)-xL,j)/(xU,j-xL,j)

(6)

式中xL,j和xU,j(j=1,2,…,n)分別為第j維變量的搜索上界和下界；x′j(k)為經(jīng)混沌映射后的第j個混沌變量Cxj(k)轉(zhuǎn)化為優(yōu)化變量而獲得的值。

2.3 CDSFOA算法步驟

1)初始化群體規(guī)模、最大迭代次數(shù)、隨機(jī)種群位置、混沌遍歷次數(shù)和味道濃度方差閾值分別設(shè)置為Sizepop,Maxgen,X0,Y0,M和H。

2)執(zhí)行基本果蠅優(yōu)化算法步驟(3)～步驟(6)。

3)根據(jù)式(1)～式(3)對更新搜尋步長和位置分別進(jìn)行更新后再進(jìn)行迭代運(yùn)算，重復(fù)步驟(2)。

4)計算Smellavrage和味道濃度方差d2

5)若滿足條件d20，則將式(3)中的(Xi,Yi)通過式(6)混沌映射成混沌位置變量(X′i,Y′i)，再根據(jù)式(5)對(X′i,Y′i)進(jìn)行變換處理，最后將(X′i,Y′i)根據(jù)式(7)返回到搜索空間內(nèi)的果蠅種群新位置，M=M-1；若條件不滿足，則執(zhí)行步驟(10)。

6)計算新位置(X′i,Y′i)與原點(diǎn)之間Dist′i和S′i

7)根據(jù)S′i求解果蠅個體Smell′i

Smell′i=Function(S′i)

(10)

8)判斷Smell′i和Smellbest二者大小，前者大于后者，則轉(zhuǎn)到步驟(9)，否則Smellbest=Smell′i，(X0,Y0)=(X′i,Y′i)，然后轉(zhuǎn)到步驟(5)。

9) 判斷Smellbest是否為定值，若是則按式(11)引入混沌擾動，然后轉(zhuǎn)步驟(4)，否則執(zhí)行步驟(10)

Xaxist=Xi(bestIndex)+tCx′i,

Yaxist=Yi(bestIndex)+tCy′i

(11)

式中Cx′i和Cy′i為當(dāng)前最優(yōu)解位置的混沌擾動變量，t<1為擾動調(diào)節(jié)參數(shù)。

10)進(jìn)入迭代尋優(yōu)，重復(fù)執(zhí)行步驟(3)～步驟(9)，并記錄每代Smellbest和(X′i,Y′i)，判斷Smellbest是否為最優(yōu)解，如果是則停止，否則，重復(fù)上述步驟直到當(dāng)前迭代次數(shù)等于最大迭代次數(shù)，搜索結(jié)束。

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

3.1 實(shí)驗(yàn)設(shè)計

選取f1～f8分別為Sphere,Griewank,Rosenbrick,Rastrigin,Apline,Schwefel,Ackley,Schaffer進(jìn)行測試函數(shù)，各函數(shù)形式、搜索范圍、理論最優(yōu)值和峰值見文獻(xiàn)[9]。其中，f1和f3是單峰函數(shù)，f2和f4～f8為多峰函數(shù)。這些函數(shù)都具有很好的測試性能，通常用來測試難度較大的復(fù)雜優(yōu)化問題，能夠有效地檢驗(yàn)CDSFOA算法的優(yōu)化性能及收斂性。

通過與粒子群算法(PSO)、蝙蝠算法(BA)、協(xié)方差矩陣自適應(yīng)進(jìn)化策略算法(CMA-ES)、FOA算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較，用以驗(yàn)證CDSFOA算法優(yōu)化性能。上述4種算法的種群規(guī)模設(shè)置為30，維數(shù)設(shè)置為30。各算法參數(shù)設(shè)置為：1)PSO算法：c1=c2=1.5，w=0.75，vmax=0.66(最大速度)；2)BA算法：A=0.25，alf=0.85，BAma=0.02，r=0.50；3)CMA-ES算法：其參數(shù)設(shè)置參見文獻(xiàn)[10]；4)FOA算法：隨機(jī)初始化果蠅群體位置參見文獻(xiàn)[9]中各測試函數(shù)的自變量搜索范圍；5)CDSFOA算法：步長調(diào)節(jié)參數(shù)a=5，混沌遍歷次數(shù)M=5，適應(yīng)度方差閾值H=0.000 1，若經(jīng)過3次迭代后最優(yōu)解仍相同，則引入混沌擾動，擾動調(diào)節(jié)參數(shù)t=0.2，隨機(jī)初始化果蠅群體位置參見文獻(xiàn)[9]中各測試函數(shù)的自變量搜索范圍。

3.2 結(jié)果與分析

3.2.1 固定進(jìn)化迭代次數(shù)的性能驗(yàn)證

將6個測試函數(shù)f1～f6固定進(jìn)化次數(shù)為1 000次，分別采用PSO，BA，CMA-ES，F(xiàn)OA和CDSFOA算法經(jīng)過20次獨(dú)立運(yùn)行，并分別將運(yùn)行得到的最優(yōu)Smellbest值進(jìn)行最優(yōu)值(best)、優(yōu)化均值(mean)、計算以及平均運(yùn)行時間來表征，維數(shù)均設(shè)置為30，得到的實(shí)驗(yàn)結(jié)果如表,1所示。

表1 各算法性能比較

由此可見，與PSO，BA，CMA-ES，F(xiàn)OA算法相比，本文提出的CDSFOA算法都能找到或更接近理論的最優(yōu)值，其求解得到的最優(yōu)值、最差值、優(yōu)化均值和標(biāo)準(zhǔn)方差均優(yōu)于POS、BA、FOA算法；該算法搜索時間比PSO、BA和CMA-ES三種算法都要短，雖然CDSFOA算法相比FOA算法的搜尋最優(yōu)值時間都要長，這主要是因?yàn)镃DSFOA算法對果蠅群體進(jìn)行了自適應(yīng)動態(tài)步長的調(diào)節(jié)操作和引入了混沌擾動操作，但可以發(fā)現(xiàn)，本算法在時間上只是略長于FOA算法(0.01～1.0 s)，但本算法所獲得的尋優(yōu)精度確是FOA算法精度的幾個數(shù)量級，這說明本算法相比其它優(yōu)化算法具有更高的精度以及更好的魯棒性和穩(wěn)定性。同時也進(jìn)一步說明CDSFOA算法的復(fù)雜度較低及其可行性和有效性。

3.2.2 算法在多維和單、多峰函數(shù)上的性能驗(yàn)證

為了比較和突出CDSFOA算法在不同維、單峰和多峰函數(shù)上的優(yōu)越性能，將4種算法與CDSFOA算法在不同測試函數(shù)上，對維數(shù)D依次遞增的情況下各算法的優(yōu)化均值(Mean)進(jìn)行試驗(yàn)比較。在不同測試函數(shù)條件下，對各算法獨(dú)立運(yùn)行20次，算法參數(shù)設(shè)置同前所述。各測試函數(shù)的維數(shù)從最低維(D=20)依次遞增至最高維(D=150)，各算法之間的優(yōu)化均值(Mean)進(jìn)行比較， 結(jié)果如表2所示。

表2 在多峰函數(shù)和高維上的優(yōu)化均值比較

可知，隨著測試函數(shù)的高維數(shù)D的增加，CDSFOA算法的優(yōu)化均值基本在同一數(shù)量級內(nèi)變化，且比較接近理論最優(yōu)值，但PSO，BA，CMA-ES，F(xiàn)OA算法則隨著維數(shù)D的增加，其優(yōu)化均值逐漸遠(yuǎn)離理論最優(yōu)均值，當(dāng)維數(shù)D增加至大于100以后，其優(yōu)化均值則以一個甚至幾個數(shù)量級的速度遠(yuǎn)離最優(yōu)值，BA算法甚至在高維情況下還出現(xiàn)了“維數(shù)災(zāi)難”。這表明隨著維數(shù)的增加，特別是維數(shù)高于100時，CDSFOA算法對高維的復(fù)雜函數(shù)仍保持平穩(wěn)且較高精度的尋優(yōu)性能。

4 結(jié) 論

根據(jù)FOA的特點(diǎn)，引入動態(tài)步長調(diào)節(jié)因子與混沌優(yōu)化理論相結(jié)合，提出了一種具有分工明確、優(yōu)勢互補(bǔ)的果蠅優(yōu)化改進(jìn)算法。一方面利用混沌特性提高了算法的種群多樣性，通過引入混沌擾動量將果蠅個體跳出局部最優(yōu)，使得算法具有持續(xù)的全局搜索能力；另一方面，通過引入動態(tài)步長調(diào)節(jié)因子對果蠅個體的搜索步長進(jìn)行隨機(jī)動態(tài)調(diào)節(jié)，使得算法具有更快的收斂速度。仿真實(shí)驗(yàn)驗(yàn)證結(jié)果表明：相較PSO、BA、CMA-ES、FOA算法，CDSFOA具有較高的收斂速度和尋優(yōu)精度，尤其針對高維、多峰函數(shù)，該算法比其他算法的優(yōu)越性能更佳。