進(jìn)化算法在單體型檢測(cè)和多變量遞歸中的應(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)的影響。
　　單體型檢測(cè)是生物信息學(xué)的一個(gè)重要分支,其中,單體型組裝加權(quán)最小字符翻轉(zhuǎn)(WMLF)問題指定個(gè)體聯(lián)配的加權(quán)DNA片斷數(shù)據(jù)、翻轉(zhuǎn)權(quán)值和最小的SNP位點(diǎn)以推測(cè)出該個(gè)體的一對(duì)單體型。該問題是NP-難的,至今尚無實(shí)用的搜索尋優(yōu)算法。
　　NP-難問題一直是計(jì)算機(jī)理論研究的熱點(diǎn)

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

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

4、出了一種更為精確和簡(jiǎn)單的分析方法:首先引入適當(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)化算法采用多點(diǎn)并行搜索的搜索機(jī)制,每次迭代時(shí)借助交換和突變產(chǎn)生新個(gè)體,不斷擴(kuò)大搜索范圍,因此很容易跳過局部最優(yōu)解,而收斂于全局最優(yōu)解。實(shí)驗(yàn)表明:在十次試驗(yàn)中,各個(gè)約束條件和目標(biāo)函數(shù)的取值都是收斂的。