一種新型的混沌步長果蠅優(yōu)化算法*

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

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

1 引言

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

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

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

2 標準果蠅優(yōu)化算法

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

Figure 1 Optimizing steps of FOA圖1 果蠅優(yōu)化算法優(yōu)化步驟

3 Hénon映射

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

(1)

Hénon映射是否發(fā)生混沌狀態(tài)由參數(shù)a、b的取值決定。研究表明，當a∈(0,1.4)，且b∈(0.2,0.314)時，Hénon映射會產生混沌現(xiàn)象，生成的混沌序列具有隨機性。圖2所示為b=0.3時，x隨參數(shù)a(a∈(0,1.4))變化的分叉圖。圖3所示為b=0.25時，x隨參數(shù)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可知,隨著參數(shù)a的遞增，x的范圍逐漸變大且取值均勻，因此可將其混沌值作為果蠅算法的步長。經研究表明，圖3中，a∈(0,0.562)時x值均大于0，且隨著a遞增x發(fā)生分叉，并同時往2個方向變化。這種映射關系可提高果蠅算法的全局搜索能力；a∈(0.562,1.4)時，隨著a遞增x的范圍逐漸擴大，使x取值范圍具有良好的遍歷性和多樣性，其可擴大果蠅算法搜索范圍，提高其跳出局部最優(yōu)解能力。但是，由圖2和圖3可知x雖存在遍歷性和多樣性，但對于大范圍大數(shù)值搜索情況，其取值太小無法跳出局部最優(yōu)解。因此，引入放大系數(shù)，如式(2)所示，以加強其跳出局部最優(yōu)解的能力。

X=N*x

(2)

其中，N為混沌步長放大系數(shù)。

4 HSFOA算法

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

算法1 HSFOA

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

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

X_axis=rand×(UB-LB)+LB

Y_axis=rand×(UB-LB)+LB

(3)

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

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

Xi=X_axis+randValue

Yi=Y_axis+randValue

(4)

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

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

(5)

Si=1/Di

(6)

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

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

(7)

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

(8)

St=1/Dt

(9)

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

Smellt=fitness(St)

(10)

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

(11)

步驟10 進入迭代尋優(yōu)，重復執(zhí)行步驟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)與經典的智能優(yōu)化算法PSO(Partical Swarm Optimization)、遺傳算法GA(Genetic Algorithm)、蝙蝠算法BA(Bat Algorithm)進行仿真對比分析。

為了更方便直觀地對比分析，實驗采用10個經典的測試函數(shù)，并以誤差值與標準差作為參考標準。表1給出了10個測試函數(shù)的維度、搜索區(qū)間和最優(yōu)值，其中，F(xiàn)1～F3的維數(shù)為2維，F(xiàn)4～F10的維數(shù)為30維。

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

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

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

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

Table 1 Test functions表1 測試函數(shù)

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

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

6 結束語

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

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