改進(jìn)遺傳算法的支持向量機特征選擇解決方案

　　支持向量機是一種在統計學(xué)習理論的基礎上發(fā)展而來(lái)的機器學(xué)習方法[1]，通過(guò)學(xué)習類(lèi)別之間分界面附近的精確信息,可以自動(dòng)尋找那些對分類(lèi)有較好區分能力的支持向量,由此構造出的分類(lèi)器可以使類(lèi)與類(lèi)之間的間隔最大化,因而有較好的泛化性能和較高的分類(lèi)準確率。由于支持向量機具有小樣本、非線(xiàn)性、高維數、避免局部最小點(diǎn)以及過(guò)學(xué)習現象等優(yōu)點(diǎn)，所以被廣泛運用于故障診斷、圖像識別、回歸預測等領(lǐng)域。但是如果缺少了對樣本進(jìn)行有效地特征選擇，支持向量機在分類(lèi)時(shí)往往會(huì )出現訓練時(shí)間過(guò)長(cháng)以及較低的分類(lèi)準確率，這恰恰是由于支持向量機無(wú)法利用混亂的樣本分類(lèi)信息而引起的，因此特征選擇是分類(lèi)問(wèn)題中的一個(gè)重要環(huán)節。特征選擇的任務(wù)是從原始的特征集合中去除對分類(lèi)無(wú)用的冗余特征以及那些具有相似分類(lèi)信息的重復特征，因而可以有效降低特征維數，縮短訓練時(shí)間，提高分類(lèi)準確率。

　　目前特征選擇的方法主要有主成分分析法、最大熵原理、粗糙集理論等。然而由于這些方法主要依據繁復的數學(xué)理論，在計算過(guò)程中可能存在求導和函數連續性等客觀(guān)限定條件，在必要時(shí)還需要設定用來(lái)指導尋優(yōu)搜索方向的搜索規則。遺傳算法作為一種魯棒性極強的智能識別方法，直接對尋優(yōu)對象進(jìn)行操作，不存在特定數學(xué)條件的限定，具有極好的全局尋優(yōu)能力和并行性;而由于遺傳算法采用概率化的尋優(yōu)方法，所以在自動(dòng)搜索的過(guò)程中可以自主獲取與尋優(yōu)有關(guān)的線(xiàn)索，并在加以學(xué)習之后可以自適應地調整搜索方向，不需要確定搜索的規則。因此遺傳算法被廣泛應用在知識發(fā)現、組合優(yōu)化、機器學(xué)習、信號處理、自適應控制和人工生命等領(lǐng)域。

基于改進(jìn)遺傳算法的特征選擇

　　遺傳算法是一種新近發(fā)展起來(lái)的搜索最優(yōu)化算法[2~5]。遺傳算法從任意一個(gè)的初始生物種群開(kāi)始，通過(guò)隨機的選擇、交叉和變異操作，產(chǎn)生一群擁有更適應自然界的新個(gè)體的新一代種群，使得種群的進(jìn)化趨勢向著(zhù)最優(yōu)的方向發(fā)展。圖1中所示的是標準的遺傳算法的流程框圖。

　　傳統的遺傳算法存在早熟收斂、非全局收斂以及后期收斂速度慢的缺點(diǎn)，為此本文提出了一種能夠在進(jìn)化過(guò)程中自適應調節變異率，以及利用模擬退火防止早熟的改進(jìn)遺傳算法，同時(shí)該算法利用敏感度信息可以有效地控制遺傳操作。圖2是改進(jìn)遺傳算法的流程框圖。

染色體編碼和適應度函數

　　所謂編碼是指將問(wèn)題的解空間轉換成遺傳算法所能處理的搜索空間。在特征選擇問(wèn)題中，常常使用二進(jìn)制的編碼形式，使得每個(gè)二進(jìn)制就是一個(gè)染色體，其位數長(cháng)度等于特征的個(gè)數。每一位代表一個(gè)特征，每位上的1表示選中該特征，0則表示不選中。每一代種群都由若干個(gè)染色體組成。

　　適應度函數是整個(gè)遺傳算法中極為重要的部分[6]，好的適應度函數能使染色體進(jìn)化到最優(yōu)個(gè)體，它決定了在整個(gè)尋優(yōu)過(guò)程中是否能夠合理地協(xié)調好過(guò)早收斂和過(guò)慢結束這對矛盾。由于本文針對的是支持向量機的特征選擇問(wèn)題，所以考慮以分類(lèi)正確率和未選擇的特征個(gè)數這兩個(gè)參數作為函數的自變量，將分類(lèi)正確率作為主要衡量標準，未選擇的特征個(gè)數為次要標準。由此建立以下的適應度函數：

　　式中C為分類(lèi)正確率，為未選擇的特征個(gè)數，a是調節系數，用來(lái)平衡分類(lèi)正確率和未選擇的特征個(gè)數對適應度函數的影響程度，同時(shí)該系數也體現了用最少的特征得到較大分類(lèi)正確率的原則，在本文中a取0.00077。由上式可知，分類(lèi)正確率越高，未選的特征個(gè)數越多，染色體的適應度就越大。

選擇操作

　　選擇操作需要按照一定的規則從原有的種群中選擇部分優(yōu)秀個(gè)體用來(lái)交叉和變異。選擇原則建立在對個(gè)體適應度進(jìn)行評價(jià)的基礎上，目的是避免基因損失，提高全局收斂性和計算效率。本文首先將整個(gè)種群中最優(yōu)的前40%的個(gè)體保留下來(lái)，以確保有足夠的優(yōu)良個(gè)體進(jìn)入下一代，對剩下的60%的個(gè)體采用輪盤(pán)算法進(jìn)行選擇，這樣做可以彌補保留前40%個(gè)體而帶來(lái)的局部最優(yōu)解不易被淘汰的不利影響，有利于保持種群的多樣性。

基于敏感度信息量的交叉、變異操作

　　獨立敏感度信息量Q(i)指的是對在所有特征都被選中時(shí)計算所得到的適應度值Allfitness以及只有特征i未被選中時(shí)計算得到的適應度值Wfitness(i)按式(2)進(jìn)行計算得到的數值。獨立敏感度信息量刻畫(huà)了適應度對特征i是否被選擇的敏感程度。

　　互敏感度信息量R(i，j)由(3)式可得，互敏感度信息量體現了特征i與特征j之間對適應度的近似影響程度。

　　交叉操作的作用是通過(guò)交換兩個(gè)染色體之間的若干位從而生成含有部分原始優(yōu)良基因的新個(gè)體。由式(3)可知互敏感度信息量可作為不同特征之間含有相似分類(lèi)信息的一種度量，所以可以將互敏感度信息量代入式(4)計算出染色體在第位發(fā)生交叉的幾率b(i)，在式(4)中i和j分別代表特征i和特征j，是染色體的長(cháng)度。b(i)是特征i相對于其他所有特征在互敏感度信息量上的歸一量，反映了特征與其余特征在相似信息量上的總和。由此對應到染色體上，b(i)就可以認為是染色體的第i位與整個(gè)染色體在基因信息上的相關(guān)性，b(i)越小則說(shuō)明相關(guān)性越大，第i位與整個(gè)染色體所含的基因信息越接近，此位為分裂點(diǎn)的幾率越小。由于b(i)是歸一化量，故可采用輪盤(pán)算法來(lái)選擇一個(gè)交叉點(diǎn)。

變異操作是引入新物種的重要手段，可以有效地增加種群個(gè)體的多樣性。本文中的變異率Pm采用相鄰兩代之間的最優(yōu)適應度增幅比作為自變量進(jìn)行自適應調節，如式(5)所示。當適應度增幅比正向增大時(shí)，較小的增幅比可以使變異率維持在中等水平，并且變異率隨著(zhù)增幅比的增大而緩慢降低，這樣既能夠擁有一定數量的新個(gè)體也可以抑制過(guò)多不良染色體的產(chǎn)生，保證優(yōu)秀染色體的進(jìn)化足夠穩定;而當適應度增幅比反向增大時(shí)，由較小增幅比則可以獲得較高的變異率，并且變異率也伴隨增幅比同比緩慢升高，確保有足夠的染色體發(fā)生變異，穩定地加快進(jìn)化速度。

　 式中dis指新生種群的最優(yōu)適應度相對于原種群的最優(yōu)適應度的增幅比，j與k均是區間(0，1)上的調節系數。文中的j與k分別取0.65和0.055。

　　獨立敏感度信息量在一定程度上體現了單個(gè)特征所含有的分類(lèi)信息量，如果獨立敏感度信息量小，則說(shuō)明該特征所含信息大部分對分類(lèi)沒(méi)有幫助，即該基因位發(fā)生突變后對整個(gè)染色體的優(yōu)異性影響不大，突變的概率也就相應減小。因此將獨立敏感度信息量歸一化后所得到的q(i)作為特征i被選為變異點(diǎn)的概率。變異點(diǎn)的具體選擇方法為：針對一個(gè)染色體按照染色體的位數進(jìn)行循環(huán)遍歷，在該循環(huán)中由變異率Pm判定是否產(chǎn)生變異位。若需要產(chǎn)生變異位，則依據q(i)按照輪盤(pán)算法進(jìn)行選擇。

模擬退火選群

　　在每一輪進(jìn)化完成后都需要決定進(jìn)入下一輪進(jìn)化的種群。如果過(guò)多地將較優(yōu)種群作為父代，就會(huì )使算法過(guò)早收斂或搜索緩慢。文獻[7]中指出模擬退火算法能夠以一定的概率接受劣解從而跳出局部極值區域并最終趨于全局最優(yōu)解，因此可以將上文提到的最優(yōu)適應度增幅比作為能量函數，運用模擬退火的Meteopolis準則來(lái)選擇待進(jìn)化的種群。為了使每個(gè)種群得到充分地進(jìn)化，預防最優(yōu)解的丟失，這里采用設置退火步長(cháng)的策略來(lái)實(shí)現模擬退火選群。該策略具體為：使退火步長(cháng)對同一種群作為父代的次數進(jìn)行計數，一旦產(chǎn)生更優(yōu)種群則退火步長(cháng)就置零并重新計數。若退火步長(cháng)累計超過(guò)一定的閾值時(shí)，就進(jìn)入模擬退火選群階段。退火步長(cháng)累計到一定數量意味著(zhù)原有種群的進(jìn)化已經(jīng)停滯，需要用模擬退火算法擺脫這種停滯狀態(tài)。如果增幅比大于零，則說(shuō)明新生種群優(yōu)于原有種群，這時(shí)完全接受新種群進(jìn)入下一輪進(jìn)化;否則新生種群劣于原有種群，并以一定的概率p接受較劣的新生種群[8]進(jìn)入下一輪進(jìn)化。接受概率p由式(6)和式(7)共同決定，其中dis為增幅比，T(s)指溫度參數，T0和s分別是初始溫度和迭代次數。

　　以上兩式的參數要滿(mǎn)足進(jìn)化對接受概率的要求。即增幅比負增長(cháng)越大，接受概率降低越迅速，但接受概率隨迭代次數的增加應緩慢下降。這樣做能夠保證在有限的迭代次數內有一個(gè)適應度較優(yōu)的新生種群進(jìn)入下一輪進(jìn)化，以達到減少計算量和優(yōu)選待進(jìn)化種群的目的。在本文中T0=0.2，A=0.9，m=0.5。

實(shí)例的驗證與分析

　　UCI數據庫常用來(lái)比較各種方法的分類(lèi)效果，因此可以用其驗證本算法對支持向量機作用后的分類(lèi)效果[9][10]。文獻[11]采用了UCI數據庫中的German、Ionosphere和Sonar三種數據作為實(shí)驗對象，為了便于與文獻[11]中所用的幾種方法進(jìn)行對比，本文也采用這三種數據進(jìn)行實(shí)驗，并按照文獻中所述的比例將各類(lèi)數據分成相應的訓練樣本和測試樣本。

　　在種群規模為30，交叉率為0.8，起始變異率為0.1的條件下使用支持向量機作為分類(lèi)器(懲罰參數為13.7，徑向基核函數參數為10.6)對所選數據進(jìn)行分類(lèi)，表1中顯示了本文算法與文獻[11]中幾種算法在分類(lèi)效果上的對比，表2給出了三種數據的最終選擇結果。表1中共出現了四種方法：方法1：使用本文算法;方法2：使用NGA/PCA方法;方法3：使用PCA方法;方法4：使用簡(jiǎn)單遺傳算法。

　　由于本文算法旨在用最少的特征個(gè)數最大化分類(lèi)正確率，因此從表1中可以看出本文算法在特征選擇個(gè)數和分類(lèi)正確率上均比其他三種方法更具優(yōu)勢。由于NGA/PCA算法是針對簡(jiǎn)單遺傳算法和主成分分析法的不足而做的改進(jìn)，其性能優(yōu)于簡(jiǎn)單遺傳算法和主成分分析法，所以本文算法的分類(lèi)效果優(yōu)于NGA/PCA算法這一事實(shí)更能說(shuō)明該算法可以較好地解決支持向量機的特征選擇問(wèn)題。

結語(yǔ)

　　通過(guò)與其他方法的比較，本文算法的分類(lèi)效果得到了充分的驗證，也說(shuō)明了該算法具有極好的泛化能力以及在敏感度信息量地指導下遺傳操作的有效性。

　　適應度函數的設計至關(guān)重要，它直接影響到最終結果的優(yōu)劣以及算法的收斂性，所以在適應度函數的設計應考慮所解決問(wèn)題的側重點(diǎn)。

　　分類(lèi)正確率的高低不僅取決于合理的特征選擇，而且與支持向量機的參數優(yōu)化有關(guān)。只有在合理的特征選擇和參數優(yōu)化的前提下，支持向量機分類(lèi)器才能發(fā)揮出最佳的分類(lèi)效果。

　　由于算法能夠較好地解決支持向量機的特征選擇問(wèn)題，因此已被應用在基于支持向量機的數字電路板故障診斷當中，并取得了良好的效果。