基于人工魚群遺傳算法的DNA編碼優(yōu)化

胡 娟，李 冬，張麗麗

(1.淮南職業(yè)技術(shù)學(xué)院基礎(chǔ)部，安徽 淮南 232001;2.淮南工業(yè)學(xué)校電子組，安徽 淮南 232001;3.安徽理工大學(xué)理學(xué)院，安徽 淮南 232001)

1994年，當文獻［1］用DNA 計算成功地解決了有向Hamilton 路問題，人類已經(jīng)進入了借助DNA 分子通過生化反應(yīng)來進行計算的嶄新時代。從此越來越多的學(xué)者用DNA 計算模型解決了許多NP 完全問題，然而早期DNA 計算中所用的序列都需要在設(shè)定編碼長度的基礎(chǔ)上隨機產(chǎn)生，這就會導(dǎo)致生物化學(xué)反應(yīng)不可控制性。因此尋找高質(zhì)量DNA 序列及合適的DNA 序列庫變得尤為重要。通常為了滿足DNA 序列可靠性的要求，就會利用約束條件來篩選序列，決定序列編碼的約束條件主要有Gibb 自由能增量約束、解鏈溫度約束Tm、H－measure 約束、生物酶和DNA 分子的生物特異性等，要想找到好的編碼就需要充分考慮這些約束條件。

遺傳算法(Genetic Algorithm，GA)是20 世紀70年代初文獻［2］16首先提出來的。它常用來處理很復(fù)雜的非線性問題，具有非常好的魯棒性。但它最大的缺點就是進化過程盲目性，常會陷入局部極值。尤其在編碼問題中，當約束條件較多時，它有可能會搜索不到符合要求的編碼。而全局人工魚群算法是模仿魚群覓食的一種算法，算法簡單，又有避免陷入局部極值的良好能力。

本文在深入研究傳統(tǒng)遺傳算法的基礎(chǔ)上，為了克服其盲目搜索的缺點，提高進化效率，給出了一種基于遺傳算法和全局人工魚群算法的混合優(yōu)化算法(GAFSA/GA)，用于DNA 的編碼問題，經(jīng)實驗結(jié)果表明，所述算法比遺傳算法產(chǎn)生的DNA 編碼序列質(zhì)量更加穩(wěn)定可靠。

1 DNA 編碼序列設(shè)計及約束項分析

1.1 DNA 編碼問題

DNA 計算中的編碼問題一般都描述為:設(shè)由四個字母組成的集合∑={A，T，C，G}，若DNA分子長度為n，其編碼集合為S，很明顯有|S|=4n，求C?S使?xi，xj∈C，τ(xi，xj)≥k，其中τ 為評價標準，k∈Z+。然而τ 越嚴格，可供選擇的編碼數(shù)|C|就會越小。編碼問題，主要是編碼質(zhì)量和數(shù)量問題。因為編碼質(zhì)量越高，可靠性就會越好;而編碼數(shù)量越大，就會擴大應(yīng)用范圍。然而，在現(xiàn)實中，他們是相互矛盾的。這就希望在保證質(zhì)量的前提下能最大限度的得到編碼集合。

1.2 約束項及評價函數(shù)

影響DNA 計算的因素［3－7］有很多，結(jié)合眾多約束條件，給出本文的DNA 編碼的約束條件。

1)H－measure 約束。H－measure 是一種通過移位比較兩個DNA 序列漢明距離的最小值而獲得的有效約束，移位后的互補堿基對的數(shù)目可以有效防止雜交，定義公式如下:

式中:σk(xj)為xj序列經(jīng)移位k位后的序列Hamming 約束。

2)Similarity 約束。相似度是計算2 個正相序列移位后的序列的相同堿基對的數(shù)目，來度量序列在集合中的差異性。

3)Continuity 約束。如果DNA 序列中某一字母連續(xù)重復(fù)出現(xiàn)，那么結(jié)構(gòu)將會變得不穩(wěn)定。

4)Hairpin 約束。發(fā)夾結(jié)構(gòu)會引起DNA 序列的自雜交，一般情況下應(yīng)加以限制。式中:r為形成發(fā)夾的最小的環(huán)長度;pinlen為形成發(fā)夾莖所應(yīng)有的最小長度。

5)GC Content 約束。

fGC(xi)=－|GC(xi)－ GC(xi)defined|

式中:GC(xi)為xi序列中字母G，C 在序列中的比例;GC(xi)defined為所指定的GC 含量。

6)Tm約束。溫度是實現(xiàn)DNA 計算的一個重要因素。在這里采用最近鄰模型近似表達式:

1.3 適應(yīng)度函數(shù)

本文定義的優(yōu)化問題其實是最大值問題，因此采用加權(quán)平均值法來處理每個DNA 個體各約束的評估函數(shù)。

式中:m為約束項個數(shù);ωj為各個約束項fj的權(quán)重。

2 人工魚群遺傳算法

2.1 基本遺傳算法

遺傳算法是模擬生物進化過程中適者生存規(guī)則，并將其與種群內(nèi)部染色體的隨機信息進行交換，是一種很好的局部優(yōu)化搜索方法［2］141。它的主要思想是:隨機生成DNA 序列;計算DNA 序列的適應(yīng)度函數(shù)值，滿足約束條件;利用遺傳算子生成滿足約束條件的新的DNA 序列，從而獲得DNA 序列的集合(見圖1)。

圖1 算法流程圖

2.2 人工魚群算法(GAFSA)

人工魚群算法就是模擬魚群的覓食，聚首及追尾行為而生成的全局優(yōu)化算法。通過觀察魚覓食會發(fā)現(xiàn)在一片水域中，魚最多的地方就是食物最多的地方，魚有自行或尾隨其他魚找到食物最多的地方特點。人工魚群算法就是根據(jù)魚群的這一特點，來構(gòu)造人工魚群來模仿魚群行為，從而實現(xiàn)尋優(yōu)。

1)確定魚群規(guī)模N，隨機產(chǎn)生N個人工魚個體，組成初始群體，同時設(shè)置相關(guān)參數(shù);

2)計算初始魚群的個體適應(yīng)函數(shù)值，并將最優(yōu)人工魚狀態(tài)記錄到公告板;

3)個體通過覓食行為，聚首行為，追尾行為［8］生成新的魚群;

4)選最優(yōu)個體與公告板進行比較，若比公告板優(yōu)，則以自身狀態(tài)更新公告板;

5)根據(jù)文獻［8］對視野和步長進行調(diào)整;

6)判斷是否滿足終止條件，若滿足，則輸出公告板記錄，算法終止;若不滿足，則執(zhí)行步驟3。

2.3 人工魚群遺傳算法(GAFSA/GA)

該算法是以基本遺傳算法為基礎(chǔ)，將人工魚群算法作為遺傳算法的一個重要算子，具體步驟如下:

1)設(shè)定相關(guān)參數(shù)，并產(chǎn)生初始種群;

2)計算個體的適應(yīng)度函數(shù)值，按照適應(yīng)度函數(shù)值進行排序;

3)判斷是否滿足目標，若滿足，輸出結(jié)果，結(jié)束進程;否則進行下一步;

4)更新個體種群，根據(jù)適應(yīng)度函數(shù)值的確定一部分個體直接進入下一代種群，剩余個體通過GAFSA 算法優(yōu)化過后進入下一代種群;

5)對下代種群執(zhí)行遺傳算法的復(fù)制、交叉和變異等操作，轉(zhuǎn)步驟2。

流程圖如圖2所示。

圖2 算法流程圖

3 算法仿真結(jié)果及分析

3.1 與遺傳算法的實驗比較

用全局人工魚群遺傳算法產(chǎn)生的DNA 序列與文獻［9］的遺傳算法的編碼序列進行了比較，并給出了好的有向哈密爾頓路問題的DNA 序列。比較結(jié)果如表1 和圖3所示。

表1 本文算法和GA 序列比較

圖3 GAFSA/GA 與遺傳算法的比對結(jié)果

從圖3 可以看出，GAFSA/GA 算法生成的DNA 編碼序列在Hairpin、GC 含量方面比GA 算法生成的DNA 編碼序列更優(yōu)，并且可以看出GAFSA/GA 生成的序列解鏈溫度變化更小，這意味著GAFSA/GA 算法具有較低的不完全匹配雙鏈產(chǎn)生的概率。同時GAFSA/GA 算法大大降低了計算的難度，在解決DNA 編碼問題方面效果很好，而且依靠群體人工魚并行計算，其收斂速度較快，如(見圖4)橫軸為進化代數(shù);豎軸為每代群體經(jīng)排序后最差個體的適應(yīng)度值。從圖4 中可以看出，算法具有較好的收斂性。

圖4 GAFSA/GA 算法的進化收斂圖

3.2 與遺傳粒子群算法的實驗比較

雖然文獻［10］遺傳粒子群算法(GA/PSO)與GAFSA/GA 選擇的約束條件不同，但鑒于實驗結(jié)果的比對應(yīng)建立在相同約束條件的基礎(chǔ)上進行，采用GAFSA/GA 的評價方法進行實驗比對。比較結(jié)果如表2 和圖5所示。

從表2 和圖5 可以看出，GAFSA/GA 算法生成的DNA 編碼序列在解鏈溫度、發(fā)夾結(jié)構(gòu)等約束方面優(yōu)于遺傳粒子群算法生成的DNA 編碼序列。

表2 本文算法和GA/PSO 序列比較

圖5 GASFA/GA 與遺傳粒子群算法的比對結(jié)果

4 結(jié)論

從DNA 編碼的多個約束條件選取合適的約束，提出了GAFSA/GA 算法對DNA 計算中的編碼序列實現(xiàn)了優(yōu)化，產(chǎn)生了很好的DNA 序列，驗證了該算法的可行性和有效性。

［1］ADLEMAN L M.Molecular computation of solution to combinatorial problems［J］.Science，1994，66(11):1 021－1 024.

［2］HOLLAND J H.Adaptation in natural and artificial systems［M］.AnnArbor:University of Michigan Press，1975:1－153.

［3］DEATON R，GARZON M.The Rmodynamic Constraints on DNA－based Computing［C］// Computing with Bio Molecues:Theory and Expirements.ed.G.Paun，Springer－Verlag:Singapore，1998:138－152.

［4］DEATON R，F(xiàn)RANCESCHETI D R，GARZON M，et al.Information transfer through hybridyzation reaction in DNA based computing［C］//Proceedings of the Second Annual Conference，1997，July 13－16，Stanford University，.Morgan Kaufmann，San Francisco:463－471.

［5］DEATON R.A DNA Based Implementation of an Evolutionary Computation［C］// Proceedings IEEE Conference on Evolutionary Computation.Indianapolis，1997:267－271.

［6］MARATHE A.On combinatorial DNA word design［J］.DIMACS Series in Discrete Mathematics and Theoretical Computer Science，1999，44:75－88.

［7］ROSE J A.The Fidelity of DNA computation［D］.Ph.D thesis，The University of Memphis，1999:11.

［8］付媛媛，張大方，向旭宇.基于人工魚群的DNA 編碼序列組合優(yōu)化算法研究［J］.湖南城市學(xué)院學(xué)報:自然科學(xué)版，2011，20(2):55－56.

［9］ARITA M，NISHIKAWA A，HAGIVA M，et al.Improving sequencedesign for DNA computing［C］// In Proceedings of the Genetic andEvolutionary Computation Conference(GECCO－2000)，2000:875－882.

［10］CUI G Z，NIU Y Y，WANG Y F，et al.A new approach based onPSO algorithm to findgood computational encoding sequences［J］.Progress in Natural Science，2007，17(6):712－716.

［11］Feldkamp U，Raube H，Banzhaf W.Software tools for DNA sequence design［J］.Genetic Programming and Evolvable Machines，2003，4(2):153－171.

［12］張凱，肖建華.基于漢明距離的DNA 編碼約束研究［J］.計算機工程與應(yīng)用，2008，44(14):24－26.

［13］XIAO J H，JIN X，CHEN Z H，et al.A hybrid quantum chaotic swarm evolutionary algorithm or DNA encoding［J］.Computers＆ Mathematics with Applications，2009，57(11/12):1 949－1 958.

［14］CUI GUANGZHAO，LI XIAO GUANG，ZHANG XUN CAI，et al.The Optimization of DNA Encodings Based on Modif ied PSO/GA Algorithm［J］.CHINESE JOU RNAL OF OMPUT ERSVol，2010，33(2):312－313.