一種改進的差分進化算法及其在SVM 中的應用

王珂，周瑤，趙媛媛

（西安建筑科技大學，西安710055）

0 引言

作為一個信息大平臺，互聯網的輿論功能為信息交流提供了一個便捷的渠道。然而網絡上的信息良莠不齊，及時準確發現網絡中的輿情信息和熱點事件并加以監督與引導，對社會的和諧穩定發展具有重要意義，尤其是根據分析的結果對輿情進行預測，這對有關部門很有必要[1-2]。

網絡輿情研究與分析的重要依托技術是文本分類。文本分類作為輿情監管的基礎，其重要性不言而喻。SVM 是文本分類中應用最為廣泛的一個算法。SVM[3]自提出之日起至今雖然只有短短二十多年，但是它在分類問題中表現出來的優越性能備受機器學習領域學者的青睞。影響SVM 的分類效率和模型預測性能的主要因素是核參數[4]，但傳統的核參數選擇并沒有一套可遵循的理論方法，往往依靠經驗進行窮舉或通過交叉驗證進行大量實驗選取合適的參數，這些方法不僅需要依靠大量的人力物力，而且最終并不能得到令人滿意的結果。本文針對SVM 這一問題提出了差分進化算法智能選取核參數。

差分進化算法是一種智能優化算法，用它來智能選取SVM 的核參數可以避免人為經驗產生的偶然與誤差，同時還可以節省人力物力。差分進化算法相較其他優化算法有較多優勢，如：參數少，算法簡單，易于實現。但也因為其容易陷入早熟收斂這一特性而受到很多局限。因此，本文首先要對標準DE 算法進行改進，再令其進行SVM 的參數尋優。本文是對標準差分進化算法進行改進，并用該算法優化SVM 的核參數，最后將其應用到分類問題中，實質上是對差分進化算法的改進與應用。

1 差分進化算法的改進

1.1 DE算法基本原理

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

1.2 標準DE局限性分析

DE 算法因其實現簡單，算法魯棒性好而備受關注，但差分進化算法也有自身的局限性，即易陷入局部極優而出現早熟收斂[7]，造成這種現象主要是因為隨著迭代次數的增加，種群多樣性降低，使得個體差異太小從而導致算法不能達到全局最優點。差分進化算法的收斂速度主要受其控制參數和變異策略的影響[8]。

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

1.3 改進的DE算法

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

為了使算法在搜索前期進行全局搜索，F 取值應較大，CR 較小；后期進行局部搜索則需要F 小CR 大，F 和CR 的值需要進行動態變化。

為使得搜索前期取較大的F，較小的CR，搜索后期有較小的F 和較大的CR，本文使F 和CR 動態變化。

本文F 和CR 的動態變化如式（1-2）所示。

其中Fmax、Fmin 分別為F 的取值上限和下限，CRmin、CRmax 分別為CR 取值的上限和下限，其中最大進化代數用T 表示，當前進化代數用t 表示。

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

DE/rand/1：

DE/best/1：

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

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

每個個體i 在迭代過程中使得目標函數未改進的次數記作count，若個體i 的目標函數在某次迭代中得到改進則count 的值保持不變，否則count+1，若新個體等于原始個體L 次則說明L 次該個體未得到更新，表明此個體性能較差已經陷入局部極優，則隨機生成一個新個體代替它。如式（6）和（7）所示：

If

則：

1.4 算法步驟

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

（1）初始化種群規模，進化代數t+1，最大迭代次數T，控制參數CR 和F 按照式（1）和式（2）設置。

（2）計算個體適應度。

（3）判斷步驟2 得到的適應度和迭代次數是否達到算法終止條件，如果適應度達到理論最優值或者滿足t=T 則輸出結果，否則轉到步驟4

（4）對當代種群，根據改進的變異策略式（5）進行變異操作，生成中間變異個體vi( g+1)

（5）交叉操作，對t+1 代變異個體vi( g+1) 進行交叉操作產生t+1代實驗個體ui,j( j+1)

（6）選擇操作，對t+1 代實驗個體ui,j( j+1) 進行選擇操作產生t+1代個體xi( g+1)

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

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

1.5 算法性能評價

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

測試函數如下：

（1）Sphere 函數：

（2）Rastrigin 函數：

（3）Rosenbrock 函數：

表1 基準函數測試結果

圖1 Sphere函數收斂曲線圖

從表1 可以看出，對于Sphere 函數，兩種算法皆表現出較高的精度，但改進的DE 算法明顯比標準DE 算法得到的值更優；對于Rastrigrin 函數，ACODE 算法收斂精度更高，說明該算法能更好地避免局部極優；對于Rosenbrock 函數，可看出ACODE 算法的平均值略差于DE 算法，而其最優值略優于DE 算法。從收斂曲線看，對于三種基準函數而言，ACODE 算法均有優越的收斂性能，極好地避免了局部極優。

綜上，ACODE 算法可克服標準DE 算法自身的缺陷，并在基準函數測試中性能較好，尋優能力較強。

圖2 Rastrigrin函數收斂曲線圖

圖3 Rosenbrock函數收斂曲線圖

2 基于ACODE算法的SVM核參數優化

由于ACODE 算法對SVM 參數優化的效果還不能完全確定，因此本文將ACODE 算法應用到具體的分類過程中。本文以搜狗語料庫為實驗數據集，共選取十類，每類數據集有220 篇文檔，其中每篇訓練集占200篇，剩下的為測試集。算法流程圖如圖4 所示。

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

圖4 ACODE-SVM流程圖

表2 三種算法的實驗結果對比

從表2 可以看出，整體而言采用ACODE-SVM 算法訓練所得模型的準確率比未優化的值更高，分類結果更準確。

3 結語

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