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

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

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

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

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