一種基于精英反向和縱橫交叉的鯨魚優(yōu)化算法

劉 琨，趙露露，王 輝

(河南理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，河南 焦作 454000)

1 引 言

全局優(yōu)化問題廣泛存在于數(shù)學(xué)、經(jīng)濟(jì)、系統(tǒng)優(yōu)化和工程實踐等領(lǐng)域中，對于具有高維、非線性、多極值、目標(biāo)函數(shù)不可導(dǎo)等特點的復(fù)雜全局優(yōu)化問題，傳統(tǒng)優(yōu)化算法很難獲得理想的優(yōu)化效果，而群智能優(yōu)化算法為求解此類優(yōu)化問題提供了有效的解決方案.近年來，許多群智能優(yōu)化算法如粒子群算法[1]，蟻獅優(yōu)化算法[2]，蜻蜓算法[3]，蝗蟲優(yōu)化算法[4]，灰狼優(yōu)化算法[5]，正弦余弦算法[6]等相繼被提出，并用于解決復(fù)雜全局優(yōu)化問題.

鯨魚優(yōu)化算法(Whale Optimization Algorithm，WOA)是Mirjalili等人在2016年提出的一種新型智能優(yōu)化算法[7].該算法具有原理簡單、結(jié)構(gòu)靈活、易于理解且便于實現(xiàn)等優(yōu)點，但其同樣存在收斂速度慢、易陷入局部最優(yōu)和收斂精度低的問題.為此，許多學(xué)者針對鯨魚優(yōu)化算法的不足做了相應(yīng)的改進(jìn).例如，Zhou等人[8]將Levy飛行引入鯨魚優(yōu)化算法中以增加種群多樣性，從而提高算法跳出局部最優(yōu)解的能力；Kaur等人[9]將混沌理論引入鯨魚優(yōu)化算法的優(yōu)化過程中，以此提升算法的收斂速度；Sun等人[10]提出一種改進(jìn)的鯨魚優(yōu)化算法用于解決大規(guī)模優(yōu)化問題，該算法利用非線性收斂因子來協(xié)調(diào)算法的探索和開發(fā)能力，采用二次插值法對最優(yōu)解進(jìn)行變異并結(jié)合Levy飛行策略避免算法陷入局部最優(yōu)；涂春梅等人[11]提出一種混沌反饋自適應(yīng)鯨魚優(yōu)化算法，將混沌初始策略用于初始化種群，增加了反饋階段來提高算法的全局探索能力，同時引入自適應(yīng)慣性權(quán)重幫助算法跳出局部最優(yōu)，實驗證明該算法具有更好的收斂精度和穩(wěn)定性；褚鼎立等人[12]提出一種基于自適應(yīng)權(quán)重和模擬退火的鯨魚優(yōu)化算法，通過改進(jìn)的自適應(yīng)權(quán)重加快局部收斂速度，并結(jié)合模擬退火策略來提升算法全局尋優(yōu)能力，從而有效提高了算法的收斂精度和優(yōu)化性能.

上述改進(jìn)策略在一定程度上改善了WOA算法的性能，然而對于復(fù)雜或規(guī)模較大的函數(shù)優(yōu)化問題，算法的收斂速度和精度仍有提升的空間.因此，本文提出一種基于精英反向和縱橫交叉的鯨魚優(yōu)化算法(Elite Opposition-Based and Crisscross Optimization for Whale Optimization Algorithm，ECWOA).該算法首先通過精英反向?qū)W習(xí)策略初始化種群，提高初始解的質(zhì)量，為算法快速收斂奠定基礎(chǔ)；其次，引入非線性收斂因子平衡算法的全局探索能力和局部開發(fā)能力，從而改善算法的收斂速度和求解精度；最后，利用縱橫交叉策略對種群個體和全局最優(yōu)解進(jìn)行修正，在保持種群多樣性的同時，避免算法陷入局部最優(yōu).通過8個測試函數(shù)驗證ECWOA算法的性能，實驗結(jié)果表明該算法在函數(shù)優(yōu)化問題上表現(xiàn)優(yōu)異，具有較好的收斂精度和收斂速度，并能有效防止算法陷入局部最優(yōu).

2 鯨魚優(yōu)化算法

WOA算法通過模擬座頭鯨的捕食行為實現(xiàn)對復(fù)雜優(yōu)化問題的尋優(yōu)，將待求解問題的解空間類比于鯨魚種群，鯨魚個體代表待求解問題的可行解，最優(yōu)個體為最優(yōu)解，其他個體通過收縮包圍、發(fā)泡網(wǎng)攻擊和隨機搜索三種方式更新自身位置向最優(yōu)個體趨近，經(jīng)過多次迭代更新后求得最優(yōu)解.

2.1 收縮包圍

令鯨魚種群規(guī)模為N，鯨魚種群S={s1,s2,…,sN}，由于WOA算法初始化鯨魚種群是無先驗經(jīng)驗的，所以假設(shè)當(dāng)前最優(yōu)個體為目標(biāo)獵物，迭代過程中鯨魚種群中的其他個體均向獵物靠近，位置更新公式如下：

si(k+1)=sbest(k)-A|Csbest(k)-si(k)|

(1)

A=2ar1-a

(2)

C=2r2

(3)

式中，si(k)為第i個鯨魚個體的位置，k為當(dāng)前迭代次數(shù)；sbest(k)為當(dāng)前最優(yōu)鯨魚個體的位置；A和C為系數(shù)變量；r1和r2為區(qū)間[0,1]上的隨機數(shù)；a=2-2k/Kmax為收斂因子，Kmax為最大迭代次數(shù).

2.2 發(fā)泡網(wǎng)攻擊

發(fā)泡網(wǎng)攻擊是座頭鯨通過螺旋向上的方式逐步縮小包圍進(jìn)行捕食的過程.該過程中的收縮包圍和螺旋更新是一種同步行為，當(dāng)|A|<1時，個體以50%的概率作為閾值來確定更新方式是螺旋更新或收縮包圍，更新公式如下：

(4)

式中，b為對數(shù)螺旋形狀常數(shù)；l為區(qū)間[-1,1]上的隨機數(shù)；p為[0,1]上的隨機數(shù).

2.3 隨機搜索

鯨魚在捕獵過程中除了可以進(jìn)行發(fā)泡網(wǎng)攻擊之外，還可以通過隨機游動來搜尋獵物.當(dāng)|A|≥1時，鯨魚根據(jù)彼此的位置對獵物進(jìn)行隨機搜索，使算法具有一定的全局搜索能力，位置更新公式如下：

si(k+1)=srand(k)-A|Csrand(k)-si(k)|

(5)

式中，srand(k)為當(dāng)前群體中隨機選擇的鯨魚個體.

3 基于精英反向和縱橫交叉的鯨魚優(yōu)化算法

為了解決WOA算法收斂速度慢，易陷入局部最優(yōu)等問題，本文通過精英反向?qū)W習(xí)、非線性收斂因子和縱橫交叉三種策略對WOA算法進(jìn)行改進(jìn)，提出一種基于精英反向和縱橫交叉的鯨魚優(yōu)化算法(ECWOA)，下面詳細(xì)介紹三種改進(jìn)策略.

3.1 精英反向?qū)W習(xí)策略

(6)

(7)

式中，rand(lbj,ubj)為區(qū)間[lbj,ubj]上的隨機值.

精英反向?qū)W習(xí)策略初始化種群的基本步驟如下：

1)隨機初始化種群S,選前N/2個適應(yīng)度較優(yōu)的個體組成精英種群E.

2)求出精英種群E的反向種群OE.

3)合并種群S和OE得到新種群{S∪OE}，從中選擇N個適應(yīng)度較優(yōu)的個體組成初始種群.

3.2 非線性收斂因子

在標(biāo)準(zhǔn)WOA算法中，系數(shù)A是影響全局探索和局部開發(fā)能力平衡的關(guān)鍵因素，當(dāng)系數(shù)|A|≥1時，種群擴大搜索區(qū)域，以搜索到更好的候選解，即算法進(jìn)行全局探索；當(dāng)系數(shù)|A|<1時，種群將縮小搜索范圍，在局部區(qū)域進(jìn)行精細(xì)搜索，即算法進(jìn)行局部開發(fā).而從式(2)中可以看出，系數(shù)A的值是由線性遞減的收斂因子a決定的，無法準(zhǔn)確地反映復(fù)雜的非線性搜索過程.因此，本文引入逆不完全Γ函數(shù)來更新收斂因子a，其具體表達(dá)式為：

(8)

圖1 非線性收斂因子的遞減曲線Fig.1 Nonlinear convergence factor decline curve

圖1為amin=0，amax=2，λ=0.01時，非線性收斂因子a的遞減曲線.從可以看出，相比于線性遞減的收斂因子a，逆不完全Γ函數(shù)具有的優(yōu)良特性使得非線性收斂因子a在算法迭代初期接近線性下降，有利于算法進(jìn)行全局探索；而在算法迭代后期，a開始呈現(xiàn)指數(shù)形式下降，有利于算法進(jìn)行局部開發(fā).非線性收斂因子能夠更好的協(xié)調(diào)算法的全局探索和局部能力，進(jìn)一步提升算法的尋優(yōu)性能.

3.3 縱橫交叉策略

由于種群中的鯨魚個體在迭代過程中向最優(yōu)個體聚集，若存在一個局部最優(yōu)解，隨著迭代次數(shù)的增加，鯨魚個體聚集在局部最優(yōu)解周圍，易導(dǎo)致種群多樣性下降.為了避免算法陷入局部最優(yōu)，防止“早熟”現(xiàn)象的發(fā)生，本文引入縱橫交叉策略[14]對種群個體和全局最優(yōu)解進(jìn)行修正，利用橫向交叉對種群進(jìn)行交叉搜索以減少搜索盲點，通過縱向交叉對最優(yōu)解進(jìn)行交叉運算，在增加種群多樣性的同時能夠降低算法陷入局部最優(yōu)的概率.縱橫交叉策略產(chǎn)生的候選解與其父代進(jìn)行競爭獲得的占優(yōu)解會呈鏈?zhǔn)椒磻?yīng)迅速傳播至整個種群，從而提升算法求解精度并加快收斂速度.

3.3.1 橫向交叉

(9)

(10)

3.3.2 縱向交叉

WOA算法在迭代后期易陷入局部最優(yōu)，往往是由于種群更新過程中某些個體的某一維陷入局部最優(yōu)而造成的.縱向交叉能夠以概率Pv對全局最優(yōu)解Fbest的兩個不同維的進(jìn)行交叉運算，使同一個體不同維之間相互學(xué)習(xí)，有利于陷入局部最優(yōu)的維度跳出局部最優(yōu).并且縱向交叉每次只對其中一維進(jìn)行更新既能夠使陷入局部最優(yōu)的維度跳出局部最優(yōu)，而又盡可能不破壞另一正常維度包含的信息.假設(shè)對Fbest的第d1維和第d2維進(jìn)行縱向交叉，通過下式產(chǎn)生子代個體：

(11)

3.4 ECWOA算法

結(jié)合標(biāo)準(zhǔn)鯨魚優(yōu)化算法以及上述改進(jìn)策略，本文提出的ECWOA算法的偽代碼如下：

1.設(shè)置種群規(guī)模N，維度D,最大迭代次數(shù)Kmax，橫向交叉概率Ph，縱向交叉概率Pv等，令當(dāng)前迭代次數(shù)k=1

2.利用精英反向?qū)W習(xí)策略初始化種群{si,i=1,2,…,N}

3.計算種群個體適應(yīng)度{f(si),i=1,2,…,N}，記錄當(dāng)前最優(yōu)個體sbest

4.While(k

5.Fort=1toN

6. 根據(jù)式(8)、式(2)和式(3)分別更新收斂因子a、參數(shù)

A和C，更新概率p∈[0,1]和隨機數(shù)l∈[-1,1]

7.If(p<0.5)

8.If(|A|<1)

9. 進(jìn)行收縮包圍，根據(jù)式(1)更新個體位置；

10.elseif(|A|≥1)

11. 進(jìn)行隨機搜索，根據(jù)式(5)更新個體位置；

12.Endif

13.elseif(p≥0.5)

14. 進(jìn)行螺旋更新，根據(jù)式(4)更新個體位置；

15.Endif

16.Endfor

//橫向交叉

17. rand1=randperm(N)//產(chǎn)生1到N的隨機整數(shù)序列

18.Fori=1toN/2

19. 生成隨機數(shù)p1∈[0,1]

20.If(p1

21.Ford=1toD

24.Endfor

27.Endif

28.Endfor

//縱向交叉

29. 計算種群適應(yīng)度，更新sbest并對sbest進(jìn)行歸一化處理

30. rand2=randperm(D)//產(chǎn)生1到D的隨機整數(shù)序列

31.For j=1 to D/2

32. 生成隨機數(shù)p2∈[0,1]

33.If (p2

(2j)

35.Endif

36.Endfor

39.k=k+1

40.Endwhile

41.輸出最優(yōu)個體sbest及其適應(yīng)度f(sbest).

3.5 改進(jìn)算法時間復(fù)雜度分析

ECWOA算法主要由精英反向?qū)W習(xí)、非線性收斂因子、鯨魚位置更新以及縱橫交叉策略組成.當(dāng)種群規(guī)模為N，搜索空間維度為D，最大迭代次數(shù)為Kmax時，本文算法時間復(fù)雜度分析如下：精英反向?qū)W習(xí)初始化種群的時間復(fù)雜度為O(ND)；迭代過程中，非線性收斂因子是在原收斂因子的基礎(chǔ)上進(jìn)行改進(jìn)，并沒有增加額外的時間復(fù)雜度，時間復(fù)雜度仍為O(KmaxN)；鯨魚個體位置更新的時間復(fù)雜度為O(KmaxND)；縱橫交叉策略的時間復(fù)雜度為O(KmaxND/2+KmaxD/2)=O(KmaxND)，其它各步計算規(guī)模較小，略去不計.因此，ECWOA算法的整體時間復(fù)雜度為O(KmaxND)，與標(biāo)準(zhǔn)鯨魚優(yōu)化算法的時間復(fù)雜度保持一致.

4 實 驗

4.1 實驗設(shè)置

為了驗證ECWOA算法的優(yōu)化性能，本文在8個測試函數(shù)上進(jìn)行仿真實驗，并與粒子群算法[1](Particle Swarm Optimization，PSO)、灰狼優(yōu)化算法[5](Grey Wolf Optimization Algorithm，GWO)、基本鯨魚優(yōu)化算法(WOA)、基于精英反向的花授粉算法[13](Elite Opposition-based Flower Pollination Algorithm，EOFPA)、縱橫交叉算法[14](Crisscross Optimization Algorithm，CSO)以及改進(jìn)的鯨魚優(yōu)化算法[15](Modified Whale Optimization Algorithm，MWOA)進(jìn)行比較.采用最優(yōu)值Best、最差值Worst、均值Mean和標(biāo)準(zhǔn)差Std作為評價指標(biāo)，其中最優(yōu)值和最差值反映解的質(zhì)量，均值反映算法所能達(dá)到的精度，標(biāo)準(zhǔn)差反映算法的魯棒性和穩(wěn)定性.本文仿真實驗基于Windows 7操作系統(tǒng)，3.2GHz主頻及4GB內(nèi)存，編程采用MATLAB R2014a軟件.

表1 測試函數(shù)Table 1 Test functions

4.2 參數(shù)設(shè)置及測試函數(shù)

在進(jìn)行仿真實驗時，為了使實驗結(jié)果更加公正和客觀，將所有算法的規(guī)模均設(shè)置為30，最大迭代次數(shù)設(shè)置為300.PSO、GWO、CSO、EOFPA和MWOA算法的其余參數(shù)設(shè)置同其相應(yīng)的參考文獻(xiàn)一致.ECWOA算法的參數(shù)如下：收斂因子a最小值amin=0，最大值amax=2，隨機變量λ=0.01，橫向交叉概率Ph=1，縱向交叉概率Pv=0.6，對數(shù)螺旋形狀常數(shù)b=1；標(biāo)準(zhǔn)WOA算法參數(shù)設(shè)置與ECWOA算法相同.

本文選取8個具有不同特點的測試函數(shù)進(jìn)行仿真實驗，其名稱及特性見表1，其中f1～f3為單峰函數(shù)，f4～f6為不定維多峰函數(shù)，f7和f8為固定維多峰函數(shù).

4.3 維度變化分析

為了驗證ECWOA算法在不同維度下的性能，設(shè)置函數(shù)f1～f6維度分別為30、50和100，將ECWOA與WOA算法在6個測試函數(shù)上獨立運行50次，仿真結(jié)果如表2所示.從中可以看出，ECWOA在不同維度下的收斂精度均優(yōu)于WOA.尤其是對于多峰函數(shù)f4和f5，無論低維還是高維，ECWOA均可以收斂到其理論最優(yōu)值0，而WOA的收斂精度隨著維度增加有所下降.另外，ECWOA在各個函數(shù)上的標(biāo)準(zhǔn)差非常小，對于多峰函數(shù)f4、f5和f6，在不同維度下所求得的標(biāo)準(zhǔn)差均為0，說明ECWOA具有較強的魯棒性和穩(wěn)定性.由此可知，隨著函數(shù)維度的增加，待求解函數(shù)的復(fù)雜程度也隨之增加，從而導(dǎo)致ECWOA的尋優(yōu)精度和穩(wěn)定性有所下降，但ECOWA的尋優(yōu)性能還是優(yōu)于標(biāo)準(zhǔn)WOA.

表2 WOA、ECWOA算法在不同維度下的實驗結(jié)果Table 2 Experimental results of WOA and ECWOA algorithm in different dimensions

4.4 算法對比分析

表3為PSO、GWO、WOA、CSO、EOFPA、MWOA和ECWOA算法在8個測試函數(shù)(其中f1～f6的維度D=30)上獨立運行50次得到的實驗結(jié)果.從表3中可以看出，對于單峰函數(shù)f1～f3，ECWOA尋優(yōu)的均值和標(biāo)準(zhǔn)差與其他算法相比高出多個數(shù)量級，說明ECWOA的求解精度和穩(wěn)定性相對較好.特別是對于極難求得最優(yōu)解的函數(shù)f2，ECWOA不僅可以收斂到其理論最優(yōu)值，而且在各項指標(biāo)上的表現(xiàn)均優(yōu)于其他算法.針對多峰函數(shù)f4和f5，CSO、EOFPA、MWOA以及ECWOA均可以搜索到函數(shù)的理論最優(yōu)值且尋優(yōu)的標(biāo)準(zhǔn)差均為0，PSO尋優(yōu)效果最差.對于多峰函數(shù)f6，該函數(shù)全局最優(yōu)點周圍存在無數(shù)次優(yōu)點為算法的尋優(yōu)過程增加了難度，雖然所有算法均無法搜索到其理論最優(yōu)值，但ECWOA和EOFPA尋優(yōu)的均值、方差和最優(yōu)值優(yōu)于其他算法.函數(shù)f7為固定維度為2的多峰函數(shù)，ECWOA和EOFPA尋優(yōu)得到的均值相同，但在標(biāo)準(zhǔn)差指標(biāo)上，ECWOA獲得最優(yōu)值，說明ECWOA具有更好的穩(wěn)定性.對于固定維度為6的多峰函數(shù)f8，ECWOA可以收斂到其理論最優(yōu)值，且尋優(yōu)的最差值、均值和標(biāo)準(zhǔn)差均優(yōu)于其他算法.

表3 算法對比Table 3 Comparison of algorithms

圖2 函數(shù)收斂曲線Fig.2 Function convergence curve

圖2為不同算法在測試函數(shù)上的收斂曲線，從圖2中可以看出，對于單峰函數(shù)f1和f3，CSO、EOFPA以及MWOA雖未陷入局部最優(yōu)，但因收斂速度過于緩慢使得算法無法獲得更好的求解精度，而ECWOA通過非線性收斂因子加快了算法的收斂速度，從而有效提高了算法的求解精度.求解函數(shù)f2和f8時，其他算法均過早的收斂到局部最優(yōu)解，而ECWOA通過非線性收斂因子合理控制收斂速度以及縱橫交叉策略提高了算法跳出局部最優(yōu)解的能力，最終收斂到理論最優(yōu)值.對于多峰函數(shù)f4和f5，CSO、EOFPA、MWOA和ECWOA均能夠收斂到其理論最優(yōu)值，但ECWOA迭代不到75次就能夠收斂到理論最優(yōu)值，收斂速度明顯優(yōu)于其他算法.在函數(shù)f6和f7的優(yōu)化過程中，所有算法在迭代后期均陷入局部最優(yōu)，但在迭代結(jié)束時，ECWOA和EOFPA獲得了更好的求解精度.

綜上所述，ECWOA算法在單峰、多峰函數(shù)上的尋優(yōu)性能均優(yōu)于PSO、GWO、WOA、CSO、EOFPA和MWOA算法.這主要得益于高質(zhì)量的初始種群、非線性動態(tài)變化的收斂因子以及縱橫交叉策略，通過這些改進(jìn)策略ECWOA算法能有效平衡全局探索和局部開發(fā)能力，避免算法陷入局部最優(yōu)，使得算法在收斂速度、求解精度和穩(wěn)定性方面均表現(xiàn)出較好的性能.

5 結(jié)束語

為進(jìn)一步提高鯨魚優(yōu)化算法的尋優(yōu)能力，本文提出了一種基于精英反向?qū)W習(xí)和縱橫交叉的鯨魚優(yōu)化算法，該算法利用精英反向?qū)W習(xí)生成初始種群以維持初始群體的多樣性；設(shè)計了一種基于逆不完全Γ函數(shù)的收斂因子使其隨迭代次數(shù)增加非線性動態(tài)變化，以平衡算法的全局探索和開局部發(fā)能力；引入縱橫交叉策略使個體信息在種群中呈鏈?zhǔn)椒磻?yīng)迅速傳播交流，從而避免算法陷入局部最優(yōu).通過對8個測試函數(shù)進(jìn)行仿真實驗表明，與PSO、GWO、WOA、CSO、EOFPA和MWOA算法相比，ECWOA算法具有更好的收斂速度、求解精度和穩(wěn)定性.后續(xù)工作將從理論上對ECWOA算法的收斂性進(jìn)行分析，并考慮將該算法應(yīng)用于實際的優(yōu)化問題中.