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

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

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

　式中dis指新生種群的最優(yōu)適應(yīng)度相對(duì)于原種群的最優(yōu)適應(yīng)度的增幅比，j與k均是區(qū)間(0，1)上的調(diào)節(jié)系數(shù)。文中的j與k分別取0.65和0.055。

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

　　模擬退火選群

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

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

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

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

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

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

　　結(jié)語(yǔ)

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

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

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

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