張前圖

摘要：為了提高支持向量機(jī)（SVM）分類性能，同時(shí)針對果蠅優(yōu)化算法（FOA）尋優(yōu)精度不高和易陷入局部最優(yōu)的特點(diǎn)，提出了一種改進(jìn)的FOA算法（LFOA），并將其應(yīng)用于SVM的參數(shù)尋優(yōu)中。該方法在運(yùn)算個(gè)過程中根據(jù)果蠅種群的進(jìn)化程度，動(dòng)態(tài)的將種群分為較差子群和較優(yōu)子群；較差子群在最優(yōu)個(gè)體的指導(dǎo)下以基本FOA算法進(jìn)行全局搜索，較優(yōu)子群則圍繞最優(yōu)個(gè)體做Levy飛行，進(jìn)行精細(xì)化局部搜索；兩個(gè)子群的信息通過全局最優(yōu)個(gè)體的更新和種群個(gè)體的重組進(jìn)行交換。通過對UCI數(shù)據(jù)庫中幾個(gè)經(jīng)典數(shù)據(jù)集的分類測試結(jié)果表明，基于LFOA優(yōu)化SVM參數(shù)能夠提高SVM的分類性能，效果優(yōu)于其他幾種方法。

Abstract： In order to overcome the problems of support vector machine （SVM） parameters selection and the demerits of fruit fly optimization algorithm，such as low convergence precision and easily relapsing into local optimum，an improvement FOA （LFOA） is presented.Firstly，the fruit fly group is dynamically divided into advanced subgroup and drawback subgroup according to its own evolutionary level. Secondly，a global search with FOA is made for drawback subgroup with the guidance of the best individual and a finely local search is made for advanced subgroup that do Levy flight around the best individual.Finally，two subgroups exchange information by updating the overall optimum and recombining the subgroups.The classify experiment results of several data set in UCI data base show that SVM parameters optimization based on LFOA can improvement the classify performance of SVM and is better than some other method.

關(guān)鍵詞：支持向量機(jī)；果蠅算法；Levy飛行；參數(shù)尋優(yōu)

Key words： support vector machine；fruit fly optimization algorithm；Levy flight；parameters optimization

中圖分類號：TP18；TP301.6 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2016）08-0218-04

0 引言

在模式識別領(lǐng)域，支持向量機(jī)（SVM）由于具有較強(qiáng)的小樣本學(xué)習(xí)能力和泛化能力，在很多方面都得到了應(yīng)用。目前，對SVM研究的一個(gè)重點(diǎn)就是對其參數(shù)的優(yōu)化，因?yàn)閼土P參數(shù)和核參數(shù)對其分類性能具有重要的影響。傳統(tǒng)的一些參數(shù)優(yōu)化方法主要包括窮舉法、網(wǎng)格搜索法、梯度下降法，這些方法雖然簡單，但搜索精度不高且耗時(shí)較長。近年來，不少學(xué)者也提出了很多智能算法對其進(jìn)行優(yōu)化操作，如遺傳算法（GA），粒子群算法（PSO），人工魚群算法（AFSA），杜鵑算法（MSC）等，都取得了不錯(cuò)的效果。但這些算法或多或少都存在一定的缺陷，如GA的操作過程較為復(fù)雜且容易出現(xiàn)早熟現(xiàn)象、PSO則容易陷入局部最優(yōu)、AFSA中人工魚視野和步長的選擇主要依靠經(jīng)驗(yàn)等，這些都降低了SVM參數(shù)的尋優(yōu)精度。而果蠅優(yōu)化算法（FOA）由于參數(shù)設(shè)置少，算法簡單易于實(shí)現(xiàn)等優(yōu)點(diǎn)，在不同的領(lǐng)域都得到了應(yīng)用，并有學(xué)者也將其應(yīng)用到了SVM參數(shù)尋優(yōu)中，效果較好。

本文將FOA和SVM結(jié)合，采用FOA對SVM參數(shù)進(jìn)行尋優(yōu)，同時(shí)針對FOA易陷入局部最優(yōu)和尋優(yōu)精度不高的缺點(diǎn)，對其尋優(yōu)過程進(jìn)行改進(jìn)，提出了改進(jìn)的FOA算法（LFOA）。該算法根據(jù)果蠅種群的進(jìn)化程度，動(dòng)態(tài)的將果蠅種群一分為二，較差子群則在最優(yōu)果蠅個(gè)體的指導(dǎo)下以FOA為基礎(chǔ)進(jìn)行全局搜索，較優(yōu)子群則引入Levy飛行策略，使z子群圍繞最優(yōu)果蠅個(gè)體做Levy飛行，進(jìn)行局部搜索，同時(shí)利用Levy飛行偶爾的長跳躍來跳出局部最優(yōu)。實(shí)驗(yàn)表明，LFOA的優(yōu)化性能要優(yōu)于FOA、GA和PSO，經(jīng)LFOA優(yōu)化的SVM對測試數(shù)據(jù)集具有更好的分類效果。

1 支持向量機(jī)及其參數(shù)

假設(shè)有一組帶有類別標(biāo)記的訓(xùn)練樣本T={（x1，y1），…，（xn，yn）}，xi是n維向量，yi代表xi的所屬類別，其中每個(gè)輸入點(diǎn)xi∈Rd（i=1，…，n）屬于兩類中的某一類，其類別標(biāo)記為y∈{+1，-1}。SVM的主要目的是構(gòu)建一個(gè)分類超平面來分割兩類不同樣本，使得分類間隔（margin）最大。最終歸結(jié)為約束條件下求解二次規(guī)劃問題：

結(jié)合前面的推導(dǎo)過程，RBF-SVM需要優(yōu)化的是懲罰參數(shù)C和核參數(shù)g。懲罰參數(shù)C主要作用就是調(diào)節(jié)SVM學(xué)習(xí)過程中的置信區(qū)間和經(jīng)驗(yàn)風(fēng)險(xiǎn)的比例，以使SVM的推廣性能最好；核參數(shù)g主要影響樣本數(shù)據(jù)在特征空間中分布的復(fù)雜度。因此，SVM的性能取決于這兩個(gè)參數(shù)的選擇，采用較好的優(yōu)化算法進(jìn)行參數(shù)的選擇可以提高SVM的性能。

2 果蠅優(yōu)化算法及其改進(jìn)

2.1 果蠅優(yōu)化算法

果蠅優(yōu)化算法是臺灣學(xué)者潘文超于2011年基于果蠅的覓食行為提出的一種全局優(yōu)化算法。果蠅可以通過嗅覺搜集飄在空中的食物味道，飛到食物附件后又可通過視覺發(fā)現(xiàn)食物，并向食物飛去。果蠅優(yōu)化算法的集體步驟如下：

2.2 果蠅優(yōu)化算法的改進(jìn)策略

從果蠅算法的步驟可以看出，在整個(gè)迭代過程中，整個(gè)果蠅種群只向最優(yōu)果蠅個(gè)體學(xué)習(xí)，一旦發(fā)現(xiàn)最優(yōu)個(gè)體，則所有果蠅都飛往該處，但如果該位置不是全局最優(yōu)，則算法極易陷入局部最優(yōu)，影響收斂精度和收斂速度。社會學(xué)經(jīng)驗(yàn)告訴我們，全局最優(yōu)往往存在于局部最優(yōu)的附近，并且種群的進(jìn)化速度更大程度取決于較差個(gè)體而不是較優(yōu)個(gè)體。另一方面，自然界中很多動(dòng)物（果蠅、蜜蜂等）在覓食的過程中，都采用類似Levy飛行的搜索策略。在這種形式的搜索中，短距離的探索性蹦蹦跳跳與偶爾的較長距離行走相間。短距離的蹦蹦跳跳可以保證覓食過程中對自身周圍的小范圍進(jìn)行仔細(xì)地搜尋，而偶爾較長距離的行走又可以保證自身能夠進(jìn)入另一個(gè)區(qū)域，在更廣闊的范圍進(jìn)行搜索。鑒于Levy飛行的優(yōu)點(diǎn)，許多學(xué)者將Levy飛行引入到進(jìn)化策略中，改進(jìn)算法性能并取得了不錯(cuò)的效果。

為了便于對比，分別運(yùn)用LFOA、FOA、GA和PSO對SVM的參數(shù)C和g進(jìn)行尋優(yōu)。在所有的算法中，種群規(guī)模都為20，最大迭代次數(shù)為100，C和g的搜索范圍都為0～100；在LFOA算法中，步進(jìn)長度a=0.5；GA算法中，交叉概率pc=0.7，變異概率pm=0.1；PSO算法中局部搜索參數(shù)c1=1.5，全局搜索參數(shù)c2=1.7。

3.2 結(jié)果分析

用表1中的數(shù)據(jù)集對上述4種方法的性能進(jìn)行測試，測試結(jié)果如表2和表3所示。表2中每種方法的平均分類準(zhǔn)確率是取10次試驗(yàn)分類準(zhǔn)確率的平均值，每次實(shí)驗(yàn)的分類準(zhǔn)確率是通過對訓(xùn)練樣本執(zhí)行5折交叉驗(yàn)證得到，同時(shí)記錄下每次實(shí)驗(yàn)得到的C和g值。在計(jì)算表3中各方法的測試準(zhǔn)確率時(shí)，選取10次實(shí)驗(yàn)中最高分類準(zhǔn)確率對應(yīng)的C和g對SVM進(jìn)行訓(xùn)練，而后對測試樣本進(jìn)行分類識別得到測試準(zhǔn)確率。需要注意的是，最高分類準(zhǔn)確率可能對應(yīng)多個(gè)C和g的值，由于C過大會造成誤差上升，這里保留最小的C以及對應(yīng)的g值。圖1還給出了4種不同方法對3個(gè)數(shù)據(jù)集的分類識別準(zhǔn)確率迭代曲線。

從表2、表3以及圖1中可以看出，LFOA優(yōu)化SVM的效果基本上都要好于其他三種方法。對于多分類不平衡數(shù)據(jù)集Glass，LFOA和PSO在平均分類準(zhǔn)確率和測試準(zhǔn)確率上效果一樣，均好于FOA和GA，尤其是測試準(zhǔn)確率方面提高較多，這在實(shí)際工程應(yīng)用中具有重要的意義，而LFOA相較于PSO的優(yōu)勢主要在尋優(yōu)速度上，如圖1（a）所示，LFOA只經(jīng)過4次迭代就達(dá)到了最高準(zhǔn)確率，PSO經(jīng)過12次迭代后才達(dá)到了最高準(zhǔn)確率，而FOA和GA雖然迭代次數(shù)較少，但卻陷入了局部最優(yōu)；對于多分類平衡數(shù)據(jù)集Segment和二分類數(shù)據(jù)集German，LFOA的平均分類準(zhǔn)確率和測試準(zhǔn)確率均優(yōu)于其他3種方法，并且從迭代曲線（圖1（b）和（c））中可以看出，LFOA在尋優(yōu)速度和尋優(yōu)精度上也均好于其他3種方法，克服了其他算法尋優(yōu)速度慢和易陷入局部最優(yōu)的缺點(diǎn)。同時(shí)從圖1中還可以發(fā)現(xiàn)，隨著數(shù)據(jù)集維數(shù)的增加，LFOA的效果就越明顯，這說明LFOA對于復(fù)雜數(shù)據(jù)集的處理能力也優(yōu)于其他幾種方法。

4 結(jié)論

本文針對果蠅優(yōu)化算法尋優(yōu)精度不高和易陷入局部最優(yōu)的缺點(diǎn)，提出了一種具有Levy飛行特征的雙子群果蠅優(yōu)化算法，其優(yōu)勢在于既可以保證果蠅種群的全局搜索能力，又增強(qiáng)了果蠅種群的局部搜索和跳出局部最優(yōu)的能力。將其用于優(yōu)化支持向量機(jī)的參數(shù)，通過對UCI數(shù)據(jù)庫中幾個(gè)經(jīng)典數(shù)據(jù)集的仿真實(shí)驗(yàn)結(jié)果顯示所提方法能夠提高支持向量機(jī)的分類精度和效率，相比于傳統(tǒng)的果蠅算法、遺傳算法和粒子群算法具有更好的效果。

參考文獻(xiàn)：

[1]付陽，李昆侖.支持向量機(jī)模型參數(shù)選擇方法綜述[J].電腦知識與技術(shù)，2010，6（28）：8081-8082.

[2]董寶玉，任光.基于GA優(yōu)化合成核支持向量機(jī)的船舶柴油機(jī)故障診斷[J]. 大連海事大學(xué)學(xué)報(bào)，2013，39（04）：79-81.

[3]和麟，梁麗嬡，黃瀟瑤，等.基于粒子群優(yōu)化SVM的飛機(jī)發(fā)電機(jī)故障診斷[J].計(jì)算機(jī)測量與控制，2013，21（12）：3237-3239.

[4]白靜，楊利紅，張雪英.一種面向語音識別的抗噪svm參數(shù)優(yōu)化方法[J].中南大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，44（02）：604-611.

[5]郭一格，孫力，劉以安.基于MCS的SVM參數(shù)優(yōu)化研究[J]. 計(jì)算機(jī)應(yīng)用研究，2012，29（12）：4553-4555.

[6]Wen-Tsao Pan. A new fruit fly optimization algorithm： Taking the financial distress model as an example[J]. Knowledge-Based Systems. 2012. 26（Complete）： 69-74.

[7]李霞，孫靈芳，楊明.基于改進(jìn)FOA匹配追蹤的超聲信號處理研究[J].儀器儀表學(xué)報(bào)，2013，34（09）：2068-2073.

[8]楊瓊，俞立峰，陳小小.一種基于果蠅優(yōu)化方法的連續(xù)查詢攻擊算法[J].四川大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，51（04）：7215-7730.

[9]張翔，陳林.基于果蠅優(yōu)化算法的支持向量機(jī)故障診斷[J]. 電子設(shè)計(jì)工程，2013，21（16）：90-93.

[10]王雪剛，鄒早建.基于果蠅優(yōu)化算法的支持向量機(jī)參數(shù)優(yōu)化在船舶操縱預(yù)報(bào)中的應(yīng)用[J].上海交通大學(xué)學(xué)報(bào)，2013，47（06）：884-888.

[11]韓俊英，劉成忠.自適應(yīng)變異的果蠅優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2013，30（09）：2641-2644.

[12]韓俊英，劉成忠，王聯(lián)國.動(dòng)態(tài)雙子群協(xié)同進(jìn)化果蠅優(yōu)化算法[J].模式識別與人工智能，2013，26（11）：1057-1067.

[13]肖劍，周建中，張孝遠(yuǎn)，等.基于Levy-ABC優(yōu)化SVM的水電機(jī)組故障診斷方法[J].振動(dòng).測試與診斷，2013，33（05）：839-844.

[14]杜利敏，阮奇，馮登科.基于共軛梯度的布谷鳥搜索算法[J].計(jì)算機(jī)與應(yīng)用化學(xué)，2013，30（04）：406-410.

[15]謝健，周永權(quán)，陳歡.一種基于Lévy飛行軌跡的蝙蝠算法[J].模式識別與人工智能，2013，26（09）：830-837.

[16]Mantegna R N. Fast，accurate algortihm for numerical simulation of levy stable stochastic process[J]. Physical Review E. 1992，49： 451-458.