資源描述：
《試論dna計(jì)算及其算法優(yōu)化》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、太原理工大學(xué)碩士學(xué)位論文DNA計(jì)算及其算法優(yōu)化姓名：王斌田申請學(xué)位級別：碩士專業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)指導(dǎo)教師：余雪麗;歐陽鐘燦20060501太原理工大學(xué)碩士研究生學(xué)位論文DNA計(jì)算及其算法優(yōu)化摘要在計(jì)算機(jī)中，利用有機(jī)分子的信息處理能力來代替數(shù)字開關(guān)部件，這就是DNA計(jì)算的基本思想。以當(dāng)前的計(jì)算機(jī)技術(shù)要實(shí)現(xiàn)微型化存在明顯的局限性，所以要進(jìn)行大的革新，很早以前就有人提出現(xiàn)代計(jì)算機(jī)的基本部件應(yīng)逐步過渡到分子水平，這樣一來，它將會比我們利用當(dāng)前技術(shù)制造出的任何東西都要小得多，量子計(jì)算和DNA計(jì)算是當(dāng)前這種思想的兩種不同表現(xiàn)，本論文主要介
2、紹DNA計(jì)算。DNA計(jì)算主要基于以下兩點(diǎn)：(1)DNA鏈的巨大并行性；(2)Watson—Crick的互補(bǔ)結(jié)構(gòu)。傳統(tǒng)理論上的計(jì)算機(jī)科學(xué)植根于重復(fù)寫操作，這對于大部分自動機(jī)械裝置和語言理論模型是正確的，然而，在計(jì)算行為中，自然界操作DNA分子利用的是完全不同的操作類型：剪切、粘貼、連接、插入、刪除等?？梢宰C明，利用這些操作可以建立計(jì)算模型，并且在功能上等價(jià)于圖靈機(jī)。以前DNA計(jì)算的研究主要集中在一些組合問題上，像Hamiltonian路徑問題、旅行商問題、3-SAT問題，甚至破解DES密碼等等，但提出的上述所有問題的DNA算法基
3、本上都是蠻力搜索，初始化時生成問題的所有可能的解決方案，然后根據(jù)條件消除掉不正確的答案，最后剩下的方案即是問題的正確答案。但值得注意的是，實(shí)際問題的正確答案也許會在計(jì)算過程中被破壞掉，最后得到的答案也許是一個錯誤的答案。為了避免這種錯誤，我們提出了將啟發(fā)式優(yōu)化算法和DNA計(jì)算結(jié)合，采用新的手段來設(shè)計(jì)算法。在這篇論文中，我們將蟻群優(yōu)化算法和DNA計(jì)算結(jié)合，來解決旅行商問題。即使正確的答案在處理的過程中被破壞掉，該正確答案在以后的處理過程總還會被構(gòu)造，在過濾掉不合適的答案以后，我們利用控制變性I太原理工大學(xué)碩士研究生學(xué)位論文溫度的
4、方法按比例放大經(jīng)過過濾剩下的序列，并把放大的結(jié)果作為下次迭代的輸入，相應(yīng)的代表正確答案的DNA序列的濃度就會增加。在經(jīng)過多次迭代之后，若結(jié)果趨于穩(wěn)定，則認(rèn)為剩下的序列即為問題的答案。論文的前兩部分主要介紹生物學(xué)的基礎(chǔ)知識、DNA計(jì)算的基本概念、基本模型和相關(guān)的著名實(shí)驗(yàn)，接下來介紹了啟發(fā)式優(yōu)化算法：蟻群優(yōu)化算法；然后提出蟻群優(yōu)化算法和DNA計(jì)算結(jié)合的構(gòu)想與具體實(shí)現(xiàn)，同時詳細(xì)介紹了算法處理過程；在文章的最后對提出的算法進(jìn)行了總結(jié)，并對DNA計(jì)算的前景進(jìn)行了展望。關(guān)鍵詞：DNA計(jì)算，啟發(fā)式優(yōu)化方法，NP完全問題，序列抽取II太原理工
5、大學(xué)碩士研究生學(xué)位論文DNACOM口UTINGANDOPTI~ⅡZATIONOFTHEALGORITHMABSTRACTInformation-processingcapabilitiesoforganicmoleculescallbeusedincomputerstoreplacedigitalswitches；thisisthebasicideainDNAcomputing．Thereareobviouslimitstominiaturizationwithcurrentcomputertechnologies．Forad
6、rasticinnovation，itwassuggestedalreadyalongtimeagothatthebasiccomponentsshouldgotothemolecularlevel．Theresultwouldbemuchsmallerthananythingwecanmakewithpresenttechnology．QuantumcomputingandDNAcomputingaretworecentmanifestationsofthissuggestion．Thisworkis*boutthelatt
7、er．DNAcomputingarebasedontwofundamentalfeatures：(1)ThemassiveparallelismofDNAstrands；(2)Watson-Crickcomplementarity．Classictheoreticalcomputerscienceisgroundedonrewritingoperations；thisistmeformostautomataandlanguagetheorymodels．Asweshallsee，naturemanipulatestheDNAm
8、oleculesinacomputingmannerbyusingoperationsofaquitedifferenttype：cutandpaste，adjoining，insertion，deletion，etc．Ithasbeenprovedthatbyusingsu
