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

劉 琨，趙露露，王 輝

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

1 引 言

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

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

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

2 鯨魚優化算法

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

2.1 收縮包圍

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

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

(1)

A=2ar1-a

(2)

C=2r2

(3)

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

2.2 發泡網攻擊

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

(4)

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

2.3 隨機搜索

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

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

(5)

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

3 基于精英反向和縱橫交叉的鯨魚優化算法

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

3.1 精英反向學習策略

(6)

(7)

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

精英反向學習策略初始化種群的基本步驟如下：

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

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

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

3.2 非線性收斂因子

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

(8)

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

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

3.3 縱橫交叉策略

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

3.3.1 橫向交叉

(9)

(10)

3.3.2 縱向交叉

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

(11)

3.4 ECWOA算法

結合標準鯨魚優化算法以及上述改進策略，本文提出的ECWOA算法的偽代碼如下：

1.設置種群規模N，維度D,最大迭代次數Kmax，橫向交叉概率Ph，縱向交叉概率Pv等，令當前迭代次數k=1

2.利用精英反向學習策略初始化種群{si,i=1,2,…,N}

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

4.While(k

5.Fort=1toN

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

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

7.If(p<0.5)

8.If(|A|<1)

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

10.elseif(|A|≥1)

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

12.Endif

13.elseif(p≥0.5)

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

15.Endif

16.Endfor

//橫向交叉

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

18.Fori=1toN/2

19. 生成隨機數p1∈[0,1]

20.If(p1

21.Ford=1toD

24.Endfor

27.Endif

28.Endfor

//縱向交叉

29. 計算種群適應度，更新sbest并對sbest進行歸一化處理

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

31.For j=1 to D/2

32. 生成隨機數p2∈[0,1]

33.If (p2

(2j)

35.Endif

36.Endfor

39.k=k+1

40.Endwhile

41.輸出最優個體sbest及其適應度f(sbest).

3.5 改進算法時間復雜度分析

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

4 實 驗

4.1 實驗設置

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

表1 測試函數Table 1 Test functions

4.2 參數設置及測試函數

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

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

4.3 維度變化分析

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

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

4.4 算法對比分析

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

表3 算法對比Table 3 Comparison of algorithms

圖2 函數收斂曲線Fig.2 Function convergence curve

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

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

5 結束語

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