引入精英反向學習和柯西變異的混沌蜉蝣算法

張少豐，李書琴

(西北農林科技大學 信息工程學院，陜西 楊凌 712100)

0 引 言

蜉蝣算法(mayfly algorithm，MA)[1]是Zervoudakis等受蜉蝣的飛行和繁衍行為啟發提出的一種新型的智能優化算法，通過模擬雌性蜉蝣選擇適合的雄性蜉蝣個體進行繁衍，逐步淘汰子代蜉蝣中適應度值較低的個體的過程完成尋優。相比于其它算法，該算法具有結構簡單、控制參數少、尋優能力強[2-4]等優點，因此在諸多領域[5，6]有廣泛的應用，但在解決高維復雜問題下，由于蜉蝣在移動過程中步長較短，導致其算法存在收斂速度慢、易陷入局部最優等缺陷。

針對蜉蝣算法的不足，Zheng-MingGAO等[7]提出異構蜉蝣算法，通過增加蜉蝣更新的方式，來提高蜉蝣算法尋優能力。李浩等[8]提出多目標離散蜉蝣算法的動態網絡社區發現方法，通過標簽擴散算法將種群進行離散化，提高了蜉蝣算法求解精度。陳偉超等[9]提出基于倒位變異的蜉蝣算法，利用倒位操作，將隨機個體的維度向最優個體靠近，提高了算法收斂性。

上述研究在一定程度上提高了蜉蝣算法的尋優能力，但是仍存在收斂速度慢、穩定性不強等問題。因此本文提出了混沌蜉蝣算法(chaotic mayfly algorithm，CMA)，主要改進策略為：

(1)基于Circle混沌初始化種群，使蜉蝣個體均勻分布在搜索空間，增加初始解的可行性。

(2)引入基于精英個體的反向學習機制，對子代蜉蝣個體中的精英個體生成反向解，并選擇其中較優個體作為下一代迭代個體，增加算法尋優能力和收斂速度。

(3)將自適應概率閾值與柯西變異策略相結合，對劣勢蜉蝣個體進行變異擾動，保證種群進化方向，提高算法的全局尋優能力，防止算法陷入局部最優。

1 蜉蝣算法(MA)

蜉蝣種群包含雄性蜉蝣和雌性蜉蝣，其數量均為N/2，N為群體總數。在蜉蝣繁衍過程中，雄性蜉蝣通過全局最優和自身歷史最優值移動，而雌性則是向優于自己的配偶移動，若配偶弱于自己則自行局部搜索。蜉蝣產生后代，逐漸淘汰適應度較低的個體并保留群體中較優個體，最終完成尋優的過程。

1.1 雄性蜉蝣的移動

雄性蜉蝣的移動會根據自身鄰域范圍內的局部最優和全局最優進行位置調整，雄性蜉蝣在t時刻的位置更新方式請參見文獻[1]，雄性蜉蝣會在水面表演舞蹈吸引雌性蜉蝣，在此階段中蜉蝣速度更新方式為

(1)

(2)

其中，xij表示蜉蝣i的第j個分量，Xi為蜉蝣對應的pbest和gbest。 為了找到最優位置，蜉蝣需要不斷更新速度，其速度的更新方式為

(3)

其中，d表示舞蹈系數，r為[-1，1]之間的隨機數。

1.2 雌性蜉蝣的移動

雌性蜉蝣會飛到雄性群體中選擇適配度較高的雄性蜉蝣進行交配繁衍。它的位置通過增加速度來更新，雌性蜉蝣位置更新方式請參見文獻[1]，雌性蜉蝣的速度計算方法如下

(4)

1.3 蜉蝣交配過程

蜉蝣交配過程中一對雌性和雄性會產生兩個后代，交配過程中通過蜉蝣的適應度選擇親本，最優的雄性蜉蝣與最優的雌性蜉蝣進行繁衍交配，次優雄性蜉蝣與次優的雌性蜉蝣進行繁衍交配。交叉算子代表兩個蜉蝣交配過程，交叉的結果是兩個后代，產生結果如下

offspring1=L·male+(1-L)·female
offspring2=L·female+(1-L)·male

(5)

其中，male表示雄性父代，female表示雌性父代，L是 [-1，1] 之間的隨機數。

2 混沌蜉蝣算法

2.1 Circle混沌映射

針對MA進行初始化種群分布是隨機生成，導致算法容易陷入局部最優的問題。本文采用混沌映射的方式實現對中群的初始化，結合混沌映射具有不可預測、非線性等特點。通過混沌初始化種群使得蜉蝣種群均勻分布在搜索空間內，從而提高蜉蝣算法的搜索性能。常用來初始化種群的混沌映射有Logistic映射和Tent映射，相關研究結果表明[10，11]Logistic映射呈現切比雪夫分布，隨著迭代次數增加在[0，0.1]和[0.9，1]區間內有較高的分布，導致分布不均，搜索盲區較大，從而影響算法的尋優能力。Tent映射分布相對均勻，但是屬于映射折疊次數有限的混沌模型，存在周期不穩定容易使得映射陷入不動點的缺陷。而Circle混沌映射不僅能克服Tent和Logistics映射的缺點，而且其產生的混沌序列也更加均勻[13]。因此采用的Circle混沌映射來生成初始群體，Circle映射定義如式(6)所示

(6)

其中，xi+1表示映射之后的位置，xi表示目標原位置，i表示維度。

隨機生成的種群分布圖和經過Circle映射后的種群分布圖如圖1和圖2所示，通過Circle混沌映射初始化后的蜉蝣種群與隨機生成的種群序列相比，蜉蝣個體的位置分布更加均勻，增加群體位置的多樣性。提高了初始解的可靠性，一定程度上提高了算法跳出局部最優的能力，從而提高了算法的尋優效率。

圖1 隨機生成種群分布

圖2 Circle映射后的種群分布

2.2 精英反向學習機制

反向學習[14](opposition-based learning，OBL)是通過求解問題可行解的反向解，并對反向解和可行解進行評估，從中選擇更優解為下一代個體，提高算法的尋優效率。為了增加MA算法的全局尋優能力，防止算法進入“早熟”階段，引入精英反向學習機制。在蜉蝣交配繁衍產生子代中，針對精英個體，使用反向學習機制生成對應的反向解，采用雙向評估導則，在選取適應度較高的蜉蝣個體作為下一代種群，加快算法的收斂速度。設當前蜉蝣在D維搜索空間的可行解表示為

Xi=(x1，x2，…，xD)

(7)

則當前可行解的反向解則表示為

(8)

(9)

其中，k為[0，1]上均勻分布的隨機函數，ai、bi分別為xi的最大值和最小值。

當前種群內所有個體中對應的評價函數的極值為精英個體，如式(10)所示。對精英個體構造反向解可以增加種群的多樣性，并從當前候選解和反向解中選擇最優值作為子代蜉蝣個體，從而提高算法的收斂能力。精英反向解的計算方法如式(11)、式(12)所示

(10)

(11)

(12)

2.3 基于柯西變異擾動機制

在蜉蝣群體在繁衍過程中，如果蜉蝣個體進化程度多次低于種群平均進化程度，則評定該蜉蝣為劣勢蜉蝣。如果劣勢蜉蝣個體較多使得種群進化方向偏移，導致算法陷入局部最優。為了減少劣勢蜉蝣個體出現，本文引入基于柯西變異的擾動機制策略，每次更新種群時，將劣勢蜉蝣個體進行柯西變異，在蜉蝣個體附近生成更大擾動，擴大尋優范圍，增加收斂速度，從而提高全局尋優能力。判斷是否為劣勢蜉蝣標準如式(13)、式(14)所示

(13)

(14)

為了避免陷入局部最優值以及保障整個種群進化方向，對劣勢蜉蝣個體通過自適應擾動概率p進行柯西變異。自適應概率p的定義如式(15)所示

(15)

其中，N為種群個數，Iter為迭代次數，ε為調節因子取值為0.05，0.1，0.15，0.2進行調整。

相比正態分布，柯西分布具有相對平緩的概率浮動的特點，在峰值處相比正態分布較低，在兩側趨近于0的速率較慢[15]。因此能夠產生更好的擾動效果，利用柯西變異對蜉蝣個體進行擾動，提高CMA跳出局部最優能力，從而提高算法的收斂能力。具體更新方式如式(16)所示，其中cauchy(0，1) 為標準柯西分布函數，標準柯西變異分布函數定義參見文獻[16]

(16)

如果當前蜉蝣滿足式(13)則可以判斷為劣勢蜉蝣個體，然后隨機生成隨機?，?∈[0，1]。 如果?>p， 則進行變異擾動，否則保持不變。因此當前蜉蝣位置更新方式如下

(17)

其中，柯西分布隨機變量生成函數為η=tan[(ξ-0，5)π]。

2.4 算法流程

綜上所述，基于精英反向學習和柯西變異的混沌蜉蝣算法的偽代碼見表1，算法流程如圖3所示，CMA算法主要流程為：

表1 混沌蜉蝣算法CMA偽代碼

圖3 CMA算法流程

步驟1 初始化參數，種群規模N，迭代次數Iterator，舞蹈系數dance， 飛行系數α。

步驟2 根據式(6)進行Circle混沌映射生成初始化種群，并初始化蜉蝣位置和速度。

步驟3 根據式(1)、式(2)更新雄性蜉蝣的速度和位置，并計算適應度值。并對雄性蜉蝣的適應度值進行排序，獲取當前雄性蜉蝣的pbest和gbest。

步驟4 根據式(4)更新雌性蜉蝣速度。

步驟5 根據式(5)蜉蝣交叉算子產生子代。

步驟6 結合蜉蝣pbest和gbest， 對適應度進行排序，選擇精英個體，根據式(14)生成精英反向解。

步驟7 通過式(13)、式(14)判斷劣勢蜉蝣個體offspringi， 如果符合則根據式(17)進行柯西變異。第n行對更新后種群進行篩選，淘汰適應度值低的個體。

步驟8 判斷是否達到終止條件，是則輸出最優解，否則執行步驟3～步驟6。

2.5 算法時間復雜度分析

設搜索空間的維度為D，種群總數為N，雄性蜉蝣的個數為N1，雌性蜉蝣的個數為N2，子代蜉蝣個體為N3，最大迭代次數為T。初始化復雜度為O(1)，則MA的時間復雜度T(n)=O(1+T(N1D+N2D+N3D))=O(TN)。 Circle混沌映射初始化種群分布的時間復雜度為O(N)，由于精英反向學習機制嵌套在種群交配循環內，時間復雜度為O(N1D)， 柯西變異的擾動機制只在子代蜉蝣產生后進行判斷，時間復雜度為O(N3D)。 所以改進CMA的時間復雜度為T(n)=Of(n)=O(T(N1(D+2)+N2(D+1)+N3(D+2)))。

3 實驗與結果分析

3.1 實驗環境

為驗證CMA算法的尋優性能，本文選取了粒子群優化算法(PSO)[17]、蜻蜓優化算法(DA)[18]、基于Logistics映射的蜉蝣算法(LMA)[19]以及蜉蝣算法(MA)[3]、進行實驗對比。并選擇8個標準benchmark測試函數進行實驗，其中包括4個單峰測試函數(f1～f4)和4個多峰測試函數(f5～f8)。種群規模設置為N=30， 最大迭代次數為Iterator=500， 維度為30，各類算法獨立運行50次，編譯工具為Matlab R2021a，算法主要參數見表2，測試函數見表3，本文的實驗分為3個部分進行：

表2 算法主要參數

表3 測試函數

(1)將CMA與基本MA算法、PSO算法、DA算法和LMA算法進行比較，分別從算法性能、收斂速度、高維度分析3個角度進行分析，驗證算法的有效性。

(2)以MA為基本模型，將CMA與基本MA算法、基于Circle混沌映射的蜉蝣算法CIMA、基于精英反向學習的蜉蝣算法EMA和基于柯西變異的蜉蝣算法CAMA進行對比分析，驗證改進策略的有效性。

(3)Wilcoxon秩和檢驗，驗證CMA與其它對比算法之間的顯著性差異。

3.2 算法性能分析

通對5種算法在8個測試函數對比分析，并以最優值Best、 平均值Mean、 標準差Std為評價標準，實驗結果見表4。在最優值方面，CMA在f1、f2、f3、f5這4個測試函數中已經達到最優值，且其它算法均沒到達最優值，說明CMA搜索性能得到了一定的提高。在單峰測試函數f4中盡管沒有到達理論最優值，但相比其余4種算法均有較大提升，而且平均值也更接近理論最優值。說明CMA在單峰測試函數中具有較強的搜索能力且有更高的收斂精度。而在多峰測試函數f6、f7、f8中，求解精度有一定的下降，但是仍然比MA、PSO、DA、LMA的求解平均高出其它算法10～15個數量級，說明引入針對精英個體的反向學習策略和柯西變異擾動策略使得CMA的跳出局部最優能力有所提升提高。

表4 測試函數的實驗對比結果

在均值和標準差方面，在f1、f2、f3中，CMA的均值都是最優的，而在測試函數f4、f8中DA、PSO、MA在尋優后期陷入了局部最優值，標準差比較小而CMA能夠跳出局部最優解，因此CMA標準差大于DA、PSO、MA三者，但是同時也具有更高求解精度。說明CMA算法的穩定性和魯棒性優于其它4種算法。通過與MA進行對比，在所有測試函數函數中最優值、均值和標準差均比MA具有更好的效果，并且在f1、f2、f3、f5這4個測試函數中已經達到了理論值，說明在MA中加入混沌映射、精英反向學習、基于柯西變異的擾動機制策略，幫助算法提高的收斂能力和尋優能力，驗證了改進策略的有效性。

3.3 收斂速度分析

為了驗證算法的收斂精度和收斂速度，繪制了測試函數的收斂曲線圖，分別如圖4～圖11所示，由圖4～圖7單峰收斂曲線可知，在f1、f2、f3、f4單峰測試函數中，PSO、DA的收斂曲線呈現平緩、停滯狀態，容易陷入局部最優值，尋優精度較低。LMA和MA收斂曲線相比PSO、DA在收斂速度所有提高，但是仍然存收斂精度較低的問題。而隨著迭代次數的增加CMA的收斂曲線一直處于其它曲線的下方，具有更快的收斂速度。在收斂速度和收斂精度方面，CMA都明顯優于其它算法，說明在單峰測試函數方面，CMA收斂速度和尋優精度有較大提升。

圖4 f1收斂曲線

圖5 f2收斂曲線

圖6 f3收斂曲線

圖7 f4收斂曲線

由于多峰測試函數都存在大量的局部最優值，在測試函數f5、f6、f7、f8中，如圖8～圖11多峰收斂曲線可知，MA、PSO、DA都容易陷入局部最優值，全局收斂性較差，收斂曲線呈現平緩趨勢，出現早熟早收斂的現象。LMA相比MA、DA、PSO具有更好的收斂速度，但仍然存在收斂精度不足的問題。相比CMA法的收斂曲線，隨著迭代次數的增加，收斂曲線表現呈現較好的向下尋優過程。說明CMA引入精英反向學習機制擴大尋優范圍和柯西變異擾動機制保證整個種群的進化方向，使得CMA算法性能得到顯著提高。綜上所述，相比于其它算法，CMA算法具有更好的收斂速度和收斂精度，改善了MA的早熟早收斂的問題。

圖8 f5收斂曲線

圖9 f6收斂曲線

圖10 f7收斂曲線

圖11 f8收斂曲線

3.4 高緯度分析

為了驗證CMA算法求解高維度問題的能力，分別測試CMA在50、100維下實驗結果，參數設置均保持不變，分別從平均值Mean和標準差Std兩個方面進行評估，實驗結果見表5。由表可知，在維度50維、100維的情況下，CMA在測試函數f1、f2、f3、f5仍然可以達到理論最優值。其它算法中表現次好的為LMA，在f1、f2單峰測試函數維度為50情況下，LMA算法均值為1.3257e-15、2.2581e-08，雖然與CMA相比仍然還有所差距，但是仍然比其它算法有更高精度。

表5 CMA算法高緯度對比結果

通過結合表4中上述算法在30維度的實驗數據，由表4、表5可知隨著維度的增加，使得函數更加復雜，搜索空間增大，尋優難度增加。所以PSO、MA、DA求解精度和魯棒性整體呈現下降趨勢，其中DA是3種算法中較差的，PSO次之。且CMA在求解單峰函數f4和多峰函數f6～f8時，隨著維度的增加，收斂精度和魯棒性整體也呈現下降趨勢。但仍比其它算法提高了5～10個的數量級的收斂精度和更好的穩定性。CMA在f4精度存在波動但表現出很強的魯棒性，在f6、f7、f8中隨著維度的增加表現出更好的收斂精度和穩定性，從而驗證CMA在低維和高維情況下均有更好的尋優能力。

在標準差方面，CMA的標準差整體都小于其它算法，但在100維多峰測試函數f6、f7、f8中，MA、PSO、DA、LMA其它4種算法隨著維度的增加而陷入局部最優值，所以每次尋優結果比較接近，標準差小。CMA標準差雖然大于其它算法，但是跳出局部最優能力較強，具有較高的求解精度。說明引入精英反向學習策略避免陷入局部最優值，在種群更新的過程中引入了柯西變異，保證了種群的多樣式，提高算法的尋優能力。

3.5 改進策略分析

為進一步探究改進策略對CMA的有效性，以標準蜉蝣算法(MA)作為基本模型，對基于Circle混沌初始化的蜉蝣法(CIMA)、基于精英反向學習的蜉蝣算法(EMA)、基于柯西變異的蜉蝣算法(CAMA)以及CMA進行對比實驗。實驗分別從最優值Best、均值Mean以及標準差Std這3個方面分析改進策略的有效性。算法參數設置與3.1節相同，算法獨立運行50次，實驗結果見表6。

表6 不同改進策略對比結果

由表6可知，CMA在測試函數f1、f2、f3、f5的3個指標均能達到理論值，對于f4、f6、f8雖然沒有尋到最優，但是相對于其它改進算法，CMA具有更高的求解精度和穩定性。相比于基礎模型MA而言，CIMA的求解精度是3種改進策略算法中最差的，但其收斂精度也得到了一定的提高，其中在f2、f3、f5函數上提升效果最好，說明混沌初始化改進策略提高了算法尋優能力。EMA在最優值Best和均值Mean都有較大提升，在整體測試函數中提升大約5～10個數量級，說明引入精英反向學習對于算法收斂性有較大提升。而CAMA在收斂精度有所提升，但是提升效果低于EMA。在標準差方面，EMA均小于MA，說明引入基于柯西變異的擾動機制增強了MA的穩定行。綜合表6的實驗結果，在最優值Best、均值Mean以及標準差Std方面相比其它算法，CMA都有更優的性能，同時具有更強的有效性和可行性。綜上所述，說明融合3種改進策略的CMA，對于增加種群多樣性、增強算法尋優能力是有效的。

3.6 Wilcoxon秩和檢驗

為了驗證CMA算法穩定性和公平性，本文采用Wil-coxon秩和檢驗[20]對CMA進行顯著性分析，對CMA獨立運行30次的數據在5%的顯著水平下驗證與其它算法是否存在顯著差異，若計算出p<0.05， 則說明兩種算法存在顯著性差異。若計算出p>0.05， 則說明兩種算法不存在顯著性差異。CMA和MA、PSO、DA、LMA在顯著水平p=5%， 維度30維下的實驗結果見表7，其中N/A表示二者性能相當，無法進行比較。由表7可知大部分的p值均小于0.05，說明CMA的尋優能力與其它算法存在顯著性差異。對于f5、f6、f7函數CMA和LMA，f4和f7函數，CMA和MA尋優效果差異不明顯，尋優能力相當。結合上述實驗，故認為CMA與其它算法存在顯著性差異且CMA的性能更加。

表7 Wilcoxon秩和檢驗結果

4 結束語

針對MA的不足，提出一種引入精英反向學習和柯西變異的混沌蜉蝣算法。首先通過Circle映射初始化種群，使其種群分布均勻，然后對精英個體進行反向學習策略生成精英反向解，提高算法的收斂速度，最后引入基于自適應概率閾值和柯西變異的擾動策略，對劣勢蜉蝣進行擾動，擴大尋優范圍保證種群尋優方向。實驗驗證CMA具有更好的尋優能力、收斂速度以及穩定性。同時本文改進策略也為其它啟發式算法提供借鑒，在未來的研究中，考慮將改進算法運用于優化移動群智感知的任務分配問題，以進一步驗證算法的性能。