基于交叉算子的反向梯度優(yōu)化算法

吳 蕓，程沖華 ，江海新，劉俊峰，李 進(jìn)

(1.九江學(xué)院 理學(xué)院，江西 九江 332005；2.浙江大學(xué) 控制科學(xué)與工程學(xué)院，工業(yè)控制技術(shù)國家重點實驗室,杭州 310027)

梯度優(yōu)化算法(Gradient-based optimizer，GBO)[1]是Iman Ahmadianfar、Omid Bozorg-Haddad 等人于2020年提出的一種群體智能優(yōu)化算法.GBO的靈感來自于牛頓法，借助群智能優(yōu)化算法的思想，利用一組向量并結(jié)合梯度搜索規(guī)則(GSR)、局部逃逸算子(LEO)來進(jìn)行搜索.

GBO概念簡單易實現(xiàn)，通過與灰狼優(yōu)化算法(GWO)[2]，人工蜂群算法(ABC)[3]，鯨魚優(yōu)化算法(WOA)[4]的比較，驗證了GBO具有較好的開發(fā)與探索能力，且在求解減速機(jī)、三桿桁架、工字鋼設(shè)計和懸臂梁等工程問題時性能顯著.GBO算法雖然性能表現(xiàn)卓越，但在解決某些復(fù)雜優(yōu)化問題時仍存在求解精度低、收斂速度慢且易陷入局部最優(yōu)等缺點，因此許多學(xué)者對GBO算法進(jìn)行了不同的改進(jìn)與應(yīng)用.Zhou Wei[5]等提了基于梯度的光伏模型參數(shù)提取優(yōu)化器，利用隨機(jī)學(xué)習(xí)機(jī)制來提高梯度優(yōu)化算法的性能；M H Hassan[6]等將曼塔射線覓食優(yōu)化(MRFO)與基于梯度優(yōu)化器(GBO)混合為MRFO-GBO，MRFO-GBO能有效求解單目標(biāo)和多目標(biāo)EED問題.

為改善GBO的性能表現(xiàn)，MGBO應(yīng)用了交叉算子和反向?qū)W習(xí)兩種策略進(jìn)行改進(jìn).首先對每次迭代前的種群進(jìn)行預(yù)處理，執(zhí)行交叉算子來提高解的質(zhì)量、增強(qiáng)種群多樣性，加快收斂速度；然后對搜索后更新的種群進(jìn)行反向?qū)W習(xí)，加強(qiáng)算法逃離局部最優(yōu)的能力，提高算法求解精度.通過對9個測試函數(shù)進(jìn)行仿真實驗對比，結(jié)果表明改進(jìn)算法效果顯著，收斂速度和求解精度得到較大的提升.

1 基本梯度優(yōu)化算法

梯度優(yōu)化算法的主要思想是將梯度搜索規(guī)則(GSR)和局部逃逸算子(LEO)相結(jié)合進(jìn)行全局和局部搜索.

1.1 梯度搜索規(guī)則 (GSR)

GBO算法從一組隨機(jī)的初始解開始，并根據(jù)指定方向的梯度更新每個個體位置.為了保證算法的探索與開發(fā)能力之間的平衡，采用的ρ1如下：

ρ1=2×rand×α-α

(1)

(2)

(3)

rand是[0,1]中的一個隨機(jī)數(shù)，βmin=0.2，βmax=1.2，m為當(dāng)前迭代次數(shù),M為總迭代次數(shù)，參數(shù)ρ1基于正弦函數(shù)α進(jìn)行更新.因此，GSR可以確定如下：

(4)

Δx=rand(1：N)×|step|

(5)

(6)

(7)

DM=rand×ρ2×(xbest-xn)

(8)

ρ2=2×rand×α-α

(9)

(10)

(11)

ypn和yqn表達(dá)式如下：

(12)

(13)

(14)

(15)

(16)

其中

定義如下：

(17)

1.2 局部逃逸算子(LEO)

ifrand

End

(18)

f1是在[-1,1]范圍內(nèi)的均勻隨機(jī)數(shù)，f2是來自均值為0、標(biāo)準(zhǔn)差為1的正態(tài)分布的隨機(jī)數(shù)，pr是概率，u1、u2、u3是三個隨機(jī)數(shù)，分別定義為：

u1=L1×2×rand+(1-L1)

(19)

u2=L1×rand+(1-L1)

(20)

u3=L1×rand+(1-L1)

(21)

(22)

其中L2是一個二進(jìn)制參數(shù)，其值為0或1.如果μ2小于0.5，則L2的值為1，否則為0.

2 基于交叉算子和反向?qū)W習(xí)的GBO

針對基本梯度優(yōu)化算法存在的求解精度低、收斂速慢、易陷入局部最優(yōu)等缺陷，MGBO分別從兩個方面進(jìn)行改進(jìn)：①利用交叉算子對當(dāng)前種群進(jìn)行處理，能豐富種群的多樣性，提高收斂速度和收斂精度；②通過對當(dāng)前所得解進(jìn)行反向?qū)W習(xí)來擴(kuò)大解的搜索范圍以逃離局部最優(yōu)，從而提高求解精度.

2.1 交叉算子

曹天問等[7]將兩點交叉算子運用于細(xì)菌覓食算法中，受此啟發(fā)，MGBO也采用兩點交叉來進(jìn)行改進(jìn)，但又與他們不同，這處理的方式是將要淘汰的一半個體分別與當(dāng)前種群最優(yōu)個體兩兩進(jìn)行交叉，交叉過后所得種群代替即將被淘汰的個體.與原始算法相比這有利于降低時間復(fù)雜度且該過程將優(yōu)質(zhì)基因帶入到當(dāng)前種群，優(yōu)質(zhì)基因的流入提高了種群多性，利于逃離局部最優(yōu)，提高求解精度.交叉算子表達(dá)式如下：

(23)

2.2 反向?qū)W習(xí)

反向?qū)W習(xí)(Opposition-based learning,OBL)是Tizhoosh教授在2005年提出來的一種優(yōu)化技術(shù)，根據(jù)概率定律，當(dāng)前解有0.5的概率比它的反向解更接近最優(yōu)解，目前反向?qū)W習(xí)已經(jīng)成功運用于果蠅優(yōu)化算法(FOA)[8]，粒子群算法(OPSO)[9]，差分算法(ODE)[10].

2.3 基于交叉算子的反向梯度優(yōu)化算法(MGBO)

MGBO算法流程大致如下：

Step 1 初始化設(shè)置算法的基本參數(shù).

Step 2 通過評估函數(shù)求出每個個體的適應(yīng)值，并記下最優(yōu)xbest和最差xworst位置.

Step 7 對當(dāng)前解的位置信息進(jìn)行越界處理，隨后計算其適應(yīng)度，判斷是否優(yōu)于當(dāng)前記錄中的全局最優(yōu)值，若是，則更新全局最優(yōu)值.

Step 8 判斷算法是否滿足迭代終止條件，若滿足，則輸出全局最優(yōu)解，否則跳轉(zhuǎn)至Step 3進(jìn)行下次迭代尋優(yōu).

2.4 算法復(fù)雜度分析

時間復(fù)雜度是指算法執(zhí)行所需要的計算工作量.在基本梯度優(yōu)化算法中，時間復(fù)雜度主要受到種群規(guī)模nP、最大迭代次數(shù)MaxIt、及問題維度D的影響.由GBO算法尋優(yōu)過程可知其時間復(fù)雜度為O(nP*MaxIt*D+nP).相比GBO算法，MGBO算法在迭代過程中，增加了將種群的一半個體與最優(yōu)個體兩兩進(jìn)行交叉、反向?qū)W習(xí)操作，因此MGBO比GBO多(MaxIt*(nP*3/2+D))次運算量.

3 實驗仿真及分析

為了驗證本文提出的MGBO算法的有效性，選取了9個經(jīng)典基準(zhǔn)函數(shù)進(jìn)行數(shù)值實驗，并與基本梯度優(yōu)化算法、灰狼優(yōu)化算法、粒子群算法[11]、哈里斯鷹優(yōu)化算法[12]和鯨魚優(yōu)化算法進(jìn)行比較.表1給出了測試函數(shù)的基本信息和相關(guān)參數(shù)設(shè)置，包含單峰、多峰等不同特征的測試函數(shù).表2為每個算法主要參數(shù)設(shè)置.

表1 測試函數(shù)參數(shù)設(shè)置

表2 算法主要參數(shù)設(shè)置

為了降低算法的隨機(jī)性對實驗結(jié)果的影響，我們對獨立運行30次的實驗結(jié)果取平均，其中種群規(guī)模為50、最大迭代次數(shù)為1 100次.表3給出了改進(jìn)算法(MGBO)、梯度優(yōu)化算法(GBO)、灰狼優(yōu)化算法(GWO)、粒子群算法(PSO)、哈里斯鷹優(yōu)化算法(HHO)和鯨魚優(yōu)化算法(WOA)在30維、50 維、100 維三種的情況下搜索得到的平均值、標(biāo)準(zhǔn)差，其中結(jié)果最好的用粗體顯示.

表3 不同算法在不同維度下的平均值及標(biāo)準(zhǔn)差

實驗環(huán)境為：Windows10 系 統(tǒng)，8 GB 內(nèi) 存，CPU 2.00 GHz，算法基于 MATLAB 2016b 用M語言編寫.

從表3知，無論是30、50、100維MGBO對于5個單峰函數(shù)(f1-f5)都是最優(yōu)，特別在求解f1和f3時獲得了理論最優(yōu)值0.對于4個多峰函數(shù)(f6-f9)，在30、50、100維上，MGBO在求解f6和f8時都獲得了理論最優(yōu)值0，MGBO雖在f7上無法取到理論最優(yōu)值，但平均值都優(yōu)于其對比算法的平均值，且求解f9函數(shù)時MGB0的結(jié)果都比對比算法要好.因此整體來說MGBO在求解單峰、多峰函數(shù)時都有更好的尋優(yōu)效果與可擴(kuò)展性.標(biāo)準(zhǔn)差可以反映算法的穩(wěn)定性.由表3可知，MGBO獨立運行30次計算的標(biāo)準(zhǔn)差始終不大于對比算法，這說明MGBO對單峰、多峰、低維、高維測試函數(shù)的穩(wěn)定性好.

表4 MAE算法排名

可以看出，MGBO排名均為 1，與另外5種算法相比，MGBO提供了最小的MAE，進(jìn)一步證明了MGBO的有效性.

為了更好地對比六種算法的尋優(yōu)性能，圖1給了它們在不同函數(shù)上50維的收斂曲線，其中橫坐標(biāo)為迭代次數(shù)，所有函數(shù)其適應(yīng)度值都取以10為底的對數(shù).

由圖1(a)-(e)可知，隨著迭代次數(shù)的增加，梯度優(yōu)化算法、灰狼優(yōu)化算法、粒子群算法、哈里斯鷹優(yōu)化算法和鯨魚優(yōu)化算法在單峰函數(shù)上均收斂速度均較慢、無法搜索到理論最優(yōu)值且MGBO的收斂曲線下降最快，速度得到了明顯的提高，這說明引入交叉算子增加了種群多樣性，使得算法加快收斂速度.圖(f)-(i)是多峰函數(shù)平均收斂曲線，MGBO在f6-f9上迭代收斂速度很快，尤其對f6和f8兩函數(shù)最明顯，這說明反向?qū)W習(xí)有效改善算法性能及交叉算子引入優(yōu)質(zhì)基因的作用是突出的.

圖1 函數(shù)收斂曲線

4 結(jié)語

本文對GBO算法中存在早熟性收斂以及陷入局部最優(yōu)，提出了一種應(yīng)用交叉算子和反向?qū)W習(xí)的梯度優(yōu)化算法(MGBO).交叉算子的引入可以豐富種群的多樣性，對單峰函數(shù)而言，尋優(yōu)能力和收斂速度得到了明顯的提高；反向?qū)W習(xí)策略是通過評價候選解和反向解的優(yōu)劣來擴(kuò)大搜索空間，對于多峰函數(shù)而言有利于逃離局部最優(yōu)值轉(zhuǎn)向全局最優(yōu)值收斂，加快算法收斂速度.實驗證明，本文的算法不但有效地加快搜尋速度，且提高了解的精度.