范方云， 孫 俊， 王夢梅

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫214122)

隨著基因表達(dá)譜技術(shù)的推廣，利用DNA芯片可以在一次實(shí)驗(yàn)中同時(shí)獲得成千上萬個(gè)基因的表達(dá)水平［1］。依據(jù)基因表達(dá)譜建立分類模型，實(shí)現(xiàn)對癌癥類型的識(shí)別與判斷，對癌癥的診斷與治療具有重要意義［2-3］。然而，基因表達(dá)譜數(shù)據(jù)維度高，樣本量很少，且分布不均勻，只有少量的基因真正具有分類信息。在進(jìn)行癌癥分類時(shí)，大量冗余特征會(huì)嚴(yán)重影響分類效果，而且增加了計(jì)算時(shí)的復(fù)雜度。所以，如何選擇出對分類具有積極作用的基因是建立有效分類模型的關(guān)鍵所在。國內(nèi)外學(xué)者在這方面已經(jīng)進(jìn)行了大量研究［4-6］。張靖等［7］利用信噪比指標(biāo)過濾無關(guān)基因，采用迭代Lasso方法進(jìn)行冗余基因的剔除，結(jié)合SVM分類器在數(shù)據(jù)Leukemia，Prostate，Colon 上分別獲得了 98．61%，96．08%，90．32% 的分類正確率;張煥萍等［8］提出了離散粒子群和支持向量機(jī)封裝模式的BPSO-SVM特征基因選擇方法，在數(shù)據(jù)集Colon上用34個(gè)特征基因子集獲得了89．67% 的平均正確率。目前，多種特征選擇方法的使用已經(jīng)取得了較好的分類效果，但存在的問題依然很明顯，即如何在提高分類正確率的同時(shí)降低基因子集的規(guī)模，換言之，如何用最少的基因得出最好的分類效果。

文中提出了基于改進(jìn)的遺傳算法的癌癥特征基因選擇方法。通過改進(jìn)遺傳算法的交叉和變異操作，使得遺傳算法在搜索分類基因時(shí)具有更強(qiáng)的全局搜索能力，并且避免了局部收斂。同時(shí)根據(jù)基因子集的特點(diǎn)，增加了最優(yōu)個(gè)體變異策略，提高算法找到最優(yōu)解的可能性。此外，將分類正確率和基因個(gè)數(shù)同時(shí)考慮，進(jìn)行多目標(biāo)優(yōu)化，使用SVM分類器進(jìn)行留一法交叉驗(yàn)證。同時(shí)，實(shí)驗(yàn)使用基本遺傳算法進(jìn)行特征選擇，將兩種遺傳算法的表現(xiàn)進(jìn)行比較。結(jié)果表明，改進(jìn)的遺傳算法相比于基本的遺傳算法明顯具有更優(yōu)的分類正確率和更小的基因子集。

1 遺傳算法的基本原理

遺傳算法(Genetic Algorithm，GA)是一個(gè)經(jīng)典的隨機(jī)搜索與優(yōu)化算法，是建立在Darwin的進(jìn)化論和Mendel的遺傳學(xué)說基礎(chǔ)上的。1975年，密執(zhí)安大學(xué)的教授Holland與其學(xué)生創(chuàng)建了該算法［9］。從此，對遺傳算法的研究引起了國內(nèi)外諸多學(xué)者的關(guān)注。

與傳統(tǒng)的搜索算法不同，遺傳算法是從一組隨機(jī)產(chǎn)生的初始解開始搜索過程的。這組初始解被稱為群體，初始解的個(gè)數(shù)就是群體的大小。群體中的每個(gè)個(gè)體都是目標(biāo)問題的一個(gè)解，稱為染色體。這些染色體在后續(xù)過程中不斷進(jìn)化迭代，這個(gè)過程稱為遺傳。遺傳算法的進(jìn)化過程主要是通過3種操作實(shí)現(xiàn)，分別為選擇、交叉、變異。選擇、交叉或者變異運(yùn)算產(chǎn)生的下一代染色體，稱為后代。染色體的好壞用適應(yīng)值進(jìn)行衡量。每個(gè)染色體都可以計(jì)算適應(yīng)值，計(jì)算適應(yīng)值的函數(shù)稱為適應(yīng)值函數(shù)。根據(jù)適應(yīng)值的大小從上一代中選擇個(gè)體，再通過交叉和變異，得到后代;再繼續(xù)進(jìn)化，經(jīng)過若干代之后，算法收斂于最好的染色體。

利用遺傳算法解決某個(gè)實(shí)際問題通常從初始化一個(gè)種群開始。所以解決某個(gè)實(shí)際問題，首先就是根據(jù)這個(gè)實(shí)際問題進(jìn)行個(gè)體編碼，然后生成初始種群，再對染色體進(jìn)行選擇、交叉以及變異操作。

2 遺傳算法的改進(jìn)

為了增加遺傳算法的全局搜索能力和局部搜索能力，文中提出了3種改進(jìn)策略:均勻交叉策略、變異概率的非線性遞增策略和最優(yōu)個(gè)體變異策略。均勻交叉策略是指兩個(gè)配對個(gè)體的每一位都以相同的概率進(jìn)行交換，從而形成兩個(gè)新的個(gè)體;變異概率的非線性遞增策略是變異概率隨著種群進(jìn)化代數(shù)的增加而非線性的增加;最優(yōu)個(gè)體變異策略是對每次迭代的最優(yōu)個(gè)體進(jìn)行變異，增加算法找到全局最優(yōu)解的可能。實(shí)驗(yàn)結(jié)果表明，3種改進(jìn)策略的提出有效地提高了基本遺傳算法在選擇特征基因的能力。

2．1 均勻交叉策略

在改進(jìn)的遺傳算法中，使用均勻交叉，而不是傳統(tǒng)的單點(diǎn)交叉。均勻交叉是指兩個(gè)配對個(gè)體的每一位都以相同的概率進(jìn)行交換，從而形成兩個(gè)新的個(gè)體。具體的操作如下:首先隨機(jī)生成一個(gè)與個(gè)體長度相等的二進(jìn)制串，稱為掩碼。掩碼的第i位與個(gè)體的第i位相對應(yīng)。對于個(gè)體A和B，當(dāng)掩碼的第i位為1時(shí)，不交換A和B的第i位。當(dāng)掩碼的第i位為0時(shí)，交換A和B的第i位。具體如圖1所示。

圖1 個(gè)體A和個(gè)體B進(jìn)行均勻交叉產(chǎn)生個(gè)體X和YFig．1 Individual A and individual B produce individual X and Y by uniform crossover

2．2 變異概率的非線性遞增策略

變異概率是遺傳算法中一個(gè)重要的參數(shù)，它直接影響到搜索算法的收斂性和算法搜索的性能。變異概率大，會(huì)使得算法不斷搜索新的空間，增加解的多樣性。但是，較大的變異概率會(huì)影響算法的收斂性。因此，在解決實(shí)際問題中，取變異概率為一個(gè)較小的值，一般在0．001～0．05之間。

在改進(jìn)的遺傳算法中，提出了一種變異概率的非線性遞增策略，即變異概率隨著種群進(jìn)化代數(shù)的增加而非線性增加。具體表示為

式中:g為當(dāng)前進(jìn)化代數(shù);gmax為最大進(jìn)化代數(shù)。

非線性遞增變異概率曲線如圖2所示。

圖2 非線性遞增變異概率曲線Fig．2 Probability curve of the nonlinearity increasing mutation

由圖2可以看出，在種群進(jìn)化初期，變異概率較小，為0．05，加速算法向最優(yōu)解靠攏;隨著進(jìn)化代數(shù)的增大，變異概率逐漸增大。改進(jìn)后，算法易搜索到新解，有利于算法擺脫局部最優(yōu)，在一定程度上抑制了早熟收斂。

2．3 最優(yōu)個(gè)體變異策略

最優(yōu)個(gè)體是指對環(huán)境適應(yīng)能力最強(qiáng)，能夠得到最好適應(yīng)值的個(gè)體。最優(yōu)個(gè)體就是搜索空間中的最好位置。在本課題中，癌癥特征基因提取的目標(biāo)是選擇出一個(gè)最優(yōu)特征基因子集，這個(gè)特征基因子集具有最強(qiáng)的分類信息，即用該特征基因子集進(jìn)行癌癥數(shù)據(jù)集的分類能得到最好的分類效果。與其他尋優(yōu)問題不同的是，最優(yōu)特征基因子集與次優(yōu)特征基因子集之間往往具有很大的重疊，在整個(gè)搜索空間中的位置是十分接近的，兩者之間可能有少數(shù)幾個(gè)基因存在差別。因此，充分利用每次迭代后得到的最優(yōu)個(gè)體，在最優(yōu)個(gè)體上進(jìn)行隨機(jī)位置變異，能夠增大尋找到全局最優(yōu)個(gè)體的可能性。做法是，隨機(jī)選擇每次迭代后的最優(yōu)個(gè)體中的某些位置進(jìn)行變異，如果變異后的新個(gè)體確實(shí)具有更好的適應(yīng)值，則代替原最優(yōu)個(gè)體。否則，不做改變。具體操作如下:

1)獲取本次迭代的最優(yōu)個(gè)體gbest;

2)隨機(jī)選擇gbest的1個(gè)或者2個(gè)位置進(jìn)行變異，得到newgbest;

3)如果 newgbest的適應(yīng)值大于 gbest，則用newgbest替換gbest，否則不做任何操作。

3 實(shí)驗(yàn)設(shè)計(jì)

為了證明改進(jìn)后的遺傳算法具有更好的性能，實(shí)驗(yàn)中同時(shí)使用基本遺傳算法進(jìn)行特征基因的選擇。因?yàn)閮蓚€(gè)算法在同樣的軟硬件環(huán)境中進(jìn)行，而且使用相同的參數(shù)、數(shù)據(jù)集、預(yù)處理和適應(yīng)值函數(shù)，所以結(jié)果具有可比性。鑒于隨機(jī)算法的隨機(jī)特點(diǎn)，實(shí)驗(yàn)對兩種算法用每一個(gè)癌癥數(shù)據(jù)集進(jìn)行25次獨(dú)立實(shí)驗(yàn)，以便比較算法的性能。

3．1 參數(shù)設(shè)置

改進(jìn)的GA和基本的GA中使用的參數(shù)見表1。這些參數(shù)都是經(jīng)過多次測試，能夠保證得到較好的分類結(jié)果。

表1 算法參數(shù)Tab．1 Parameters of the algorithm

3．2 實(shí)驗(yàn)數(shù)據(jù)集

大量公開的癌癥基因表達(dá)研究實(shí)驗(yàn)已經(jīng)提供了許多DNA微陣列數(shù)據(jù)集。文中使用了其中5個(gè)癌癥基因表達(dá)譜數(shù)據(jù)集，分別為白血病數(shù)據(jù)集(Leukemia)，前列腺癌數(shù)據(jù)集(Prostate)，結(jié)腸癌數(shù)據(jù)集(Colon)，肺癌數(shù)據(jù)集(Lung)和淋巴癌數(shù)據(jù)集(Lymphoma)。所有這5個(gè)數(shù)據(jù)集都可以從如下網(wǎng)址獲得:http://linus．nci．nih．gov/ ～ brb/DataArchive_New．html。表2給出了這5個(gè)數(shù)據(jù)集的詳細(xì)信息。其中，類別1和類別2中括號(hào)中的數(shù)字是該類樣本的個(gè)數(shù)。

表2 實(shí)驗(yàn)數(shù)據(jù)集描述Tab．2 Description for the experimental datasets

3．3 預(yù)處理

由于原始的癌癥數(shù)據(jù)集中有幾千甚至幾萬個(gè)基因，這些基因中含有大量的冗余基因，這些冗余基因?qū)?yán)重影響特征選擇的效果，所以在選擇特征基因之前，先對數(shù)據(jù)集進(jìn)行初步篩選。首先對數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，消除量綱對分類的影響。采用T檢驗(yàn)進(jìn)行初步篩選。根據(jù)T檢驗(yàn)的P值對基因進(jìn)行排序，選擇P值最小的100個(gè)基因作為遺傳算法的全局搜索空間。至此，已經(jīng)去除了數(shù)據(jù)集中大量的冗余基因。

3．4 適應(yīng)值函數(shù)

在遺傳算法中，適應(yīng)值用于評價(jià)個(gè)體的優(yōu)劣，利用適應(yīng)值函數(shù)計(jì)算個(gè)體的適應(yīng)值。在本方法中，粒子Xi是一個(gè)表示基因子集的二進(jìn)制串，SVM分類器使用每個(gè)粒子表示的基因子集進(jìn)行留一交叉驗(yàn)證(Leave-one-out Cross Validation，LOOCV)。文中設(shè)適應(yīng)值函數(shù)為

其中，accuracy為LOOCV正確率;feature_number為基因子集中基因的個(gè)數(shù);α和β為權(quán)重參數(shù)，本方法中分別將 α 設(shè)為0．6，β 設(shè)為0．4。因?yàn)?，相比于基因子集的?guī)模，數(shù)據(jù)集的分類正確率是該實(shí)驗(yàn)研究更加關(guān)注的內(nèi)容，所以設(shè)置α值為0．6大于β值0．4，這樣可以更好地控制數(shù)據(jù)集分類正確率在評價(jià)基因子集中的主要地位。因?yàn)檫m應(yīng)值越大，基因子集越優(yōu)，所以該適應(yīng)值函數(shù)利于最大化分類正確率和最小化特征基因的規(guī)模。

3．5 改進(jìn)的遺傳算法選擇基因

T檢驗(yàn)進(jìn)行初步篩選之后，已經(jīng)排除了原始數(shù)據(jù)中大部分無關(guān)基因。下面利用改進(jìn)的遺傳算法對數(shù)據(jù)集進(jìn)行進(jìn)一步的篩選，選擇出真正具有分類信息的基因。

利用改進(jìn)后的遺傳算法作為特征選擇的全局搜索引擎，SVM作為特征基因子集的評價(jià)分類器。設(shè)種群中的個(gè)體數(shù)為20，使用改進(jìn)的遺傳算法對種群進(jìn)行選擇交叉變異操作，設(shè)置最多進(jìn)化代數(shù)為100。當(dāng)滿足結(jié)束條件時(shí)，結(jié)束迭代。在本算法中設(shè)置結(jié)束條件為:①LOOCV分類正確率≥99．99% 且選擇的基因個(gè)數(shù)≤10時(shí);②達(dá)到最多進(jìn)化代數(shù)。滿足兩個(gè)條件中的任何一個(gè)，即可結(jié)束迭代過程。迭代結(jié)束后，輸出最終選擇的基因，至此一次實(shí)驗(yàn)結(jié)束。因?yàn)檫z傳算法的隨機(jī)性，為了得到更加可靠的結(jié)果，對每一個(gè)數(shù)據(jù)集進(jìn)行25次獨(dú)立實(shí)驗(yàn)。算法流程如圖3所示。

圖3 算法流程Fig．3 Flowchart of the algorithm

4 結(jié)果分析

4．1 LOOCV正確率分析

表3給出了改進(jìn)的GA+SVM與基本GA+SVM對癌癥數(shù)據(jù)分類正確率的比較。其中最優(yōu)為25次獨(dú)立實(shí)驗(yàn)中的最優(yōu)LOOCV正確率，平均為25次獨(dú)立實(shí)驗(yàn)LOOCV正確率的平均值。

表3 改進(jìn)的GA+SVM與基本的GA+SVM對癌癥數(shù)據(jù)LOOCV正確率比較Tab．3 Comparison of LOOCV accuracy for each dataset between the improved GA+SVM and the basic GA+SVM 單位:%

由表3中可以看出，改進(jìn)的GA+SVM在所有的5個(gè)數(shù)據(jù)集上都比基本的GA+SVM得到了更好的結(jié)果。

圖4給出了最終選擇出的基因子集中基因的個(gè)數(shù)。其中選擇基因個(gè)數(shù)為相應(yīng)癌癥數(shù)據(jù)集25次獨(dú)立實(shí)驗(yàn)所得到基因子集的平均個(gè)數(shù)。

圖4 改進(jìn)的GA+SVM與基本的GA+SVM對癌癥數(shù)據(jù)選擇基因個(gè)數(shù)比較Fig．4 Number of the selected genes for each dataset between the improved GA+SVM and the basic GA+SVM

由圖4中可以看出，改進(jìn)后的GA+SVM在5個(gè)數(shù)據(jù)集上都比基本的GA+SVM得到了更小的基因子集規(guī)模。

4．2 魯棒性分析

除了算法的性能，算法在獨(dú)立執(zhí)行多次產(chǎn)生相同或相近結(jié)果的能力即魯棒性也是衡量算法的一個(gè)重要指標(biāo)。包括實(shí)驗(yàn)所研究的遺傳算法在內(nèi)的元啟發(fā)式方法更是如此。表4給出了改進(jìn)的GA+SVM與基本的GA+SVM魯棒性的比較。其中，標(biāo)準(zhǔn)差是25次獨(dú)立實(shí)驗(yàn)的LOOCV正確率的標(biāo)準(zhǔn)差。

表4 改進(jìn)的GA+SVM與基本的GA+SVM魯棒性比較Tab．4 Robustness between the improved GA+SVMand the basic GA+SVM

由表4可以看出，在數(shù)據(jù)集Leukemia，Colon中，改進(jìn)的GA+SVM算法魯棒性明顯比基本GA+SVM好;兩個(gè)算法在Lung數(shù)據(jù)集上都得到了25次100%的正確率;對于Prostate和Lymphoma數(shù)據(jù)集，雖然改進(jìn)的GA+SVM得到的標(biāo)準(zhǔn)差比基本GA+SVM更大，但是前者找到了更好的基因子集，由此得到了更好的平均正確率。

4．3 生物意義分析

將所有基因子集中的基因進(jìn)行統(tǒng)計(jì)，列出每個(gè)數(shù)據(jù)集出現(xiàn)頻率最高的5個(gè)基因和相應(yīng)的基因描述。表5給出了Colon和Lung數(shù)據(jù)集的基因子集中出現(xiàn)頻率最高的5個(gè)基因及其基因描述。

表5 Colon和Lung數(shù)據(jù)集的基因子集中出現(xiàn)頻率最高的5個(gè)基因Tab．5 Top 5 genes with the highest selection frequency of the Colon and the Lung

圖5和圖6給出了表5中的10個(gè)基因的基因表達(dá)在熱點(diǎn)圖中的表現(xiàn)。由圖5和圖6可以明顯看出，對于Colon和Lung數(shù)據(jù)集，5個(gè)基因在兩個(gè)類別間有明顯的表達(dá)差異，即用改進(jìn)的遺傳算法選擇出的這5個(gè)基因具有明顯的分類信息。

5 結(jié)語

對基本遺傳算法的交叉和變異操作進(jìn)行改進(jìn)，將改進(jìn)后的遺傳算法和基本遺傳算法用于對5個(gè)癌癥數(shù)據(jù)集進(jìn)行基因選擇和分類。對比兩種算法，實(shí)驗(yàn)結(jié)果充分證明了改進(jìn)后的遺傳算法在搜索性能、魯棒性上都有明顯的優(yōu)勢，且選擇出的基因的確具有明顯的分類信息。

圖5 Colon數(shù)據(jù)集選出的基因的熱點(diǎn)圖Fig．5 Heat map of the genes selected from the Colon dataset

圖6 Lung數(shù)據(jù)集選出的基因的熱點(diǎn)圖Fig．6 Heat map of the genes selected from the Lung dataset

［1］Lander E S．Array of hope［J］．Nature Genetics，1999，21:3-4．

［2］Ramaswamy S，Golub T R．DNA microarrays in clinical oncology［J］．Journal of Clinical Oncology，2002，20(7):1932-1941．

［3］DeRisi J，Penland L，Brown P O，et al．Use of a cDNA microarray to analyse gene expression patterns in human cancer［J］．Nature Genetics，1996，14(4):457-460．

［4］劉金勇，鄭恩輝，陸慧娟．基于聚類和微粒群優(yōu)化的基因選擇方法［J］．?dāng)?shù)據(jù)采集與處理，2014，29(1):83-89．LIU Jinyong，ZHENG Enhui，LU Huijuan．Gene selection based on clustering method and particle swarm optimization［J］．Journal of Data Acquisition and Processing，2014，29(1):83-89．(in Chinese)

［5］于彬，張巖．基于 GA-SVM方法的結(jié)腸癌基因表達(dá)譜數(shù)據(jù)分析［J］．青島科技大學(xué)學(xué)報(bào):自然科學(xué)版，2013，33(6):587-592．YU Bin，ZHANG Yan．Analysis of colon cancer gene expression profiles based on GA-SVM method［J］．Journal of Qingdao University of Science and Technology:Natural Science Edition，2013，33(6):587-592．(in Chinese)

［6］徐久成，徐天賀，孫林，等．基于鄰域粗糙集和粒子群優(yōu)化的腫瘤分類特征基因選?。跩］．小型微型計(jì)算機(jī)系統(tǒng)，2014(11):31．XU Jiucheng，XU Tianhe，SUN Lin，et al．Feature selection for cancer classification based on neighborhood rough set and particle swarm optimization［J］．Mini-Micro Sysitms，2014(11):31．(in Chinese)

［7］張靖，胡學(xué)鋼，李培培，等．基于迭代 Lasso的腫瘤分類信息基因選擇方法研究［J］．模式識(shí)別與人工智能，2014，27(1):49-59．ZHANG Jing，HU Xuegang，LI Peipei，et al．Informative gene selection for tumor classification based on iterative lasso［J］．Pattern Recognition and Artificial Intelligence，2014，27(1):49-59．(in Chinese)

［8］張煥萍，宋曉峰，王惠南．基于離散粒子群和支持向量機(jī)的特征基因選擇算法［J］．計(jì)算機(jī)與應(yīng)用化學(xué)，2007，24(9):1159-1162．ZHANG Huanping，SONG Xiaofeng，WANG Huinan．Feature gene selection based on binary particle swarm optimization and support vector machine［J］．Computers and Applied Chemistry，2007，24(9):1159-1162．(in Chinese)

［9］Holland J H．Adaptation in Natural and Artificial Systems:An Introductory Analysis with Applications to Biology［M］．Ann Arbor:University Michigan Press，1975．