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

張保東 張亞楠 郭黎明 江進禮 趙嚴振

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

1 引言

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

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

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

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

MFO 算法是對飛蛾撲火這一自然現(xiàn)象的模擬，其假定飛蛾與火焰均為解空間中的候選解。然后，飛蛾種群在解空間中圍繞火焰種群進行螺旋飛行，當發(fā)現(xiàn)新的位置優(yōu)于已有解時，將其作為新的火焰位置。接著，飛蛾圍繞新的火焰進行搜索，并反復迭代，直到發(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)度值進行排序生成火焰種群F 及適應(yīng)度值OF 。

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

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

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

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

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

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

2.2 基于交叉算子和非均勻變異算子的改進方法

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

2.2.1 交叉算子

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

圖1 交叉運算流程圖

2.2.2 非均勻變異算子

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

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

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

圖2 變異運算流程圖

3 算法性能測試及分析

3.1 基準測試函數(shù)

為了驗證改進方案的有效性，本實驗選取了8個常用的最優(yōu)化算法基準測試函數(shù)（ f1～f8）對改進方案進行了測試［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é)果的準確性，實驗中將針對每個基準測試函數(shù)分別進行30 次運算，獲取其最優(yōu)值、最差值、平均值和標準差，并將其與原MFO 算法、灰狼優(yōu)化算法和粒子群優(yōu)化算法的測試結(jié)果進行對比。

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

表1 測試結(jié)果

實驗結(jié)果表明，改進后的算法相比原算法求解能力有明顯提高，8 個測試函數(shù)的求解精度均優(yōu)于原MFO 算法和PSO 算法。對于Sphere 函數(shù)（f1）和Rastrigin 函數(shù)（f5），改進方案在30 次運算中均尋找到了全局最優(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，無法直觀地比較求解精度，但可看出改進后的算法所求結(jié)果與理論最優(yōu)值-12569.487接近，平均值與標準差均優(yōu)于原算法。與GWO 算法相比，改進方案在函數(shù)f1、f2、f4和f8的求解中表現(xiàn)優(yōu)于該算法，函數(shù)f5、f6、f7的測試結(jié)果則基本一致。但對于函數(shù)f3，改進方案的求解精度低于GWO 算法。對于函數(shù)f4，改進方案得到的平均值6.76與理論最優(yōu)值相差較大，表明改進方案在該函數(shù)的求解中仍然易陷入局部最優(yōu)值。

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

圖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)解的問題提出了一種改進方案。實驗結(jié)果表明，改進后的算法相較于原算法在收斂速度和尋優(yōu)精度上均有明顯提高，同時在計算后期能夠以較大概率跳出局部最優(yōu)解。然而，該算法在面對部分復雜函數(shù)時仍會陷入局部最優(yōu)解，同時對火焰的擾動會增加計算復雜度，降低計算速度。在今后的研究中，將進一步研究局部最優(yōu)解的避免方法以及提高計算速度的方法。