一種改進(jìn)的差分進(jìn)化算法及其在SVM 中的應(yīng)用

王珂，周瑤，趙媛媛

（西安建筑科技大學(xué)，西安710055）

0 引言

作為一個(gè)信息大平臺(tái)，互聯(lián)網(wǎng)的輿論功能為信息交流提供了一個(gè)便捷的渠道。然而網(wǎng)絡(luò)上的信息良莠不齊，及時(shí)準(zhǔn)確發(fā)現(xiàn)網(wǎng)絡(luò)中的輿情信息和熱點(diǎn)事件并加以監(jiān)督與引導(dǎo)，對(duì)社會(huì)的和諧穩(wěn)定發(fā)展具有重要意義，尤其是根據(jù)分析的結(jié)果對(duì)輿情進(jìn)行預(yù)測(cè)，這對(duì)有關(guān)部門很有必要[1-2]。

網(wǎng)絡(luò)輿情研究與分析的重要依托技術(shù)是文本分類。文本分類作為輿情監(jiān)管的基礎(chǔ)，其重要性不言而喻。SVM 是文本分類中應(yīng)用最為廣泛的一個(gè)算法。SVM[3]自提出之日起至今雖然只有短短二十多年，但是它在分類問題中表現(xiàn)出來(lái)的優(yōu)越性能備受機(jī)器學(xué)習(xí)領(lǐng)域?qū)W者的青睞。影響SVM 的分類效率和模型預(yù)測(cè)性能的主要因素是核參數(shù)[4]，但傳統(tǒng)的核參數(shù)選擇并沒有一套可遵循的理論方法，往往依靠經(jīng)驗(yàn)進(jìn)行窮舉或通過(guò)交叉驗(yàn)證進(jìn)行大量實(shí)驗(yàn)選取合適的參數(shù)，這些方法不僅需要依靠大量的人力物力，而且最終并不能得到令人滿意的結(jié)果。本文針對(duì)SVM 這一問題提出了差分進(jìn)化算法智能選取核參數(shù)。

差分進(jìn)化算法是一種智能優(yōu)化算法，用它來(lái)智能選取SVM 的核參數(shù)可以避免人為經(jīng)驗(yàn)產(chǎn)生的偶然與誤差，同時(shí)還可以節(jié)省人力物力。差分進(jìn)化算法相較其他優(yōu)化算法有較多優(yōu)勢(shì)，如：參數(shù)少，算法簡(jiǎn)單，易于實(shí)現(xiàn)。但也因?yàn)槠淙菀紫萑朐缡焓諗窟@一特性而受到很多局限。因此，本文首先要對(duì)標(biāo)準(zhǔn)DE 算法進(jìn)行改進(jìn)，再令其進(jìn)行SVM 的參數(shù)尋優(yōu)。本文是對(duì)標(biāo)準(zhǔn)差分進(jìn)化算法進(jìn)行改進(jìn)，并用該算法優(yōu)化SVM 的核參數(shù)，最后將其應(yīng)用到分類問題中，實(shí)質(zhì)上是對(duì)差分進(jìn)化算法的改進(jìn)與應(yīng)用。

1 差分進(jìn)化算法的改進(jìn)

1.1 DE算法基本原理

差分進(jìn)化算法是一種智能隨機(jī)搜索算法[5]。變異、交叉、選擇是差分進(jìn)化算法的主要操作算子。其基本思想是：首先初始化各參數(shù)，隨機(jī)生成初始種群，然后從初始種群中隨機(jī)選擇兩個(gè)不同的個(gè)體，利用其向量差與第三個(gè)個(gè)體按照一定的規(guī)則生成新的變異個(gè)體。然后利用該變異個(gè)體與父代的目標(biāo)個(gè)體進(jìn)行交叉生成試驗(yàn)個(gè)體。判斷試驗(yàn)個(gè)體的適應(yīng)度與目標(biāo)個(gè)體適應(yīng)度值的大小，適應(yīng)度高的保留，差的淘汰，不斷迭代，直至逼近全局最優(yōu)解[6]。然而標(biāo)準(zhǔn)差分尋優(yōu)算法受到種群大小、F 值、CR 以及變異策略等的影響。

1.2 標(biāo)準(zhǔn)DE局限性分析

DE 算法因其實(shí)現(xiàn)簡(jiǎn)單，算法魯棒性好而備受關(guān)注，但差分進(jìn)化算法也有自身的局限性，即易陷入局部極優(yōu)而出現(xiàn)早熟收斂[7]，造成這種現(xiàn)象主要是因?yàn)殡S著迭代次數(shù)的增加，種群多樣性降低，使得個(gè)體差異太小從而導(dǎo)致算法不能達(dá)到全局最優(yōu)點(diǎn)。差分進(jìn)化算法的收斂速度主要受其控制參數(shù)和變異策略的影響[8]。

變異因子F 決定著種群的多樣性和收斂速度，F(xiàn)一般取值范圍在[0，2]。當(dāng)F 較大時(shí)全局搜索能力提高，不易陷入早熟收斂，但收斂速度減慢；反之，算法的收斂速度加快，對(duì)種群擾動(dòng)小，易陷入局部極優(yōu)出現(xiàn)早熟收斂。交叉概率CR 通常的取值范圍為[0，1]，當(dāng)CR較大時(shí)，局部搜索能力加強(qiáng)收斂速度加快，易陷入局部極優(yōu)；反之，CR 取值較小時(shí)，種群多樣性增加有利于全局搜索。

1.3 改進(jìn)的DE算法

為了避免標(biāo)準(zhǔn)DE 易陷入早熟收斂這一特點(diǎn)，本文提出了一種自適應(yīng)組合優(yōu)化差分進(jìn)化算法（Adaptive Combinatorial Optimization Differential Evolution，ACODE）。在搜索前期注重全局搜索能力，在后期主要進(jìn)行精確的局部搜索，加快收斂速度。因此需要合理選取F 和CR 的值[9-10]。

為了使算法在搜索前期進(jìn)行全局搜索，F(xiàn) 取值應(yīng)較大，CR 較小；后期進(jìn)行局部搜索則需要F 小CR 大，F(xiàn) 和CR 的值需要進(jìn)行動(dòng)態(tài)變化。

為使得搜索前期取較大的F，較小的CR，搜索后期有較小的F 和較大的CR，本文使F 和CR 動(dòng)態(tài)變化。

本文F 和CR 的動(dòng)態(tài)變化如式（1-2）所示。

其中Fmax、Fmin 分別為F 的取值上限和下限，CRmin、CRmax 分別為CR 取值的上限和下限，其中最大進(jìn)化代數(shù)用T 表示，當(dāng)前進(jìn)化代數(shù)用t 表示。

DE 中還存在一個(gè)重要影響因素，即變異策略。式（3）和（4）是其中兩種常見的變異模式，通常情況下使用單一且固定的變異模式，最常采用的是DE/rand/1。

DE/rand/1：

DE/best/1：

其中，變異個(gè)體決定著優(yōu)化的方向，同時(shí)影響著全局最優(yōu)解的搜索能力。為了既能保證種群的多樣性又能提高收斂速度，本文采取自適應(yīng)的變異策略，使搜索前期采用式（3）保證全局搜索，后期采用式（4）保證收斂速度。具體變異策略如式（5）。

在前期有助于保持種群的多樣性，后期提高收斂速度，但是如果后期還沒有找到最優(yōu)解，則容易陷入局部最優(yōu)產(chǎn)生早熟收斂。本文采用新增隨機(jī)個(gè)體來(lái)逃出局部極優(yōu)。如果搜索停滯則增加新的個(gè)體。搜索停滯即新生成的個(gè)體適應(yīng)度值等于原種群個(gè)體的適應(yīng)度，使得種群個(gè)體難以更新從而導(dǎo)致搜索停滯現(xiàn)象。

每個(gè)個(gè)體i 在迭代過(guò)程中使得目標(biāo)函數(shù)未改進(jìn)的次數(shù)記作count，若個(gè)體i 的目標(biāo)函數(shù)在某次迭代中得到改進(jìn)則count 的值保持不變，否則count+1，若新個(gè)體等于原始個(gè)體L 次則說(shuō)明L 次該個(gè)體未得到更新，表明此個(gè)體性能較差已經(jīng)陷入局部極優(yōu)，則隨機(jī)生成一個(gè)新個(gè)體代替它。如式（6）和（7）所示：

If

則：

1.4 算法步驟

ACODE 算法具體操作步驟如下：

（1）初始化種群規(guī)模，進(jìn)化代數(shù)t+1，最大迭代次數(shù)T，控制參數(shù)CR 和F 按照式（1）和式（2）設(shè)置。

（2）計(jì)算個(gè)體適應(yīng)度。

（3）判斷步驟2 得到的適應(yīng)度和迭代次數(shù)是否達(dá)到算法終止條件，如果適應(yīng)度達(dá)到理論最優(yōu)值或者滿足t=T 則輸出結(jié)果，否則轉(zhuǎn)到步驟4

（4）對(duì)當(dāng)代種群，根據(jù)改進(jìn)的變異策略式（5）進(jìn)行變異操作，生成中間變異個(gè)體vi( g+1)

（5）交叉操作，對(duì)t+1 代變異個(gè)體vi( g+1) 進(jìn)行交叉操作產(chǎn)生t+1代實(shí)驗(yàn)個(gè)體ui,j( j+1)

（6）選擇操作，對(duì)t+1 代實(shí)驗(yàn)個(gè)體ui,j( j+1) 進(jìn)行選擇操作產(chǎn)生t+1代個(gè)體xi( g+1)

（7）判斷是否存在停滯現(xiàn)象并解決參見式（6）和式（7）

（8）t=t+1，返回步驟2。

1.5 算法性能評(píng)價(jià)

本文采用基準(zhǔn)函數(shù)測(cè)試ACODE 算法的性能。這里標(biāo)準(zhǔn)DE 的CR 和F 的值均設(shè)置0.8。而ACODE 算法中的CR 和F 分別按照式子（1）和（2）進(jìn)行自適應(yīng)變化，且變異策略也按照式子（5）進(jìn)行自適應(yīng)變化。為避免實(shí)驗(yàn)偶然性，保證測(cè)試質(zhì)量，算法獨(dú)立運(yùn)行20 次，算法迭代次數(shù)為1000，種群大小為100，維數(shù)為10。結(jié)果如表1 所示，收斂曲線圖分別如圖1-3 所示。

測(cè)試函數(shù)如下：

（1）Sphere 函數(shù)：

（2）Rastrigin 函數(shù)：

（3）Rosenbrock 函數(shù)：

表1 基準(zhǔn)函數(shù)測(cè)試結(jié)果

圖1 Sphere函數(shù)收斂曲線圖

從表1 可以看出，對(duì)于Sphere 函數(shù)，兩種算法皆表現(xiàn)出較高的精度，但改進(jìn)的DE 算法明顯比標(biāo)準(zhǔn)DE 算法得到的值更優(yōu)；對(duì)于Rastrigrin 函數(shù)，ACODE 算法收斂精度更高，說(shuō)明該算法能更好地避免局部極優(yōu)；對(duì)于Rosenbrock 函數(shù)，可看出ACODE 算法的平均值略差于DE 算法，而其最優(yōu)值略優(yōu)于DE 算法。從收斂曲線看，對(duì)于三種基準(zhǔn)函數(shù)而言，ACODE 算法均有優(yōu)越的收斂性能，極好地避免了局部極優(yōu)。

綜上，ACODE 算法可克服標(biāo)準(zhǔn)DE 算法自身的缺陷，并在基準(zhǔn)函數(shù)測(cè)試中性能較好，尋優(yōu)能力較強(qiáng)。

圖2 Rastrigrin函數(shù)收斂曲線圖

圖3 Rosenbrock函數(shù)收斂曲線圖

2 基于ACODE算法的SVM核參數(shù)優(yōu)化

由于ACODE 算法對(duì)SVM 參數(shù)優(yōu)化的效果還不能完全確定，因此本文將ACODE 算法應(yīng)用到具體的分類過(guò)程中。本文以搜狗語(yǔ)料庫(kù)為實(shí)驗(yàn)數(shù)據(jù)集，共選取十類，每類數(shù)據(jù)集有220 篇文檔，其中每篇訓(xùn)練集占200篇，剩下的為測(cè)試集。算法流程圖如圖4 所示。

首先初始化ACODE-SVM 算法中的參數(shù)，其中，種群規(guī)模M=20，最大進(jìn)化代數(shù)gmax=100，其他參數(shù)設(shè)定依照前文，SVM 的懲罰參數(shù)C 和核函數(shù)的參數(shù)g 的上下限均設(shè)為[0.0001，1000]。使用ACODE 算法對(duì)SVM 進(jìn)行最優(yōu)參數(shù)選擇，利用得到的參數(shù)進(jìn)行模型的訓(xùn)練和測(cè)試，并與未優(yōu)化的模型的結(jié)果進(jìn)行對(duì)比，表2 是本次的實(shí)驗(yàn)結(jié)果。

圖4 ACODE-SVM流程圖

表2 三種算法的實(shí)驗(yàn)結(jié)果對(duì)比

從表2 可以看出，整體而言采用ACODE-SVM 算法訓(xùn)練所得模型的準(zhǔn)確率比未優(yōu)化的值更高，分類結(jié)果更準(zhǔn)確。

3 結(jié)語(yǔ)

本文研究分類問題中影響SVM 分類效率的主要因素：核參數(shù)和懲罰因子。由于差分進(jìn)化算法相比較其他智能算法而言控制參數(shù)較少，具有較強(qiáng)的全局搜索能力，魯棒性好，很適合參數(shù)尋優(yōu)問題，因此本文引入差分進(jìn)化算法優(yōu)化SVM 的參數(shù)并對(duì)其進(jìn)行改進(jìn)，實(shí)驗(yàn)表明基于ACODE-SVM 的優(yōu)化算法大大提高了SVM 的分類準(zhǔn)確率。