混沌動態步長果蠅優化算法*

廖建慶， 王 涵， 王咸鵬

(1.宜春學院 物理科學與工程技術學院，江西 宜春 336000； 2.海南大學 南海海洋資源利用國家重點實驗室，海南 海口 570228)

0 引 言

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

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

1 標準果蠅優化算法[6]

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

2) 給果蠅方向和距離分配隨機參數，產生新位置;

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

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

5)對Smelli值進行排序，找出當前Smelli最大的果蠅個體;

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

7) 最后迭代運算，重復步驟(2)～步驟(5)，在尋優過程中判斷當前最佳味道濃度是否優于上一迭代結果，且判斷當前迭代次數是否小于最大迭代數；若是則執行步驟(6)，否則結束。

2 混沌動態步長果蠅優化算法

2.1 動態步長調整策略

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

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

(1)

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

(2)

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

式中 (X0，Y0)為隨機初始化果繩群體位置。則動態步長調節因子w(n)隨迭代次數的動態變化。

2.2 混沌優化

混沌優化算法[9]是一種利用混沌運動特性進行優化搜索方法，本文引入Logistic映射，其數學模型為

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

(4)

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

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

(5)

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

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

(6)

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

2.3 CDSFOA算法步驟

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

2)執行基本果蠅優化算法步驟(3)～步驟(6)。

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

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

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

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

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

Smell′i=Function(S′i)

(10)

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

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

Xaxist=Xi(bestIndex)+tCx′i,

Yaxist=Yi(bestIndex)+tCy′i

(11)

式中Cx′i和Cy′i為當前最優解位置的混沌擾動變量，t<1為擾動調節參數。

10)進入迭代尋優，重復執行步驟(3)～步驟(9)，并記錄每代Smellbest和(X′i,Y′i)，判斷Smellbest是否為最優解，如果是則停止，否則，重復上述步驟直到當前迭代次數等于最大迭代次數，搜索結束。

3 仿真實驗與結果分析

3.1 實驗設計

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

通過與粒子群算法(PSO)、蝙蝠算法(BA)、協方差矩陣自適應進化策略算法(CMA-ES)、FOA算法的實驗結果進行比較，用以驗證CDSFOA算法優化性能。上述4種算法的種群規模設置為30，維數設置為30。各算法參數設置為：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算法：其參數設置參見文獻[10]；4)FOA算法：隨機初始化果蠅群體位置參見文獻[9]中各測試函數的自變量搜索范圍；5)CDSFOA算法：步長調節參數a=5，混沌遍歷次數M=5，適應度方差閾值H=0.000 1，若經過3次迭代后最優解仍相同，則引入混沌擾動，擾動調節參數t=0.2，隨機初始化果蠅群體位置參見文獻[9]中各測試函數的自變量搜索范圍。

3.2 結果與分析

3.2.1 固定進化迭代次數的性能驗證

將6個測試函數f1～f6固定進化次數為1 000次，分別采用PSO，BA，CMA-ES，FOA和CDSFOA算法經過20次獨立運行，并分別將運行得到的最優Smellbest值進行最優值(best)、優化均值(mean)、計算以及平均運行時間來表征，維數均設置為30，得到的實驗結果如表,1所示。

表1 各算法性能比較

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

3.2.2 算法在多維和單、多峰函數上的性能驗證

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

表2 在多峰函數和高維上的優化均值比較

可知，隨著測試函數的高維數D的增加，CDSFOA算法的優化均值基本在同一數量級內變化，且比較接近理論最優值，但PSO，BA，CMA-ES，FOA算法則隨著維數D的增加，其優化均值逐漸遠離理論最優均值，當維數D增加至大于100以后，其優化均值則以一個甚至幾個數量級的速度遠離最優值，BA算法甚至在高維情況下還出現了“維數災難”。這表明隨著維數的增加，特別是維數高于100時，CDSFOA算法對高維的復雜函數仍保持平穩且較高精度的尋優性能。

4 結 論

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