基于隨機替換和混合變異的蜻蜓算法

張水平，高 棟

(江西理工大學信息工程學院,贛州 341000)

美國學者Mirjalili[1]受到自然界中蜻蜓覓食和遷徙行為的啟發,提出了一種新型的群智能算法:蜻蜓算法(dragonfly algorithm, DA)。該算法原理簡單,易于理解且便于實現,具有較強的搜索能力,受到國內外學者的廣泛研究和討論,現已被成功用于圖像多級分割[2]、變壓器故障診斷[3]、特征選擇[4]等諸多領域。

然而,和其他群智能算法類似,基本蜻蜓算法同樣存在求解精度低、收斂速度慢、易陷于局部最優等問題,因此,在近3年的研究中,關于蜻蜓算法的改進逐步涌現:Sree等[5]提出了具有記憶算子的混合蜻蜓算法,一定程度上提高了算法的搜索能力；吳偉民等[6]通過引入貪婪、平衡和組合三種策略,增強個體間的信息交流,從而提升了算法的求解精度；馬駿等[7]通過改進算法步長的更新公式,并對最優解逐維進行更新,提高了算法的收斂速度；趙齊輝等[8]通過引入差分進化策略,增加了種群的多樣性,有效提升了算法整體的性能。

以上算法均在一定程度上提高了基本蜻蜓算法的尋優性能,但相比其他群智能算法的研究,基本蜻蜓算法仍有改進優化的空間,因此本文研究提出了基于隨機替換和混合變異的蜻蜓算法(dragonfly algorithm based on random substitution and hybrid mutation, DASM),該算法通過提高初始解的質量、對中心點進行隨機替換、進行混合變異以跳出局部最優三種策略對基本蜻蜓算法進行改進,通過對八個測試函數進行仿真實驗對比,結果表明,本文提出的改進算法具有較好的尋優速度和精度。

1 基本蜻蜓算法

蜻蜓算法的主要思想是通過模擬蜻蜓群體避撞、結隊、聚集、覓食及避敵五種飛行行為,以進行全局和局部搜索,蜻蜓尋找食物的過程即算法的尋優過程。

1.1 算法數學描述

(1)避撞行為,盡量避免和環繞的蜻蜓個體產生碰撞,數學表達式如下:

(1)

式(1)中：X是當前蜻蜓個體的位置信息；N代表和當前個體相鄰的蜻蜓個體的數量；Xj是第j個相鄰個體的位置信息。

(2)結隊行為,若干個體之間以同等速度結隊飛行,數學表達式如下:

(2)

式(2)中：Vj是第j個相鄰個體的飛行速度。

(3)聚集行為,若干個體向某個體飛行聚集,數學表達式如下:

(3)

(4)覓食行為,個體向著食物所在位置靠攏,數學表達式如下:

Fi=X+-X

(4)

式(4)中：X+為食物源所在位置信息,即已記錄的目標最優解。

(5)避敵行為,個體遠離天敵所在位置,數學表達式如下:

Ei=X-+X

(5)

式(5)中：X-為天敵所在位置信息,即已記錄的最差解。

蜻蜓的群體行為是上述五種行為的結合,同時為了更加準確的模擬蜻蜓的移動過程,算法又引入了步長向量ΔX和位置向量X,對蜻蜓個體飛行時所在位置進行仿真和更新,步長向量更新公式如下:

ΔXt+1=(sSi+aAi+cCi+fFi+eEi)+ωΔXt

(6)

式(6)中：s為避撞權重；a為結隊權重；c為聚集權重；f為食物因子；e為天敵因子；ω為慣性權重；t為迭代次數。

為了提高算法的性能,蜻蜓算法設置了兩種位置更新模式,當該個體周圍有鄰近個體時,以式(7)更新位置信息,否則以式(8)Levy飛行方式更新位置信息。

Xt+1=Xt+ΔXt+1

(7)

Xt+1=Xt+Levy(d)Xt

(8)

式中：d為向量維度；Levy函數具體信息如下:

(9)

(10)

式中：Γ(x)=(x-1)??；r1、r2為區間[0,1]內的隨機數；β為常數。

1.2 算法尋優步驟

蜻蜓算法假設天敵和食物源位置分別為當前發現的最差解和最優解,種群內的個體可以通過兩種方式更新自身的位置信息,經過多次迭代后得到全局最優解,其尋優步驟如下：

步驟1初始化設置算法的基本參數,主要包括算法運行最大迭代次數Tmax、種群內個體數N、群體的可搜索空間、問題維度及各類權重系數等。

步驟2在搜索空間內隨機初始化種群內每個個體的位置信息,并計算其對應的適應度值,從而得到當前全局最優解和最優位置。

步驟3更新食物源位置(當前最優解)和天敵位置(當前最差解),并更新蜻蜓五種行為對應的權重s、a、c、f、e和慣性權重w。

步驟4通過式(1)～式(5)更新蜻蜓群體的五種行為因子S、A、C、F、E。

步驟5判斷該個體周圍是否有鄰近個體,若有鄰近個體則通過式(7)更新位置信息并進行越界處理,否則通過式(8)更新位置信息并進行越界處理。

步驟6根據更新的位置信息,重新計算個體的適應度值,并找出最優的適應度值,判斷其是否優于當前記錄中的全局最優值,若是,則更新全局最優值。

步驟7判斷算法是否滿足迭代終止條件,若滿足,則輸出全局最優解和全局最優值,否則跳轉至步驟3進行下一次迭代尋優。

2 基于隨機替換和混合變異的DA

針對基本蜻蜓算法存在的求解精度低、收斂速度慢、陷于局部最優后難以跳出等缺陷,DASM算法分別從三個方面進行改進:①通過“等價替換”和“混沌映射”處理初始位置,使其更加均勻隨機,從而提高初始解的質量；②從算法的迭代軌跡出發,在算法中引入中心點隨機替換策略,從而加快算法收斂速度；③引入混合變異策略提高種群多樣性以跳出局部最優,從而提高算法的求解精度。通過三種改進措施相結合,從整體上提高蜻蜓算法尋優性能。

2.1 通過混沌映射提升初始解的質量

種群的初始位置在算法的迭代尋優過程中有重要的作用,較好的初始解可以加快算法的收斂速度并有助于找到全局最優值,而初始解的質量受到初始位置的數量和分布情況的影響。

為了提高種群中初始位置的數量,采用以迭代次數換取初始位置數量的策略,在基本蜻蜓算法中,迭代t次將遍歷t×N個位置,因此可在不影響算法時間復雜度和空間復雜度的情況下,用t次的迭代次數換取t×N個位置點,從而提升初始解的質量。

在基本蜻蜓算法中,種群內的初始位置隨機產生,從而導致蜻蜓個體不能全面的對空間進行搜索?；煦缬成淇梢岳没煦绲谋闅v性和規律性細化算法中變量的搜索空間,從而得到較優的初始群體,以提高種群中個體的多樣性。傳統的Tent混沌映射數學表達式如式(11)所示,具有較好的遍歷均勻性,但其迭代序列中存在小周期和不穩定的周期點,因此本文采用文獻[9]提出的改進的Tent混沌映射來產生混沌序列以初始化種群,當xk={0,0.25,0.5,0.75}或者xk=xk-m(m為區間[1,5]內的整數)時,以式(12)更新序列,否則以式(11)更新序列,由于隨機函數的作用,可以擾動跳出不動點或小周期點,從而可以使得Tent映射可以從周期循環狀態重新進入混沌狀態。

(11)

xk+1=T′(xk)=T(xk)+0.1rand(0,1)

(12)

2.2 通過中心點隨機替換提高收斂速度

通過實驗研究算法中蜻蜓的搜索過程,發現其種群的進化方向是有一定規律可循的,在種群的中心點和最優點的連線上,其中必有一部分點更靠近下次迭代的最優解,假設搜索空間為兩維時,其尋優路徑如圖1所示,因此可根據這種性質,將其推廣至高維空間,提出中心點隨機替換策略,以對全局最優解擾動,其核心思想是在種群中心點和當前全局最優點的連線及其延長線上,隨機取一點替換當前解,以提高種群的多樣性,同時提高算法的收斂速度和全局探索能力如式(13)所示。

(13)

式(13)中：λ為區間[-2,3]之間的隨機數,當0≤λ≤1時,將生成兩點連線上的點,當λ>1或λ<0時,將取得兩點延長線上的點,Xbest為當前全局最優點。

圖1 蜻蜓尋優路徑及種群中心點位置Fig.1 The optimal path and population center of dragonflies

2.3 通過混合變異跳出局部最優點

以上兩種改進措施可以一定程度上提高初始解的質量并加快算法的收斂速度,但群體智能算法的特性決定了其仍然無法避免會于陷于局部最優且難以跳出,為了提高算法的求解精度,需要采取相關措施提高種群多樣性并擴大搜索范圍,以跳出局部最優點。李煜等[10]將高斯變異策略用于蝙蝠優化算法中,使得種群具有較高的多樣性和活躍性,便于算法跳出局部最優；賀智明等[11]將柯西變異策略引入花授粉算法中,以解決算法在迭代后期由于種群多樣性降低而引起的早熟收斂問題。

由文獻[12]可知,高斯變異有較強的局部搜索能力,可以維持算法的收斂速度,柯西變異有較強的全局探索能力,能及時引導個體跳出局部最優。因此,將高斯變異和柯西變異進行組成,通過式(14)對適應度值最差的個體進行變異,提高算法的搜索能力并降低局部極值點的約束能力,使得算法在陷入局部極值點時可以迅速跳出。

(14)

式(14)中：Xt是第t次迭代時蜻蜓個體的位置；rand()為[0,1]區間內的隨機數,T為最大迭代次數,G(0,1)為標準高斯分布,C(0,1)為柯西分布。

2.4 DASM算法實現步驟

結合基本蜻蜓算法原理和上述改進算法,提出的改進算法的具體尋優步驟如下。

步驟1初始化設置算法的基本參數。

步驟2利用等價替換和混沌映射策略處理并得到種群內的初始解,并計算其對應的適應度值,從而得到當前全局最優解和最優位置。

步驟3更新食物源位置(當前最優解)、天敵位置(當前最差解)和個體屬性信息,并更新蜻蜓五種行為對應的權重s、a、c、f、e和慣性權重w。

步驟4判斷個體屬性,若為最優個體,則通過式(13)更新位置信息,進行越界處理后跳轉至步驟7；若為最差個體,則通過式(14)對其進行混合變異,進行越界處理后跳轉至步驟7；否則跳轉至步驟5更新位置信息。

步驟5通過式(1)～式(5)更新蜻蜓群體的五種行為因子S、A、C、F、E。

步驟6判斷該個體周圍是否有鄰近個體,若有鄰近個體則通過式(7)更新位置信息并進行越界處理,否則通過式(8)更新位置信息并進行越界處理。

步驟7根據更新的位置信息,重新計算個體的適應度值,并找出最優的適應度值,判斷其是否優于當前記錄中的全局最優值,若是,則更新全局最優值。

步驟8判斷算法是否滿足迭代終止條件,若滿足,則輸出全局最優解和全局最優值,否則跳轉至步驟3進行下一次迭代尋優。

2.5 算法復雜度分析

時間復雜度是指算法執行所需要的計算工作量,主要取決于問題重復執行的次數,在基本蜻蜓算法中,時間復雜度主要受到種群規模N、迭代次數T和搜索維度D的影響,由DA算法尋優步驟可知,其時間復雜度為O(NTD)。相比DA算法,DASM算法在迭代過程中,需要判斷個體屬性以確定其用何種方式更新位置信息,增加了O(NT)的運算量,但總體上時間復雜度未發生改變。

空間復雜度主要受到種群規模和搜索維度的影響,因此兩種算法的空間復雜度均為O(ND)。

3 實驗仿真與結果分析

為了檢驗所提出的DASM算法的有效性,以求最小值為例,用8個經典性能測試函數進行MATLAB實驗仿真對比。一是通過固定迭代次數和種群規模,比較本文改進算法與基本蜻蜓算法、基本果蠅優化算法[13]、基本花授粉算法[14]和部分參考文獻改進算法在不同函數上的尋優速度和尋優精度；二是通過固定收斂精度,比較DA、DASM算法和部分參考文獻所改進算法的尋優成功率和平均迭代次數[15]。

表1給出了測試函數的基本信息和相關參數設置,當函數自變量的搜索空間越廣、維度越大,目標的收斂精度要求越高時,可以順利找到最優解的難度也就越大,對算法的性能要求也就越高。

表1 測試函數參數設置

3.1 固定種群規和模迭代次數下的性能測試

為了降低算法的隨機性對實驗結果的影響,以30次獨立運行的平均值作為評估算法性能的最終結果,其中設置種群規模為30、最大迭代次數為500。表2給出了基本果蠅優化算法(FOA)、基本花授粉算法(FPA)、基本蜻蜓算法(DA)和本文改進算法(DASM)在8種測試函數(均為30維)上的最優值(best)、平均值(avg)、最差值(worst)和標準差(sd),結果保留三位小數,其中最優值和最差值反映了解的質量,平均值反映了算法所能達到的精度,標準差反映了算法的魯棒性和穩定性。為了更好地對比四種算法的尋優性能,圖2給出了它們在不同函數(30維)上迭代尋優的對比曲線,其中橫坐標為迭代次數,同時為了便于觀察,將適應度值取以10為底的對數,此時縱坐標可看作尋優精度。

結合表2中的實驗數據和圖2中的迭代對比曲線,分析如下：

表2 算法性能比較

圖2 函數進化曲線(D=30)Fig.2 Functional evolution curve(D=30)

(1) 隨著迭代次數的增加,在八個函數的尋優過程中,基本花授粉算法、基本果蠅優化算法和基本蜻蜓算法均會較早的陷入局部最優并且難以跳出,均無法搜索到理論最優值且尋優精度有限。從整體上看,在三種基本算法中,果蠅優化算法的尋優性能最佳,蜻蜓算法尋優性能次之,花授粉算法的尋優性能最差。

(2) 相比基本蜻蜓算法,本文提出的DASM算法在每次迭代尋優的過程中均可成功的找到Griewank和Rastrigin函數的理論最優值,同時在對Sphere、Schwefel 2.22、Schwefel 1.2和Schwefel 2.21函數進行尋優時,DASM算法有一定概率找到其理論最優值,即使無法準確找到,亦能提高20～40個數量級的收斂精度。

(3) 從整體上看,相比其他七個函數,DASM算法對Rosenbrock函數的尋優效果最差,只提升了4個數量級的收斂精度,其尋優效果和基本果蠅優化算法相似。從函數本身特性分析,發現Rosenbrock函數在其取值區間內走勢平坦,最優值位于類似山谷的甬道中,算法在陷入局部最優后均難以跳出,因此雖然DASM算法在迭代初期尋優速度較快,但是在迭代后期陷入局部最優后也難以跳出,導致所提升的收斂精度有限。

(4) 通過表2中提供的標準差數據可知,三種基本算法對8個測試函數進行獨立運行迭代尋優時,得到的標準差均不為0,但DASM算法在對Griewank、Rastrigin、Ackley函數進行尋優時得到的標準差可為0,對其他5個函數尋優得到的標準差亦遠遠小于基本蜻蜓算法,因此,相比較而言,本文改進的DASM算法具有更好的穩定性。

綜上所述,無論多峰還是單峰函數,本文提出的改進算法優于基本蜻蜓算法,具有更快的搜索速度和更高的收斂精度,為了更好地驗證DASM算法性能,表3給出了DASM算法和部分參考文獻[7-8]所改進算法在不同維度(10、30、50、100維)函數優化中的均值對比,“()”中數字是根據均值由小到大進行排名的順序,以便可以直觀地對比分析,同時為了更加直觀地反映DASM算法的尋優性能,圖3給出了四種算法在100維的函數尋優進化對比曲線。

由表3中的數據及圖3的進化對比曲線可知,相比DA、DGSDA、DEDA三種算法,無論10、30、50或100維,DASM算法在對Griewank和Rastrigin函數進行迭代尋優時均可找到其理論最優值,對Schwefel 1.2函數迭代尋優時均可提升50個數量級的收斂精度,在對Ackley和Sphere函數迭代尋優時均可提升10個數量級的收斂精度,充分說明了本文提出的改進算法在求解高維優化問題時有較強的魯棒性,同時具有更高的收斂精度和更好的搜索能力。

表3 不同算法均值比較

3.2 固定收斂精度下的性能測試

為了更好地驗證DASM算法的收斂性和穩定性,通過設定固定的收斂精度,對8個測試函數進行了性能測試,其40次獨立運行的成功率(K)和平均迭代次數(T)如表4所示。

圖3 函數進化曲線(D=100)Fig.3 Functional evolution curve(D=100)

通過數據分析可知,本文提出的DASM算法除了在對Rosenbrock函數迭代尋優時無法保證每次運行都能達到設置的收斂精度,對另外7個函數迭代尋優時均可在350次迭代以內達到目標精度并且尋優成功率均為100%,充分說明改進算法的穩定性相比較而言更好。因此,從整體上講,在固定收斂精度的情況下,DASM算法具有更高的尋優效率和更好的尋優可信性,尋優性能相對而言更好。

4 結論

通過對基本蜻蜓算法進行分析,針對其存在的缺陷并結合現有文獻對其做出的改進,提出了一種隨機替換和混合變異的蜻蜓算法。在種群初始化過程中通過等價替換和混沌映射處理,以提高初始解的質量；通過引入中心點隨機替換策略,提高算法尋優速度；通過混合變異提高種群多樣性以跳出局部最優,從而提高算法求解精度。

通過進行仿真實驗,得到如下結論。

(1)本文提出的改進算法相比基本蜻蜓算法、基本果蠅優化算法和基本花授粉算法具有更高的收斂精度、更快的求解速度和更好的穩定性。

(2)相比部分參考文獻中的改進算法,本文改進算法更易于跳出局部最優并得到全局最優,尋優可信性更強。

但是,由于本文改進的算法在對個別函數尋優上仍然存在缺陷,因此,提高算法在部分函數上的尋優性能、對算法的收斂性進行詳細的研究分析以解決生活中的實際問題,將是下一步研究的工作重點。

表4 算法成功率和平均迭代次數比較