基于文化鯨魚優(yōu)化算法的特征權重優(yōu)化分配方法

嚴愛軍,曹付起

(1.北京工業(yè)大學信息學部，北京 100124；2.數字社區(qū)教育部工程研究中心，北京 100124；3.城市軌道交通北京實驗室，北京 100124)

權重指的是某一因素或指標相對于某一事物的重要程度，反映該因素或指標的相對重要性.權重的分配廣泛應用于社會的各種系統(tǒng)中，無論是在多目標多因素系統(tǒng)的綜合評價[1]和決策領域[2]，還是在經濟、社會、環(huán)境、科技等系統(tǒng)的軟科學研究領域[3]，以及不確定性環(huán)境下的參數預測領域[4]，都涉及權重分配的問題.研究證明，權重的合理分配與否會對預測和決策結果產生較大的影響，因此，國內外學者對特征權重的分配方法展開了大量的研究.

綜合國內外的研究，特征權重的分配方法主要分為3類：主觀賦權法、客觀賦權法和組合賦權法.主觀賦權法主要是根據專家的知識經驗或偏好，根據重要性程度對各特征的權重進行比較、分配或計算，主要方法有層次分析法[5]、專家估評法[6]和環(huán)比評分法[7]，但主觀賦權法的主觀性和不確定性很強，專家對于權重的分配是根據實際經驗和對預測對象的熟悉程度來制定的，不同的專家得到的結果并不完全一樣，因此，主觀賦權法的一致性和可信性難以得到保障.客觀賦權法則是根據一定的數學理論和計算方法從特征數據出發(fā)對特征權重進行分配.主要方法有灰色關聯(lián)度分析法[8]、神經網絡法[9]、遺傳算法[10]等.灰色關聯(lián)度分析法通過將數據對比與幾何圖形發(fā)展態(tài)勢相結合來求權重，該方法具有計算過程簡單、無需大量樣本等優(yōu)點，但無法解決特征間相關性導致的冗余問題；神經網絡法通過訓練樣本得到特征權重優(yōu)化分配的計算模型，但其結構設計較為困難，對訓練樣本的要求也比較嚴格；遺傳算法是一種通過模擬自然進化過程搜索最優(yōu)個體的方法，通過對權重進行迭代尋優(yōu)得到最優(yōu)權重，具有運行簡單、魯棒性強等優(yōu)點，但收斂速度慢、局部搜索能力差.組合賦權法[11]將上述的主觀賦權法和客觀賦權法結合起來，依據不同的偏好系數確定特征權重，這種方法可能存在較大的隨機性偏差，計算復雜度普遍比較高.可見，上述3類賦權法在特征權重的優(yōu)化分配中得到了廣泛應用，但仍具有一些缺陷以及局限性，因此，研究一種新的權重分配方法十分必要.

元啟發(fā)式算法由于其具有簡單性、靈活性、魯棒性以及高性能性被運用到各學科或工程問題中.作為元啟發(fā)式算法的一個熱點研究方向，群體智能優(yōu)化算法通過不停地對群體進行迭代從而獲得最優(yōu)解.目前，已經有很多群體智能優(yōu)化算法及其改進方法被提出，比如粒子群算法[12]、人工蜂群算法[13]、螢火蟲算法[14]、灰狼算法[15]等.

鯨魚優(yōu)化算法(whale optimization algorithm，WOA)是由澳大利亞學者Mirjalili等[16]于2016年提出的一種群體智能優(yōu)化算法，它通過鯨魚群體搜索、包圍和追捕攻擊獵物等過程實現搜索和優(yōu)化目的.雖然鯨魚算法已被證明在求解精度和收斂速度方面存在很大優(yōu)勢，但仍存在局部最優(yōu)問題.針對此問題，學者提出了一些改進的方法.文獻[17]提出一種反向學習自適應的WOA，在搜索空間中利用反向學習算法對鯨魚的位置進行初始化，并在局部搜索階段加入線性權重增強算法的局部搜索能力.該文獻對高維度基準函數進行計算，展現出了良好的計算性能.文獻[18]使用混沌映射來優(yōu)化鯨魚算法的內部參數，進一步地提高了算法的計算精度，具有更好的全局搜索能力.文獻[19]提出了一種結合自適應權重和模擬退火的鯨魚算法，通過改進的自適應權重來調整算法的收斂速度，并使用模擬退火加強鯨魚算法的全局搜索能力，用于對測試函數的極值計算，計算精度和收斂速度都有了一定的提高.

Reynolds[20]于1994年提出了文化算法，其思想是利用種群進化過程中的知識構造信仰空間，以知識的方式指導種群空間的種群進化，能有效提高算法的全局搜索能力.種群空間可用于實現任何基于種群的優(yōu)化算法，一方面，對種群個體進行演化操作，另一方面，將優(yōu)秀的個體作為樣本提供給信仰空間.信仰空間通過接受函數接受種群空間中選擇出來的優(yōu)勢個體，并在各類演化算法的作用下，提取樣本個體攜帶的隱含信息，以知識的形式加以概括、描述和儲存.最終各類知識通過影響函數作用于種群空間，從而實現對種群空間中個體的更新指導.目前已成功應用于粒子群算法[21]、螢火蟲算法[22]、蜂群算法[23]等隨機優(yōu)化算法.文化算法的優(yōu)勢及成功應用為有效解決鯨魚算法容易陷入局部最優(yōu)提供了一種很好的思路.鑒于文化算法的全局搜索優(yōu)勢，本文將鯨魚算法納入到文化算法的種群空間，得到一種文化鯨魚優(yōu)化算法(cultural whale optimization algorithm，CWOA)來進行特征權重的優(yōu)化分配.

本文以案例推理預測模型為例，對加州大學歐文分校(University of California Irvine，UCI)標準預測數據集中的特征權重研究了優(yōu)化分配方法.將本文提出的文化鯨魚算法用于權重的優(yōu)化分配，并通過實驗測試證明了本文方法的有效性.

1 基于CWOA的權重優(yōu)化

CWOA的框架結構如圖1所示，包括種群空間和信仰空間.它采用雙層進化機制，即在種群進化算法的基礎上構建信仰空間，2個空間相對獨立地進行進化，并通過接受函數和影響函數進行交互.圖中的種群空間是求解最優(yōu)權重的主空間，具有性能評價和演化操作2個功能，其中，演化操作是利用WOA更新權重，性能評價則是通過計算適應度對這些權重進行評價.信仰空間采用形勢知識和規(guī)范知識進行該空間的知識描述，權重的更新則是利用雙變異演化策略來實現.2個空間之間的交互操作主要有接受操作和影響操作2種方式，信仰空間通過接受函數選取種群空間中的最優(yōu)權重，種群空間通過影響函數利用信仰空間的形勢知識和規(guī)范知識來指導權重的更新[24].下面從種群空間的演化策略、信仰空間的知識描述以及2個空間之間的交互操作三方面來介紹.

圖1 文化鯨魚算法框架Fig.1 Cultural whale algorithm framework

1.1 種群空間的演化策略

種群空間采用鯨魚算法進行權重的演化更新和性能評價.鯨魚算法是一種模仿座頭鯨泡泡網覓食行為的仿生智能優(yōu)化算法.令每個鯨魚的位置代表一個權重的可行解，該算法主要分為2個部分：一部分為隨機搜索最優(yōu)權重，另一部分是通過泡泡網覓食行為獲得最優(yōu)權重.

1)隨機搜索

隨機搜索階段對應著算法的全局探索階段，是隨機尋找最優(yōu)權重的過程.在n個特征權重中，令每一個權重的可行解在D維空間內，則第j個權重的可行解可表示為ωj=(ωj,1,ωj,2,…,ωj,i,…,ωj,D)，更新公式為

(1)

A=2ar1-a
C=2r2

(2)

計算.式中：r1和r2為[0,1]中的隨機數；a為控制參數，隨著迭代次數t的增加從2線性減小到0，即

a=2-2t/tmax

(3)

式中tmax為最大迭代次數.

當式(2)中的|A|≥1時，進入隨機搜索階段，根據各權重的可行解進行隨機搜索最優(yōu)權重；當|A|<1時，進入局部搜索階段，采用泡泡網覓食行為進行最優(yōu)權重的搜索.

2)泡泡網覓食

泡泡網覓食對應著算法的局部搜索階段，通過收縮包圍和螺旋上升更新權重.當式(2)中的|A|<1時，權重值會通過泡泡網覓食行為不斷趨向當前最優(yōu)解.其中收縮包圍方式可表示為

(4)

在進行螺旋更新權重時，當前權重以螺旋形運動趨向最優(yōu)權重，即

(5)

上述的式(4)收縮包圍和式(5)螺旋更新權重的選擇由隨機產生的概率因子p的值來決定.當p≥0.5時，進入螺旋更新權重階段；當p<0.5時，進入收縮包圍階段.即

(6)

在種群空間，通過上述的隨機搜索和泡泡網覓食算法可得到該空間中的最優(yōu)權重.

1.2 信仰空間的知識描述和更新策略

信仰空間的核心是知識表示和存儲更新，知識表示根據種群空間的演化策略和應用領域來制定，該空間中的知識共有5類：形勢知識、規(guī)范知識、拓撲知識、領域知識和歷史知識[25].本文采用形勢知識和規(guī)范知識描述信仰空間，這2種知識的形成依賴于對種群空間的最優(yōu)權重進行雙變異演化和性能評價的結果.下面是具體的算法描述.

1)形勢知識

形勢知識用于記錄進化過程中的最優(yōu)權重，采用雙變異演化策略進行權重的更新演化.雙變異演化策略的基本思想是在迭代的早期和后期分別采用非均勻變異算子和柯西變異算子對權重進行變異操作.其中的非均勻變異算子[26]在迭代早期能均勻地搜索整個空間以盡快發(fā)現可能的最優(yōu)區(qū)域，但隨著算法的進行，搜索范圍隨概率變小不斷縮減，到算法臨近結束時僅在當前解的小范圍中搜索，因此，需要在迭代后期采用柯西變異算子進行變異.柯西變異算子[27]可以產生較大的變異步長，有利于算法引導個體跳出局部最優(yōu)解，保證了算法的全局搜索能力.下面介紹非均勻變異算子和柯西變異算子，并從中獲得權重更新演化的形勢知識.

非均勻變異算子定義為

(7)

柯西變異算子定義為

(8)

為了實現權重的更新演化，需定義權重所對應的適應度函數，根據案例推理預測模型輸出的均方根誤差得到適應度函數

(9)

式中：s為源案例總數；y(i)為第i條案例的實際值；y′(i)為第i條案例的預測值.

根據上述雙變異策略，可得到信仰空間在第t次迭代時用于權重更新演化的形勢知識

(10)

2)規(guī)范知識

規(guī)范知識用于描述權重的可行解空間，對其更新體現為權重搜索空間的變化.針對權重的優(yōu)化問題，其結構描述為Ij,Lj,Uj,j=1,2,…，其中Ij=[lj,uj]={lj≤ωj≤uj，ωj∈}，表示第j個權重搜索空間邊界的值，上界uj初始化為1，下界lj初始化為0.規(guī)范知識根據每代獲得的優(yōu)勢權重進行更新，規(guī)則[28]為

(11)

(12)

(13)

(14)

信仰空間通過雙變異演化策略對種群空間的最優(yōu)權重進行更新演化后，為了達到2個空間相互影響從而提高精度的目的，還需要進行空間之間的交互操作設計.

1.3 空間之間的交互操作設計

種群空間和信仰空間的交互通過接受操作和影響操作來實現，具體操作如下.

1)接受操作

信仰空間通過接受函數從種群空間接受一組最優(yōu)權重子集，這里采取比例接受策略,即按接受比例ka依適應值升序接受權重個體，接受個數為

m=Nka

(15)

式中：m為信仰空間接受權重個數；N為種群空間權重個數.

在種群空間的權重進行過程中，每當接受操作執(zhí)行間隔為Acc時，按照

KM=ωopt

(16)

用種群空間中的最優(yōu)權重代替信仰空間中適應度差的權重.式中：KM為信仰空間中適應度最差的權重個體，M為信仰空間權重個數；ωopt為種群空間中適應度最好的權重個體.

2)影響操作

信仰空間中的形勢知識和規(guī)范知識形成后，通過影響函數對種群空間的權重進行引導以使種群空間在進化過程中得到全局最優(yōu)值，每當影響操作執(zhí)行間隔為Inf時，按照

ωf=Xr

(17)

用信仰空間中適應度最好的權重代替種群空間中適應度最差的權重.式中：Xr為信仰空間中適應度最好的權重個體；ωf為種群空間中適應度最差的權重個體.

CWOA通過雙層進化機制不斷更新迭代權重，當迭代到最后一次時，取種群空間中的最優(yōu)權重ωopt作為特征權重的最優(yōu)化分配.

根據上述1.1～1.3節(jié)的算法描述，可以得到CWOA偽代碼如下.

算法1CWOA

輸入：數據集Ck=(x1,…，xj,…,xn；y)、最大迭代次數tmax、信仰空間權重個數M、種群空間權重個數N、接受操作執(zhí)行間隔Acc、影響操作執(zhí)行間隔Inf、權重搜索空間上限uj和下限lj.

輸出：特征變量權重值ωopt.

1 隨機產生種群空間的權重；

2 通過式(9)計算每組權重的適應度，并由小到大排列;

3 根據隨機權重的信息給信仰空間中的形勢知識和規(guī)范化知識賦初值;

4 獲得當前最優(yōu)權重ωopt；

5 while滿足停止條件

6 fori=1,2,…,tmaxdo

7 ifi%Acc=0

8 通過式(16)將種群空間中的最優(yōu)權重代替信仰空間中適應度差的權重;

9 end if

10 if|A|≥1

11 種群空間通過式(1)更新下一代權重；

12 else

13 種群空間通過式(6)更新下一代權重；

14 ifi>tmax/2

15 信仰空間通過式(8)(10)更新權重;

16 else

17 信仰空間通過式(7)(10)更新權重;

18 end if

19 信仰空間通過式(11)(12)(13)(14)進行規(guī)范知識的更新;

20 ifi%Inf=0

21 通過式(17)將信仰空間中適應度最好的權重代替種群空間中適應度最差的權重；

22 end if

23 end for

24 end while

25 返回權重值ωopt;

1.4 收斂性分析

下面首先給出隨機優(yōu)化算法全局收斂需要滿足的2個條件[29]，然后分析CWOA的全局收斂性.

條件1若f(D(x,ξ))≤f(x)且ξ∈A,則f(D(x,ξ))≤f(ξ).

條件2對于A的任意Borel子集B，若其概率測度v(B)>0，則有

(18)

式中μk(B)為算法第k次迭代的權重在集合B上的概率測度.此假設保證了在測度大于0的情況下,算法經無窮多次迭代后,未搜索到空間B中的權重的概率為0.

引理假設適應度函數f為可測的，Rε為全局最優(yōu)權重集，P(zk∈Rε)為算法第k步生成的權重xk屬于最優(yōu)解Rε的概率測度，若條件1和2成立,則有

(19)

CWOA采用信仰空間保存最優(yōu)權重集，保證了最優(yōu)權重適應度不遞增，符合條件1.

綜上可知，CWOA收斂于全局最優(yōu)權重.

2 實驗研究

2.1 實驗設計

為了驗證本文方法進行特征權重優(yōu)化分配的有效性，以基于案例推理的數據預測模型為例，選取UCI機器學習的4個數據集作為測試數據進行實驗.4個數據集分別是Airfoil Self-Noise、Concrete Slump Test、Concrete Compressive Strength、QSAR aquatic toxicity，具體信息如表1所示.Airfoil Self-Noise為預測機翼自身噪聲的數據集，Concrete Slump Test是混凝土坍落度測試數據集，Concrete Compressive Strength是預測混凝土抗壓強度的數據集，QSAR aquatic toxicity是預測水生毒性定量構效關系的數據集.

表1 數據集信息Table 1 Dataset information

為了全面考察本文方法的效能,采用五折交叉驗證法進行實驗，實驗方案如下.

針對UCI的4個數據集，根據1.3節(jié)介紹的算法,對案例推理(case-based reasoning，CBR)檢索環(huán)節(jié)進行特征權重的優(yōu)化分配,然后利用得到的權重結果進行回歸預測,并與其他權重分配方法(傳統(tǒng)均權值(mean average，MA)、遺傳算法(genetic algorithm，GA)、差分進化(differential evolution，DE)和WOA)進行實驗結果的對比.其中，采用CWOA優(yōu)化權重的CBR預測模型簡稱為CBRCWOA，采用其他權重分配方法的CBR預測模型依次簡稱為CBRMA、CBRGA、CBRDE和CBRWOA.

實驗中的參數選取情況為：GA種群大小設為100,交叉概率為0.4,變異概率為0.05,進化代數為30；DE的種群規(guī)模設為100，縮放因子為0.5，交叉概率為0.9，進化代數為30；WOA的種群規(guī)模設為100，最大進化代數為30；CWOA群體空間的種群大小設為100，信仰空間種群大小30，信仰空間非均勻變異概率為0.4，柯西變異概率為0.5，接受操作執(zhí)行間隔為3，影響操作執(zhí)行間隔為4.

2.2 實驗步驟

根據上文的實驗設計，實驗步驟如下：

步驟1選擇數據集，將數據集的特征變量進行歸一化處理，并把特征值和相應的預測值表示成式(1)的形式存儲在案例庫中.

步驟2采用五折交叉驗證法進行實驗，將數據集中的數據平均分為5份，其中的4份組成歷史案例庫，另外1份組成目標案例庫.

步驟3分別采用MA、GA、DE、WOA和CWOA五種算法進行特征權重的優(yōu)化分配.

步驟4對于目標案例庫中的案例，采用K最近鄰方法在歷史案例庫中進行案例檢索，通過式(9)計算相似度并將其從大到小進行排序，取出前3個案例.

步驟5計算前3個案例輸出值的平均值作為目標案例的建議解.

步驟6將目標案例特征值及其建議解存儲在歷史案例庫中.

步驟7重復步驟4～6，直到目標案例庫中所有目標案例測試完成.

步驟8利用目標案例的預測值和實際值計算均方根誤差和平均絕對百分比誤差.

步驟9重復步驟1～7十次，計算10次實驗結果的標準差.

2.3 比較分析

根據2.2節(jié)中的實驗步驟1～7，利用表1中的4個回歸數據集分別驗證CBRMA、CBRGA、CBRWOA和CBRCWOA的擬合性能，實驗結果如圖2～5所示.由圖中可以看出，相對于CBRMA、CBRGA、CBRDE和CBRWOA，CBRCWOA更能擬合數據的變化趨勢.CWOA算法能在信仰空間的作用下對空間全局進行搜索得到最優(yōu)權重，得到的預測值逼近能力最好，預測精度最優(yōu).

圖2 Concrete Slump Test數據集擬合曲線Fig.2 Fitting curve of Concrete Slump Test dataset

圖3 Airfoil Self-Noise數據集擬合曲線Fig.3 Fitting curve of Airfoil Self-Noise dataset

圖4 Concrete Compressive Strength數據集擬合曲線Fig.4 Fitting curve of Concrete Compressive Strength dataset

圖5 QSAR aquatic toxicity數據集擬合曲線Fig.5 Fitting curve of QSAR aquatic toxicity dataset

根據2.2節(jié)中的實驗步驟，利用表1中的4個回歸數據集分別驗證CBRMA、CBRGA、CBRWOA、CBRDE和CBRCWOA的標準差，實驗結果如圖6所示.由圖中可以看出，在前3個數據集中5種預測模型的標準差由低到高依次為CBRMA、CBRCWOA、CBRDE、CBRWOA、CBRGA，而在最后一個數據集中標準差由低到高依次為CBRMA、CBRCWOA、CBRGA、CBRWOA、CBRDE.從結果可知，CWOA算法通過信仰空間不斷對權重迭代尋優(yōu)，得到的權重比較穩(wěn)定，使得預測模型的輸出比較穩(wěn)定.

圖6 標準差Fig.6 Standard deviation

根據2.2節(jié)中的實驗步驟，利用表1中的4個回歸數據集分別驗證CBRMA、CBRGA、CBRWOA、CBRDE和CBRCWOA的平均絕對百分比誤差，實驗結果如圖7所示.由圖中可知，5種模型的平均絕對百分比誤差由低到高分別為CBRCWOA、CBRWOA、CBRDE、CBRGA、CBRMA.由結果分析可知，CWOA算法能夠通過雙層空間機制進行全局搜索得到最優(yōu)權重，使得預測模型的實際預測誤差較小.

圖7 平均絕對百分比誤差Fig.7 Mean absolute percentage error

根據2.2節(jié)中的實驗步驟，利用表1中的4個回歸數據集分別驗證CBRMA、CBRGA、CBRWOA、CBRDE和CBRCWOA的均方根誤差，實驗結果如表2所示.由圖中可以看出，在第2、4個數據集中均方根誤差由小到大分別為CBRCWOA、CBRWOA、CBRDE、CBRGA、CBRMA，而在第1、3個數據集中均方根誤差由小到大分別為CBRCWOA、CBRGA、CBRDE、CBRWOA、CBRMA.由此可得，CWOA算法能有效地利用數據集中數據的潛在信息，跳出局部最優(yōu)值，得出最優(yōu)權重，使得模型的預測精度較高.

表2 均方根誤差Table 2 Root mean squared error

3 結論

1)為了提高預測模型的精度，本文將WOA納入文化算法的種群空間得到CWOA，進而通過迭代確定特征權重的最優(yōu)解.通過案例推理的數據預測對比實驗，CWOA相對其他方法可以在預測精度方面得到一定的提升，學習性能得到一定的改進.

2)本文方法的最大優(yōu)勢是采用雙層進化結構，信仰空間不受種群空間WOA策略的影響，可以更加充分地利用WOA權重迭代過程中的進化信息，提高進化的效率，而且其算法簡單，易實現，可拓展性好，可以跳出局部最優(yōu)，搜索到最優(yōu)權重.

3)雖然本方法在特征權重學習領域有一定的價值，但仍有一些不足之處，比如：一些問題的變量維數很多，目標和約束條件更加復雜.如何高效實現高維度變量空間的迭代尋優(yōu)是以后的主要研究方向.