面向特征選擇問題的差分鯨魚優(yōu)化算法

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

（1.泰州學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇泰州225300；2.富山大學(xué)工學(xué)部，日本富山9308555）

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

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

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

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

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

1 混合方法

1.1 鯨魚優(yōu)化算法的最優(yōu)解開發(fā)

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

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

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

算法通過式（3）中a值的減小實(shí)現(xiàn)了鯨魚的收縮包圍行為，其計(jì)算方法如下：

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

為了對(duì)這兩種機(jī)制建模，即收縮并環(huán)繞獵物和螺旋狀的路徑，在優(yōu)化過程中，假設(shè)各有50%的概率選擇其中的任意一種方式，如式（7）所示：

其中，p是在[-1,1]范圍中的隨機(jī)數(shù)。

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

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

在變異的環(huán)節(jié)，采用差分的方式來變異向量，定義如下：

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

為了增加種群向量的多樣性，差分進(jìn)化中設(shè)置了交叉的環(huán)節(jié)，對(duì)交叉的定義可以用如下的公式描述：

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

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

1.3 基于鯨魚優(yōu)化的差分進(jìn)化算法

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

圖1 混合算法流程圖

2 進(jìn)化特征選擇

從本質(zhì)上來說，特征選擇問題是一個(gè)二進(jìn)制優(yōu)化問題，因?yàn)閱栴}解決方案僅限于二進(jìn)制{0，1}兩個(gè)值。要將WODE 算法應(yīng)用于特征選擇問題，就需要設(shè)計(jì)一個(gè)二進(jìn)制編碼的版本。在這項(xiàng)工作中，解決的方案用一維向量來表示，向量的長(zhǎng)度與原始數(shù)據(jù)集的特征數(shù)量相同。向量中的每個(gè)值都由“1”或者“0”來表示。用數(shù)值“1”表示選擇相應(yīng)的特征；而數(shù)值“0”表示不選擇相應(yīng)的特征。

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

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

3 仿真結(jié)果

3.1 函數(shù)集測(cè)試結(jié)果

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

上述提到的算法測(cè)試結(jié)果已經(jīng)在表1中列了出來, 30 次獨(dú)立運(yùn)行結(jié)果的平均值表示算法的平均性能，而標(biāo)準(zhǔn)偏差（Std）反映了算法的魯棒性，4 種算法對(duì)每個(gè)函數(shù)求解的最優(yōu)解的最小值已經(jīng)被加粗，如表1～表4所示。

表1 CEC2017中單峰函數(shù)測(cè)試結(jié)果

表2 CEC2017中多峰函數(shù)測(cè)試結(jié)果

表3 CEC2017中混合函數(shù)測(cè)試結(jié)果

表4 CEC2017中組合函數(shù)測(cè)試結(jié)果

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

圖2是從30 個(gè)測(cè)試函數(shù)中隨機(jī)抽取的4 個(gè)測(cè)試函數(shù)的數(shù)據(jù)所畫的收斂圖，從圖2可以看出,WODE測(cè)試結(jié)果的最優(yōu)值優(yōu)于其余3 種算法。

圖2 收斂圖

圖3是隨機(jī)選取的4 個(gè)測(cè)試函數(shù)數(shù)據(jù)的箱線圖，從圖3可以看出，WODE 的測(cè)試結(jié)果分布要優(yōu)于其余3 個(gè)算法。

圖3 箱線圖

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

表5 Wilcoxon檢驗(yàn)

3.2 特征選擇的測(cè)試結(jié)果

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

表7中羅列了算法的測(cè)試結(jié)果，其中，3 種算法中最優(yōu)的分類準(zhǔn)確性和最小的特征數(shù)量已經(jīng)被加粗。從表7中可以明顯看出，對(duì)于特征選擇而言，WODE 的效果更好。

表7 分類準(zhǔn)確率和特征的平均數(shù)量

4 結(jié) 論

文中提出了一種基于鯨魚優(yōu)化的差分進(jìn)化算法，以提高進(jìn)化算法的搜索能力。實(shí)驗(yàn)結(jié)果表明，提出的WODE 可以有效地提高DE 對(duì)于最優(yōu)解的挖掘能力。此外，WODE 在處理特征選擇問題時(shí)表現(xiàn)出了一定的優(yōu)越性。在將來，將提出的WODE 應(yīng)用于多目標(biāo)優(yōu)化問題[14]、組合優(yōu)化問題[15]以及神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)[16]。