基于交叉算子和非均勻變異算子的飛蛾撲火優(yōu)化算法?

張保東 張亞楠 郭黎明 江進(jìn)禮 趙嚴(yán)振

（中鐵工程裝備集團(tuán)有限公司智能工程研究院 鄭州 450016）

1 引言

群智能優(yōu)化算法是一類受到人類或大自然種群進(jìn)化或行為規(guī)律啟發(fā)而產(chǎn)生的智能優(yōu)化算法，例如經(jīng)典的粒子群優(yōu)化算法和蟻群優(yōu)化算法等。由于具有靈活性、魯棒性和自組織性等優(yōu)點(diǎn)［1］，近些年來群智能優(yōu)化算法受到了國內(nèi)外學(xué)者的廣泛關(guān)注，相繼出現(xiàn)了許多新型算法。例如人工蜂群算法（Artificial Bee Colony Algorithm，ABC）［2］、螢火蟲算法（Firefly Algorithm，F(xiàn)A）［3］、布 谷 鳥 搜 索 算 法（Cuckoo Search，CS）［4］、蝙蝠算法（Bat Algorithm，BA）［5］、果蠅優(yōu)化算法（Fruit Fly Optimization Algorithm，F(xiàn)OA）［6］、灰狼優(yōu)化算法（Grey Wolf Optimizer，GWO）［7］和飛蛾撲火優(yōu)化算法（Moth-Flame Optimization，MFO）［8］等。

飛蛾撲火優(yōu)化算法是由Mirjalili受到飛蛾螺旋飛行模型啟發(fā)于2015 年提出的一種群智能優(yōu)化算法。該算法通過模擬飛蛾種群在解空間中進(jìn)行螺旋飛行從而搜索最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，該算法在各類基準(zhǔn)測試函數(shù)以及齒輪系設(shè)計、三桿桁架設(shè)計和船用螺旋槳設(shè)計等多個實(shí)際工程問題中取得了優(yōu)良的效果。但由于其存在收斂速度慢以及易收斂到局部最優(yōu)解的問題，不少國內(nèi)外學(xué)者提出了改進(jìn)方案以提高其尋優(yōu)能力。Li 等［9］將Lévy 飛行策略引入飛蛾撲火優(yōu)化算法，提高了算法的全局收斂能力。Soliman 等［10］研究了將飛蛾位置更新公式由對數(shù)螺線函數(shù)更改為雙曲螺線和阿基米德螺線時算法的性能。Muangkote等［11］在飛蛾的位置更新公式中引入了混沌映射和交叉算子，同時優(yōu)化了火焰數(shù)量的自適應(yīng)計算公式。Kaur 等［12］利用柯西分布函數(shù)生成隨機(jī)數(shù)對飛蛾位置進(jìn)行擾動，并對飛蛾的位置更新公式進(jìn)行了優(yōu)化，使飛蛾的飛行同時受到最優(yōu)火焰和其所對應(yīng)火焰的影響。Sapre等［13］研究了將反向?qū)W習(xí)策略、柯西擾動和進(jìn)化邊界約束處理綜合應(yīng)用到飛蛾位置更新公式時算法的性能。吳偉民等［14］引入了縱橫交叉機(jī)制和混沌算子對每一代火焰位置進(jìn)行擾動，減少了算法的搜索盲點(diǎn)，提高了算法跳出局部最優(yōu)解的能力。徐慧等［15］在對網(wǎng)絡(luò)入侵檢測系統(tǒng)的研究中，提出了一種融合粒子群算法的二進(jìn)制飛蛾撲火優(yōu)化算法。APINANTANAKON等［16］提出了一種基于反向?qū)W習(xí)策略的改進(jìn)算法，在飛蛾位置更新后利用反向?qū)W習(xí)策略擾動飛蛾位置。Sayed等［17］將模擬退火算法引入飛蛾的位置更新公式中以提高算法收斂速度。Zhang等［18］提出了一種基于自適應(yīng)權(quán)重和模擬退火的改進(jìn)算法，該算法通過自適應(yīng)權(quán)重動態(tài)地平衡算法的全局搜索能力與局部探測能力，并利用模擬退火算法防止其陷入局部最優(yōu)解。Xu 等［19］提出的方案將文化學(xué)習(xí)算法融入到飛蛾的位置更新公式中，同時利用高斯擾動改變最優(yōu)火焰的位置。Li 等［20］使用差分進(jìn)化策略中的交叉、變異和選擇算子以及動態(tài)火焰引導(dǎo)策略對火焰的位置及飛蛾的更新策略進(jìn)行了優(yōu)化。

綜上所述，針對MFO 算法的改進(jìn)主要分為三個方面：第一是對飛蛾位置更新方法的優(yōu)化，例如對位置更新公式的改變或更新策略的改變；第二是對飛蛾位置進(jìn)行隨機(jī)擾動以提高飛蛾種群的多樣性，第三是對火焰位置進(jìn)行隨機(jī)擾動以提高可行解的多樣性。針對第三種改進(jìn)思路，本文提出了一種基于傳統(tǒng)遺傳算法交叉算子和非均勻變異算子的改進(jìn)方案。在飛蛾圍繞火焰飛行的過程中使用交叉與變異算子隨機(jī)擾動火焰的位置，防止算法過快陷入局部最優(yōu)解。

2 飛蛾撲火優(yōu)化算法改進(jìn)方法

2.1 飛蛾撲火優(yōu)化算法

MFO 算法是對飛蛾撲火這一自然現(xiàn)象的模擬，其假定飛蛾與火焰均為解空間中的候選解。然后，飛蛾種群在解空間中圍繞火焰種群進(jìn)行螺旋飛行，當(dāng)發(fā)現(xiàn)新的位置優(yōu)于已有解時，將其作為新的火焰位置。接著，飛蛾圍繞新的火焰進(jìn)行搜索，并反復(fù)迭代，直到發(fā)現(xiàn)最優(yōu)解。MFO 算法的計算過程如下：

步驟1：初始化飛蛾種群的位置與適應(yīng)度值。假設(shè)種群數(shù)量為n，解空間維度為d ，則飛蛾種群的位置及其適應(yīng)度值可分別用矩陣M 與OM 表示：

其中，M1，M2，…，Mn代表飛蛾在解空間中的位置，OM1，OM2，…，OMn分別對應(yīng)每只飛蛾的適應(yīng)度值。

步驟2：將飛蛾種群按個體適應(yīng)度值進(jìn)行排序生成火焰種群F 及適應(yīng)度值OF 。

步驟3：更新飛蛾位置。位置更新公式為對數(shù)螺旋線函數(shù)，可表示如下：

其中，Mi和Fj分別表示飛蛾與火焰?zhèn)€體。 Di=|Fj-Mi|，表示飛蛾與火焰的距離。b 為與螺旋函數(shù)形狀有關(guān)的常數(shù)，t 為［-1，1］之間的隨機(jī)數(shù)。

步驟4：更新火焰種群位置。合并更新后的飛蛾種群位置M 與原火焰位置F ，按適應(yīng)度值排序后取前n 個解作為新火焰種群位置。

步驟5：循環(huán)執(zhí)行步驟3 和4 直到達(dá)到結(jié)束條件。

為了使算法能更快收斂，計算過程中將不斷減少火焰種群的數(shù)量。每一代的火焰數(shù)量flameno可以根據(jù)以下公式確定：

其中，n 為飛蛾種群數(shù)量，l 為當(dāng)前迭代次數(shù)，T 為最大迭代次數(shù)。

2.2 基于交叉算子和非均勻變異算子的改進(jìn)方法

遺傳算法通過遺傳算子模擬生物種群的進(jìn)化過程。遺傳算子主要分為三種：選擇算子、交叉算子和變異算子［21］。其中，交叉算子模擬的是父代基因重組過程。主要包括均勻交叉、模擬二進(jìn)制交叉、部分映射交叉、次序交叉、單位置次序交叉、線性次序交叉、優(yōu)先保存交叉、基于位置的交叉和循環(huán)交叉等方法。變異算子則模擬了生物進(jìn)化過程中的染色體變異，主要包括均勻變異、非均勻變異和多項(xiàng)式變異等。本文提出的改進(jìn)方案使用交叉算子和非均勻變異算子對每一代火焰的位置進(jìn)行隨機(jī)擾動。

2.2.1 交叉算子

改進(jìn)方案使用的交叉算子類似于均勻交叉算子。但不同的是依次針對火焰矩陣的每一維隨機(jī)選擇k 對火焰進(jìn)行交叉運(yùn)算，每次交叉運(yùn)算將火焰對應(yīng)維度的元素互換并重新計算適應(yīng)度值，當(dāng)新火焰的適應(yīng)度值優(yōu)于原火焰時則替代原火焰，從而使其有一定概率跳出局部最優(yōu)解。交叉運(yùn)算具體流程如圖1 所示。其中，d 表示火焰位置的維度。k為常數(shù)，表示進(jìn)行k 次交叉互換。

圖1 交叉運(yùn)算流程圖

2.2.2 非均勻變異算子

本文選擇非均勻變異算子對火焰位置進(jìn)行擾動，以使火焰在求解初期能在較大范圍內(nèi)搜索并在后期對局部區(qū)域進(jìn)行精細(xì)搜索。非均勻算子可表示如下：

其中，fi，j表示火焰矩陣中第i 個火焰第j 維的元素。t 為當(dāng)前迭代次數(shù)。Umax和Umin分別表示搜索空間每一維度的最大值和最小值。 r 為區(qū)間［0，1］之間的隨機(jī)數(shù)。Δ( t，y )可表示如下：

其中，T 為最大迭代次數(shù)，b 為決定非均勻度的參數(shù)。在使用非均勻變異算子對火焰位置進(jìn)行擾動時，依次針對每個火焰隨機(jī)選擇k 個維度進(jìn)行擾動，每次擾動產(chǎn)生的新火焰優(yōu)于原火焰時則替換原火焰。變異運(yùn)算流程如圖2 所示。其中，n 表示火焰總數(shù)量。k 為常數(shù)，表示進(jìn)行k 次位置擾動。

圖2 變異運(yùn)算流程圖

3 算法性能測試及分析

3.1 基準(zhǔn)測試函數(shù)

為了驗(yàn)證改進(jìn)方案的有效性，本實(shí)驗(yàn)選取了8個常用的最優(yōu)化算法基準(zhǔn)測試函數(shù)（ f1～f8）對改進(jìn)方案進(jìn)行了測試［22］。其中，f1～f4為單峰函數(shù)，僅包含一個全局最優(yōu)值，無局部最優(yōu)值，主要用于測試算法的收斂速度和求解精度。 f5～f8為多峰函數(shù)，在搜索空間中包含大量局部最優(yōu)解，主要用于測試算法的全局搜索能力。所有測試函數(shù)的維度均使用30維，8個測試函數(shù)如下：

1）Sphere函數(shù)

其中，xi∈[-100，100] ，d=30 。該函數(shù)最優(yōu)值為0，最優(yōu)解為(0，…，0)。

2）Schwefel's Problem 2.22函數(shù)

其中，xi∈[-100，100] ，d=30 。該函數(shù)最優(yōu)值為0，最優(yōu)解為(0，…，0)。

4）Rosenbrock函數(shù)

其中，xi∈[- 5.12，5.12] ，d=30。該函數(shù)最優(yōu)值為0，最優(yōu)解為( 0 ，…，0 )。

6）Ackley函數(shù)

其中，xi∈[-600，600] ，d=30 。該函數(shù)最優(yōu)值為0，最優(yōu)解為(0，…，0)。

8）Schwefel's Problem 2.26函數(shù)

其中，xi∈[- 500，500] ，d=30 。該函數(shù)最優(yōu)值為-418.9829d，最優(yōu)解為(420.9687，…，420.9687)。

3.2 測試結(jié)果及分析

為了保證測試結(jié)果的準(zhǔn)確性，實(shí)驗(yàn)中將針對每個基準(zhǔn)測試函數(shù)分別進(jìn)行30 次運(yùn)算，獲取其最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差，并將其與原MFO 算法、灰狼優(yōu)化算法和粒子群優(yōu)化算法的測試結(jié)果進(jìn)行對比。

實(shí)驗(yàn)中設(shè)定的飛蛾種群數(shù)量為30，所有測試函數(shù)均取30維，每次運(yùn)算最大迭代次數(shù)為2000次，交叉算子與非均勻變異算子中k 值均取7，即分別進(jìn)行7 次交叉或變異運(yùn)算。測試結(jié)果如表1 所示，改進(jìn)方案以CNMFO表示。

表1 測試結(jié)果

實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法相比原算法求解能力有明顯提高，8 個測試函數(shù)的求解精度均優(yōu)于原MFO 算法和PSO 算法。對于Sphere 函數(shù)（f1）和Rastrigin 函數(shù)（f5），改進(jìn)方案在30 次運(yùn)算中均尋找到了全局最優(yōu)值。對于Schwefel's Problem 2.22 函數(shù)（f2）、Schwefel's Problem 1.2 函數(shù)（f3）、Rosenbrock函數(shù)（f4）、對于Ackley 函數(shù)（f6）和Griewank 函數(shù)（f7），平均求解精度相較于原算法分別提高了153、6、4、16 及4 個 數(shù) 量 級。由 于Schwefel's Problem 2.26函數(shù)（f8）的全局最優(yōu)值不為0，無法直觀地比較求解精度，但可看出改進(jìn)后的算法所求結(jié)果與理論最優(yōu)值-12569.487接近，平均值與標(biāo)準(zhǔn)差均優(yōu)于原算法。與GWO 算法相比，改進(jìn)方案在函數(shù)f1、f2、f4和f8的求解中表現(xiàn)優(yōu)于該算法，函數(shù)f5、f6、f7的測試結(jié)果則基本一致。但對于函數(shù)f3，改進(jìn)方案的求解精度低于GWO 算法。對于函數(shù)f4，改進(jìn)方案得到的平均值6.76與理論最優(yōu)值相差較大，表明改進(jìn)方案在該函數(shù)的求解中仍然易陷入局部最優(yōu)值。

四種算法的收斂曲線如圖3～圖10 所示，其中圖3～圖9 中縱坐標(biāo)軸為對數(shù)坐標(biāo)軸。從圖中可以看出，改進(jìn)方案在函數(shù)f3的求解中收斂速度低于GWO 算法，在函數(shù)f5、f6和f7的求解中與GWO 算法的收斂速度大致相同，其他函數(shù)的收斂速度則優(yōu)于GWO 算法。而對于8 個基準(zhǔn)測試函數(shù)，改進(jìn)方案的收斂速度與精度均優(yōu)于MFO 算法和PSO 算法，證明了改進(jìn)方案的有效性。

圖3 函數(shù)f1收斂曲線

圖4 函數(shù)f2收斂曲線

圖5 函數(shù)f3收斂曲線

圖6 函數(shù)f4收斂曲線

圖7 函數(shù)f5收斂曲線

圖8 函數(shù)f6收斂曲線

圖9 函數(shù)f7收斂曲線

圖10 函數(shù)f8收斂曲線

4 結(jié)語

本文針對飛蛾撲火優(yōu)化算法收斂速度慢以及易收斂到局部最優(yōu)解的問題提出了一種改進(jìn)方案。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法相較于原算法在收斂速度和尋優(yōu)精度上均有明顯提高，同時在計算后期能夠以較大概率跳出局部最優(yōu)解。然而，該算法在面對部分復(fù)雜函數(shù)時仍會陷入局部最優(yōu)解，同時對火焰的擾動會增加計算復(fù)雜度，降低計算速度。在今后的研究中，將進(jìn)一步研究局部最優(yōu)解的避免方法以及提高計算速度的方法。