一種新型的混沌步長果蠅優化算法*

張 鑄，饒盛華,2，張仕杰

(1.湖南科技大學信息與電氣工程學院，湖南 湘潭 411201；2.湖南科技大學海洋礦產資源探采裝備與安全技術國家地方聯合工程實驗室，湖南 湘潭 411201)

1 引言

Pan[1]于2011年提出了一種由果蠅覓食行為而演化出來的群體智能全局優化算法——果蠅優化算法FOA(fruit Fly Optimization Algorithm)。相比于其他動物，果蠅具有較好的感官特性，如敏銳的視覺與嗅覺。FOA算法具有易實現、易理解、原理簡單、調節參數少等特點，被廣泛應用到了生物技術、金融、醫學、模式識別、神經網絡等領域。因此，對FOA研究具有較好的學術價值[2]。

作為群體智能算法，FOA易陷入早熟收斂且缺少跳出局部最優解的機制，在解高維度復雜的優化問題時尤為突出。為了解決上述問題，Pan[3]提出了一種改進型果蠅優化算法MFOA(Modifided FOA)，通過加入跳出局部最優解參數增強全局收斂能力；韓俊英等[4]提出了一種動態雙子群協同進化果蠅優化算法，通過混沌優化在局部最優解附近進行搜索，提高其跳出局部最優解的能力；Yuan[5]等提出了一種多種群果蠅優化算法MSFOA(Multi-Swarm FOA)，通過多種群與縮小搜索半徑的方法提高全局收斂能力；Pan等[6]提出了一種通過新的控制參數以及候選解機制提高性能的IFFO(Improved Fruit Fly Optimization)算法；文獻[5,7]中提出通過采用自適應步長提高算法全局和局部搜索能力；Wang等[8]提出帶有擾動機制的果蠅優化算法，使部分果蠅隨機飛行，以增加果蠅群體的多樣性；文獻[9]中引入Levy飛行策略，提高FOA跳出局部最優解的能力，并將果蠅群體分為優質群體和劣質群體進行不同的搜索，提高種群多樣性；張斌等[10]提出一種與模擬退火算法相結合的果蠅優化算法，通過概率吸收最差解作為下一次迭代位置來達到跳出局部最優解的目的；文獻[11]提出一種雙種群的果蠅優化算法，將果蠅群體分為搜索果蠅和跟隨果蠅，并定義群度概念以平衡算法的全局和局部搜索能力。

本文提出一種基于Hénon混沌步長的果蠅優化算法HSFOA(fruit Fly Optimization Algorithm with Hénon chaotic of Step)，通過混沌映射的遍歷性和多樣性特征來改進FOA的固定步長，擴大其搜索范圍；并對混沌步長增加放大系數，以適應不同的搜索環境，提高其搜索效率以及跳出局部最優解的能力。本文詳細介紹了Hénon混沌映射的特點，以及HSFOA的原理和偽代碼，并用10個測試函數進行了測試，與多種算法進行了對比分析，研究結果表明：HSFOA算法具有較高的全局搜索和跳出局部最優解的能力。

2 標準果蠅優化算法

果蠅優化算法是一種模擬果蠅覓食行為而推演出來的全局優化算法。果蠅通過嗅覺去尋找食物，而在接近食物后再通過靈敏的視覺發現食物[7]。果蠅優化算法原理簡單、調節參數少、適應性強、收斂速度快，但也存在尋優結果不穩定等不足[5]。果蠅優化算法的優化步驟如圖1所示。

Figure 1 Optimizing steps of FOA圖1 果蠅優化算法優化步驟

3 Hénon映射

Hénon映射是一種二維的非線性動力系統，具有不可預測性以及不確定性等特征[12]。Hénon映射對初值敏感，初值不同會導致結果具有極大的差異性，因此其經常應用于信息安全領域[13,14]。Hénon映射是二維空間產生的混沌現象，如式(1)所示：

(1)

Hénon映射是否發生混沌狀態由參數a、b的取值決定。研究表明，當a∈(0,1.4)，且b∈(0.2,0.314)時，Hénon映射會產生混沌現象，生成的混沌序列具有隨機性。圖2所示為b=0.3時，x隨參數a(a∈(0,1.4))變化的分叉圖。圖3所示為b=0.25時，x隨參數a(a∈(0.4,1.4))變化的分叉圖。

Figure 2 Chaotic graph of Hénon mapping (b=0.3)圖2 Hénon映射混沌圖(b=0.3)

Figure 3 Chaotic graph of Hénon mapping(b=0.25)圖3 Hénon映射混沌圖(b=0.25)

由圖2可知,隨著參數a的遞增，x的范圍逐漸變大且取值均勻，因此可將其混沌值作為果蠅算法的步長。經研究表明，圖3中，a∈(0,0.562)時x值均大于0，且隨著a遞增x發生分叉，并同時往2個方向變化。這種映射關系可提高果蠅算法的全局搜索能力；a∈(0.562,1.4)時，隨著a遞增x的范圍逐漸擴大，使x取值范圍具有良好的遍歷性和多樣性，其可擴大果蠅算法搜索范圍，提高其跳出局部最優解能力。但是，由圖2和圖3可知x雖存在遍歷性和多樣性，但對于大范圍大數值搜索情況，其取值太小無法跳出局部最優解。因此，引入放大系數，如式(2)所示，以加強其跳出局部最優解的能力。

X=N*x

(2)

其中，N為混沌步長放大系數。

4 HSFOA算法

在FOA中，步長的選擇直接影響到算法的收斂速度和精度，因此本文將Hénon映射的混沌值作為步長，Hénon映射所發生的混沌現象具有較好的遍歷性、多樣性，可以解決果蠅優化算法的易早熟和收斂不足的問題，從而提高算法的效率和跳出局部最優解的能力。HSFOA的步驟和偽代碼如下所示。

算法1 HSFOA

步驟1 初始化參數：sizepop(種群規模)，maxgen(最大迭代次數)，a(Hénon混沌參數)，b(Hénon混沌參數)，N(混沌步長放大系數)。

步驟2 果蠅群體位置(X_axis，Y_axis)通過式(3)進行初始化；

X_axis=rand×(UB-LB)+LB

Y_axis=rand×(UB-LB)+LB

(3)

其中,rand為[0,1]的隨機數，UB和LB分別為搜索范圍的上下界。

步驟3 嗅覺搜索階段。根據式(4)更新所有果蠅個體位置：

Xi=X_axis+randValue

Yi=Y_axis+randValue

(4)

其中，randValue是一個返回值為[-1,1]的隨機函數。

步驟4 計算果蠅個體位置與原點距離Di,再求出味道濃度判斷值Si:

(5)

Si=1/Di

(6)

步驟5 根據式(1)對此時的最優解進行混沌化，產生混沌步長L。

步驟6 根據式(2)對混沌步長進行迭代放大，得到此時果蠅個體的位置(Xt，Yt)：

(7)

步驟7 計算果蠅個體位置與原點的距離Dt，并求出味道濃度判斷值:

(8)

St=1/Dt

(9)

步驟8 求出此時味道濃度值:

Smellt=fitness(St)

(10)

步驟9 若此時味道濃度優于最優味道濃度值，則取代最優味道濃度值，并記錄此時的果蠅位置:

(11)

步驟10 進入迭代尋優，重復執行步驟2～步驟9。

HSFOA偽代碼:

1:initializationsizepop,maxgen,randValue,a,b;

2:Xi=X_axis+randValue;

3:Yi=Y_axis+randValue;

5:Si=1/Di;

6:Smelli=fitness(Si);

7: [bestSmell,bestIndex]=min(Smelli);

8:Smellbest=bestSmell;

9:X_axis=X(bestIndex),x=X_axis;

10:Y_axis=Y(bestIndex),y=Y_axis;

11: whilet

12:Xi=X_axis+randValue;

13:Yi=Y_axis+randValue;

15.Si=1/Di;

16.smelli=fitness(Si);

17: fori=1:N

19: end for

20: forj=1:sizepop

21:L=j×x;

本次施工在閘室上下游齒及兩側岸墻底板下采用高壓灌漿擺噴墻，組成封閉基礎以提高閘基的防滲能力。同時通過采用圍井注水試驗進行檢查，在場地交通允許下，可進行開挖檢查，每處高噴灌漿工程可作一個圍井試驗和一處開挖檢查，可有效提高該工程的防滲能力。

22:Xt=X_axis+L;

23:Yt=Y_axis+L;

25:St=1/Dt;

26:Smelli=fitness(Si);

27: [bestSmell,bestIndex]=min(Smelli);

28: ifbestSmell

29:Smellbest=bestSmell;

31:Y_axis=Y(bestIndex),x=X_axis;

32: end if

33: end for

34:t=t+1;

35: end while

5 仿真實驗與結果分析

為了驗證HSFOA有效性和可行性，本文設計了2組仿真對比實驗。(1)與同種類型的改進型果蠅算法MFOA、IFFO和標準FOA進行仿真對比分析；(2)與經典的智能優化算法PSO(Partical Swarm Optimization)、遺傳算法GA(Genetic Algorithm)、蝙蝠算法BA(Bat Algorithm)進行仿真對比分析。

為了更方便直觀地對比分析，實驗采用10個經典的測試函數，并以誤差值與標準差作為參考標準。表1給出了10個測試函數的維度、搜索區間和最優值，其中，F1～F3的維數為2維，F4～F10的維數為30維。

本文實驗種群規模為30，最大迭代次數為200；MFOA的隨機值randValue=1；IFFO的最大半徑λ_max=(UB-LB)/2，最小半徑λ_min=1×10-5;HSFOA的Hénon混沌參數a∈(0,1.4)，b=0.25，運行F1、F2，F4～F7時混沌步長放大系數N=10，運行F3、F8時混沌步長放大系數N=3；PSO的加速常數c1=c2=1.5，慣性因子w=0.75，最大速度Vmax=1，最小速度Vmin=-1；GA的交叉率pc=0.6，變異率pm=0.001；BA的響度A=0.25，響度衰減系數alf=0.85，脈沖發射頻率增加系數BAma=0.02，脈沖發射率r=0.5。

將表1所示的10個測試函數F1～F10分別采用HSFOA、IFFO、MFOA、FOA算法單獨進行20次獨立尋優，尋優結果如表2所示。

由表2可見，與IFFO、MFOA、FOA相比較，本文提出的HSFOA尋優到的最優值更接近理論值，其尋優得到的誤差與標準差均優于IFFO、MFOA、FOA的；對比IFFO、MFOA、FOA的穩定性，F4、F5、F7、F8的標準差均達到10-11以上，高出其他算法最少2個數量級，而對于F1、F2、F3、F6、F9，標準差雖只高出1個數量級，但其仍然優于其他算法，因此HSFOA具有更高的穩定性；同時HSFOA的誤差均優于其他算法，說明其具有更好的尋優能力，尤其在F7、F8時，HSFOA的誤差達到了10-10以下。綜上可得，相比于同種類型的果蠅優化算法，HSFOA具有較好的穩定性和全局搜索能力。

下面將HSFOA與智能優化算法PSO、GA、BA進行仿真實驗與對比分析，以驗證HSFOA的有效性。將F1～F10在HSFOA、PSO、GA、BA中獨立運行20次，結果如表3所示。

Table 1 Test functions表1 測試函數

Table 2 Experimental results comparison of HSFOA and other FOAs表2 HSFOA與其他FOA實驗結果比較

由表3可見，HSFOA的結果更接近函數的最優值，其誤差和標準差均優于PSO、GA、BA最少2個數量級，可見HSFOA有較好的穩定性和局部搜索能力。對于F2、F3，HSFOA優于PSO、GA、BA最少2個數量級，而對于F1、F6，HSFOA優于PSO、GA、BA最少4個數量級，其中運行F4、F5、F7、F8時優于其他算法9個數量級，而運行F9、F10時雖只略優于其他算法，但其仍取得了較好的結果。綜上可得，相比于智能優化算法，HSFOA具有較好的全局搜索和跳出局部最優的能力。

6 結束語

針對果蠅優化算法存在算法易早熟、收斂不足的問題，將Hénon混沌映射引用為步長因子，提出了一種混沌步長果蠅優化算法。Hénon混沌映射a∈(0,0.562)時，可提高算法全局搜索能力，a∈(0.562,1.4)時，可提高算法跳出局部最優解的能力。采用10個經典測試函數進行測試，將HSFOA與同類型的果蠅優化算法MFOA、IFFO和標準FOA進行了對比分析，并與智能優化算法PSO、GA、BA進行了對比分析，結果表明：相比于MFOA、IFFO、FOA、PSO、GA、BA，HSFOA具有較高的全局搜索和跳出局部最優解的能力。

Table 3 Experimental results comparison of HSFOA and other intelligent algorithms表3 HSFOA與其他智能優化算法實驗結果比較