面向特征選擇問題的差分鯨魚優化算法

于航，王子謙，雷振宇，高尚策

（1.泰州學院計算機科學與技術學院，江蘇泰州225300；2.富山大學工學部，日本富山9308555）

近年來，隨機搜索算法已經被應用于全局優化問題。由于這些算法中隨機算子的存在，相比確定性搜索算法而言，這些算法在運行時間和準確性方面展現出了極大的優越性。進化算法(EA)[1]是這些隨機搜索算法中的一種。進化算法在求解目標函數的全局最優解時，采用隨機算子來隨機生成新的子代。進化算法由于在避免陷入局部最小的方面展現出了良好的性能，因此已逐漸成為研究人員所關注的熱點，并被廣泛地應用于各個領域。

一些已經被廣泛使用的進化算法如下：粒子群優化算法（PSO）[2]是模擬鳥集群飛行覓食的行為，通過集體的協作使群體達到最優目的的算法；蟻群優化算法（ACO）[3]是一種模擬螞蟻尋找食物來源的隨機搜索算法；人工蜂群算法（ABC）[4]是一種模擬蜜蜂覓食行為的優化算法；遺傳算法（GA）[5]借鑒了進化生物學中的遺傳、突變和自然選擇現象。當然，差分進化(DE)[6]和鯨魚優化算法（WOA）[7]也屬于其中。

在設計和使用這些元啟發式算法時，對于搜索空間的探索能力和對于最優解的開發能力是一對既矛盾又需要被綜合考慮的方面。近年來，研究人員發現采用混合元啟發式算法可以有效地改善原算法這兩方面的能力，并且混合算法展現出了良好的解決實際問題的能力。例如，文獻[8]混合了粒子群算法（PSO）和人工蜂群算法（ABC）來訓練前饋神經網絡；文獻[9]混合了鯨魚優化算法（WOA）和模擬退火算法(SA)并應用于特征選擇問題。

在數據挖掘和機器學習[10]中，實際問題中通常會涉及大量的特征。然而，并非所有特征都是必不可少的，許多特征是多余的甚至是不相關的，這些特征夾雜在其中可能會降低分類算法的準確性。而特征選擇旨在通過僅選擇特征集的一小部分子集來解決實際問題。通過刪除不相關和冗余的特征，加快分類器的分類速度，簡化學習的模型。

特征選擇[11]是一項非常困難的任務，主要原因在于其搜索空間的維數十分龐大。假設一個數據集合具有n個特征，則其可能的解決方案總數為2n。隨著數據收集技術的進步，這些問題越來越復雜，實際問題的特征數量n也會越來越大，遍歷所有子集，從而選擇一個合適的子集的難度更會越來越大。所以從實際上來說，搜索給定數據集的所有特征子集在大多數情況下是不可能實現的。于是，研究人員嘗試利用多種搜索技術應用于特征選擇，例如元啟發式搜索和隨機搜索。但是研究人員發現，大多數現有特征選擇方法仍然遭受局部最小和停滯的困擾，且計算成本尤為高昂。因此，高效的全局搜索技術才能更好地解決特征選擇問題。進化算法由于其強大的全局搜索能力，在特征選擇領域中獲得了研究人員的關注。文中同樣嘗試著用混合進化算法的方式來解決特征選擇問題。

1 混合方法

1.1 鯨魚優化算法的最優解開發

鯨魚優化算法(WOA)是一種模仿座頭鯨捕食獵物行為的算法。為了捕捉獵物，首先需要將獵物包圍。其數學模型可用以下公式描述：

其中，t表示當前迭代，(t)表示到目前為止獲得的最佳解決方案，X是位置矢量。另外，A和C是等式中的系數向量，計算方法如下：

其中，a在迭代過程中從2 線性減少到0，r是在[0,1]間隔內以均勻分布生成的隨機向量。根據式（2），搜索單元（鯨魚）根據最優解（獵物）的位置來更新其位置。調整A和C向量的值可以控制鯨魚在獵物附近的區域。

算法通過式（3）中a值的減小實現了鯨魚的收縮包圍行為，其計算方法如下：

式中，t為迭代次數，M為允許迭代的最大次數。為了模擬螺旋形路徑，計算了搜索單元（X）與迄今為止的最優解（X*）之間的距離，然后使用式（6）的螺旋方程式來獲取臨近搜索單元的位置：

為了對這兩種機制建模，即收縮并環繞獵物和螺旋狀的路徑，在優化過程中，假設各有50%的概率選擇其中的任意一種方式，如式（7）所示：

其中，p是在[-1,1]范圍中的隨機數。

1.2 差分進化算法

差分進化(DE)算法是眾多進化算法的其中之一。近年來，結構簡單的差分進化算法已展現出其快速解決優化問題的能力。受到遺傳算法的啟發，差分進化算法主要包括初始化、差分變異、交叉、選擇。在初始化部分，假設有一個隨機的NP維參數向量作為每一代的種群，定義如下：

在變異的環節，采用差分的方式來變異向量，定義如下：

其中，r1,r2,r3 ∈[1,2,3,…,NP]是3 個隨機數。F是差分因子且是一個常數，一般可以取0.5。G是指迭代次數。

為了增加種群向量的多樣性，差分進化中設置了交叉的環節，對交叉的定義可以用如下的公式描述：

式中，rand是在[0,1]范圍中的隨機數。CR是交叉概率，一般取值為0.9。

最后一個選擇的環節，顧名思義，就是去確定哪一個個體會被選擇進入下一個種群。在差分進化中，采用了貪婪選擇的方式，即代價函數值越小的個體，越需要被保留在種群中。于是，比較新獲得的個體uji,G+1與過去的個體xji,G，若uji,G+1的代價函數值小于xji,G的代價函數值，則新個體uji,G+1取代舊個體xji,G保留在種群中。反之，則舍棄新個體uji,G+1。

1.3 基于鯨魚優化的差分進化算法

上述介紹的鯨魚優化算法(WOA)是近期提出的模仿座頭鯨捕食獵物行為的優化算法，它展現出了解決優化問題的能力，并且已經被廣泛地應用于各個領域。但是，鯨魚優化算法的開發能力（如在式（2）和（6）中提到的一樣）主要取決于到目前為止搜索單元與最優解之間的距離，所以首先需要有一個足夠好的當前最優解，才能更好地利用鯨魚優化算法的開發性能。于是設想采用一種有效的具有較強探索能力的算法來大致確定最優解的方位，再利用鯨魚優化算法的開發能力找到最優解，從而提升搜索算法的能力。差分進化(DE)是眾多進化算法的其中之一，它以其簡單的結構和快速解決問題的能力，深受研究人員的關注。然而，差分進化算法具有較強探索能力的同時，開發能力卻略顯不足，因此，文中考慮結合鯨魚優化算法和差分進化算法的優點，設計出了一種基于鯨魚優化的差分進化混合算法。混合算法的流程圖如圖1所示。

圖1 混合算法流程圖

2 進化特征選擇

從本質上來說，特征選擇問題是一個二進制優化問題，因為問題解決方案僅限于二進制{0，1}兩個值。要將WODE 算法應用于特征選擇問題，就需要設計一個二進制編碼的版本。在這項工作中，解決的方案用一維向量來表示，向量的長度與原始數據集的特征數量相同。向量中的每個值都由“1”或者“0”來表示。用數值“1”表示選擇相應的特征；而數值“0”表示不選擇相應的特征。

特征選擇問題可以看作是一個多目標優化問題，其中要實現如下兩個目標：最少的特征數量和更高的分類精度。解決方案中選定的特征數量越少，分類的精度越高，則可以說解決方案就越好。每個解決方案的評價都需要使用代價函數，而代價函數主要利用KNN 分類器來獲取解決方案中選定特征的分類精度。為了在解決方案中選定特征的數量（最小）和分類精度（最大）之間取得平衡，可使用如下方程式來定義代價函數：

其中，γR(D)表示給定分類器的分類誤差，文中采用了K 鄰近分類器。R表示所選子集的特征數量，N是數據集中特征的總數，α和β是與分類精度和選定子集長度有關的兩個參數，α∈[0，1]，β=1-α。

3 仿真結果

3.1 函數集測試結果

下面將對提出的WODE 算法在CEC2017 函數集上進行測試。種群規模已設定為100，維度設置為30，最大迭代次數在算法中設置為3 000。此外，為了減小隨機性帶來的誤差，算法在每一個函數上都會測試30 次，然后計算這30 次結果的平均值和標準偏差，得出最終結果。此外，將提出的WODE 算法與其他一些已經被廣泛應用的進化算法進行比較，例如差分進化（DE）、鯨魚優化算法（WOA）、粒子群優化算法（PSO），以顯示提出算法的優越性。

上述提到的算法測試結果已經在表1中列了出來, 30 次獨立運行結果的平均值表示算法的平均性能，而標準偏差（Std）反映了算法的魯棒性，4 種算法對每個函數求解的最優解的最小值已經被加粗，如表1～表4所示。

表1 CEC2017中單峰函數測試結果

表2 CEC2017中多峰函數測試結果

表3 CEC2017中混合函數測試結果

表4 CEC2017中組合函數測試結果

通過4 個表可以很明顯看出，在5 個多峰測試函數和11 個組合測試函數中，WODE 比其余3 種算法的解更優。在4 個單峰測試函數中，WODE 有一半是最優。在10 個混合測試函數中，WODE 有8 個是最優。

圖2是從30 個測試函數中隨機抽取的4 個測試函數的數據所畫的收斂圖，從圖2可以看出,WODE測試結果的最優值優于其余3 種算法。

圖2 收斂圖

圖3是隨機選取的4 個測試函數數據的箱線圖，從圖3可以看出，WODE 的測試結果分布要優于其余3 個算法。

圖3 箱線圖

同時，Wilcoxon 檢驗[13]被用來精確比較WODE和其他測試算法之間的性能。Wilcoxon 檢驗是一種非參數檢驗，主要涉及兩個樣本的假設檢驗。實驗中的置信區間設置為95%，即當Wilcoxon 檢驗之后得出的P值小于0.05 時，表示前者測試解的結果相比后者有顯著性優勢。表5列出了WODE 與DE、WOA、PSO 4 種算法的Wilcoxon 檢驗結果。從表5可以看出，WODE 的測試結果要優于其他3 種算法。

表5 Wilcoxon檢驗

3.2 特征選擇的測試結果

文中還將所提出的混合算法WODE 應用于特征選擇問題。同時，與DE、WOA 兩種算法進行了比較，測試了算法的分類準確性和特征的數量。分類準確性取數據集運行30 次中的最優一次分類準確性，特征數量則為這30 次運行的平均特征數量。測試過程中，α取0.9。表6中列出了所采用的數據集基本信息，包括特征數量和數據集維度，測試用的3 個數據集均來自于UCI。

表7中羅列了算法的測試結果，其中，3 種算法中最優的分類準確性和最小的特征數量已經被加粗。從表7中可以明顯看出，對于特征選擇而言，WODE 的效果更好。

表7 分類準確率和特征的平均數量

4 結 論

文中提出了一種基于鯨魚優化的差分進化算法，以提高進化算法的搜索能力。實驗結果表明，提出的WODE 可以有效地提高DE 對于最優解的挖掘能力。此外，WODE 在處理特征選擇問題時表現出了一定的優越性。在將來，將提出的WODE 應用于多目標優化問題[14]、組合優化問題[15]以及神經網絡的學習[16]。