混合遺傳算法在圖著色及MSA問題中的應(yīng)用.pdf

1、圖著色問題和MSA 問題都是被廣泛研究的組合優(yōu)化問題，同時它們也都是典型的NP 完全問題，隨著圖的規(guī)模的增大或比對序列個數(shù)的增加，計算量將會以指數(shù)的速度增加到不可接受的地步。遺傳算法、模擬退火算法、禁忌搜索算法都是求解NP 完全問題的有效方法。本文首先對遺傳算法的基本原理和框架進行詳細介紹，然后對圖著色問題和多序列比對問題進行了相應(yīng)的研究，提出將遺傳算法與模擬退火算法及禁忌搜索算法結(jié)合在一起的混合遺傳算法。該算法充分發(fā)揮了它們的優(yōu)越性，

2、提高了求解GCP 問題和MSA 問題的精度與速度。實驗表明，該算法是有效的。具體內(nèi)容如下： 在系統(tǒng)分析了圖的頂點著色、邊著色及全著色問題的基礎(chǔ)上，將遺傳算法與模擬退火方法和禁忌搜索方法結(jié)合，提出了圖著色的混合遺傳算法。在混合方法中：模擬退火算法用于局部尋優(yōu)，以提高算法的收斂速度，同時防止出現(xiàn)早熟收斂；禁忌搜索算法通過其記憶能力防止進化過程出現(xiàn)循環(huán)來提高全局尋優(yōu)能力；而遺傳算法進行全局搜索。并與貪婪遺傳算法和Dsatur 算法進行

3、了比較，結(jié)果表明，混合遺傳算法的尋優(yōu)質(zhì)量優(yōu)于對照算法。然后在分析了混合遺傳算法落入局部最優(yōu)陷阱的原因后，增加了自適應(yīng)策略和清空重填策略使算法盡快跳出陷阱，通過實驗表明在保持尋優(yōu)質(zhì)量的同時，這種改進的混合遺傳算法可以在稠密圖上獲得更好的尋優(yōu)效率，在稀疏圖上其效率則略有下降。這表明文中設(shè)計的改進混合遺傳算法的合理性和有效性。 在圖的著色問題上獲得成功后，本文又嘗試將這種混合遺傳算法用于MSA 問題。首先系統(tǒng)介紹了多序列比對的概念、比

4、對記分方法、現(xiàn)有的幾種多序列比對算法的優(yōu)缺點，然后針對于MSA 問題的特點重新構(gòu)建了染色體空間，引入SP_AFFINE 打分函數(shù)衡量比對質(zhì)量，對遺傳算子（選擇算子、交叉算子、突變算子、模擬退火算子、禁忌搜索算子）根據(jù)需要進行了相應(yīng)的修改，為了進一步提高比對的質(zhì)量和效率，引入初始化算子和移位算子。初始化算子采用類似于星比對的方法使種群的第一代位于較接近最優(yōu)比對的位置，移位算子通過在若干連續(xù)空位的鄰域內(nèi)移動它們以找到局部的最佳比對。通過與C