胡 娟，李 冬，張麗麗

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

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

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

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

1 DNA 編碼序列設(shè)計(jì)及約束項(xiàng)分析

1.1 DNA 編碼問(wèn)題

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

1.2 約束項(xiàng)及評(píng)價(jià)函數(shù)

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

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

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

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

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

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

5)GC Content 約束。

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

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

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

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

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

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

2 人工魚(yú)群遺傳算法

2.1 基本遺傳算法

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

圖1 算法流程圖

2.2 人工魚(yú)群算法(GAFSA)

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

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

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

3)個(gè)體通過(guò)覓食行為，聚首行為，追尾行為［8］生成新的魚(yú)群;

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

5)根據(jù)文獻(xiàn)［8］對(duì)視野和步長(zhǎng)進(jìn)行調(diào)整;

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

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

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

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

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

3)判斷是否滿(mǎn)足目標(biāo)，若滿(mǎn)足，輸出結(jié)果，結(jié)束進(jìn)程;否則進(jìn)行下一步;

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

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

流程圖如圖2所示。

圖2 算法流程圖

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

3.1 與遺傳算法的實(shí)驗(yàn)比較

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

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

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

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

圖4 GAFSA/GA 算法的進(jìn)化收斂圖

3.2 與遺傳粒子群算法的實(shí)驗(yàn)比較

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

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

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

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

4 結(jié)論

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

［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］付媛媛，張大方，向旭宇.基于人工魚(yú)群的DNA 編碼序列組合優(yōu)化算法研究［J］.湖南城市學(xué)院學(xué)報(bào):自然科學(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］.計(jì)算機(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.