一種基于交叉選擇的柯西反向鯨魚優(yōu)化算法

馮文濤,鄧 兵

(盲信號處理國家級重點(diǎn)實(shí)驗(yàn)室， 成都 610041)

在現(xiàn)代社會中最優(yōu)化的需求普遍存在，如資源調(diào)度、導(dǎo)航規(guī)劃、任務(wù)分配以及結(jié)構(gòu)優(yōu)化等等。傳統(tǒng)的優(yōu)化算法如最速下降法、共軛梯度法、最小二乘法等[1]，對于優(yōu)化問題的求解通常是利用梯度信息進(jìn)行迭代計(jì)算，需要正確選取初始值且要求目標(biāo)函數(shù)連續(xù)可導(dǎo)，對于解決大規(guī)模、不連續(xù)、非線性等復(fù)雜性較高的問題往往顯得力不從心。針對傳統(tǒng)優(yōu)化算法存在的缺陷，基于概率搜索的隨機(jī)優(yōu)化算法成為了幾十年來新的研究熱點(diǎn)。隨機(jī)優(yōu)化算法中的模擬退火算法、遺傳算法、禁忌搜索算法等[2]算法在解決NP完全或者NP難問題上顯示出了良好的性能。模仿自然界生物群體行為的群體智能算法屬于隨機(jī)優(yōu)化算法的一個(gè)分支，也受到了人們廣泛的關(guān)注與研究，比如人工蜂群算法[3]模仿的是自然界中蜜蜂群的采蜜行為、蟻群算法[4]模仿的是自然界中蟻群的集體覓食行為。模仿大海中鯨群捕食行為的鯨魚優(yōu)化算法(Whale Optimization Algorithm，WOA)[5]在2016年提出，具有原理新穎、結(jié)構(gòu)簡單等優(yōu)點(diǎn)，已成功的應(yīng)用于瞬時(shí)混疊信號的盲源分離[6]、水資源的優(yōu)化配置問題[7]等，WOA算法及其改進(jìn)算法的性能也優(yōu)于傳統(tǒng)的群體智能算法[8-9]。同其他的群體智能算法一樣，WOA算法有時(shí)也存在求解精度不高、易陷于局部最優(yōu)的缺點(diǎn)，而且算法后期的開發(fā)能力較弱。

差分進(jìn)化算法(Differential Evolution,DE)[10]是一種應(yīng)用非常廣泛的智能優(yōu)化算法，其具有流程簡單、容易實(shí)現(xiàn)等諸多優(yōu)點(diǎn)，自提出以來獲得了廣泛的研究與應(yīng)用。吳擎等[11]提出了一種基于混合交叉的差分進(jìn)化算法，李袁等[12]提出了一種基于差分進(jìn)化模型的多等級子群雜草優(yōu)化算法，均取得了較好的效果。反向?qū)W習(xí)的概念由Tizhoosh在2005年提出[13]，并在其后成功的應(yīng)用于機(jī)器學(xué)習(xí)、進(jìn)化計(jì)算等諸多領(lǐng)域。Rahnamayan等[14-15]證明了基于反向?qū)W習(xí)的差分進(jìn)化算法比普通差分進(jìn)化算法有更快的收斂速度和更高的收斂精度，而且柯西反向點(diǎn)比普通反向點(diǎn)的尋優(yōu)概率更高。

針對WOA算法存在的缺點(diǎn)，本文首先采用柯西反向?qū)W習(xí)生成算法的初始種群，然后利用WOA算法生成當(dāng)前種群的變異向量，并對變異向量進(jìn)行交叉和選擇操作以生成新的子代個(gè)體，在更新完種群所有個(gè)體后再利用柯西反向跳轉(zhuǎn)技術(shù)生成新的反向種群，最后選擇當(dāng)前種群和反向種群中較優(yōu)的一半個(gè)體進(jìn)入下一次迭代。試驗(yàn)結(jié)果證明，所提改進(jìn)算法能顯著提高WOA算法的性能。

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

WOA算法模仿的是海洋中鯨魚群的群體合作捕食行為，算法中的種群更新機(jī)制主要包含搜索覓食、收縮包圍和螺旋更新位置3種，其選擇方式由隨機(jī)概率因子p和系數(shù)|A|的值共同決定。如圖1所示。

圖1 WOA算法的種群更新機(jī)制框圖

隨機(jī)概率因子p是在[0,1]之間生成的隨機(jī)數(shù)，系數(shù)A的定義為：

A=2a·r-a

(1)

式(1)中：r為[0,1]之間的隨機(jī)向量；a被稱為控制參數(shù)。a定義為：

(2)

式(2)中：t為當(dāng)前迭代次數(shù)；Max_iter為最大迭代次數(shù)。可以看出隨迭代次數(shù)t的增加a從2線性減小到0，因此系數(shù)|A|的值也隨之從2減小到0。

搜索覓食階段是鯨魚隨機(jī)尋找食物的過程，當(dāng)前鯨魚個(gè)體隨機(jī)選取另一鯨魚個(gè)體作為目標(biāo)并向其位置靠攏，對應(yīng)著算法的全局開發(fā)階段，其數(shù)學(xué)模型可表示為：

D=|C·Xrand(t)-X(t)|

(3)

X(t+1)=Xrand(t)-A·|C·Xrand(t)-X(t)|

(4)

式(3) ～(4)中：Xrand(t)是從當(dāng)前鯨魚群體中隨機(jī)選取的鯨魚個(gè)體；X(t)是當(dāng)前的鯨魚個(gè)體位置；系數(shù)A由式(1)決定；C是隨機(jī)分布于[0,2]之間的系數(shù)向量。

鯨魚群在捕食獵物時(shí)采用了泡泡網(wǎng)的攻擊方法，包含了收縮包圍和螺旋更新位置兩種機(jī)制，對應(yīng)著WOA算法的局部開采階段。在鯨魚優(yōu)化算法中，當(dāng)前獲得最優(yōu)解的種群個(gè)體被認(rèn)為是目標(biāo)獵物，其他所有個(gè)體均向其進(jìn)行靠攏。

收縮包圍階段的數(shù)學(xué)模型如下：

D=|C·Xbest(t)-X(t)|

(5)

X(t+1)=Xbest(t)-A·|C·Xbest(t)-X(t)|

(6)

式(5)～(6)中：Xbest(t)是當(dāng)前鯨魚群體中位置最佳的鯨魚個(gè)體；A·|C·Xbest(t)-X(t)|為包圍步長；|A|越小時(shí)鯨魚游走的步長越小。

在螺旋更新位置階段，其他鯨魚個(gè)體在接近最佳鯨魚個(gè)體的同時(shí)，會以螺旋方式進(jìn)行游走覓食，搜索其至最佳個(gè)體之間可能存在的最優(yōu)解。螺旋更新的初始點(diǎn)為當(dāng)前鯨魚個(gè)體的位置，目標(biāo)終點(diǎn)是當(dāng)前最佳鯨魚個(gè)體的位置。其數(shù)學(xué)模型可表示為：

D′=|Xbest(t)-X(t)|

(7)

X(t+1)=D′·ebl·cos(2πl(wèi))+Xbest(t)

(8)

式(7)～(8)中：D′表示當(dāng)前鯨魚個(gè)體與最佳位置鯨魚之間的距離；b是常量系數(shù)；l是[-1,1]之間的隨機(jī)數(shù)。

2 差分進(jìn)化算法

DE算法主要包含變異、交叉和選擇3個(gè)過程，其控制參數(shù)有種群規(guī)模大小、差分變異參數(shù)F和交叉概率CR三個(gè)。DE算法首先通過差分變異參數(shù)F控制生成新一代變異向量，然后將變異向量與目標(biāo)向量之間進(jìn)行交叉操作并生成新的試驗(yàn)向量，最后對試驗(yàn)向量和目標(biāo)向量進(jìn)行貪婪選擇，適應(yīng)度更好的個(gè)體被選擇進(jìn)入下一代迭代過程。

DE算法中的變異操作一般定義如下：

(9)

式(9)中：Xr1(t)、Xr2(t)和Xr3(t)是從當(dāng)前種群中任意選出的3個(gè)不重復(fù)的個(gè)體向量；變異尺度因子F∈[0,1]。式(9)也被稱為DE/rand/1策略，其他變異策略還有DE/rand/2、DE/best/1、DE/best/2等。

在變異操作生成變異向量后，即將變異向量與原目標(biāo)向量進(jìn)行交叉操作生成試驗(yàn)向量，常見的交叉方式有二項(xiàng)式交叉和指數(shù)交叉兩種。其中二項(xiàng)式交叉的應(yīng)用較為普遍，其定義如下：

(10)

式(10)中：randi, j[0,1]是定義在[0,1]之間的隨機(jī)數(shù)；交叉概率CR∈[0,1]。

試驗(yàn)向量生成后，比較其與目標(biāo)向量的適應(yīng)度值，適應(yīng)度值較優(yōu)的個(gè)體被選擇進(jìn)入下一代。選擇操作的數(shù)學(xué)模型定義如下：

(11)

式(11)中，f(*)表示適應(yīng)度函數(shù)。

選擇過程也可分為同步選擇和非同步選擇兩種，其中非同步選擇的方式比同步選擇的方式性能更優(yōu)。在非同步選擇方式中，每一個(gè)新生成的試驗(yàn)向量在與目標(biāo)向量進(jìn)行比較后，較優(yōu)的試驗(yàn)向量立刻替換種群中對應(yīng)的目標(biāo)向量并參與剩余種群個(gè)體的更新操作，因此算法的收斂速度更快。

3 改進(jìn)鯨魚優(yōu)化算法

根據(jù)第1節(jié)對鯨魚優(yōu)化算法的描述可知，WOA算法將探索過程和開發(fā)過程分離開來，且其局部開采能力顯著強(qiáng)于全局開發(fā)能力，導(dǎo)致算法在迭代后期的全局探索能力不足，易于陷入局部最優(yōu)。針對WOA算法的上述特點(diǎn)，本文采用了柯西反向?qū)W習(xí)技術(shù)和DE算法的交叉與選擇策略以提高WOA算法求解的速度與精度。

3.1 柯西反向?qū)W習(xí)

k維空間中一個(gè)點(diǎn)的反向點(diǎn)定義如下：

定義1假定P=x(x1,x2,…,xk)是k維空間中的一個(gè)點(diǎn)，其中xi∈[ai,bi],i=1,2,…,k，ai和bi為P點(diǎn)在第i維的最小值和最大值。則P點(diǎn)的反向點(diǎn)為：

(12)

在一般反向點(diǎn)概念的基礎(chǔ)上，很多新穎的反向?qū)W習(xí)概念也隨之產(chǎn)生。柯西反向點(diǎn)定義如下：

定義2假定P=x(x1,x2,…,xk)是k維空間中的一個(gè)點(diǎn)，其中xi∈[ai,bi],i=1,2,…,k，ai和bi為P點(diǎn)在第i維的最小值和最大值。則P點(diǎn)的柯西反向點(diǎn)為：

(13)

與普通反向點(diǎn)相比，柯西反向點(diǎn)是在中點(diǎn)和普通反向點(diǎn)之間隨機(jī)產(chǎn)生的一個(gè)點(diǎn)。

本文除了利用柯西反向?qū)W習(xí)生成初始種群外，在迭代過程中還采用了柯西反向跳轉(zhuǎn)的方式生成當(dāng)前種群的反向種群，從而加快算法的收斂速度。柯西反向跳轉(zhuǎn)的定義如下:

定義3假如rand[0,1]≤Jr條件滿足，則為當(dāng)前種群生成對應(yīng)的柯西反向種群，其中Jr為跳轉(zhuǎn)率。

3.2 引入交叉與選擇策略的鯨魚優(yōu)化算法

在DE算法中，交叉是影響算法性能的關(guān)鍵步驟之一。本文將DE算法的二項(xiàng)式交叉與非同步選擇過程引入到WOA算法中，提高了WOA算法的種群多樣性和求解精度。

引入交叉和選擇策略后的柯西反向鯨魚優(yōu)化算法(quasi-oppositional whale optimization algorithm based on crossover and selection strategy，QOWOA-CS)的偽代碼如算法1所示。

算法1 QOWOA-CS算法偽代碼

1: 設(shè)置算法初始參數(shù)

2: 生成初始種群P0

3: 生成初始種群P0的柯西反向種群OP0

4: 選擇{P0,OP0}中適應(yīng)度較優(yōu)的一半個(gè)體作為初始種群

5: 選擇{P0,OP0}中適應(yīng)度值最小的個(gè)體作為當(dāng)前最優(yōu)解

6:while(t

7:for(i=0;i

8: 更新a,A,C

9:if1 (p<0.5)

10:if2 (|A|≥1)

11: 按照公式(4)生成變異向量Vi(t)

12:elseif2 (|A|<1)

13: 按照公式(6)生成變異向量Vi(t)

14:endif2

15:elseif1 (p≥0.5)

16: 按照公式(8)生成變異向量Vi(t)

17:endif1

18: 檢查變異向量Vi(t)的有效性

19: 按照公式(10)生成試驗(yàn)向量Ui(t)

20:if3f(Ui(t))

21: 選擇用Ui(t)替換Xi(t)

22:endif3

23:endfor

24:if4 rand[0,1]≤Jr

25: 生成當(dāng)前種群P的反向種群OP

26:endif4

27: 選擇{P,OP}中適應(yīng)度較優(yōu)的一半個(gè)體進(jìn)入下一次迭代循環(huán)

28: 選擇{P,OP}中適應(yīng)度值最小的個(gè)體作為當(dāng)前最優(yōu)解

29:t=t+1

30:endwhile

31: 算法結(jié)束，返回當(dāng)前所獲得的最優(yōu)解

4 數(shù)值試驗(yàn)及分析

為了驗(yàn)證本文所提QOWOA-CS算法的有效性，采用文獻(xiàn)[5]中表2及表3所示的f1(x)～f13(x)共13組可變維度的標(biāo)準(zhǔn)測試函數(shù)來對算法進(jìn)行仿真測試，其中f1(x)～f7(x)為高維的單峰函數(shù)，f8(x)～f13(x)為高維的多峰函數(shù)，所有測試函數(shù)的維度均為30維。標(biāo)準(zhǔn)函數(shù)f8(x)的理論最小值為-418.982 9×30，其余標(biāo)準(zhǔn)函數(shù)的理論最小值均為0。WOA算法的種群大小設(shè)置為30，迭代次數(shù)為500，算法的獨(dú)立運(yùn)行次數(shù)為30。算法所在的實(shí)驗(yàn)平臺參數(shù)為Windows 7操作系統(tǒng)、CPU主頻2.4 GHz、內(nèi)存8 GB，實(shí)現(xiàn)程序?yàn)镸latlab 2015b。

本節(jié)將對柯西反向鯨魚優(yōu)化算法(quasi-oppositional whale optimization algorithm,QOWOA)、引入交叉和選擇策略的鯨魚優(yōu)化算法(whale optimization algorithm based on crossover and selection strategy,WOA-CS)、引入交叉和選擇策略的柯西反向鯨魚優(yōu)化算法(QOWOA-CS)三種算法與WOA算法分別進(jìn)行比較，分析柯西反向?qū)W習(xí)方法和交叉選擇策略對WOA算法的影響。

從算法1的描述可以看出，柯西反向跳轉(zhuǎn)步驟生成了當(dāng)前種群的柯西反向種群，增加了算法的計(jì)算復(fù)雜度。為了保證算法間比較的公平性，對QOWOA和QOWOA-CS算法的參數(shù)設(shè)置如下：柯西反向跳轉(zhuǎn)概率Jr=1，交叉概率CR=0.95，迭代次數(shù)為250次；WOA-CS算法的CR=0.95，迭代次數(shù)為500次，其余參數(shù)設(shè)置與WOA算法相同。

4.1 柯西反向?qū)W習(xí)對算法的影響

對QOWOA和WOA算法進(jìn)行仿真所得的結(jié)果如表1所示，平均值較優(yōu)的值以粗體顯示。從表1的結(jié)果可以看出，與WOA算法相比，QOWOA算法在f1～f4、f9和f11函數(shù)上的尋優(yōu)能力明顯提升，在函數(shù)f7和f10上的收斂精度則略有改善，其他標(biāo)準(zhǔn)函數(shù)上WOA算法較優(yōu)。圖2示出了函數(shù)f7和f13的典型收斂曲線，可以看出柯西反向?qū)W習(xí)有助于算法在早期的迅速收斂，但是總體而言在算法的迭代后期柯西反向?qū)W習(xí)對收斂速度及精度的影響較小。

4.2 交叉和選擇策略對算法的影響

對WOA-CS和WOA算法進(jìn)行仿真所得結(jié)果如表2所示，平均值較優(yōu)的值以粗體顯示。

從表2的結(jié)果可以看出，與WOA算法相比，WOA-CS算法在f1～f7和f10～f13共11個(gè)標(biāo)準(zhǔn)函數(shù)上的收斂能力更強(qiáng)，僅在f8和f9函數(shù)上處于劣勢，表明引入的交叉和選擇策略能有效提升WOA算法的求解精度。圖3示出了兩種算法在函數(shù)f6和f12上的收斂曲線。

從圖3可以看出，WOA算法在后半段迭代過程中已經(jīng)陷入局部最優(yōu)，但是WOA-CS算法能持續(xù)尋求精度更高的最優(yōu)解。這也表明交叉和選擇策略有效保持了WOA-CS算法種群的多樣性，有助于算法及時(shí)跳出局部極值，提高了算法的收斂精度。

圖2 函數(shù)f7(左)和函數(shù)f13(右)的收斂曲線

圖3 函數(shù)f6(左)和函數(shù)f12(右)的收斂曲線

表1 QOWOA算法和WOA算法的計(jì)算結(jié)果比較

表2 WOA-CS算法和WOA算法的計(jì)算結(jié)果比較

表3 QOWOA-CS算法和WOA算法的計(jì)算結(jié)果比較

4.3 基于交叉選擇的柯西反向鯨魚優(yōu)化算法

對QOWOA-CS和WOA算法進(jìn)行仿真所得的結(jié)果如表3所示，平均值較優(yōu)的值以粗體顯示。圖4至圖10示出了兩種算法在13個(gè)標(biāo)準(zhǔn)測試函數(shù)上的收斂曲線。從表3、圖4至圖10的結(jié)果可以看出，QOWOA-CS算法在最優(yōu)值、平均值等指標(biāo)上均明顯優(yōu)于WOA算法，而且在f9和f11上均能收斂到理論最優(yōu)值0，WOA算法只在f8上勝出。QOWOA-CS算法在收斂速度和收斂精度上均明顯優(yōu)于WOA算法，表明了本文針對WOA算法所提的改進(jìn)策略切實(shí)有效。

圖4 函數(shù)f1(左)和函數(shù)f2(右)的收斂曲線

圖5 函數(shù)f3(左)和函數(shù)f4(右)的收斂曲線

圖6 函數(shù)f5(左)和函數(shù)f6(右)的收斂曲線

圖7 函數(shù)f7(左)和函數(shù)f8(右)的收斂曲線

圖8 函數(shù)f9(左)和函數(shù)f10(右)的收斂曲線

圖9 函數(shù)f11(左)和函數(shù)f12(右)的收斂曲線

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

5 結(jié)論

提出了一種基于交叉選擇策略的柯西反向鯨魚優(yōu)化算法QOWOA-CS。該算法使用柯西反向?qū)W習(xí)生成初始種群以及算法進(jìn)化時(shí)當(dāng)前種群的反向種群，并將DE算法的交叉和選擇策略引入WOA算法以提高種群進(jìn)化時(shí)的多樣性。實(shí)驗(yàn)結(jié)果表明，所提的QOWOA-CS算法在收斂速度和收斂精度上相比WOA算法有較大提升。

本文提出的QOWOA-CS算法能夠在海量的傳感器集合中快速、準(zhǔn)確的給出最優(yōu)的解決方案，具有非常廣闊的應(yīng)用前景。