改進遺傳算法的支持向量機特征選擇解決方案介紹

1、    改進遺傳算法的支持向量機特征選擇解決方案介紹        時間:2011年12月15日     字 體: 大 中 小        關(guān)鍵詞:        基于改進遺傳算法的特征選擇遺傳算法是一種新近發(fā)展起來的搜索最優(yōu)化算法25。遺傳算法從任意一個的初始生物種群開始，通

2、過隨機的選擇、交叉和變異操作，產(chǎn)生一群擁有更適應(yīng)自然界的新個體的新一代種群，使得種群的進化趨勢向著最優(yōu)的方向發(fā)展。圖1中所示的是標準的遺傳算法的流程框圖。 傳統(tǒng)的遺傳算法存在早熟收斂、非全局收斂以及后期收斂速度慢的缺點，為此本文提出了一種能夠在進化過程中自適應(yīng)調(diào)節(jié)變異率，以及利用模擬退火防止早熟的改進遺傳算法，同時該算法利用敏感度信息可以有效地控制遺傳操作。圖2是改進遺傳算法的流程框圖。 染色體編碼和適應(yīng)度函數(shù)所謂編碼是指將問題的解空間轉(zhuǎn)換成遺傳算法所能處理的搜索空間。在特征選擇問題中，常常使用二進制的編碼形式，使得每個二進制就是一個染色體，其位數(shù)長度等于特征的個數(shù)。每一位

3、代表一個特征，每位上的1表示選中該特征，0則表示不選中。每一代種群都由若干個染色體組成。適應(yīng)度函數(shù)是整個遺傳算法中極為重要的部分6，好的適應(yīng)度函數(shù)能使染色體進化到最優(yōu)個體，它決定了在整個尋優(yōu)過程中是否能夠合理地協(xié)調(diào)好過早收斂和過慢結(jié)束這對矛盾。由于本文針對的是支持向量機的特征選擇問題，所以考慮以分類正確率和未選擇的特征個數(shù)這兩個參數(shù)作為函數(shù)的自變量，將分類正確率作為主要衡量標準，未選擇的特征個數(shù)為次要標準。由此建立以下的適應(yīng)度函數(shù)： 式中C為分類正確率，為未選擇的特征個數(shù)，a是調(diào)節(jié)系數(shù)，用來平衡分類正確率和未選擇的特征個數(shù)對適應(yīng)度函數(shù)的影響程度，同時該系數(shù)也體現(xiàn)了用最少的特征得到較大

4、分類正確率的原則，在本文中a取0.00077。由上式可知，分類正確率越高，未選的特征個數(shù)越多，染色體的適應(yīng)度就越大。選擇操作選擇操作需要按照一定的規(guī)則從原有的種群中選擇部分優(yōu)秀個體用來交叉和變異。選擇原則建立在對個體適應(yīng)度進行評價的基礎(chǔ)上，目的是避免基因損失，提高全局收斂性和計算效率。本文首先將整個種群中最優(yōu)的前40%的個體保留下來，以確保有足夠的優(yōu)良個體進入下一代，對剩下的60%的個體采用輪盤算法進行選擇，這樣做可以彌補保留前40%個體而帶來的局部最優(yōu)解不易被淘汰的不利影響，有利于保持種群的多樣性?；诿舾卸刃畔⒘康慕徊?、變異操作獨立敏感度信息量Q(i)指的是對在所有特征都被選中時計算所得到

5、的適應(yīng)度值A(chǔ)llfitness以及只有特征i未被選中時計算得到的適應(yīng)度值Wfitness(i)按式(2)進行計算得到的數(shù)值。獨立敏感度信息量刻畫了適應(yīng)度對特征i是否被選擇的敏感程度。 互敏感度信息量R(i，j)由(3)式可得，互敏感度信息量體現(xiàn)了特征i與特征j之間對適應(yīng)度的近似影響程度。交叉操作的作用是通過交換兩個染色體之間的若干位從而生成含有部分原始優(yōu)良基因的新個體。由式(3)可知互敏感度信息量可作為不同特征之間含有相似分類信息的一種度量，所以可以將互敏感度信息量代入式(4)計算出染色體在第位發(fā)生交叉的幾率b(i)，在式(4)中i和j分別代表特征i和特征j，是染色體的長度。b(i)

6、是特征i相對于其他所有特征在互敏感度信息量上的歸一量，反映了特征與其余特征在相似信息量上的總和。由此對應(yīng)到染色體上，b(i)就可以認為是染色體的第i位與整個染色體在基因信息上的相關(guān)性，b(i)越小則說明相關(guān)性越大，第i位與整個染色體所含的基因信息越接近，此位為分裂點的幾率越小。由于b(i)是歸一化量，故可采用輪盤算法來選擇一個交叉點。變異操作是引入新物種的重要手段，可以有效地增加種群個體的多樣性。本文中的變異率Pm采用相鄰兩代之間的最優(yōu)適應(yīng)度增幅比作為自變量進行自適應(yīng)調(diào)節(jié)，如式(5)所示。當適應(yīng)度增幅比正向增大時，較小的增幅比可以使變異率維持在中等水平，并且變異率隨著增幅比的增大而緩慢降低，這

7、樣既能夠擁有一定數(shù)量的新個體也可以抑制過多不良染色體的產(chǎn)生，保證優(yōu)秀染色體的進化足夠穩(wěn)定;而當適應(yīng)度增幅比反向增大時，由較小增幅比則可以獲得較高的變異率，并且變異率也伴隨增幅比同比緩慢升高，確保有足夠的染色體發(fā)生變異，穩(wěn)定地加快進化速度。獨立敏感度信息量在一定程度上體現(xiàn)了單個特征所含有的分類信息量，如果獨立敏感度信息量小，則說明該特征所含信息大部分對分類沒有幫助，即該基因位發(fā)生突變后對整個染色體的優(yōu)異性影響不大，突變的概率也就相應(yīng)減小。因此將獨立敏感度信息量歸一化后所得到的q(i)作為特征i被選為變異點的概率。變異點的具體選擇方法為：針對一個染色體按照染色體的位數(shù)進行循環(huán)遍歷，在該循環(huán)中由變異

8、率Pm判定是否產(chǎn)生變異位。若需要產(chǎn)生變異位，則依據(jù)q(i)按照輪盤算法進行選擇。模擬退火選群在每一輪進化完成后都需要決定進入下一輪進化的種群。如果過多地將較優(yōu)種群作為父代，就會使算法過早收斂或搜索緩慢。文獻7中指出模擬退火算法能夠以一定的概率接受劣解從而跳出局部極值區(qū)域并最終趨于全局最優(yōu)解，因此可以將上文提到的最優(yōu)適應(yīng)度增幅比作為能量函數(shù)，運用模擬退火的Meteopolis準則來選擇待進化的種群。為了使每個種群得到充分地進化，預(yù)防最優(yōu)解的丟失，這里采用設(shè)置退火步長的策略來實現(xiàn)模擬退火選群。該策略具體為：使退火步長對同一種群作為父代的次數(shù)進行計數(shù)，一旦產(chǎn)生更優(yōu)種群則退火步長就置零并重新計數(shù)。若退

9、火步長累計超過一定的閾值時，就進入模擬退火選群階段。退火步長累計到一定數(shù)量意味著原有種群的進化已經(jīng)停滯，需要用模擬退火算法擺脫這種停滯狀態(tài)。如果增幅比大于零，則說明新生種群優(yōu)于原有種群，這時完全接受新種群進入下一輪進化;否則新生種群劣于原有種群，并以一定的概率p接受較劣的新生種群8進入下一輪進化。接受概率p由式(6)和式(7)共同決定，其中dis為增幅比，T(s)指溫度參數(shù)，T0和s分別是初始溫度和迭代次數(shù)。 以上兩式的參數(shù)要滿足進化對接受概率的要求。即增幅比負增長越大，接受概率降低越迅速，但接受概率隨迭代次數(shù)的增加應(yīng)緩慢下降。這樣做能夠保證在有限的迭代次數(shù)內(nèi)有一個適應(yīng)度較優(yōu)的新生種

10、群進入下一輪進化，以達到減少計算量和優(yōu)選待進化種群的目的。在本文中T0=0.2，A=0.9，m=0.5。實例的驗證與分析UCI數(shù)據(jù)庫常用來比較各種方法的分類效果，因此可以用其驗證本算法對支持向量機作用后的分類效果910。文獻11采用了UCI數(shù)據(jù)庫中的German、Ionosphere和Sonar三種數(shù)據(jù)作為實驗對象，為了便于與文獻11中所用的幾種方法進行對比，本文也采用這三種數(shù)據(jù)進行實驗，并按照文獻中所述的比例將各類數(shù)據(jù)分成相應(yīng)的訓(xùn)練樣本和測試樣本。在種群規(guī)模為30，交叉率為0.8，起始變異率為0.1的條件下使用支持向量機作為分類器(懲罰參數(shù)為13.7，徑向基核函數(shù)參數(shù)為10.6)對所選數(shù)據(jù)進

11、行分類，表1中顯示了本文算法與文獻11中幾種算法在分類效果上的對比，表2給出了三種數(shù)據(jù)的最終選擇結(jié)果。表1中共出現(xiàn)了四種方法：方法1：使用本文算法;方法2：使用NGA/PCA方法;方法3：使用PCA方法;方法4：使用簡單遺傳算法。 由于本文算法旨在用最少的特征個數(shù)最大化分類正確率，因此從表1中可以看出本文算法在特征選擇個數(shù)和分類正確率上均比其他三種方法更具優(yōu)勢。由于NGA/PCA算法是針對簡單遺傳算法和主成分分析法的不足而做的改進，其性能優(yōu)于簡單遺傳算法和主成分分析法，所以本文算法的分類效果優(yōu)于NGA/PCA算法這一事實更能說明該算法可以較好地解決支持向量機的特征選擇問題。結(jié)語通過與其他方法的比較，本文算法的分類效果得到了充分的驗證，也說明了該算法具有極好的泛化能力以及在敏感度信息量地指導(dǎo)下遺傳操作的有效性。適應(yīng)度函數(shù)的設(shè)計至關(guān)重要，它直接影響到最終結(jié)果的優(yōu)劣以及算法的收斂性，所以在適應(yīng)度函數(shù)