構(gòu)建系統(tǒng)發(fā)生樹的進化算法.pdf

1、系統(tǒng)發(fā)生樹的構(gòu)建是一個非常具有挑戰(zhàn)性的問題，對此問題的研究在生物信息學(xué)中變得越來越重要。由于可能拓?fù)浣Y(jié)構(gòu)的系統(tǒng)發(fā)生樹數(shù)目隨著物種數(shù)目增加呈指數(shù)形式增長，關(guān)于最優(yōu)樹的構(gòu)建問題都是NP-Complete問題，巨大的搜索空間使得系統(tǒng)發(fā)生樹的構(gòu)建極其消耗計算資源。當(dāng)物種數(shù)目很大時，沒有一種優(yōu)化算法能在適當(dāng)?shù)臅r間內(nèi)計算得到其精確解，因此，尋找能夠在合理的時間內(nèi)得到最優(yōu)近似解的算法就有很強的實際意義。 遺傳算法(Genetic Algori

2、thm)和蟻群算法(Ant Colony Algorithm)是兩種求解復(fù)雜優(yōu)化問題的模擬進化算法。大量實驗結(jié)果表明，這兩種算法在解決許多組合優(yōu)化問題時都能表現(xiàn)出較好的求解能力。針對系統(tǒng)發(fā)生分析問題的組合復(fù)雜性，及遺傳算法和蟻群算法在解決此類問題中的優(yōu)勢，本文將這兩種算法應(yīng)用于系統(tǒng)發(fā)生樹的構(gòu)建問題，提出了四種系統(tǒng)發(fā)生樹的構(gòu)建方法。 首先，本文提出了一種構(gòu)建系統(tǒng)發(fā)生樹的遺傳算法GA-PTC，將可能的系統(tǒng)發(fā)生樹的拓?fù)浣Y(jié)構(gòu)編碼成問題的

3、解空間，并在解空間中搜索最優(yōu)樹。在此方法中，我們提出了系統(tǒng)發(fā)生樹的后綴表示法作為遺傳算法的編碼方式，在對個體評價時，采用基于距離設(shè)計的適應(yīng)度函數(shù)對個體進行記分，并根據(jù)選擇概率與適應(yīng)度成正比的賭輪盤選擇策略從父代中選擇部分較優(yōu)個體，然后通過遺傳操作產(chǎn)生新一代個體。實驗結(jié)果表明，此算法能夠得到正確的系統(tǒng)發(fā)生樹。 其次，本文在分析蟻群算法的原理及性能的基礎(chǔ)上，提出三種基于蟻群算法的系統(tǒng)發(fā)生樹構(gòu)建方法：(1)基于TSP問題的構(gòu)建系統(tǒng)發(fā)生

4、樹的蟻群算法TSP-PTC。給定一個物種集合以及它們之間的距離矩陣，我們可以構(gòu)造一個帶權(quán)圖。對于圖中的每一條哈密爾頓回路，都可以對應(yīng)于一棵系統(tǒng)發(fā)生樹，在所有回路所對應(yīng)的系統(tǒng)發(fā)生樹中，適應(yīng)度值最小的是TSP問題的解所對應(yīng)的系統(tǒng)發(fā)生樹。因此我們可以利用蟻群算法在帶權(quán)圖中尋找最優(yōu)路徑，然后用此回路及物種之間的距離構(gòu)建系統(tǒng)發(fā)生樹。在構(gòu)建系統(tǒng)發(fā)生樹時，首先根據(jù)回路構(gòu)建其拓?fù)浣Y(jié)構(gòu)，然后根據(jù)拓?fù)浣Y(jié)構(gòu)和距離矩陣給各邊分配權(quán)值。此方法比傳統(tǒng)算法構(gòu)建出來的

5、系統(tǒng)發(fā)生樹的準(zhǔn)確度要高。(2)基于蟻群聚類的構(gòu)建系統(tǒng)發(fā)生樹的蟻群算法．AC-PTC。在算法開始搜索之前，同樣將物種群用一個帶權(quán)圖來表示。圖中的頂點表示待研究的物種，邊上的距離用螞蟻在訪問圖的過程中所積累的信息素來衡量。用螞蟻遍歷該圖并在遍歷過程中更新信息素，在算法停止迭代后刪去圖中某些信息素較少的邊，然后通過求該圖的強連通分量達到對物種聚類的目的。我們在算法中引入了信息素的自適應(yīng)更新策略，以防止算法早熟和局部收斂。最終系統(tǒng)發(fā)生樹由各個聚

6、類構(gòu)建而成。(3)基于后綴表示的構(gòu)建系統(tǒng)發(fā)生樹的蟻群算法SR-PTC。在此方法中，螞蟻訪問物種集合的目的是形成一個對應(yīng)于最優(yōu)系統(tǒng)發(fā)生樹的后綴表示序列。一個合法的后綴表示序列對應(yīng)于一棵二叉樹。為構(gòu)成一個合法的系統(tǒng)發(fā)生樹的后綴表示，螞蟻對內(nèi)部結(jié)點的選擇要受到限制，我們分別為葉結(jié)點和內(nèi)部結(jié)點設(shè)置兩個不同的選擇概率，并用賭輪盤選擇方法來決定兩種結(jié)點的選擇。另外，在信息素更新時，加入當(dāng)前樹的評價值來影響螞蟻的運動方向。我們用本文的算法與傳統(tǒng)的系統(tǒng)