進化算法在單體型檢測和多變量遞歸中的應用研究.pdf

1、進化算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應全局優(yōu)化概率搜索算法。二十世紀六十年代以來被廣泛應用于工業(yè)工程優(yōu)化領域,并產(chǎn)生了深遠的影響。
　　單體型檢測是生物信息學的一個重要分支,其中,單體型組裝加權最小字符翻轉(WMLF)問題指定個體聯(lián)配的加權DNA片斷數(shù)據(jù)、翻轉權值和最小的SNP位點以推測出該個體的一對單體型。該問題是NP-難的,至今尚無實用的搜索尋優(yōu)算法。
　　NP-難問題一直是計算機理論研究的熱點

2、和難點。分支定界法是常分析求解NP-難問題的一種精確算法。而用分支定界法求解NP-難問題,所得待求解表達式在形式上則表現(xiàn)為回溯算法所衍生的一系列多變量遞歸。通過分析求解這些多變量遞歸式,可以得出算法的上界或下界,把此類問題稱為多變量遞歸求解問題。傳統(tǒng)的一些分析方法或者有缺陷,或者太復雜。
　　本文主要的工作是針對上述的兩個問題用進化算法來進行優(yōu)化和求解。
　　1.針對單體型組裝的WMLF模型問題,本文提出了一種單目標的進化算

3、法,該算法引入了權值矩陣并且設計了新的適應度函數(shù)。衡量算法好壞的評價指標有兩個:重構率和運行時間。為了凸現(xiàn)進化算法的優(yōu)越性又把解決單體型組裝問題WMLF模型的經(jīng)典算法-動態(tài)類聚算法來和進化算法作比較,可以從試驗圖表看出:無論是否存在空隙率,在兩種算法運行時間相當?shù)那闆r下,進化算法的重構率要明顯高一些。結論是:用進化算法來處理單體型檢測的WMLF模型問題比傳統(tǒng)的方法要更加優(yōu)越。
　　2.針對多變量遞歸求解問題,相比于傳統(tǒng)的分析方法提

4、出了一種更為精確和簡單的分析方法:首先引入適當?shù)馁x權函數(shù),把多變量遞歸函數(shù)轉化為單變量遞歸函數(shù),然后提出有效的優(yōu)化模型,把求解單變量遞歸函數(shù)問題進一步轉化為一般的帶約束條件的函數(shù)優(yōu)化問題。傳統(tǒng)的算法求得的解多為局部最優(yōu)解,而本文采用的多目標進化算法采用多點并行搜索的搜索機制,每次迭代時借助交換和突變產(chǎn)生新個體,不斷擴大搜索范圍,因此很容易跳過局部最優(yōu)解,而收斂于全局最優(yōu)解。實驗表明:在十次試驗中,各個約束條件和目標函數(shù)的取值都是收斂的。