進(jìn)化算法在單體型檢測和多變量遞歸中的應(yīng)用研究.pdf

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

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

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

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